A geometric analysis of subspace clustering with outliers. (English) Zbl 1318.62217
Summary: This paper considers the problem of clustering a collection of unlabeled data points assumed to lie near a union of lower-dimensional planes. As is common in computer vision or unsupervised learning applications, we do not know in advance how many subspaces there are nor do we have any information about their dimensions. We develop a novel geometric analysis of an algorithm named sparse subspace clustering (SSC), which significantly broadens the range of problems where it is provably effective. For instance, we show that SSC can recover multiple subspaces, each of dimension comparable to the ambient dimension. We also prove that SSC can correctly cluster data points even when the subspaces of interest intersect. Further, we develop an extension of SSC that succeeds when the data set is corrupted with possibly overwhelmingly many outliers. Underlying our analysis are clear geometric insights, which may bear on other sparse recovery problems. A numerical study complements our theoretical analysis and demonstrates the effectiveness of these methods.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62-07 | Data analysis (statistics) (MSC2010) |
Keywords:
subspace clustering; spectral clustering; outlier detection; \(\ell_{1}\) minimization; duality in linear programming; geometric functional analysis; properties of convex bodies; concentration of measureReferences:
| [1] | Agarwal, P. and Mustafa, N. (2004). \(k\)-means projective clustering. In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems 155-165. ACM. |
| [2] | Alonso-Gutiérrez, D. (2008). On the isotropy constant of random convex sets. Proc. Amer. Math. Soc. 136 3293-3300. · Zbl 1157.52005 · doi:10.1090/S0002-9939-08-09487-2 |
| [3] | Ball, K. and Pajor, A. (1990). Convex bodies with few faces. Proc. Amer. Math. Soc. 110 225-231. · Zbl 0704.52003 · doi:10.2307/2048263 |
| [4] | Boult, T. E. and Gottesfeld Brown, L. (1991). Factorization-based segmentation of motions. In Proceedings of the IEEE Workshop on Visual Motion , 1991 179-186. IEEE. |
| [5] | Bradley, P. S. and Mangasarian, O. L. (2000). \(k\)-plane clustering. J. Global Optim. 16 23-32. · Zbl 0990.90135 · doi:10.1023/A:1008324625522 |
| [6] | Brandenberg, R., Dattasharma, A., Gritzmann, P. and Larman, D. (2004). Isoradial bodies. Discrete Comput. Geom. 32 447-457. · Zbl 1066.52006 · doi:10.1007/s00454-004-1132-4 |
| [7] | Candes, E. J., Elhamifar, E., Soltanolkotabi, M. and Vidal, R. (2012). Subspace-sparse recovery in the presence of noise. Unpublished manuscript. |
| [8] | Candès, E. J., Romberg, J. and Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52 489-509. · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [9] | Chen, G. and Lerman, G. (2009). Spectral Curvature Clustering (SCC). Int. J. Comput. Vis. 81 317-330. |
| [10] | Costeira, J. and Kanade, T. (1998). A multibody factorization method for independently moving objects. Int. J. Comput. Vis. 29 3. |
| [11] | Elhamifar, E. and Vidal, R. (2009). Sparse subspace clustering. In IEEE Conference on Computer Vision and Pattern Recognition , 2009. CVPR 2009 2790-2797. IEEE. |
| [12] | Elhamifar, E. and Vidal, R. (2010). Clustering disjoint subspaces via sparse representation. In IEEE International Conference on Acoustics Speech and Signal Processing ( ICASSP ), 2010 1926-1929. IEEE. |
| [13] | Favaro, P., Vidal, R. and Ravichandran, A. (2011). A closed form solution to robust subspace estimation and clustering. In IEEE Conference on Computer Vision and Pattern Recognition ( CVPR ), 2011 1801-1807. IEEE. |
| [14] | Gear, C. W. (1998). Multibody grouping from motion images. Int. J. Comput. Vis. 29 133-150. |
| [15] | Gluskin, E. (1988). Extremal properties of rectangular parallelipipeds and their applications to the geometry of Banach spaces. Mat. Sb. ( N.S. ) 136 85-95. · Zbl 0668.52002 · doi:10.1070/SM1989v064n01ABEH003295 |
| [16] | Goh, A. and Vidal, R. (2007). Segmenting motions of different types by unsupervised manifold clustering. In IEEE Conference on Computer Vision and Pattern Recognition , 2007. CVPR’ 07 1-6. IEEE. |
| [17] | Hastie, T. and Simard, P. Y. (1998). Metrics and models for handwritten character recognition. Statist. Sci. 13 54-65. · Zbl 0966.68186 · doi:10.1214/ss/1028905973 |
| [18] | Ho, J., Yang, M. H., Lim, J., Lee, K. C. and Kriegman, D. (2003). Clustering appearances of objects under varying illumination conditions. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition , 2003. Proceedings . 2003 1 I-11-I-18. IEEE. |
| [19] | Hong, W., Wright, J., Huang, K. and Ma, Y. (2006). Multiscale hybrid linear models for lossy image representation. IEEE Trans. Image Process. 15 3655-3671. · doi:10.1109/TIP.2006.882016 |
| [20] | Ichimura, N. (1999). Motion segmentation based on factorization method and discriminant criterion. In The Proceedings of the Seventh IEEE International Conference on Computer Vision , 1999 1 600-605. IEEE. |
| [21] | Johnstone, I. M. (2008). Multivariate analysis and Jacobi ensembles: Largest eigenvalue, Tracy-Widom limits and rates of convergence. Ann. Statist. 36 2638-2716. · Zbl 1284.62320 · doi:10.1214/08-AOS605 |
| [22] | Kanatani, K. (1998). Geometric information criterion for model selection. Int. Journal of Computer Vision 26 171-189. |
| [23] | Kanatani, K. (2001). Motion segmentation by subspace separation and model selection. In Eighth IEEE International Conference on Computer Vision , 2001. ICCV 2001. Proceedings 2 586-591. IEEE. |
| [24] | Kanatani, K. and Matsunaga, C. (2002). Estimating the number of independent motions for multibody motion segmentation. In Asian Conference on Computer Vision 7-12. Citeseer. |
| [25] | Klartag, B. and Vershynin, R. (2007). Small ball probability and Dvoretzky’s theorem. Israel J. Math. 157 193-207. · Zbl 1120.46003 · doi:10.1007/s11856-006-0007-1 |
| [26] | Kriegel, H. P., Kröger, P. and Zimek, A. (2009). Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering. ACM Transactions on Knowledge Discovery from Data ( TKDD ) 3 1-58. |
| [27] | Lerman, G. and Zhang, T. (2011). Robust recovery of multiple subspaces by geometric \(l_p\) minimization. Ann. Statist. 39 2686-2715. · Zbl 1232.62097 · doi:10.1214/11-AOS914 |
| [28] | Liu, G., Lin, Z. and Yu, Y. (2010). Robust subspace segmentation by low-rank representation. In Proceedings of the 26 th International Conference on Machine Learning ( ICML ). |
| [29] | Liu, G., Xu, H. and Yan, S. (2012). Exact subspace segmentation and outlier detection by low-rank representation. In Int’l Conf. Artificial Intelligence and Statistics . |
| [30] | Lu, L. and Vidal, R. (2006). Combined central and subspace clustering on computer vision applications. In Proceedings of the 23 rd International Conference on Machine Learning 593-600. ACM. |
| [31] | Ma, Y., Derksen, H., Hong, W. and Wright, J. (2007). Segmentation of multivariate mixed data via lossy coding and compression. IEEE Transactions on Pattern Analysis and Machine Intelligence 29 1546-1562. |
| [32] | Milman, V. D. and Schechtman, G. (1986). Asymptotic Theory of Finite-Dimensional Normed Spaces. Lecture Notes in Math. 1200 . Springer, Berlin. · Zbl 0606.46013 |
| [33] | Ng, A., Jordan, M. and Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems (T. Dietterich, S. Becker and Z. Ghahramani, eds.) 14 849-856. MIT Press, Cambridge. |
| [34] | Rao, S., Tron, R., Vidal, R. and Ma, Y. (2008). Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories. In IEEE Conference on Computer Vision and Pattern Recognition , 2008. CVPR 2008 1-8. IEEE. |
| [35] | Shi, J. and Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22 8. |
| [36] | Simard, P. Y., LeCun, Y. and Denker, J. (1993). Efficient pattern recognition using a new transformation distance. In Advances in Neural Information Processing Systems 50-58. Morgan Kaufman, San Mateo, CA. |
| [37] | Sugaya, Y. and Kanatani, K. (2004). Geometric structure of degeneracy for multi-body motion segmentation. In Statistical Methods in Video Processing 125-201. Springer. · Zbl 1098.68868 |
| [38] | Tipping, M. and Bishop, C. (1999). Mixture of probabilistic principle component analyzers. Neural Comput. 11 443-482. |
| [39] | Tron, R. and Vidal, R. (2007). A benchmark for the comparison of 3-D motion segmentation algorithms. In IEEE Conference on Computer Vision and Pattern Recognition , 2007. CVPR’ 07 1-8. IEEE. |
| [40] | Tseng, P. (2000). Nearest \(q\)-flat to \(m\) points. J. Optim. Theory Appl. 105 249-252. · Zbl 0971.90055 · doi:10.1023/A:1004678431677 |
| [41] | Vershynin, R. (2011). Lectures in geometric functional analysis. Unpublished manuscript. Available at . |
| [42] | Vidal, R. (2011). A tutorial on subspace clustering. IEEE Signal Processing Magazine 28 52-68. |
| [43] | Vidal, R., Ma, Y. and Sastry, S. (2005). Generalized Principle Component Analysis (GPCA). IEEE Transactions on Pattern Analysis and Machine Intelligence 27 1-15. |
| [44] | Vidal, R., Soatto, S., Ma, Y. and Sastry, S. (2003). An algebraic geometric approach to the identification of a class of linear hybrid systems. In 42 nd IEEE Conference on Decision and Control , 2003. Proceedings 1 167-172. IEEE. |
| [45] | Vidal, R., Tron, R. and Hartley, R. (2008). Multiframe motion segmentation with missing data using PowerFactorization and GPCA. Int. J. Comput. Vis. 79 85-105. |
| [46] | Wu, Y., Zhang, Z., Huang, T. S. and Lin, J. Y. (2001). Multibody grouping via orthogonal subspace decomposition. In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition , 2001. CVPR 2001 2 II-252-II-257. IEEE. |
| [47] | Yan, J. and Pollefeys, M. (2006). A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In Computer Vision-ECCV 2006 94-106. Springer. |
| [48] | Yang, A., Wright, J., Ma, Y. and Sastry, S. (2008). Unsupervised segmentation of natural images via lossy data compression. Computer Vision and Image Understanding 110 212-225. |
| [49] | Yang, A. Y., Rao, S. R. and Ma, Y. (2006). Robust statistical estimation and segmentation of multiple subspaces. In Conference on Computer Vision and Pattern Recognition Workshop , 2006. CVPRW’ 06 99. IEEE. |
| [50] | Zhang, T., Szlam, A. and Lerman, G. (2009). Median \(k\)-flats for hybrid linear modeling with many outliers. In IEEE 12 th International Conference on Computer Vision Workshops ( ICCV Workshops ), 2009 234-241. IEEE. |
| [51] | Zhang, T., Szlam, A., Wang, Y. and Lerman, G. (2012). Hybrid linear modeling via local best-fit flats. Int. J. Comput. Vis. 100 217-240. · Zbl 1259.68207 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
