2009/09/01 by Teng Zhang, Arthur Szlam, Gilad Lerman · 3 citations
Computer Science · Engineering · #Advanced Multi-Objective Optimization Algorithms #Control Systems and Identification #Sparse and Compressive Sensing Techniques #cs.CV #cs.LG
paper · pdf · doi:10.1109/iccvw.2009.5457695
published as Proc. of 2nd IEEE International Workshop on Subspace Methods (Subspace 2009), pp. 234-241 (2009)
openalex publication_date 2009/09/01 · arxiv created 2009/09/16 · arxiv updated 2010/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We describe the Median K-flats (MKF) algorithm, a simple online method for hybrid linear modeling, i.e., for approximating data by a mixture of flats. This algorithm simultaneously partitions the data into clusters while finding their corresponding best approximating ¿1d-flats, so that the cumulative ¿1error is minimized. The current implementation restricts d-flats to be d-dimensional linear subspaces. It requires a negligible amount of storage, and its complexity, when modeling data consisting of N points in ¿Dwith K d-dimensional linear subspaces, is of order O(ns· K · d · D + ns· d2· D), where nsis the number of iterations required for convergence (empirically on the order of 104). Since it is an online algorithm, data can be supplied to it incrementally and it can incrementally produce the corresponding output. The performance of the algorithm is carefully evaluated using synthetic and real data.