A Review on Low-Rank Models in Data Analysis

Zhouchen Lin; Zhouchen Lin

doi:10.3934/bdia.2016001

Big Data and Information Analytics

2016, Volume 1, Issue 2&3: 139-161. doi: 10.3934/bdia.2016001

Previous Article Next Article

A Review on Low-Rank Models in Data Analysis

Zhouchen Lin ^{1,2
,}

1.
Key Lab. of Machine Perception (MOE), School of EECS, Peking University, Beijing, China
2.
Cooperative Medianet Innovation Center, Shanghai Jiao Tong University, Shanghai, China

Received: 01 May 2015 Revised: 01 January 2016 Published: 01 July 2016
Primary: 62H30, 62-07, 68T10; Secondary: 90C25, 90C26, 15A83, 15A23

Nowadays we are in the big data era. The high-dimensionality of data imposes big challenge on how to process them effectively and efficiently. Fortunately, in practice data are not unstructured. Their samples usually lie around low-dimensional manifolds and have high correlation among them. Such characteristics can be effectively depicted by low rankness. As an extension to the sparsity of first order data, such as voices, low rankness is also an effective measure for the sparsity of second order data, such as images. In this paper, I review the representative theories, algorithms and applications of the low rank subspace recovery models in data processing.
- Sparsity,
- low-rankness,
- subspace recovery,
- subspace clustering,
- lowrank optimization
Citation: Zhouchen Lin. 2016: A Review on Low-Rank Models in Data Analysis, Big Data and Information Analytics, 1(2&3): 139-161. doi: 10.3934/bdia.2016001

Related Papers:

Abstract

Nowadays we are in the big data era. The high-dimensionality of data imposes big challenge on how to process them effectively and efficiently. Fortunately, in practice data are not unstructured. Their samples usually lie around low-dimensional manifolds and have high correlation among them. Such characteristics can be effectively depicted by low rankness. As an extension to the sparsity of first order data, such as voices, low rankness is also an effective measure for the sparsity of second order data, such as images. In this paper, I review the representative theories, algorithms and applications of the low rank subspace recovery models in data processing.

References

