Median K-Flats for Hybrid Linear Modeling with Many Outliers
Abstract
We describe the MedianK-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 ℓ<inf>1</inf> d-flats, so that the cumulative ℓ<inf>1</inf> error 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 ℝ<sup>D</sup> with K d-dimensional linear subspaces, is of order O(n<inf>s</inf> · K · d · D + n<inf>s</inf> · d<sup>2</sup> · D), where n<inf>s</inf> is the number of iterations required for convergence (empirically on the order of 10<sup>4</sup>). 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.
Cite
Text
Zhang et al. "Median K-Flats for Hybrid Linear Modeling with Many Outliers." IEEE/CVF International Conference on Computer Vision Workshops, 2009. doi:10.1109/ICCVW.2009.5457695Markdown
[Zhang et al. "Median K-Flats for Hybrid Linear Modeling with Many Outliers." IEEE/CVF International Conference on Computer Vision Workshops, 2009.](https://mlanthology.org/iccvw/2009/zhang2009iccvw-median/) doi:10.1109/ICCVW.2009.5457695BibTeX
@inproceedings{zhang2009iccvw-median,
title = {{Median K-Flats for Hybrid Linear Modeling with Many Outliers}},
author = {Zhang, Teng and Szlam, Arthur and Lerman, Gilad},
booktitle = {IEEE/CVF International Conference on Computer Vision Workshops},
year = {2009},
pages = {234-241},
doi = {10.1109/ICCVW.2009.5457695},
url = {https://mlanthology.org/iccvw/2009/zhang2009iccvw-median/}
}