nips nips2013 nips2013-259 nips2013-259-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yu-Xiang Wang, Huan Xu, Chenlei Leng
Abstract: Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR) are both considered as the state-of-the-art methods for subspace clustering. The two methods are fundamentally similar in that both are convex optimizations exploiting the intuition of “Self-Expressiveness”. The main difference is that SSC minimizes the vector 1 norm of the representation matrix to induce sparsity while LRR minimizes nuclear norm (aka trace norm) to promote a low-rank structure. Because the representation matrix is often simultaneously sparse and low-rank, we propose a new algorithm, termed Low-Rank Sparse Subspace Clustering (LRSSC), by combining SSC and LRR, and develops theoretical guarantees of when the algorithm succeeds. The results reveal interesting insights into the strength and weakness of SSC and LRR and demonstrate how LRSSC can take the advantages of both methods in preserving the “Self-Expressiveness Property” and “Graph Connectivity” at the same time. 1
[1] D. Alonso-Guti´ rrez. On the isotropy constant of random convex sets. Proceedings of the American e Mathematical Society, 136(9):3293–3300, 2008.
[2] L. Bako. Identification of switched linear systems via sparse optimization. Automatica, 47(4):668–677, 2011.
[3] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends R in Machine Learning, 3(1):1–122, 2011.
[4] E.J. Cand` s and B. Recht. Exact matrix completion via convex optimization. Foundations of Computae tional mathematics, 9(6):717–772, 2009.
[5] G. Chen and G. Lerman. Spectral curvature clustering (SCC). International Journal of Computer Vision, 81(3):317–330, 2009.
[6] M. Elad. Sparse and redundant representations. Springer, 2010.
[7] E. Elhamifar and R. Vidal. Sparse subspace clustering. In Computer Vision and Pattern Recognition (CVPR’09), pages 2790–2797. IEEE, 2009.
[8] E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm, theory, and applications. to appear in IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2013.
[9] P. Favaro, R. Vidal, and A. Ravichandran. A closed form solution to robust subspace estimation and clustering. In Computer Vision and Pattern Recognition (CVPR’11), pages 1801–1807. IEEE, 2011.
[10] P. Gritzmann and V. Klee. Computational complexity of inner and outerj-radii of polytopes in finitedimensional normed spaces. Mathematical programming, 59(1):163–213, 1993.
[11] N. Hurley and S. Rickard. Comparing measures of sparsity. Information Theory, IEEE Transactions on, 55(10):4723–4741, 2009.
[12] A. Jalali, Y. Chen, S. Sanghavi, and H. Xu. Clustering partially observed graphs via convex optimization. In International Conference on Machine Learning (ICML’11), pages 1001–1008, 2011.
[13] I.T. Jolliffe. Principal component analysis, volume 487. Springer-Verlag New York, 1986.
[14] F. Lauer and C. Schnorr. Spectral clustering of linear subspaces for motion segmentation. In International Conference on Computer Vision (ICCV’09), pages 678–685. IEEE, 2009.
[15] Z. Lin, R. Liu, and Z. Su. Linearized alternating direction method with adaptive penalty for low-rank representation. In Advances in Neural Information Processing Systems 24 (NIPS’11), pages 612–620. 2011.
[16] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma. Robust recovery of subspace structures by low-rank representation. IEEE Trans. on Pattern Analysis and Machine Intelligence (TPAMI), 2012.
[17] G. Liu, Z. Lin, and Y. Yu. Robust subspace segmentation by low-rank representation. In International Conference on Machine Learning (ICML’10), pages 663–670, 2010.
[18] G. Liu, H. Xu, and S. Yan. Exact subspace segmentation and outlier detection by low-rank representation. In International Conference on Artificial Intelligence and Statistics (AISTATS’12), 2012.
[19] B. Nasihatkon and R. Hartley. Graph connectivity in sparse subspace clustering. In Computer Vision and Pattern Recognition (CVPR’11), pages 2137–2144. IEEE, 2011.
[20] A.Y. Ng, M.I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 15 (NIPS’02), volume 2, pages 849–856, 2002.
[21] E. Richard, P. Savalle, and N. Vayatis. Estimation of simultaneously sparse and low rank matrices. In International Conference on Machine learning (ICML’12), 2012.
[22] M. Soltanolkotabi and E.J. Candes. A geometric analysis of subspace clustering with outliers. The Annals of Statistics, 40(4):2195–2238, 2012.
[23] R. Tron and R. Vidal. A benchmark for the comparison of 3-d motion segmentation algorithms. In Computer Vision and Pattern Recognition (CVPR’07), pages 1–8. IEEE, 2007.
[24] R. Vidal. Subspace clustering. Signal Processing Magazine, IEEE, 28(2):52–68, 2011.
[25] R. Vidal, Y. Ma, and S. Sastry. Generalized principal component analysis (gpca). IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(12):1945–1959, 2005.
[26] R. Vidal, S. Soatto, Y. Ma, and S. Sastry. An algebraic geometric approach to the identification of a class of linear hybrid systems. In Decision and Control, 2003. Proceedings. 42nd IEEE Conference on, volume 1, pages 167–172. IEEE, 2003.
[27] R. Vidal, R. Tron, and R. Hartley. Multiframe motion segmentation with missing data using powerfactorization and gpca. International Journal of Computer Vision, 79(1):85–105, 2008.
[28] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395–416, 2007.
[29] Y.X. Wang and H. Xu. Noisy sparse subspace clustering. In International Conference on Machine Learning (ICML’13), volume 28, pages 100–108, 2013. 9