[1]	Adler A., Elad M., Hel-Or Y. (2013) Probabilistic subspace clustering via sparse representations. IEEE Signal Processing Letters 20: 63-66.
[2]	Beck A., Teboulle M. (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2: 183-202.
[3]	Cai J., Candès E., Shen Z. (2010) A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization 20: 1956-1982.
[4]	E. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis? Journal of the ACM, 58 (2011), Art. 11, 37 pp. 10.1145/1970392.1970395 MR2811000
[5]	Candès E., Plan Y. (2010) Matrix completion with noise. Proceedings of the IEEE 98: 925-936.
[6]	Candès E., Recht B. (2009) Exact matrix completion via convex optimization. Foundations of Computational Mathematics 9: 717-772.
[7]	V. Chandrasekaran, S. Sanghavi, P. Parrilo and A. Willsky, Sparse and low-rank matrix decompositions, Annual Allerton Conference on Communication, Control, and Computing, 2009, 962–967.
[8]	Chen C., He B., Ye Y., Yuan X. (2016) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Mathematical Programming 155: 57-79.
[9]	Y. Chen, H. Xu, C. Caramanis and S. Sanghavi, Robust matrix completion with corrupted columns, International Conference on Machine Learning, 2011, 873–880.
[10]	Cheng B., Liu G., Wang J., Huang Z., Yan S. (2011) Multi-task low-rank affinity pursuit for image segmentation. International Conference on Computer Vision : 2439-2446.
[11]	A. Cichocki, R. Zdunek, A. H. Phan and S. Ichi Amari, Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation, 1st edition, Wiley, 2009. 10.1002/9780470747278
[12]	Y. Cui, C.-H. Zheng and J. Yang, Identifying subspace gene clusters from microarray data using low-rank representation, PLoS One, 8 (2013), e59377. 10.1371/journal.pone.0059377
[13]	Drineas P., Kannan R., Mahoney M. (2006) Fast Monte Carlo algorithms for matrices Ⅱ: Computing a low rank approximation to a matrix. SIAM Journal on Computing 36: 158-183.
[14]	E. Elhamifar and R. Vidal, Sparse subspace clustering, in IEEE International Conference on Computer Vision and Pattern Recognition, 2009, 2790–2797. 10.1109/CVPR.2009.5206547
[15]	Elhamifar E., Vidal R. (2013) Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence 35: 2765-2781.
[16]	Favaro P., Vidal R., Ravichandran A. (2011) A closed form solution to robust subspace estimation and clustering. IEEE Conference on Computer Vision and Pattern Recognition : 1801-1807.
[17]	Feng J., Lin Z., Xu H., Yan S. (2014) Robust subspace segmentation with block-diagonal prior. IEEE Conference on Computer Vision and Pattern Recognition : 3818-3825.
[18]	Frank M., Wolfe P. (1956) An algorithm for quadratic programming. Naval Research Logistics Quarterly 3: 95-110.
[19]	Fu Y., Gao J., Tien D., Lin Z. (2014) Tensor LRR based subspace clustering. International Joint Conference on Neural Networks : 1877-1884.
[20]	Ganesh A., Lin Z., Wright J., Wu L., Chen M., Ma Y. (2009) Fast algorithms for recovering a corrupted low-rank matrix. International Workshop on Computational Advances in MultiSensor Adaptive Processing : 213-216.
[21]	Gao H., Cai J.-F., Shen Z., Zhao H. (2011) Robust principal component analysis-based four-dimensional computed tomography. Physics in Medicine and Biology 56: 3181-3198.
[22]	M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming (web page and software), http://cvxr.com/cvx/, 2009.
[23]	Gu S., Zhang L., Zuo W., Feng X. (2014) Weighted nuclear norm minimization with application to image denoising. IEEE Conference on Computer Vision and Pattern Recognition : 2862-2869.
[24]	Hu H., Lin Z., Feng J., Zhou J. (2014) Smooth representation clustering. IEEE Conference on Computer Vision and Pattern Recognition : 3834-3841.
[25]	Hu Y., Zhang D., Ye J., Li X., He X. (2013) Fast and accurate matrix completion via truncated nuclear norm regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence 35: 2117-2130.
[26]	M. Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization, in International Conference on Machine Learning, 2013, 427–435.
[27]	M. Jaggi and M. Sulovský, A simple algorithm for nuclear norm regularized problems, in International Conference on Machine Learning, 2010, 471–478.
[28]	Jhuo I., Liu D., Lee D., Chang S. (2012) Robust visual domain adaptation with low-rank reconstruction. IEEE Conference on Computer Vision and Pattern Recognition : 2168-2175.
[29]	Ji H., Liu C., Shen Z., Xu Y. (2010) Robust video denoising using low rank matrix completion. IEEE Conference on Computer Vision and Pattern Recognition : 1791-1798.
[30]	Jin Y., Wu Q., Liu L. (2012) Unsupervised upright orientation of man-made models. Graphical Models 74: 99-108.
[31]	Kolda T. G., Bader B. W. (2009) Tensor decompositions and applications. SIAM Review 51: 455-500.
[32]	Lang C., Liu G., Yu J., Yan S. (2012) Saliency detection by multitask sparsity pursuit. IEEE Transactions on Image Processing 21: 1327-1338.
[33]	R. M. Larsen, http://sun.stanford.edu/~rmunk/PROPACK/, 2004.
[34]	D. Lee and H. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), 788.
[35]	Liang X., Ren X., Zhang Z., Ma Y. (2012) Repairing sparse low-rank texture. European Conference on Computer Vision 7576: 482-495.
[36]	Lin Z., Liu R., Li H. (2015) Linearized alternating direction method with parallel splitting and adaptive penality for separable convex programs in machine learning. Machine Learning 99: 287-325.
[37]	Lin Z., Liu R., Su Z. (2011) Linearized alternating direction method with adaptive penalty for low-rank representation. Advances in Neural Information Processing Systems : 612-620.
[38]	Liu G., Lin Z., Yan S., Sun J., Ma Y. (2013) Robust recovery of subspace structures by low-rank representation. IEEE Transactions Pattern Analysis and Machine Intelligence 35: 171-184.
[39]	G. Liu, Z. Lin and Y. Yu, Robust subspace segmentation by low-rank representation, in International Conference on Machine Learning, 2010, 663–670.
[40]	G. Liu, H. Xu and S. Yan, Exact subspace segmentation and outlier detection by low-rank representation, International Conference on Artificial Intelligence and Statistics, 2012, 703– 711.
[41]	G. Liu and S. Yan, Latent low-rank representation for subspace segmentation and feature extraction, in IEEE International Conference on Computer Vision, IEEE, 2011, 1615–1622. 10.1109/ICCV.2011.6126422
[42]	Liu J., Musialski P., Wonka P., Ye J. (2013) Tensor completion for estimating missing values in visual data. IEEE Transactions on Pattern Analysis and Machine Intelligence 35: 208-220.
[43]	Liu R., Lin Z., Su Z., Gao J. (2014) Linear time principal component pursuit and its extensions using $\ell_1$ filtering. Neurocomputing 142: 529-541.
[44]	Liu R., Lin Z., Torre F., Su Z. (2012) Fixed-rank representation for unsupervised visual learning. IEEE Conference on Computer Vision and Pattern Recognition : 598-605.
[45]	Lu C., Feng J., Lin Z., Yan S. (2013) Correlation adaptive subspace segmentation by trace lasso. International Conference on Computer Vision : 1345-1352.
[46]	Lu C., Lin Z., Yan S. (2015) Smoothed low rank and sparse matrix recovery by iteratively reweighted least squared minimization. IEEE Transactions on Image Processing 24: 646-654.
[47]	Lu C., Min H., Zhao Z., Zhu L., Huang D., Yan S. (2012) Robust and efficient subspace segmentation via least squares regression. European Conference on Computer Vision 7578: 347-360.
[48]	Lu C., Zhu C., Xu C., Yan S., Lin Z. (2015) Generalized singular value thresholding. AAAI Conference on Artificial Intelligence : 1805-1811.
[49]	Lu X., Wang Y., Yuan Y. (2013) Graph-regularized low-rank representation for destriping of hyperspectral images. IEEE Transactions on Geoscience and Remote Sensing 51: 4009-4018.
[50]	Y. Ma, S. Soatto, J. Kosecka and S. Sastry, An Invitation to 3-D Vision: From Images to Geometric Models, 1st edition, Springer, 2004. 10.1007/978-0-387-21779-6 MR2015496
[51]	K. Min, Z. Zhang, J. Wright and Y. Ma, Decomposing background topics from keywords by principal component pursuit, in ACM International Conference on Information and Knowledge Management, 2010, 269–278. 10.1145/1871437.1871475
[52]	Ming Y., Ruan Q. (2012) Robust sparse bounding sphere for 3D face recognition. Image and Vision Computing 30: 524-534.
[53]	Mukherjee L., Singh V., Xu J., Collins M. (2012) Analyzing the subspace structure of related images: Concurrent segmentation of image sets. European Conference on Computer Vision 7575: 128-142.
[54]	Nesterov Y. (1983) A method of solving a convex programming problem with convergence rate O$(1/k^2)$. (Russian) Dokl. Akad. Nauk SSSR 269: 543-547.
[55]	Panagakis Y., Kotropoulos C. (2012) Automatic music tagging by low-rank representation. International Conference on Acoustics, Speech, and Signal Processing : 497-500.
[56]	Peng Y., Ganesh A., Wright J., Xu W., Ma Y. (2012) RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Transactions on Pattern Analysis and Machine Intelligence 34: 2233-2246.
[57]	Qian J., Yang J., Zhang F., Lin Z. (2014) Robust low-rank regularized regression for face recognition with occlusion. The Workshop of IEEE Conference on Computer Vision and Pattern Recognition : 21-26.
[58]	Ren X., Lin Z. (2013) Linearized alternating direction method with adaptive penalty and warm starts for fast solving transform invariant low-rank textures. International Journal of Computer Vision 104: 1-14.
[59]	Singh A. P., Gordon G. J. (2008) A unified view of matrix factorization models. Proceedings of Machine Learning and Knowledge Discovery in Databases 5212: 358-373.
[60]	H. Tan, J. Feng, G. Feng, W. Wang and Y. Zhang, Traffic volume data outlier recovery via tensor model, Mathematical Problems in Engineering, 2013 (2013), 164810. 10.1155/2013/164810
[61]	Tso M. (1981) Reduced-rank regression and canonical analysis. Journal of the Royal Statistical Society, Series B (Methodological) 43: 183-189.
[62]	Vidal R., Ma Y., Sastry S. (2005) Generalized principal component analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence 27: 1945-1959.
[63]	Vidal R. (2011) Subspace clustering. IEEE Signal Processing Magazine 28: 52-68.
[64]	Wang J., Saligrama V., Castanon D. (2011) Structural similarity and distance in learning. Annual Allerton Conf. Communication, Control and Computing : 744-751.
[65]	Wang Y.-X., Zhang Y.-J. (2013) Nonnegative matrix factorization: A comprehensive review. IEEE Transactions on Knowledge and Data Engineering 25: 1336-1353.
[66]	S. Wei and Z. Lin, Analysis and improvement of low rank representation for subspace segmentation, arXiv: 1107.1561.
[67]	Wen Z., Yin W., Zhang Y. (2012) Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Mathematical Programming Computation 4: 333-361.
[68]	Wright J., Ganesh A., Rao S., Peng Y., Ma Y. (2009) Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Advances in Neural Information Processing Systems : 2080-2088.
[69]	Wu L., Ganesh A., Shi B., Matsushita Y., Wang Y., Ma Y. (2010) Robust photometric stereo via low-rank matrix completion and recovery. Asian Conference on Computer Vision : 703-717.
[70]	Yang L., Lin Y., Lin Z., Zha H. (2014) Low rank global geometric consistency for partial-duplicate image search. International Conference on Pattern Recognition : 3939-3944.
[71]	Yin M., Gao J., Lin Z. (2016) Laplacian regularized low-rank representation and its applications. IEEE Transactions on Pattern Analysis and Machine Intelligence 38: 504-517.
[72]	Yu Y., Schuurmans D. (2011) Rank/norm regularization with closed-form solutions: Application to subspace clustering. Uncertainty in Artificial Intelligence : 778-785.
[73]	Zhang H., Lin Z., Zhang C. (2013) A counterexample for the validity of using nuclear norm as a convex surrogate of rank. European Conference on Machine Learning 8189: 226-241.
[74]	Zhang H., Lin Z., Zhang C., Chang E. (2015) Exact recoverability of robust {PCA} via outlier pursuit with tight recovery bounds. AAAI Conference on Artificial Intelligence : 3143-3149.
[75]	Zhang H., Lin Z., Zhang C., Gao J. (2014) Robust latent low rank representation for subspace clustering. Neurocomputing 145: 369-373.
[76]	Zhang H., Lin Z., Zhang C., Gao J. (2015) Relation among some low rank subspace recovery models. Neural Computation 27: 1915-1950.
[77]	Zhang T., Ghanem B., Liu S., Ahuja N. (2012) Low-rank sparse learning for robust visual tracking. European Conference on Computer Vision 7577: 470-484.
[78]	Zhang Z., Ganesh A., Liang X., Ma Y. (2012) TILT: Transform invariant low-rank textures. International Journal of Computer Vision 99: 1-24.
[79]	Zhang Z., Liang X., Ma Y. (2011) Unwrapping low-rank textures on generalized cylindrical surfaces. International Conference on Computer Vision : 1347-1354.
[80]	Zhang Z., Matsushita Y., Ma Y. (2011) Camera calibration with lens distortion from low-rank textures. IEEE Conference on Computer Vision and Pattern Recognition : 2321-2328.
[81]	Zheng Y., Zhang X., Yang S., Jiao L. (2013) Low-rank representation with local constraint for graph construction. Neurocomputing 122: 398-405.
[82]	X. Zhou, C. Yang, H. Zhao and W. Yu, Low-rank modeling and its applications in image analysis, ACM Computing Surveys, 47 (2014), p36. 10.1145/2674559
[83]	G. Zhu, S. Yan and Y. Ma, Image tag refinement towards low-rank, content-tag prior and error sparsity, in International conference on Multimedia, 2010, 461–470. 10.1145/1873951.1874028
[84]	Zhuang L., Gao H., Lin Z., Ma Y., Zhang X., Yu N. (2012) Non-negative low rank and sparse graph for semi-supervised learning. IEEE International Conference on Computer Vision and Pattern Recognition : 2328-2335.
[85]	Zuo W., Lin Z. (2011) A generalized accelerated proximal gradient approach for total-variation-based image restoration. IEEE Transactions on Image Processing 20: 2748-2759.

Reader Comments

Your name:*

Email:*
© 2016 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)