×

Recovering low-rank and sparse matrix based on the truncated nuclear norm. (English) Zbl 1428.68231

Summary: Recovering the low-rank, sparse components of a given matrix is a challenging problem that arises in many real applications. Existing traditional approaches aimed at solving this problem are usually recast as a general approximation problem of a low-rank matrix. These approaches are based on the nuclear norm of the matrix, and thus in practice the rank may not be well approximated. This paper presents a new approach to solve this problem that is based on a new norm of a matrix, called the truncated nuclear norm (TNN). An efficient iterative scheme developed under the linearized alternating direction method multiple framework is proposed, where two novel iterative algorithms are designed to recover the sparse and low-rank components of matrix. More importantly, the convergence of the linearized alternating direction method multiple on our matrix recovering model is discussed and proved mathematically. To validate the effectiveness of the proposed methods, a series of comparative trials are performed on a variety of synthetic data sets. More specifically, the new methods are used to deal with problems associated with background subtraction (foreground object detection), and removing shadows and peculiarities from images of faces. Our experimental results illustrate that our new frameworks are more effective and accurate when compared with other methods.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
15A23 Factorization of matrices
62H25 Factor analysis and principal components; correspondence analysis
68T45 Machine vision and scene understanding
68U10 Computing methodologies for image processing

Software:

RASL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2, 1, 183-202 (2009) · Zbl 1175.94009
[2] Bertsekas, D. P., Constrained optimization and Lagrange multiplier methods (2014), Academic Press
[3] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3, 1, 1-122 (2011) · Zbl 1229.90122
[4] Cai, J.-F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 4, 1956-1982 (2010) · Zbl 1201.90155
[5] Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, Journal of the ACM, 58, 3, 11 (2011) · Zbl 1327.62369
[6] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9, 6, 717-772 (2009) · Zbl 1219.90124
[7] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[8] Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Transactions on Information Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[9] Candès, E. J.; Tao, T., The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56, 5, 2053-2080 (2010) · Zbl 1366.15021
[10] Cao, F.; Cai, M.; Tan, Y., Image interpolation via low-rank matrix completion and recovery, IEEE Transactions on Circuits and Systems for Video Technology, 25, 8, 1261-1270 (2015)
[11] Chandrasekaran, V.; Sanghavi, S.; Parrilo, P. A.; Willsky, A. S., Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, 21, 2, 572-596 (2011) · Zbl 1226.90067
[12] Combettes, P. L.; Wajs, V. R., Signal recovery by proximal forward-backward splitting, Multiscale Modeling and Simulation, 4, 4, 1168-1200 (2005) · Zbl 1179.94031
[13] Ding, X.; He, L.; Carin, L., Bayesian robust principal component analysis, IEEE Transactions on Image Processing, 20, 12, 3419-3430 (2011) · Zbl 1381.62144
[14] Fazel, M., Matrix rank minimization with applications (2002), Stanford University, (Ph.D. thesis)
[15] Ganesh, A.; Wright, J.; Li, X.; Candès, E. J.; Ma, Y., Dense error correction for low-rank matrices via principal component pursuit, (2010 IEEE international symposium on information theory (2010), IEEE), 1513-1517
[16] Hu, Y.; Zhang, D.; Ye, J.; Li, X.; He, X., Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 9, 2117-2130 (2013)
[17] Li, L.; Huang, W.; Gu, I. Y.-H.; Tian, Q., Statistical modeling of complex backgrounds for foreground object detection, IEEE Transactions on Image Processing, 13, 11, 1459-1472 (2004)
[20] Liu, Y.; Jiao, L.; Shang, F.; Yin, F.; Liu, F., An efficient matrix bi-factorization alternative optimization method for low-rank matrix recovery and completion, Neural Networks, 48, 8-18 (2013) · Zbl 1297.65048
[21] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and bregman iterative methods for matrix rank minimization, Mathematical Programming, 128, 1-2, 321-353 (2011) · Zbl 1221.65146
[22] Mu, Y.; Dong, J.; Yuan, X.; Yan, S., Accelerated low-rank visual recovery by random projection, (2011 IEEE conference on computer vision and pattern recognition (CVPR) (2011), IEEE), 2609-2616
[23] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24, 2, 227-234 (1995) · Zbl 0827.68054
[25] Peng, Y.; Ganesh, A.; Wright, J.; Xu, W.; Ma, Y., Rasl: Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34, 11, 2233-2246 (2012)
[26] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52, 3, 471-501 (2010) · Zbl 1198.90321
[27] Rockafellar, R. T., Convex analysis (2015), Princeton University Press
[28] Toh, K.-C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6, 15, 615-640 (2010) · Zbl 1205.90218
[30] Yang, A. Y.; Sastry, S. S.; Ganesh, A.; Ma, Y., Fast \(\ell_1\)-minimization algorithms and an application in robust face recognition: A review, (2010 IEEE international conference on image processing (2010), IEEE), 1849-1852
[32] Zhang, Z.; Ganesh, A.; Liang, X.; Ma, Y., Tilt: Transform invariant low-rank textures, International Journal of Computer Vision, 99, 1, 1-24 (2012) · Zbl 1254.68290
[33] Zhang, D.; Hu, Y.; Ye, J.; Li, X.; He, X., Matrix completion by truncated nuclear norm regularization, (2012 IEEE conference on computer vision and pattern recognition (CVPR) (2012), IEEE), 2192-2199
[34] Zhou, Z.; Li, X.; Wright, J.; Candès, E.; Ma, Y., Stable principal component pursuit, (2010 IEEE international symposium on information theory (2010), IEEE), 1518-1522
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.