稀疏子空间聚类综述

王卫卫; 李小平; 冯象初; 王斯琪

doi:10.16383/j.aas.2015.c140891

稀疏子空间聚类综述

doi: 10.16383/j.aas.2015.c140891

1.
西安电子科技大学数学与统计学院西安 710126

基金项目:

国家自然科学基金(61472303, 61271294, 61379030, 61362029, 61301229)和中央高校基本科研业务费(NSIY21)资助

详细信息

作者简介:
王卫卫西安电子科技大学数学与统计学院教授.2001年获西安电子科技大学理学博士学位.主要研究方向为小波、变分偏微分方程、低秩表示、稀疏表示在图像处理中的应用.E-mail:wwwang@mail.xidian.edu.cn

计量
- 文章访问数: 8953
- HTML全文浏览量: 392
- PDF下载量: 7413
- 被引次数: 0
出版历程
- 收稿日期: 2014-12-22
- 修回日期: 2015-04-23
- 刊出日期: 2015-08-20

A Survey on Sparse Subspace Clustering

1.
School of Mathematics and Statistics, Xidian University, Xi'an 710126

Funds:

Supported by National Natural Science Foundation of China (61472303, 61271294, 61379030, 61362029, 61301229) and Fundamental Research Fund for the Central Universities (NSIY21)

摘要

摘要: 稀疏子空间聚类(Sparse subspace clustering, SSC)是一种基于谱聚类的数据聚类框架. 高维数据通常分布于若干个低维子空间的并上, 因此高维数据在适当字典下的表示具有稀疏性. 稀疏子空间聚类利用高维数据的稀疏表示系数构造相似度矩阵, 然后利用谱聚类方法得到数据的子空间聚类结果. 其核心是设计能够揭示高维数据真实子空间结构的表示模型, 使得到的表示系数及由此构造的相似度矩阵有助于精确的子空间聚类. 稀疏子空间聚类在机器学习、计算机视觉、图像处理和模式识别等领域已经得到了广泛的研究和应用, 但仍有很大的发展空间. 本文对已有稀疏子空间聚类方法的模型、算法和应用等方面进行详细阐述, 并分析存在的不足, 指出进一步研究的方向.
- 高维数据 /
- 子空间聚类 /
- 稀疏表示 /
- 低秩表示
Abstract: Sparse subspace clustering (SSC) is a newly developed spectral clustering-based framework for data clustering. High-dimensional data usually lie in a union of several low-dimensional subspaces, which allows sparse representation of high-dimensional data with an appropriate dictionary. Sparse subspace clustering methods pursue a sparse representation of high-dimensional data and use it to build the affinity matrix. The subspace clustering result of the data is finally obtained by means of spectral clustering. The key to sparse subspace clustering is to design a good representation model which can reveal the real subspace structure of high-dimensional data. More importantly, the obtained representation coefficient and the affinity matrix are more beneficial to accurate subspace clustering. Sparse subspace clustering has been successfully applied to different research fields, including machine learning, computer vision, image processing, system identification and others, but there is still a vast space to develop. In this paper, the fundamental models, algorithms and applications of sparse subspace clustering are reviewed in detail. Limitations existing in available methods are analyzed. Problems for further research on sparse subspace clustering are discussed.
- High-dimensional data /
- subspace clustering (SC) /
- sparse representation /
- low rank representation

HTML全文

参考文献(101)

