\(\ell ^{0}\) -Sparse Subspace Clustering

详细信息    查看全文

• 关键词：Sparse subspace clustering ; Proximal gradient descent
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9906
• 期：1
• 页码：731-747
• 全文大小：336 KB
• 参考文献：1.Elhamifar, E., Vidal, R.: Sparse subspace clustering: algorithm, theory, and applications. IEEE Trans. Pattern Anal. Mach. Intell. 35(11), 2765–2781 (2013)CrossRef
  2.Vidal, R.: Subspace clustering. IEEE Sig. Process. Mag. 28(2), 52–68 (2011)CrossRef
  3.Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: analysis and an algorithm. In: NIPS, pp. 849–856 (2001)
  4.Liu, G., Lin, Z., Yu, Y.: Robust subspace segmentation by low-rank representation. In: Proceedings of the 27th International Conference on Machine Learning (ICML-10), 21–24 June 2010, Haifa, Israel, pp. 663–670 (2010)
  5.Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., Ma, Y.: Robust recovery of subspace structures by low-rank representation. IEEE Trans. Pattern Anal. Mach. Intell. 35(1), 171–184 (2013)CrossRef
  6.Park, D., Caramanis, C., Sanghavi, S.: Greedy subspace clustering. In: Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 8–13 December 2014, Montreal, Quebec, Canada, pp. 2753–2761 (2014)
  7.Wang, Y.X., Xu, H., Leng, C.: Provable subspace clustering: when LRR meets SSC. In: Burges, C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K. (eds.) Advances in Neural Information Processing Systems 26, pp. 64–72. Curran Associates, Inc. (2013)
  8.Soltanolkotabi, M., Cands, E.J.: A geometric analysis of subspace clustering with outliers. Ann. Statist. 40(4), 2195–2238 (2012)MathSciNet CrossRef MATH
  9.Wang, Y., Xu, H.: Noisy sparse subspace clustering. In: Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, pp. 89–97, 16–21 June 2013
  10.Yan, S., Wang, H.: Semi-supervised learning by sparse representation. In: SDM, pp. 792–801 (2009)
  11.Cheng, B., Yang, J., Yan, S., Fu, Y., Huang, T.S.: Learning with l1-graph for image analysis. IEEE Trans. Image Process. 19(4), 858–866 (2010)MathSciNet CrossRef
  12.Elhamifar, E., Vidal, R.: Sparse manifold clustering and embedding. In: NIPS, pp. 55–63 (2011)
  13.Yang, Y., Wang, Z., Yang, J., Han, J., Huang, T.: Regularized l1-graph for data clustering. In: Proceedings of the British Machine Vision Conference. BMVA Press (2014)
  14.Yang, Y., Wang, Z., Yang, J., Wang, J., Chang, S., Huang, T.S.: Data clustering by Laplacian regularized l1-graph. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 27–31 July 2014, Québec City, Québec, Canada, pp. 3148–3149 (2014)
  15.Peng, X., Yi, Z., Tang, H.: Robust subspace clustering via thresholding ridge regression. In: AAAI Conference on Artificial Intelligence (AAAI), pp. 3827–3833 (2015)
  16.Jenatton, R., Mairal, J., Bach, F.R., Obozinski, G.R.: Proximal methods for sparse hierarchical dictionary learning. In: Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 487–494 (2010)
  17.Mairal, J., Bach, F., Ponce, J., Sapiro, G.: Online learning for matrix factorization and sparse coding. J. Mach. Learn. Res. 11, 19–60 (2010)MathSciNet MATH
  18.Mairal, J., Bach, F.R., Ponce, J., Sapiro, G., Zisserman, A.: Supervised dictionary learning. In: Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, 8–11 December 2008, pp. 1033–1040 (2008)
  19.Mancera, L., Portilla, J.: L0-norm-based sparse representation through alternate projections. In: 2006 IEEE International Conference on Image Processing, pp. 2089–2092, October 2006
  20.Yang, J., Yu, K., Gong, Y., Huang, T.S.: Linear spatial pyramid matching using sparse coding for image classification. In: CVPR, pp. 1794–1801 (2009)
  21.Cheng, H., Liu, Z., Yang, L., Chen, X.: Sparse representation and learning in visual recognition: theory and applications. Sig. Process. 93(6), 1408–1425 (2013)CrossRef
  22.Zhang, T., Ghanem, B., Liu, S., Xu, C., Ahuja, N.: Low-rank sparse coding for image classification. In: IEEE International Conference on Computer Vision, ICCV 2013, Sydney, Australia, 1–8 December 2013, pp. 281–288 (2013)
  23.Soltanolkotabi, M., Elhamifar, E., Cands, E.J.: Robust subspace clustering. Ann. Statist. 2(04), 669–699
  24.Wang, Y., Wang, Y.X., Singh, A.: Graph connectivity in noisy sparse subspace clustering. CoRR abs/1504.01046 (2016)
  25.Dyer, E.L., Sankaranarayanan, A.C., Baraniuk, R.G.: Greedy feature selection for subspace clustering. J. Mach. Learn. Res. 14, 2487–2517 (2013)MathSciNet MATH
  26.Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theor. 50(10), 2231–2242 (2004)MathSciNet CrossRef MATH
  27.Hyder, M., Mahata, K.: An approximate l0 norm minimization algorithm for compressed sensing. In: IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2009, pp. 3365–3368, April 2009
  28.Zhang, C.H., Zhang, T.: A general theory of concave regularization for high-dimensional sparse estimation problems. Statist. Sci. 27(4), 576–593 (2012)MathSciNet CrossRef MATH
  29.Candes, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theor. 51(12), 4203–4215 (2005)MathSciNet CrossRef MATH
  30.Cands, E.J.: The restricted isometry property and its implications for compressed sensing. C.R. Math. 346(910), 589–592 (2008)MathSciNet CrossRef MATH
  31.Zheng, X., Cai, D., He, X., Ma, W.Y., Lin, X.: Locality preserving clustering for image database. In: Proceedings of the 12th Annual ACM International Conference on Multimedia, MULTIMEDIA 2004, pp. 885–891. ACM, New York (2004)
  32.Asuncion, A., D.N.: UCI machine learning repository (2007)
  
