Enhanced low-rank representation via sparse manifold adaption for semi-supervised learning. (English) Zbl 1394.68307
Summary: Constructing an informative and discriminative graph plays an important role in various pattern recognition tasks such as clustering and classification. Among the existing graph-based learning models, low-rank representation (LRR) is a very competitive one, which has been extensively employed in spectral clustering and semi-supervised learning (SSL). In SSL, the graph is composed of both labeled and unlabeled samples, where the edge weights are calculated based on the LRR coefficients. However, most of existing LRR related approaches fail to consider the geometrical structure of data, which has been shown beneficial for discriminative tasks. In this paper, we propose an enhanced LRR via sparse manifold adaption, termed manifold low-rank representation (MLRR), to learn low-rank data representation. MLRR can explicitly take the data local manifold structure into consideration, which can be identified by the geometric sparsity idea; specifically, the local tangent space of each data point was sought by solving a sparse representation objective. Therefore, the graph to depict the relationship of data points can be built once the manifold information is obtained. We incorporate a regularizer into LRR to make the learned coefficients preserve the geometric constraints revealed in the data space. As a result, MLRR combines both the global information emphasized by low-rank property and the local information emphasized by the identified manifold structure. Extensive experimental results on semi-supervised classification tasks demonstrate that MLRR is an excellent method in comparison with several state-of-the-art graph construction approaches.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68T10 | Pattern recognition, speech recognition |
Keywords:
low-rank representation; sparse manifold adaption; graph construction; semi-supervised learning; face recognitionSoftware:
l1_lsReferences:
| [1] | Cai, J. F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 1956-1982, (2010) · Zbl 1201.90155 |
| [2] | Cai, D.; He, X.; Han, J., Locally consistent concept factorization for document clustering, IEEE Transactions on Knowledge and Data Engineering, 23, 902-913, (2011) |
| [3] | Cai, D.; He, X.; Han, J.; Huang, T. S., Graph regularized nonnegative matrix factorization for data representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33, 1548-1560, (2011) |
| [4] | Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, Journal of the ACM, 58, 11, (2011) · Zbl 1327.62369 |
| [5] | Chen, C. F., Wei, C. P., & Wang, Y. C. (2012). Low-rank matrix recovery with structural incoherence for robust face recognition. In Proceedings of IEEE international conference on computer vision and pattern recognition (pp. 2618-2625). |
| [6] | Chen, J., Zhou, J., & Ye, J. (2011). Integrating low-rank and group-sparse structures for robust multi-task learning. In Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (pp. 42-50). |
| [7] | Cheng, B.; Yang, J.; Yan, S.; Fu, Y.; Huang, T. S., Learning with \(\ell_1\)-graph for image analysis, IEEE Transactions on Image Processing, 19, 858-866, (2010) · Zbl 1371.68229 |
| [8] | Elhamifar, E., & Vidal, R. (2009). Sparse subspace clustering. In Proceedings of IEEE international conference on computer vision and pattern recognition (pp.2790-2797). |
| [9] | Elhamifar, E., & Vidal, R. (2011). Sparse manifold clustering and embedding. In Proceedings of advances in neural information processing systems (pp. 55-63). |
| [10] | He, R., Zheng, W. S., Hu, B. G., & Kong, X. W. (2011). Nonnegative sparse coding for discriminative semi-supervised learning. In Proceedings of IEEE international conference on computer vision and pattern recognition (pp. 2849-2856). |
| [11] | Ji, S., & Ye, J. (2009). An accelerated gradient method for trace norm minimization. In Proceedings of international conference on machine learning (pp. 457-464). |
| [12] | Karasuyama, M., & Mamitsuka, H. (2013). Manifold-based similarity adaptation for label propagation. In Proceedings of advances in neural information processing systems (pp. 1547-1555). |
| [13] | Koh, K.; Kim, S.; Boyd, S., \(\ell\)1_ls: A Matlab solver for large-scale \(\ell\)1-regularized least squares problems, (2007), Stanford University |
| [14] | Lee, J. M., Introduction to smooth manifolds, Vol. 218, (2012), Springer |
| [15] | Li, S., & Fu, Y. (2013) Low-rank coding with b-matching constraint for semi-supervised classification. In Proceedings of international joint conference on artificial intelligence (pp. 1472-1478). |
| [16] | Lin, Z., Chen, M., & Ma, Y. (2010). The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv preprint arXiv:1009.5055. |
| [17] | Lin, Z., Liu, R., & Su, Z. (2011). Linearized alternating direction method with adaptive penalty for low-rank representation. In Proceedings of advances in neural information processing systems (pp. 612-620). |
| [18] | 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, 171-184, (2013) |
| [19] | Liu, G., Lin, Z., & Yu, Y. (2010). Robust subspace segmentation by low-rank representation. In Proceedings of international conference on machine learning (pp. 663-670). |
| [20] | Liu, G.; Yan, S., Active subspace: toward scalable low-rank learning, Neural Computation, 24, 3371-3394, (2012) · Zbl 1268.68139 |
| [21] | Lu, C., Feng, J., Lin, Z., & Yan, S. (2013). Correlation adaptive subspace segmentation by trace Lasso. In Proceedings of IEEE international conference on computer vision (pp. 1345-1352). |
| [22] | Lu, X.; Wang, Y.; Yuan, Y., Graph-regularized low-rank representation for destriping of hyperspectral images, IEEE Transactions on Geoscience and Remote Sensing, 15, 4009-4018, (2013) · Zbl 1395.90100 |
| [23] | Lu, J.; Zhou, X.; Tan, Y. P.; Shang, Y.; Zhou, J., Cost-sensitive semi-supervised discriminant analysis for face recognition, IEEE Transactions on Information Forensics and Security, 7, 944-953, (2012) |
| [24] | Luo, D., Nie, F., Ding, C., & Huang, H. (2011). Multi-subspace representation and discovery. In Proceedings of the European conference on machine learning and principles and practice of knowledge discovery in databases (pp. 405-420). |
| [25] | Nie, F.; Xiang, S.; Jia, Y.; Zhang, C., Semi-supervised orthogonal discriminant analysis via label propagation, Pattern Recognition, 42, 2615-2627, (2009) · Zbl 1175.68338 |
| [26] | Nie, F.; Xu, D.; Tsang, I. W.H.; Zhang, C., Flexible manifold embedding: a framework for semi-supervised and unsupervised dimension reduction, IEEE Transactions on Image Processing, 19, 1921-1932, (2010) · Zbl 1371.94276 |
| [27] | Okutomi, M., Yan, S., Sugimoto, S., Liu, G., & Zheng, Y. (2012). Practical low-rank matrix approximation under robust \(\ell_1\)-norm. In Proceedings of IEEE international conference on computer vision and pattern recognition (pp. 1410-1417). |
| [28] | Peng, Y., Wang, S., Wang, S., & Lu, B. L. (2013). Structure preserving low-rank representation for semi-supervised face fecognition. In Proceedings of international conference on neural information processing (pp. 148-155). |
| [29] | Roweis, S. T.; Saul, L. K., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326, (2000) |
| [30] | Shen, B., & Si, L. (2010). Non-negative matrix factorization clustering on multiple manifolds. In Proceedings of AAAI conference on artificial intelligence(pp. 575-580). |
| [31] | Tibshirani, R., Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society. Series B (Methodological), 267-288, (1996) · Zbl 0850.62538 |
| [32] | Wang, F.; Zhang, C., Label propagation through linear neighborhoods, IEEE Transactions on Knowledge and Data Engineering, 20, 55-67, (2008) |
| [33] | Wright, J.; Ma, Y.; Mairal, J.; Sapiro, G.; Huang, T. S.; Yan, S., Sparse representation for computer vision and pattern recognition, Proceedings of IEEE, 98, 1031-1044, (2010) |
| [34] | Xiang, S.; Nie, F.; Zhang, C., Semi-supervised classification via local spline regression, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32, 2039-2053, (2010) |
| [35] | Yan, S., & Wang, H. (2009). Semi-supervised learning by sparse representation. In Proceedings of SIAM international conference on data mining (pp. 792-801). |
| [36] | Yang, Y.; Nie, F.; Xu, D.; Luo, J.; Zhuang, Y.; Pan, Y., A multimedia retrieval framework based on semi-supervised ranking and relevance feedback, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34, 723-742, (2012) |
| [37] | Yang, S.; Wang, X.; Wang, M.; Han, Y.; Jiao, L., Semi-supervised low-rank representation graph for pattern recognition, IET Image Processing, 7, 131-136, (2013) |
| [38] | Yang, J.; Yuan, X., Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Mathematics of Computation, 82, 301-329, (2013) · Zbl 1263.90062 |
| [39] | Yang, A.; Zhou, Z.; Balasubramanian, A.; Sastry, S.; Ma, Y., Fast \(\ell\)1-minimization algorithms for robust face recognition, IEEE Transactions on Image Processing, 22, 3234-3246, (2013) |
| [40] | Yu, K., Zhang, T., & Gong, Y. (2009). Nonlinear learning using local coordinate coding. In Proceedings of advances in neural information processing systems(pp. 2223-2231). |
| [41] | Zhang, T., Ji, R., Liu, W., Tao, D., & Hua, G. (2013). Semi-supervised learning with manifold fitted graphs. In Proceedings of international joint conference on artificial intelligence (pp. 1896-1902). |
| [42] | Zhang, Z. Y.; Zha, H. Y., Principal manifolds and nonlinear dimensionality reduction via tangent space alignment, SIAM Journal on Scientific Computing, 26, 313-338, (2004) · Zbl 1077.65042 |
| [43] | Zheng, M.; Bu, J.; Chen, C.; Wang, C.; Zhang, L.; Qiu, G.; Cai, D., Graph regularized sparse coding for image representation, IEEE Transactions on Image Processing, 20, 1327-1336, (2011) · Zbl 1372.94314 |
| [44] | Zheng, Z., Zhang, H., Jia, J., Zhao, J., Guo, L., Fu, F., & Yu, M. (2013). Low-rank matrix recovery with discriminant regularization. In Proceedings of Pacific-Asia conference on knowledge discovery and data mining (pp. 437-448). |
| [45] | Zheng, Y.; Zhang, X.; Yang, S.; Jiao, L., Low-rank representation with local constraint for graph construction, Neurocomputing, 122, 398-405, (2013) |
| [46] | Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2004). Learning with local and global consistency. In Proceedings of advances in neural information processing systems (pp. 321-328). |
| [47] | Zhu, X., Semi-supervised learning literature survey, technical report, (2008), University of Wisconsin-Madison |
| [48] | 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 Proceedings of IEEE international conference on computer vision and pattern recognition(pp. 2328-2335). |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
