DocumentCode :
2267283
Title :
Median K-Flats for hybrid linear modeling with many outliers
Author :
Zhang, Teng ; Szlam, Arthur ; Lerman, Gilad
Author_Institution :
Sch. of Math., Univ. of Minnesota, Minneapolis, MN, USA
fYear :
2009
fDate :
Sept. 27 2009-Oct. 4 2009
Firstpage :
234
Lastpage :
241
Abstract :
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 ¿1 d-flats, so that the cumulative ¿1 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 ¿D with K d-dimensional linear subspaces, is of order O(ns · K · d · D + ns · d2 · D), where ns is 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.
Keywords :
approximation theory; computational complexity; computer vision; iterative methods; pattern clustering; cumulative ¿1 error; d-dimensional linear subspaces; hybrid linear modeling; median K-flat algorithm; online algorithm; ¿1 d-flat approximation; Automatic logic units; Clustering algorithms; Conferences; Convergence; Information geometry; Iterative algorithms; Mathematical model; Mathematics; Partitioning algorithms; Principal component analysis;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference on
Conference_Location :
Kyoto
Print_ISBN :
978-1-4244-4442-7
Electronic_ISBN :
978-1-4244-4441-0
Type :
conf
DOI :
10.1109/ICCVW.2009.5457695
Filename :
5457695
Link To Document :
بازگشت