Accelerated matrix recovery via random projection based on inexact augmented Lagrange multiplier method

Abstract

In this paper, a unified matrix recovery model was proposed for diverse corrupted matrices. Resulting from the separable structure of the proposed model, the convex optimization problem can be solved efficiently by adopting an inexact augmented Lagrange multiplier (IALM) method. Additionally, a random projection accelerated technique (IALM+RP) was adopted to improve the success rate. From the preliminary numerical comparisons, it was indicated that for the standard robust principal component analysis (PCA) problem, IALM+RP was at least two to six times faster than IALM with an insignificant reduction in accuracy; and for the outlier pursuit (OP) problem, IALM+RP was at least 6.9 times faster, even up to 8.3 times faster when the size of matrix was 2 000×2 000.

Keywords

matrix recovery / random projection / robust principal component analysis / matrix completion / outlier pursuit / inexact augmented Lagrange multiplier method

References

[1] Candès E J, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[2] Zhang C J, Liu J, Tian Q, et al. Image classification by nonnegative sparse coding, low-rank and sparse decomposition[C]. International Conference on Computer Vision and Pattern Recognition, 2011

[3] Ji H, Huang S B, Shen Z W, et al. Robust video restoration by joint sparse and low rank matrix approximation[J]. SIAM Journal on Imaging Sciences, 2011, 4(4): 1122 1142

[4] Eckart C, Young G. The approximation of one matrix by another of lower rank[J]. Psychometrika, 1936, 1(3): 211-218.

[5] Jolliffe I T. Principal Component Analysis[M]. 1986, New York, USA: Springer-Verlag.

[6] Wright J, Ganesh A, Rao S, et al. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[C]. Neural Information Processing Systems, 2009, Canada: Vancouver and Whistler.

[7] Candès E J, Li X D, Ma Y, et al. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3): 1-37.

[8] Ganesh A, Wright J, Li X D, et al. Dense error correction for low-rank matrices via principal component pursuit[C]. IEEE International Symposium on Information Theory, 2010

[9] Xu H, Caramanis C, Sanghavi S. Robust PCA via outlier pursuit[J]. IEEE Transactions on Information Theory, 2012, 58(5): 3047 3064

[10] Toh K C, Yun S W. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems[J]. Pacific Journal of Optimization, 2010, 6(3): 615-640.

[11] Wright J, Ganesh A, Min K, et al. Compressive principal component pursuit[C]. IEEE International Symposium on Information Theory, 2012

[12] Waters A E, Sankaranarayanan A C, Baraniuk R G. SpaRCS: Recovering low-rank and sparse matrices from compressive measurements[C]. Neural Information Processing Systems (NIPS), 2011

[13] Ganesh A, Min K, Wright J, et al. Principal component pursuit with reduced linear measurements[C]. IEEE International Symposium on Information Theory, 2012

[14] Mu Y D, Dong J, Yuan X T, et al. Accelerated low-rank visual recovery by random projection[C]. International Conference on Computer Vision and Pattern Recognition, 2011

[15] Cai J F, Candès E J, Shen Z W. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956 1982

[16] Fazel M. Matrix Rank Minimization with Applications[D]. 2002

[17] Candès E J, Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717 772

[18] Lin Z C, Chen M M, Ma Y. The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Lowrank Matrices[R]. 2009

[19] Hestenes M R. Multiplier and gradient methods[J]. Journal of Optimization Theory and Applications, 1969, 4(5): 303 320

[20] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite-element approximation[J]. Computers and Mathematics with Applications, 1976, 2(1): 17-40.

[21] Yuan X M, Yang J F. Low-rank and sparse matrix decomposition via alternating direction methods[J]. Pacific Journal of Optimization, 2013, 9(1): 167-180.

[22] He B S, Yang H. Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities[J]. Operations Research Letters, 1998, 23(3–5): 151 161

[23] Kontogiorgis S, Meyer R R. A variable-penalty alternating directions method for convex optimization[J]. Mathematical Programming, 1998, 83(1–3): 29-53.

[24] Goldfarb D, Ma S Q. Convergence of fixed point continuation algorithms for matrix rank minimization[J]. Foundations of Computational Mathematics, 2011, 11(2): 183 210

[25] Papadimitriou C H, Raghavan P, Tamaki H, et al. Latent semantic indexing: A probabilistic analysis[J]. Journal of Computer and System Sciences, 2000, 61(2): 217 235

[26] Vempala S S. The Random Projection Method[M]. 2004, USA: American Mathematical Society.