×

zbMATH — the first resource for mathematics

A rank-constrained matrix representation for hypergraph-based subspace clustering. (English) Zbl 1394.68313
Summary: This paper presents a novel, rank-constrained matrix representation combined with hypergraph spectral analysis to enable the recovery of the original subspace structures of corrupted data. Real-world data are frequently corrupted with both sparse error and noise. Our matrix decomposition model separates the low-rank, sparse error, and noise components from the data in order to enhance robustness to the corruption. In order to obtain the desired rank representation of the data within a dictionary, our model directly utilizes rank constraints by restricting the upper bound of the rank range. An alternative projection algorithm is proposed to estimate the low-rank representation and separate the sparse error from the data matrix. To further capture the complex relationship between data distributed in multiple subspaces, we use hypergraph to represent the data by encapsulating multiple related samples into one hyperedge. The final clustering result is obtained by spectral decomposition of the hypergraph Laplacian matrix. Validation experiments on the Extended Yale Face Database B, AR, and Hopkins 155 datasets show that the proposed method is a promising tool for subspace clustering.
MSC:
68T05 Learning and adaptive systems in artificial intelligence
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C65 Hypergraphs
62H30 Classification and discrimination; cluster analysis (statistical aspects)
Software:
AR face
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Vidal, R., Subspace clustering, IEEE Signal Processing Magazine, 28, 2, 52-68, (2011)
[2] Wright, J.; Ma, Y.; Mairal, J.; Sapiro, G.; Huang, T. S.; Yan, S., Sparse representation for computer vision and pattern recognition, Proceedings of the IEEE, 98, 6, 1031-1044, (2010)
[3] Ho, J.; Yang, M.-H.; Lim, J.; Lee, K.-C.; Kriegman, D., Clustering appearances of objects under varying illumination conditions, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE
[4] Yang, A. Y.; Wright, J.; Ma, Y.; Sastry, S. S., Unsupervised segmentation of natural images via lossy data compression, Computer Vision and Image Understanding, 110, 2, 212-225, (2008)
[5] Vidal, R., A tutorial on subspace clustering, IEEE Signal Processing Magazine, 28, 2, 52-68, (2011)
[6] Boult, T. E.; Brown, L. G., Factorization-based segmentation of motions, Proceedings of the IEEE Workshop on Visual Motion, IEEE
[7] Costeira, J. P.; Kanade, T., A multibody factorization method for independently moving objects, International Journal of Computer Vision, 29, 3, 159-179, (1998)
[8] Kanatani, K., Motion segmentation by subspace separation and model selection, Proceedings of the IEEE International Conference on Computer Vision (ICCV ’01)
[9] Vidal, R.; Ma, Y.; Sastry, S., Generalized principal component analysis (GPCA), IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 12, 1945-1959, (2005)
[10] Ma, Y.; Yang, A. Y.; Derksen, H.; Fossum, R., Estimation of subspace arrangements with applications in modeling and segmenting mixed data, SIAM Review, 50, 3, 413-458, (2008) · Zbl 1147.52010
[11] Tipping, M. E.; Bishop, C. M., Mixtures of probabilistic principal component analyzers, Neural Computation, 11, 2, 443-482, (1999)
[12] 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, 29, 9, 1546-1562, (2007)
[13] 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 Association for Computing Machinery, 24, 6, 381-395, (1981)
[14] Elhamifar, E.; Vidal, R., Sparse subspace clustering, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’09), IEEE
[15] Liu, G.; Lin, Z.; Yu, Y., Robust subspace segmentation by low-rank representation, Proceedings of the 27th International Conference on Machine Learning (ICML ’10)
[16] Liu, G.; Lin, Z.; Yan, S.; Sun, J.; Yu, Y.; Ma, Y., Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 1, 171-184, (2013)
[17] Sprechmann, P.; Bronstein, A. M.; Sapiro, G., Learning efficient sparse and low rank models, IEEE Transactions on Pattern Analysis and Machine Intelligence, 37, 9, 1821-1833, (2015)
[18] Zhou, T.; Tao, D., GoDec: randomized low-rank & sparse matrix decomposition in noisy case, Proceedings of the 28th International Conference on Machine Learning (ICML ’11)
[19] Favaro, P.; Vidal, R.; Ravichandran, A., A closed form solution to robust subspace estimation and clustering, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’11)
[20] Basri, R.; Jacobs, D. W., Lambertian reflectance and linear subspaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, 25, 2, 218-233, (2003)
[21] Zhou, D.; Huang, J.; Schlkopf, B., Learning with hypergraphs: clustering, classification, and embedding, Advances in Neural Information Processing Systems (NIPS) 19, 1601-1608, (2007), MIT Press
[22] Agarwal, S.; Lim, J.; Zelnik-Manor, L.; Perona, P.; Kriegman, D.; Belongie, S., Beyond pairwise clustering, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’05), IEEE
[23] Zhou, T.; Tao, D., Bilateral random projections, Proceedings of the IEEE International Symposium on Information Theory (ISIT ’12)
[24] Toh, K.-C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6, 3, 615-640, (2010) · Zbl 1205.90218
[25] Liu, Q.; Huang, Y.; Metaxas, D. N., Hypergraph with sampling for image retrieval, Pattern Recognition, 44, 10-11, 2255-2262, (2011) · Zbl 1218.68188
[26] Huang, Y.; Liu, Q.; Zhang, S.; Metaxas, D. N., Image retrieval via probabilistic hypergraph ranking, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR ’10)
[27] Tron, R.; Vidal, R., A benchmark for the comparison of 3-D motion segmentation algorithms, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE
[28] Lee, K.-C.; Ho, J.; Kriegman, D. J., Acquiring linear subspaces for face recognition under variable lighting, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 5, 684-698, (2005)
[29] Martinez, A. M.; Benavente, R., The AR face database, CVC Technical Report, 24, (1998)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.