• 作者单位：Yingzhen Yang (17)
  Jiashi Feng (18)
  Nebojsa Jojic (19)
  Jianchao Yang (20)
  Thomas S. Huang (17)
  
  17. Beckman Institute, University of Illinois at Urbana-Champaign, Urbana, USA
  18. Department of ECE, National University of Singapore, Singapore, Singapore
  19. Microsoft Research, Redmond, USA
  20. Snapchat, Los Angeles, USA
  
• 丛书名：Computer Vision – ECCV 2016
• ISBN：978-3-319-46475-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9906

文摘

Subspace clustering methods with sparsity prior, such as Sparse Subspace Clustering (SSC) [1], are effective in partitioning the data that lie in a union of subspaces. Most of those methods require certain assumptions, e.g. independence or disjointness, on the subspaces. These assumptions are not guaranteed to hold in practice and they limit the application of existing sparse subspace clustering methods. In this paper, we propose \(\ell ^{0}\)-induced sparse subspace clustering (\(\ell ^{0}\)-SSC). In contrast to the required assumptions, such as independence or disjointness, on subspaces for most existing sparse subspace clustering methods, we prove that subspace-sparse representation, a key element in subspace clustering, can be obtained by \(\ell ^{0}\)-SSC for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We also present the “no free lunch” theorem that obtaining the subspace representation under our general assumptions can not be much computationally cheaper than solving the corresponding \(\ell ^{0}\) problem of \(\ell ^{0}\)-SSC. We develop a novel approximate algorithm named Approximate \(\ell ^{0}\)-SSC (\(\hbox {A}\ell ^{0}\)-SSC) that employs proximal gradient descent to obtain a sub-optimal solution to the optimization problem of \(\ell ^{0}\)-SSC with theoretical guarantee, and the sub-optimal solution is used to build a sparse similarity matrix for clustering. Extensive experimental results on various data sets demonstrate the superiority of \(\hbox {A}\ell ^{0}\)-SSC compared to other competing clustering methods.