LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM

Peng Wang; Chengde Lin; Xiaobo Yang; Shengwu Xiong

doi:10.11948/20190182

2020 Volume 10 Issue 3

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2020 > 10(3): 1024-1037

Next Article Previous Article

Peng Wang, Chengde Lin, Xiaobo Yang, Shengwu Xiong. LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM[J]. Journal of Applied Analysis & Computation, 2020, 10(3): 1024-1037. doi: 10.11948/20190182

Citation:

Peng Wang, Chengde Lin, Xiaobo Yang, Shengwu Xiong. LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM[J]. Journal of Applied Analysis & Computation, 2020, 10(3): 1024-1037. doi: 10.11948/20190182

LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM

1.
School of Computer Science and Technology, Wuhan University of Technology, Wuhan 430070, China
2.
School of Mathematics and Computational Science, Wuyi University, Jiangmen 529020, China
3.
Henan Branch of China Development Bank, Zhengzhou 450008, China

Corresponding authors: Email address:p_wong@126.com(P. Wang); Email address:swxiong@whut.edu.cn(S. Xiong)

Abstract

Abstract

Recovering low-rank and sparse matrix from a given matrix arises in many applications, such as image processing, video background substraction, and so on. The 3-block alternating direction method of multipliers (ADMM) has been applied successfully to solve convex problems with 3-block variables. However, the existing sufficient conditions to guarantee the convergence of the 3-block ADMM usually require the penalty parameter $ \gamma $ to satisfy a certain bound, which may affect the performance of solving the large scale problem in practice. In this paper, we propose the 3-block ADMM to recover low-rank and sparse matrix from noisy observations. In theory, we prove that the 3-block ADMM is convergent when the penalty parameters satisfy a certain condition and the objective function value sequences generated by 3-block ADMM converge to the optimal value. Numerical experiments verify that proposed method can achieve higher performance than existing methods in terms of both efficiency and accuracy.
- Low-rank /
- sparse /
- nuclear norm minimization /
- ℓ₁-norm minimization /
- 3-block alternating direction method
MSC: 49, 04

FullText(HTML)

References

[1]	S. Boyd, N. Parikh, E. Chu et al., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends ® in Machine learning, 2011, 3(1), 1–122. Google Scholar
[2]	J.-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 2010, 20(4), 1956–1982. doi: 10.1137/080738970 CrossRef Google Scholar
[3]	E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of the ACM (JACM), 2011, 58(3), 11. Google Scholar
[4]	V. Chandrasekaran, S. Sanghavi, P. A. Parrilo and A. S. Willsky, Rank-sparsity incoherence for matrix decomposition, SIAM Journal on Optimization, 2011, 21(2), 572–596. Google Scholar
[5]	R. Chartrand, Nonconvex splitting for regularized low-rank+ sparse decomposition, IEEE Transactions on Signal Processing, 2012, 60(11), 5810–5819. doi: 10.1109/TSP.2012.2208955 CrossRef Google Scholar
[6]	C. Chen, B. He, Y. Ye and X. Yuan, The direct extension of ADMM for multiblock convex minimization problems is not necessarily convergent, Mathematical Programming, 2016, 155(1-2), 57–79. doi: 10.1007/s10107-014-0826-5 CrossRef Google Scholar
[7]	J. Eckstein and D. P. Bertsekas, On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 1992, 55(1-3), 293–318. doi: 10.1007/BF01581204 CrossRef Google Scholar
[8]	M. Fazel, Matrix rank minimization with applications, Ph.D. thesis, Doctoral dissertation, Stanford University, 2002. Google Scholar
[9]	D. Han and X. Yuan, A note on the alternating direction method of multipliers, Journal of Optimization Theory and Applications, 2012, 155(1), 227–238. Google Scholar
[10]	B. He and X. Yuan, On the O(1/n) convergence rate of the douglas–rachford alternating direction method, SIAM Journal on Numerical Analysis, 2012, 50(2), 700–709. Google Scholar
[11]	Y. Hu, X. Liu and M. Jacob, A generalized structured low-rank matrix completion algorithm for MR image recovery, IEEE Transactions on Medical Imaging, 2019, 38(8), 1841–1851. doi: 10.1109/TMI.2018.2886290 CrossRef Google Scholar
[12]	S. Javed, A. Mahmood, T. Bouwmans and S. K. Jung, Spatiotemporal lowrank modeling for complex scene background initialization, IEEE Transactions on Circuits and Systems for Video Technology, 2018, 28(6), 1315–1329. doi: 10.1109/TCSVT.2016.2632302 CrossRef Google Scholar
[13]	H. Ji, S. Huang, Z. Shen and Y. Xu, Robust video restoration by joint sparse and low rank matrix approximation, SIAM Journal on Imaging Sciences, 2011, 4(4), 1122–1142. doi: 10.1137/100817206 CrossRef Google Scholar
[14]	M. Li, D. Sun and K.-C. Toh, A convergent 3-block semi-proximal admm for convex minimization problems with one strongly convex block, Asia-Pacific Journal of Operational Research, 2015, 32(04), 1550024. doi: 10.1142/S0217595915500244 CrossRef Google Scholar
[15]	T. Lin, S. Ma and S. Zhang, Global convergence of unmodified 3-block admm for a class of convex minimization problems, Journal of Scientific Computing, 2018, 76(1), 69–88. doi: 10.1007/s10915-017-0612-7 CrossRef Google Scholar
[16]	P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 1979, 16(6), 964–979. Google Scholar
[17]	R. D. Monteiro and B. F. Svaiter, Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers, SIAM Journal on Optimization, 2013, 23(1), 475–507. Google Scholar
[18]	M. Tao and X. Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM Journal on Optimization, 2011, 21(1), 57–81. Google Scholar
[19]	J. J. Wang and W. Song, An algorithm twisted from generalized admm for multi-block separable convex minimization models, Journal of Computational and Applied Mathematics, 2017, 309, 342–358. doi: 10.1016/j.cam.2016.02.001 CrossRef Google Scholar
[20]	J. Wright, A. Y. Yang, A. Ganesh et al., Robust face recognition via sparse representation, IEEE transactions on pattern analysis and machine intelligence, 2009, 31(2), 210–227. doi: 10.1109/TPAMI.2008.79 CrossRef Google Scholar
[21]	S. Yang, L. Zhang, L. He and Y. Wen, Sparse low-rank component-based representation for face recognition with low-quality images, IEEE Transactions on Information Forensics and Security, 2019, 14(1), 251–261. doi: 10.1109/TIFS.2018.2849883 CrossRef Google Scholar
[22]	X. Yuan and J. Yang, Sparse and low rank matrix decomposition via alternating direction method, Pacific Journal of Optimization, 2013, 9(1), 167. Google Scholar
[23]	Z. Zhou, X. Li, J. Wright et al., Stable principal component pursuit, in 2010 IEEE international symposium on information theory, IEEE, 2010, 1518–1522.https://www.researchgate.net/publication/224157727_Stable_Principal_Component_Pursuit Google Scholar