A NEW MODEL FOR SPARSE AND LOW-RANK MATRIX DECOMPOSITION

Zisheng Liu; Jicheng Li; Guo Li; Jianchao Bai; Xuenian Liu

doi:10.11948/2017037

2017 Volume 7 Issue 2

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2017 > 7(2): 600-616

Next Article Previous Article

Zisheng Liu, Jicheng Li, Guo Li, Jianchao Bai, Xuenian Liu. A NEW MODEL FOR SPARSE AND LOW-RANK MATRIX DECOMPOSITION[J]. Journal of Applied Analysis & Computation, 2017, 7(2): 600-616. doi: 10.11948/2017037

Citation:

Zisheng Liu, Jicheng Li, Guo Li, Jianchao Bai, Xuenian Liu. A NEW MODEL FOR SPARSE AND LOW-RANK MATRIX DECOMPOSITION[J]. Journal of Applied Analysis & Computation, 2017, 7(2): 600-616. doi: 10.11948/2017037

A NEW MODEL FOR SPARSE AND LOW-RANK MATRIX DECOMPOSITION

1 School of Mathematics and Statistics, Xi'an Jiaotong University, 710049, Xi'an, China;
2 College of Mathematics and Statistics, Shenzhen University, 518060, Shenzhen, China

Fund Project:

Abstract

Abstract

The robust principal component analysis (RPCA) model is a popular method for solving problems with the nuclear norm and l₁ norm. However, it is time-consuming since in general one has to use the singular value decomposition in each iteration. In this paper, we introduce a novel model to reformulate the existed model by making use of low-rank matrix factorization to surrogate the nuclear norm for the sparse and low-rank decomposition problem. In such case we apply the Penalty Function Method (PFM) and Augmented Lagrangian Multipliers Method (ALMM) to solve this new nonconvex optimization problem. Theoretically, corresponding to our methods, the convergence analysis is given respectively. Compared with classical RPCA, some practical numerical examples are simulated to show that our methods are much better than RPCA.
- Robust principal component analysis /
- sparse matrix /
- low-rank matrix /
- nuclear norm /
- matrix decomposition
MSC: 15A23;65K05;90C22

FullText(HTML)

References

[1]	A. Argyriou, T. Evgeniou and M. Pontil, Multi-task feature learning, Adv. Neural Inform. Process. Syst., 2007, 19, 41-48. Google Scholar
[2]	J. Abernethy, F. Bach, T. Evgeniou and J. P. Vert, Low-rank Matrix Factorization with Attributes, Arxiv preprint cs/0611124, 2006. Google Scholar
[3]	Y. Amit, M. Fink, N. Srebro and S. Ullman, Uncovering shared structures in multiclass classification, in Proceedings of the 24th International Conference on Machine Learning, ACM, Providence, RI, 2007, 17-24. Google Scholar
[4]	J-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrxi completion, SIAM J. Optim., 2010, 20(4), 1956-1982. Google Scholar
[5]	E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis? Journal of the ACM, 2011, 58(3), 1-37. Google Scholar
[6]	E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 2009, 9(6), 717-772. Google Scholar
[7]	V. Chandrasekaran, S. Sanghavi, P. A. Parrilo and A. S. Willskyc, Ranksparsity incoherence for matrix decomposition, SIAM J. Optim., 2011, 21(2), 572-596. Google Scholar
[8]	P. Chen and D. Suter, Recovering the missing components in a large noisy low-rank matrix:Application to SFM, IEEE Trans. Pattern Anal. Machine Intelligence, 2004, 26(8), 1051-1063. Google Scholar
[9]	G. Chen and M. Teboulle, A proximal-based decomposition method for convex minimization problems, Math. Program., 1994, 64, 81-101. Google Scholar
[10]	L. Cheng, M. Gong, D. Schuurmans and T. Caelli, Real-time discriminative background subtraction, IEEE Trans. Image Process., 2011, 20(5), 1401-1414. Google Scholar
[11]	S. Deerwester, S. T. Dumains, T. Landauer, G. Furnas and R. Harshman, Indexing by latent semantic analysis, J. Soc. Inf. Sci., 1990, 41(6), 391-407. Google Scholar
[12]	C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika, 1936, 1(3), 211-218. Google Scholar
[13]	E. Esser, Applications of Lagrangian-based Alternating Direction Methods and Connections to Split Bregman, CAM report, 2009. Google Scholar
[14]	R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1984. Google Scholar
[15]	R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, volume 9 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. Google Scholar
[16]	I. Jolliffe, Principal Component Analysis, Springer-Verlag, 1986. Google Scholar
[17]	S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 2011, 128(1), 321-353. Google Scholar
[18]	M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinitelinear matrix inequality, IEEE Trans. Automat. Control, 1997, 42, 239-243. Google Scholar
[19]	C. Papadimitriou, P. Raghavan, H. Tamaki and S. Vempala, Latent semantic indexing, a probabilistic analysis, J. Comput. Syst. Sci., 2000, 61(2), 217-235. Google Scholar
[20]	B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 2010, 52(3), 471-501. Google Scholar
[21]	C. Tomasi and T. Kanade, Shape and motion from image streams under orthography:A factorization method, Int. J. Comput. Vision, 1992, 9, 137-154. Google Scholar
[22]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 1996, 38, 49-95. Google Scholar
[23]	G. A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 1992, 170, 1039-1053. Google Scholar
[24]	J. Wright, A. Ganesh, S. Rao, Y. Peng and Y. Ma, Robust principal component analysis:Exact recovery of corrupted low-rank matrices via convex optimization, Twenty-Third Annual Conference on Neural Information Processing Systems (NIPS 2009), 12/2009. Google Scholar
[25]	X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pacific Journal of Optimization, 2013, 9(1), 167-180. Google Scholar