[1]	Donoho D L. High-dimensional data analysis: the curses and blessings of dimensionality. American Mathematical Society Math Challenges Lecture, 2000. 1-32
[2]	从稀疏约束到低秩约束优化. 信号处理, 2012, 28(5): 609-623)
[3]	Parsons L, Haque E, Liu H. Subspace clustering for high dimensional data: a review. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 90-105
[4]	理论与应用. 自动化学报, 2013, 39(7): 981-994)
[5]	Vidal R. Subspace clustering. IEEE Signal Processing Magazine, 2011, 28(2): 52-68
[6]	系统工程与电子技术, 2014, 36(3): 580-585)
[7]	Agrawal R, Gehrke J, Gunopulos D, Raghavan P. Automatic subspace clustering of high dimensional data for data mining applications. ACM SIGMOD Record, 1998, 27(2): 94-105
[8]	西安电子科技大学学报(自然科学版), 2013, 40(5): 86-91)
[9]	Lu L, Vidal R. Combined central and subspace clustering for computer vision applications. In: Proceedings of the 23rd International Conference on Machine Learning (ICML). Pittsburgh, USA: ACM, 2006. 593-600
[10]	Hong W, Wright J, Huang K, Ma Y. Multi-scale hybrid linear models for lossy image representation. IEEE Transactions on Image Processing, 2006, 15(12): 3655-3671
[11]	Yang A Y, Wright J, Ma Y, Sastry S. Unsupervised segmentation of natural images via lossy data compression. Computer Vision and Image Understanding, 2008, 110(2): 212-225
[12]	Vidal R, Soatto S, Ma Y, Sastry S. An algebraic geometric approach to the identification of a class of linear hybrid systems. In: Proceedings of the 42nd IEEE Conference on Decision and Control. Maui, HI, USA: IEEE, 2003. 167-172
[13]	Boult T E, Brown L G. Factorization-based segmentation of motions. In: Proceedings of the 1991 IEEE Workshop on Visual Motion. Princeton, NJ: IEEE, 1991. 179-186
[14]	Wu Y, Zhang Z Y, Huang T S, Lin J Y. Multibody grouping via orthogonal subspace decomposition. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Kauai, HI, USA: IEEE, 2001. 2: 252-257
[15]	Vidal R, Ma Y, Sastry S. Generalized principal component analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(12): 1945-1959
[16]	Rao S R, Yang A Y, Sastry S S, Ma Y. Robust algebraic segmentation of mixed rigid-body and planar motions from two views. International Journal of Computer Vision, 2010, 88(3): 425-446
[17]	Ma Y, Yang A Y, Derksen H, Fossum R. Estimation of subspace arrangements with applications in modeling and segmenting mixed data. SIAM Review, 2008, 50(3): 413-458
[18]	Ho J, Yang M H, Lim J, Lee K C, Kriegman D. Clustering appearances of objects under varying illumination conditions. In: Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Madison, WI, USA: IEEE, 2003. 1: 11-18
[19]	Bradley P S, Mangasarian O L. k-plane clustering. Journal of Global Optimization, 2000, 16(1): 23-32
[20]	Tipping M E, Bishop C M. Mixtures of probabilistic principal component analyzers. Neural Computation, 1999, 11(2): 443-482
[21]	Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 1981, 24: 381-395
[22]	Ma Y, Derksen H, Hong W, Wright J. Segmentation of multivariate mixed data via lossy data coding and compression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(9): 1546-1562
[23]	Von Luxburg U. A tutorial on spectral clustering. Statistics and Computing, 2007, 17(4): 395-416
[24]	Chen G L, Lerman G. Spectral curvature clustering (SCC). International Journal of Computer Vision, 2009, 81(3): 317-330
[25]	Lauer F, Schnorr C. Spectral clustering of linear subspaces for motion segmentation. In: Proceedings of the 12th IEEE International Conference on Computer Vision (ICCV). Kyoto, Japan: IEEE, 2009. 678-685
[26]	Shi J B, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905
[27]	Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 1998, 20(1): 33-61
[28]	Candés E J. Compressive sampling. In: Proceedings of the 2006 International Congress of Mathematics. Madrid, Spain: the European Mathematical Society, 2006. 1433-1452
[29]	Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306
[30]	Davenport M A, Duarte M F, Eldar Y C, Kutyniok G. Introduction to compressed sensing. Compressed Sensing: Theory and Applications. Cambridge: Cambridge University Press, 2012.
[31]	Liu Fang, Wu Jiao, Yang Shu-Yuan, Jiao Li-Cheng. Research advances on structured compressive sensing. Acta Automatica Sinica, 2013, 39(12): 1980-1995 (刘芳, 武娇, 杨淑媛, 焦李成. 结构化压缩感知研究进展. 自动化学报,
[32]	Elad M, Aharon M. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing, 2006, 15(12): 3736-3745
[33]	Li T, Wang W W, Feng X C, Xu L. Image denoising using low-rank dictionary and sparse representation. In: Proceedings of the 10th International Conference on Computational Intelligenceand Security (CIS'2014). Kunming, Yunnan Province, China: IEEE. 2014. 228-232
[34]	Yang J C, Wright J, Huang T S, Ma Y. Image super-resolution via sparse representation. IEEE Transactions on Image Processing, 2010, 19(11): 2861-2873
[35]	Starck J L, Elad M, Donoho D L. Image decomposition via the combination of sparse representations and a variational approach. IEEE Transactions on Image Processing, 2005, 14(10): 1570-1582
[36]	Elhamifar E, Vidal R. Sparse subspace clustering. In: Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Miami, FL, USA: IEEE, 2009. 2790-2797
[37]	Elhamifar E, Vidal R. Sparse subspace clustering: algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2765-2781
[38]	Elhamifar E, Vidal R. Sparsity in unions of subspaces for classification and clustering of high-dimensional data. In: Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing. Monticello, Illinois, USA: IEEE, 2011. 1085-1089
[39]	Li C G, Guo J, Zhang H G. Local sparse representation based classification. In: Proceedings of the 20th International Conference on Pattern Recognition (ICPR). Istanbul, Turkey: IEEE, 2010. 649-652
[40]	Yin J, Liu Z H, Jin Z, Yang W K. Kernel sparse representation based classification. Neurocomputing, 2012, 77(1): 120-128
[41]	Wright J, Yang A Y, Ganesh A, Sastry S S, Ma Y. Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227
[42]	Zhang L, Yang M, Feng X C. Sparse representation or collaborative representation: which helps face recognition? In: Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV). Barcelona, Spain: IEEE, 2011. 471-478
[43]	Wright J, Ma Y, Mairal J, Sapiro G, Huang T S, Yan S C. Sparse representation for computer vision and pattern recognition. Proceedings of the IEEE, 2010, 98(6): 1031-1044
[44]	Zhang H Y, Lin Z C, Zhang C. A counterexample for the validity of using nuclear norm as a convex surrogate of rank. Machine Learning and Knowledge Discovery in Databases. Berlin Heidelberg: Springer, 2013. 226-241
[45]	Candes E J, Tao T. The power of convex relaxation: near-optimal matrix completion. IEEE Transactions on Information Theory, 2010, 56(5): 2053-2080
[46]	Ma Jian-Wei, Xu Jie, Bao Yue-Quan, Yu Si-Wei. Compressive sensing and its application: from sparse to low-rank regularized optimization. Signal Processing, 2012, 28(5): 609-623 (马坚伟, 徐杰, 鲍跃全, 于四伟. 压缩感知及其应用:
[47]	Peng Yi-Gang, Suo Jin-Li, Dai Qiong-Hai, Xu Wen-Li. From compressed sensing to low-rank matrix recovery: theory and applications. Acta Automatica Sinica, 2013, 39(7): 981-994 (彭义刚, 索津莉, 戴琼海, 徐文立. 从压缩传感到低秩矩阵恢复:
[48]	Candés E J, Recht B. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 2009, 9(6): 717-772
[49]	Cai J F, Candés E J, Shen Z W. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 2010, 20(4): 1956-1982
[50]	Candés E J, Li X D, Ma Y, Wright J. Robust principal component analysis? Journal of the ACM, 2011, 58(3): 11.
[51]	Liu G C, Lin Z C, Yu Y. Robust subspace segmentation by low-rank representation. In: Proceedings of the 27th International Conference on Machine Learning (ICML). Haifa, Israel, 2010. 663-670
[52]	Liu G C, Lin Z C, Yan S C, Sun J, Yu Y, Ma Y. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 171-184
[53]	Zhang Y, Jiang Z L, Davis L S. Learning structured low-rank representations for image classification. In: Proceedings of the 2013 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Portland, OR, USA: IEEE, 2013. 676-683
[54]	Li L Y, Li S, Fu Y. Learning low-rank and discriminative dictionary for image classification. Image and Vision Computing, 2014, 32(10): 814-823
[55]	Chen C F, Wei C P, Wang Y C F. Low-rank matrix recovery with structural incoherence for robust face recognition. In: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2012. 2618-2625
[56]	Zheng Y G, Zhang X R, Yang S Y, Jiao L C. Low-rank representation with local constraint for graph construction. Neurocomputing, 2013, 122: 398-405
[57]	Vidal R, Favaro P. Low rank subspace clustering (LRSC). Pattern Recognition Letters, 2014, 43: 47-61
[58]	Costeira J P, Kanade T. A multibody factorization method for independently moving objects. International Journal of Computer Vision, 1998, 29(3): 159-179
[59]	Hu H, Lin Z C, Feng J J, Zhou J. Smooth representation clustering. In: Proceedings of the 2014 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Columbus, OH, USA: IEEE, 2014. 3834-3841
[60]	He X F, Niyogi P. Locality preserving projections. Advances in Neural Information Processing Systems, 2003, 16: 153-160
[61]	Liu W F, Pokharel P P, Principe J C. Correntropy: properties and applications in non-Gaussian signal processing. IEEE Transactions on Signal Processing, 2007, 55(11): 5286-5298
[62]	Lu C Y, Tang J H, Lin M, Lin L, Yan S C, Lin Z C. Correntropy induced L2 graph for robust subspace clustering. In: Proceedings of the 2013 IEEE International Conference on Computer Vision (ICCV). Sydney, NSW, Australia: IEEE, 2013. 1801-1808
[63]	Zhang Y Y, Sun Z N, He R, Tan T N. Robust subspace clustering via half-quadratic minimization. In: Proceedings of the 2013 IEEE International Conference on Computer Vision (ICCV). Sydney, NSW, Australia: IEEE, 2013. 3096-3103
[64]	Feng J S, Lin Z C, Xu H, Yan S C. Robust subspace segmentation with block-diagonal prior. In: Proceedings of the 2014 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Columbus, OH, USA: IEEE, 2014. 3818-3825
[65]	Elhamifar E, Vidal R. Clustering disjoint subspaces via sparse representation. In: Proceedings of the 2010 International Conference on Acoustics, Speech, and Signal Processing (ICASSP). Dallas, Texas, USA: IEEE, 2010. 1926-1929
[66]	Wang S S, Yuan X T, Yao T S, Yan S C, Shen J L. Efficient subspace segmentation via quadratic programming. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI). San Francisco, California, USA: AAAI Press, 2011. 519-524.
[67]	Luo D J, Nie F P, Ding C, Huang H. Multi-subspace representation and discovery. Machine Learning and Knowledge Discovery in Databases. Berlin Heidelberg: Springer, 2011. 405-420
[68]	Liu G C, Yan S C. Latent low-rank representation for subspace segmentation and feature extraction. In: Proceedings of the 2011 IEEE International Conference on Computer Vision (ICCV). Barcelona, Spain: IEEE, 2011. 1615-1622
[69]	Zhuang L S, Gao H Y, Lin Z C, Ma Y, Zhang X, Yu N H. Non-negative low rank and sparse graph for semi-supervised learning. In: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2012. 2328-2335
[70]	Lu C Y, Min H, Zhao Z Q, Zhu L, Huang D S, Yan S C. Robust and efficient subspace segmentation via least squares regression. In: Proceedings of the the 2012 Computer Vision-European Conference on Computer Vision (ECCV). Florence, Italy: Springer Berlin Heidelberg, 2012. 347-360
[71]	Pham D S, Budhaditya S, Phung D, Venkatesh S. Improved subspace clustering via exploitation of spatial constraints. In: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2012. 550-557
[72]	Saha B, Pham D S, Phung D, Venkatesh S. Sparse subspace clustering via group sparse coding. In: Proceedings of the 2013 SIAM International Conference on Data Mining (SDM 2013). Austin, Texas, USA: Society for Industrial and Applied Mathematics, 2013. 130-138
[73]	Lu C Y, Feng J S, Lin Z C, Yan S C. Correlation adaptive subspace segmentation by Trace Lasso. In: Proceedings of the 2013 IEEE International Conference on Computer Vision (ICCV). Sydney, Australia: IEEE, 2013. 1345-1352
[74]	Soltanolkotabi M, Cand\'{es E J. A geometric analysis of subspace clustering with outliers. The Annals of Statistics, 2012, 40(4): 2195-2238
[75]	Lin Z C, Chen M M, Ma Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. UIUC Technical Report UILU-ENG-09-2215, arXiv preprint arXiv: 1009.5055, 2010
[76]	Nikolova M, Ng M K. Analysis of half-quadratic minimization methods for signal and image recovery. SIAM Journal on Scientific Computing, 2005, 27(3): 937-966
[77]	Lin Z C, Liu R S, Su Z X. Linearized alternating direction method with adaptive penalty for low-rank representation. Advances in Neural Information Processing Systems, 2011. 612-620
[78]	Lin Z C, Liu R S, Li H. Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. Machine Learning, 2015, 99(2): 287-325
[79]	Patel V M, Van Nguyen H, Vidal R. Latent space sparse subspace clustering. In: Proceedings of the 2013 IEEE International Conference on Computer Vision (ICCV). Darling Harbour, Sydney: IEEE, 2013. 225-232
[80]	Zhang X, Sun F C, Liu G C, Ma Y. Fast low-rank subspace segmentation. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5): 1293-1297
[81]	Liu Y Y, Jiao L C, Shang F H. An efficient matrix factorization based low-rank representation for subspace clustering. Pattern Recognition, 2013, 46(1): 284-292
[82]	Liu Y Y, Jiao L C, Shang F H, Yin F, Liu F. An efficient matrix bi-factorization alternative optimization method for low-rank matrix recovery and completion. Neural Networks, 2013, 48: 8-18
[83]	Liu Y Y, Jiao L C, Shang F H. A fast tri-factorization method for low-rank matrix recovery and completion. Pattern Recognition, 2013, 46(1): 163-173
[84]	Favaro P, Vidal R, Ravichandran A. A closed form solution to robust subspace estimation and clustering. In: Proceedings of the 2011 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2011. 1801-1807
[85]	Peng X, Zhang L, Yi Z. Scalable sparse subspace clustering. In: Proceedings of the 2013 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Portland, OR, USA: IEEE, 2013. 430-437
[86]	Ma L, Wang C H, Xiao B H, Zhou W. Sparse representation for face recognition based on discriminative low-rank dictionary learning. In: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI: IEEE, 2012. 2586-2593
[87]	Qian J J, Yang J, Zhang F L, Lin Z C. Robust low-rank regularized regression for face fecognition with occlusion. In: Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). Columbus, Ohio, USA: IEEE, 2014. 21-26
[88]	Gui J, Sun Z N, Jia W, Hu R X, Lei Y K, Ji S W. Discriminant sparse neighborhood preserving embedding for face recognition. Pattern Recognition, 2012, 45(8): 2884-2893
[89]	Tron R, Vidal R. A benchmark for the comparison of 3-d motion segmentation algorithms. In: Proceedings of the 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Minneapolis, MN: IEEE, 2007. 1-8
[90]	Rao S R, Tron R, Vidal R, Ma Y. Motion segmentation via robust subspace separation in the presence of outlying, incomplete, or corrupted trajectories. In: Proceedings of the 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK: IEEE, 2008. 1-8
[91]	Rao S R, Tron R, Vidal R, Ma Y. Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1832-1845
[92]	Li Tao, Wang Wei-Wei, Zhai Dong, Jia Xi-Xi. Weighted-sparse subspace clustering method for image segmentation. Systems Engineering and Electronics, 2014, 36(3): 580-585 (李涛, 王卫卫, 翟栋, 贾西西. 图像分割的加权稀疏子空间聚类方法.
[93]	Zhang Wen-Juan, Feng Xiang-Chu. Image super-pixels segmentation method based on the non-convex low-rank and sparse constraints. Journal of Xidian University, 2013, 40(5): 86-91 (张文娟, 冯象初. 非凸低秩稀疏约束的图像超像素分割方法.
[94]	Cheng B, Liu G C, Wang J D, Huang Z Y, Yan S C. Multi-task low-rank affinity pursuit for image segmentation. In: Proceedings of the 2011 International Conference on Computer Vision (ICCV). Barcelona, Spain: IEEE, 2011. 2439-2446
[95]	Lang C Y, Liu G C, Yu J, Yan S C. Saliency detection by multitask sparsity pursuit. IEEE Transactions on Image Processing, 2012, 21(3): 1327-1338
[96]	Basri R, Jacobs D W. Lambertian reflectance and linear subspaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(2): 218-233
[97]	Lee K C, Ho J, Kriegman D. Acquiring linear subspaces for face recognition under variable lighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 684-698
[98]	Oja E. Simplified neuron model as a principal component analyzer. Journal of Mathematical Biology, 1982, 15(3): 267-273
[99]	Babacan S D, Luessi M, Molina R, Katsaggelos A K. Sparse Bayesian methods for low-rank matrix estimation. IEEE Transactions on Signal Processing, 2012, 60(8): 3964-3977
[100]	Zhao Q, Meng D Y, Xu Z B, Zuo W M, Zhang L. Robust principal component analysis with complex noise. In: Proceedings of the 31st International Conference on Machine Learning (ICML). Beijing, China, 2014. 55-63
[101]	, 39(12): 1980-1995)