Abstract
In this paper, we propose a low-rank representation method that incorporates graph regularization for robust subspace clustering. We make the assumption that high-dimensional data can be approximated as the union of low-dimensional subspaces of unknown dimension. The proposed method extends the low-rank representation algorithm by incorporating graph regularization with a discriminative dictionary. Existing low-rank representation methods for subspace clustering use noisy data as the dictionary. The proposed technique, however, takes advantage of the discriminative dictionary to seek the lowest-rank representation by virtue of matrix recovery and completion techniques. Moreover, the discriminative dictionary is further used to construct a graph Laplacian to separate the low-rank representation of high-dimensional data. The proposed algorithm can recover the low-dimensional subspace structure from high-dimensional observations (which are often corrupted by gross errors). Simultaneously, the samples are clustered into their corresponding underlying subspaces. Extensive experimental results on benchmark databases demonstrate the efficiency and effectiveness of the proposed algorithm for subspace clustering.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aharon M, Elad M, Bruckstein A (2006) K-svd: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Trans Signal Process 54(11):4311–4322
Basri R, Jacobs DW (2003) Lambertian reflectance and linear subspaces. IEEE Trans Pattern Anal Mach Intell 25(2):218–233
Cai D, He X, Han J, Huang TS (2011) Graph regularized nonnegative matrix factorization for data representation. IEEE Trans Pattern Anal Mach Intell 33(8):1548–1560
Cai JF, Candès EJ, Shen Z (2010) A singular value thresholding algorithm for matrix completion. SIAM J Optim 20(4):1956–1982
Candès EJ, Li X, Ma Y et al (2011) Robust principal component analysis? JACM 58(3):11. doi:10.1145/1970392.1970395
Chen J, Yang J (2014) Robust subspace segmentation via low-rank representation. IEEE Trans Cybernet 44(8):1432–1445
Chen J, Yi Z (2014a) Sparse representation for face recognition by discriminative low-rank matrix recovery. J Vis Commun Image Represent 25(5):763–773
Chen J, Yi Z (2014b) Subspace clustering by exploiting a low-rank representation with a symmetric constraint. arXiv:1403.2330
Cheng B, Yang J, Yan S, Fu Y, Huang TS (2010) Learning with \({l_1}\)-graph for image analysis. IEEE Trans 19(4):858–866
Donoho D (2006) For most large underdetermined systems of linear equations the minimal \({l_1}\)-norm solution is also the sparsest solution. Commun Pure Appl Math 59(6):797–829
Elhamifar E, Vidal R (2013) Sparse subspace clustering algorithm, theory, and applications. IEEE Trans Pattern Anal Mach Intell 35(11):2765–2781
Fischler M, Bolles R (1981) Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun ACM 24(6):381–395
Georghiades A, Belhumeur P, Kriegman D (2011) From few to many: illumination cone models for face recognition under variable lighting and pose. IEEE Trans Pattern Anal Mach Intell 23(6):643–660
Hartigan JA, Wong MA (1979) Algorithm AS 136: A \(k\)-means clustering algorithm. Appl Stat 28(1):100–108. doi:10.2307/2346830
He R, Tan T, Wang L (2014) Robust recovery of corrupted low-rank matrix by implicit regularizers. IEEE Trans Pattern Anal Mach Intell 36(4):770–783
Ho J, Yang MH, Lim J et al (2003) Clustering appearances of objects under varying illumination conditions. In: 2003 IEEE computer society conference on computer vision and pattern recognition, vol 1: I-11–I-18. IEEE. doi:10.1109/CVPR.2003.1211332
Jolliffe I (2002) Principal component analysis. Springer, New York
Kuang D, Ding H, Park H (2012) Symmetric nonnegative matrix factorization for graph clustering. In: Proceedings of the 2012 SIAM international conference on data mining, vol 12, pp 106–117
Lauer F, Schnorr C (2009) Spectral clustering of linear subspaces for motion segmentation. In: IEEE international conference on computer vision, pp 678–685
LeCun Y, Bottou L, Bengio Y, Haffner P (1998) Gradient-based learning applied to document recognition. Proc IEEE 86(11):2278–2324
Lee K, Ho J, Kriegman D (2005a) Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans Pattern Anal Mach Intell 27(5):684–698
Lin Z, Liu R, Su Z (2012) Linearized alternating direction method with adaptive penalty for low-rank representation. arXiv:1109.0367
Liu G, Lin Z, Yu Y (2010) Robust subspace segmentation by low-rank representation. In: Proceedings of the 27th international conference on machine learning (ICML-10), pp 663–670. http://machinelearning.wustl.edu/mlpapers/paper_files/icml2010_LiuLY10.pdf
Liu G, Lin Z, Yan S, Sun J, Yu Y, Ma Y (2013) Robust recovery of subspace structures by low-rank representation. IEEE Trans Pattern Anal Mach Intell 35(1):171–184
Lu X, Wang Y, Yuan Y (2013) Graph-regularized low-rank representation for destriping of hyperspectral images. IEEE Trans Pattern Anal Mach Intell 51(7):4009–4018
Ma L, Wang C, Xiao B et al (2012) Sparse representation for face recognition based on discriminative low-rank dictionary learning. In: IEEE conference on computer vision and pattern recognition. IEEE, pp 2586–2593. doi:10.1109/CVPR.2012.6247977
Martinez A, Benavente R (1998) The ar face database. CVC Tech report no 24
McWilliams B, Montana G (2014) Subspace clustering of high-dimensional data: a predictive approach. Data Min Knowl Discov 28(3):736–772
Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Syst 2(11):849–856
Parsons L, Haque E, Liu H (2004) Subspace clustering for high dimensional data: a review. ACM SIGKDD Explor Newslett 6(1):90–105
Peng X, Zhang L, Yi Z (2013) Inductive sparse subspace clustering. Letters 49:1222–1224 (2)
Ramirez I, Sprechmann P, Sapiro G (2010) Classification and clustering via dictionary learning with structured incoherence and shared features. In: IEEE conference on computer vision and pattern recognition (CVPR). IEEE, pp 3501–3508. doi:10.1109/CVPR.2010.5539964
Rao S, Yang A, Sastry S, Ma Y (2010) Robust algebraic segmentation of mixed rigid-body and planar motions from two views. Int J Comput Vis 88(3):425–446
Saha B, Pham DS, Phung D, Venkatesh S (2013) Sparse subspace clustering via group sparse coding. In: SDM 2013: proceedings of the thirteenth SIAM international conference on data mining, pp 130–138
Shi J, Malik J, Sastry S (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22(8):888–905
Tibshiran R (1996) Regression shrinkage and selection via the lasso. J R Stat Soc Ser B 58(1):267–288
Vidal R, Ma Y, Sastry S (2005) Generalized principal component analysis (GPCA). IEEE Trans Pattern Anal Mach Intell 27(12):1945–1959
Wright J, Ganesh A, Rao S et al (2009) Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. In: Advances in neural information processing systems, pp 2080–2088. http://papers.nips.cc/paper/3704-robust-principal-component-analysis-exact-recovery-of-corrupted-low-rank-matrices-via-convex-optimization
Yan J, Pollefeys M (2006) A general framework for motion segmentation: independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In: European conference on computer vision, pp 94–106
Yang A, Rao S, Ma Y (2006) Robust statistical estimation and segmentation of multiple subspaces. In: 2006 CVPRW’06 conference on computer vision and pattern recognition workshop, p 99
Yang M, Zhang L, Feng X et al (2011) Fisher discrimination dictionary learning for sparse representation. In: IEEE international conference on computer vision (ICCV), pp 543–550. doi:10.1109/ICCV.2011.6126286
Zhang Z, Zhao K (2013) Low-rank matrix approximation with manifold regularization. IEEE Trans Pattern Anal Mach Intell 35(7):1717–1729
Zhang Z, Zhang J, Xue H (2008) Improved k-means clustering algorithm. In: 2008 CISP’08 congress on image and signal processing, vol 11, pp 169–172
Zhao M, Jiao L, Feng J, Liu T (2014) A simplified low rank and sparse graph for semi-supervised learning. Neurocomputing 140:84–96
Zheng M, Bu J, Chen C, Wang C, Zhang L, Qiu G, Cai D (2011) Graph regularized sparse coding for image representation. IEEE Trans Image Process 20(5):1327–1336
Zheng Y, Zhang X, Yang S, Jiao L (2013) Low-rank representation with local constraint for graph construction. Neurocomputing 122:398–405
Zhuang L, Gao H, Lin Z, Ma Y, Zhang X, Yu N (2012) Non-negative low rank and sparse graph for semi-supervised learning. In: CVPR
Acknowledgments
The authors would like to thank the anonymous reviewers for their valuable comments and suggestions. This research was supported by Scientific Research Fund of Sichuan Provincial Education Department under Grant 13ZB0154.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interests.
Additional information
Communicated by V. Loia.
Rights and permissions
About this article
Cite this article
He, W., Chen, J.X. & Zhang, W. Low-rank representation with graph regularization for subspace clustering. Soft Comput 21, 1569–1581 (2017). https://doi.org/10.1007/s00500-015-1869-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-015-1869-0