May  2012, 6(2): 357-372. doi: 10.3934/ipi.2012.6.357

Strongly convex programming for exact matrix completion and robust principal component analysis

1. 

Department of Mathematics and Systems Science, National University of Defense Technology, Changsha, Hunan 410073, China, China, China

2. 

Department of Mathematics, University of Iowa, Iowa City, IA 52242, United States

Received  July 2011 Revised  January 2012 Published  May 2012

The common task in matrix completion (MC) and robust principle component analysis (RPCA) is to recover a low-rank matrix from a given data matrix. These problems gained great attention from various areas in applied sciences recently, especially after the publication of the pioneering works of Candès et al.. One fundamental result in MC and RPCA is that nuclear norm based convex optimizations lead to the exact low-rank matrix recovery under suitable conditions. In this paper, we extend this result by showing that strongly convex optimizations can guarantee the exact low-rank matrix recovery as well. The result in this paper not only provides sufficient conditions under which the strongly convex models lead to the exact low-rank matrix recovery, but also guides us on how to choose suitable parameters in practical algorithms.
Citation: Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
References:
[1]

A. Argyriou, T. Evgeniou and M. Pontil, Multi-task feature learning,, Advances in Neural Information Processing Systems (NIPS), (2007).   Google Scholar

[2]

J.-F. Cai, E.J. Candès and Z. Shen, A singular value thresholding algorithm for matrixcompletion,, SIAM J. on Optimization, 20 (2010), 1956.  doi: 10.1137/080738970.  Google Scholar

[3]

J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing,, Math. Comp., 78 (2009), 1515.  doi: 10.1090/S0025-5718-08-02189-3.  Google Scholar

[4]

J.-F. Cai, S. Osher and Z. Shen, Convergence of the linearized Bregman iteration for $_1$-norm minimization,, Math. Comp., 78 (2009), 2127.  doi: 10.1090/S0025-5718-09-02242-X.  Google Scholar

[5]

J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for frame-based image deblurring,, SIAM J. Imaging Sciences, 2 (2009), 226.   Google Scholar

[6]

E. J. Candès and B. Recht, Exact matrix completion via convexoptimization,, Foundations of Computational Mathematics, 9 (2009), 717.   Google Scholar

[7]

E.J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion,, IEEE Transactions on InformationTheory, 56 (2010), 2053.  doi: 10.1109/TIT.2010.2044061.  Google Scholar

[8]

E. J. Candès and Y. Plan, Matrix completion with noise,, Proceeding of the IEEE, 98 (2010), 925.  doi: 10.1109/JPROC.2009.2035722.  Google Scholar

[9]

E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?,, Journal of ACM, 58 (2011), 1.   Google Scholar

[10]

E. J. Candès and T. Tao, Decoding by linear programming,, IEEE Transactions on Information Theory, 51 (2006), 4203.   Google Scholar

[11]

E.J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,, IEEE Trans. Inform. Theory, 52 (2006), 489.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[12]

V. Chandrasekharan, S. Sanghavi, P. Parillo and A. Wilsky, Rank-sparsity incoherence for matrix decomposition,, SIAM Journal on Optimization, 21 (2011), 572.  doi: 10.1137/090761793.  Google Scholar

[13]

S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit,, SIAM J. Sci. Comput., 20 (1998), 33.  doi: 10.1137/S1064827596304010.  Google Scholar

[14]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[15]

M. Fazel, "Matrix Rank Minimization with Applications,", Ph.D. thesis, (2002).   Google Scholar

[16]

M. P. Friedlander and P. Tseng, Exact regularization of convex programs,, SIAM J. Optim., 18 (2007), 1326.  doi: 10.1137/060675320.  Google Scholar

[17]

H. Gao, J.-F. Cai, Z. Shen and H. Zhao, Robust principalcomponent analysis-based four-dimensional computed tomography,, Physics in Medicine and Biology, 56 (2011), 3181.   Google Scholar

[18]

D. Gross, Recovering low-rank matrices from few coefficients in any basis,, IEEE Trans. Inform. Theory, 57 (2011), 1548.  doi: 10.1109/TIT.2011.2104999.  Google Scholar

[19]

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, 4 (2011), 1122.   Google Scholar

[20]

H. Ji, C. Liu, Z. W. Shen and Y. Xu, Robust video denoising using low rank matrix completion,, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), (2010), 1791.   Google Scholar

[21]

Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification,, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235.  doi: 10.1137/090755436.  Google Scholar

[22]

Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fastconvex optimization algorithms for exact recovery of a corrupted low-rank matrix,, Technical Report UILU-ENG-09-2214, (2010), 09.   Google Scholar

[23]

Z. Lin, M. Chen, L. Wu and Y. Ma, The augmentedLagrange multiplier method for exact recovery of corrupted low-rankmatrices,, Technical Report UILU-ENG-09-2215, (2010), 09.   Google Scholar

[24]

K. Min, Z. D. Zhang, J. Writht and Y. Ma, Decomposing background topic from keywords by principle component pursuit,, Proceeding of the 19th ACM Interational Conference on Information and Knowledge, (2010), 269.   Google Scholar

[25]

J. Meng, W. Yin, E. Houssain and Z. Han, Collaborative spectrum sensing from sparse observations using matrix completion for cognitive radio networks,, Proceedings of ICASSP, (2010), 3114.   Google Scholar

[26]

S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterativemethods for matrix rank minimization,, Mathematical Programming Series A, 128 (2011), 321.  doi: 10.1007/s10107-009-0306-5.  Google Scholar

[27]

M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality,, IEEE Transactions on Automatic Control, 42 (1997), 239.  doi: 10.1109/9.554402.  Google Scholar

[28]

Y. Nesterov, Smooth minimization of non-smooth functions,, Math. Program. Serie A, 103 (2005), 127.   Google Scholar

[29]

S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising,, Comm. in Math. Sciences, 1 (2010), 93.   Google Scholar

[30]

B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum rank solutionsof matrix equations via nuclear norm minimization,, SIAM Review, 52 (2010), 471.  doi: 10.1137/070697835.  Google Scholar

[31]

B. Recht, W. Xu and B. Hassibi, Necessary and sufficient conditions forsuccess of the nuclear norm heuristic for rank minimization,, Proceedings of the 47th IEEE Conference on Decision and Control, (2008), 3065.   Google Scholar

[32]

B. Recht, W. Xu and B. Hassibi, Null space conditions and thresholds for rank minimization,, Mathematics Programming, 127 (2011), 175.  doi: 10.1007/s10107-010-0422-2.  Google Scholar

[33]

B. Recht, A simpler approach to matrix completion,, J. Machine Learning Res., 12 (2011), 3413.   Google Scholar

[34]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970).   Google Scholar

[35]

K. C. Toh and S. Yun, An accelerated proximal gradient algorithm fornuclear norm regularized least squares problems,, Pacific Journal of Optimization, 6 (2009), 615.   Google Scholar

[36]

C. Tomasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method,, International Journal of Computer Vision, 9 (1992), 137.   Google Scholar

[37]

J. Wright, A. Ganesh, S. Rao and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization,, submitted to Journal of the ACM, (2009).   Google Scholar

[38]

W. Yin, Analysis and generalizations of the linearized Bregman method,, SIAM Journal on Image Science, 3 (2010), 856.   Google Scholar

[39]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$ minimization with applications to compressed sensing,, SIAM J. Imaging Sciences, 1 (2008), 143.   Google Scholar

[40]

Z. D. Zhang, X. Liang, A. Ganesh and Y. Ma, TILT: Transform invariant low-rank textures,, Computer Vision-ACCV, (2010), 314.   Google Scholar

[41]

H. Zhang and L. Z. Cheng, Projected Landweber iteration for matrix completion,, Journal of Computational and Applied Mathematics, 235 (2010), 593.  doi: 10.1016/j.cam.2010.06.010.  Google Scholar

[42]

H. Zhang, L. Z. Cheng and W. Zhu, A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm,, Applied and Computational Harmonic Analysis, 31 (2011), 454.  doi: 10.1016/j.acha.2011.04.004.  Google Scholar

[43]

H. Zhang, L. Z. Cheng and W. Zhu, Nuclear norm regularization with low-rank constraint for matrix completion,, Inverse Problems, 26 (2010).  doi: 10.1088/0266-5611/26/11/115009.  Google Scholar

show all references

References:
[1]

A. Argyriou, T. Evgeniou and M. Pontil, Multi-task feature learning,, Advances in Neural Information Processing Systems (NIPS), (2007).   Google Scholar

[2]

J.-F. Cai, E.J. Candès and Z. Shen, A singular value thresholding algorithm for matrixcompletion,, SIAM J. on Optimization, 20 (2010), 1956.  doi: 10.1137/080738970.  Google Scholar

[3]

J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing,, Math. Comp., 78 (2009), 1515.  doi: 10.1090/S0025-5718-08-02189-3.  Google Scholar

[4]

J.-F. Cai, S. Osher and Z. Shen, Convergence of the linearized Bregman iteration for $_1$-norm minimization,, Math. Comp., 78 (2009), 2127.  doi: 10.1090/S0025-5718-09-02242-X.  Google Scholar

[5]

J.-F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for frame-based image deblurring,, SIAM J. Imaging Sciences, 2 (2009), 226.   Google Scholar

[6]

E. J. Candès and B. Recht, Exact matrix completion via convexoptimization,, Foundations of Computational Mathematics, 9 (2009), 717.   Google Scholar

[7]

E.J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion,, IEEE Transactions on InformationTheory, 56 (2010), 2053.  doi: 10.1109/TIT.2010.2044061.  Google Scholar

[8]

E. J. Candès and Y. Plan, Matrix completion with noise,, Proceeding of the IEEE, 98 (2010), 925.  doi: 10.1109/JPROC.2009.2035722.  Google Scholar

[9]

E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?,, Journal of ACM, 58 (2011), 1.   Google Scholar

[10]

E. J. Candès and T. Tao, Decoding by linear programming,, IEEE Transactions on Information Theory, 51 (2006), 4203.   Google Scholar

[11]

E.J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,, IEEE Trans. Inform. Theory, 52 (2006), 489.  doi: 10.1109/TIT.2005.862083.  Google Scholar

[12]

V. Chandrasekharan, S. Sanghavi, P. Parillo and A. Wilsky, Rank-sparsity incoherence for matrix decomposition,, SIAM Journal on Optimization, 21 (2011), 572.  doi: 10.1137/090761793.  Google Scholar

[13]

S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit,, SIAM J. Sci. Comput., 20 (1998), 33.  doi: 10.1137/S1064827596304010.  Google Scholar

[14]

D. L. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289.  doi: 10.1109/TIT.2006.871582.  Google Scholar

[15]

M. Fazel, "Matrix Rank Minimization with Applications,", Ph.D. thesis, (2002).   Google Scholar

[16]

M. P. Friedlander and P. Tseng, Exact regularization of convex programs,, SIAM J. Optim., 18 (2007), 1326.  doi: 10.1137/060675320.  Google Scholar

[17]

H. Gao, J.-F. Cai, Z. Shen and H. Zhao, Robust principalcomponent analysis-based four-dimensional computed tomography,, Physics in Medicine and Biology, 56 (2011), 3181.   Google Scholar

[18]

D. Gross, Recovering low-rank matrices from few coefficients in any basis,, IEEE Trans. Inform. Theory, 57 (2011), 1548.  doi: 10.1109/TIT.2011.2104999.  Google Scholar

[19]

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, 4 (2011), 1122.   Google Scholar

[20]

H. Ji, C. Liu, Z. W. Shen and Y. Xu, Robust video denoising using low rank matrix completion,, IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), (2010), 1791.   Google Scholar

[21]

Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification,, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235.  doi: 10.1137/090755436.  Google Scholar

[22]

Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen and Y. Ma, Fastconvex optimization algorithms for exact recovery of a corrupted low-rank matrix,, Technical Report UILU-ENG-09-2214, (2010), 09.   Google Scholar

[23]

Z. Lin, M. Chen, L. Wu and Y. Ma, The augmentedLagrange multiplier method for exact recovery of corrupted low-rankmatrices,, Technical Report UILU-ENG-09-2215, (2010), 09.   Google Scholar

[24]

K. Min, Z. D. Zhang, J. Writht and Y. Ma, Decomposing background topic from keywords by principle component pursuit,, Proceeding of the 19th ACM Interational Conference on Information and Knowledge, (2010), 269.   Google Scholar

[25]

J. Meng, W. Yin, E. Houssain and Z. Han, Collaborative spectrum sensing from sparse observations using matrix completion for cognitive radio networks,, Proceedings of ICASSP, (2010), 3114.   Google Scholar

[26]

S. Ma, D. Goldfarb and L. Chen, Fixed point and Bregman iterativemethods for matrix rank minimization,, Mathematical Programming Series A, 128 (2011), 321.  doi: 10.1007/s10107-009-0306-5.  Google Scholar

[27]

M. Mesbahi and G. P. Papavassilopoulos, On the rank minimization problem over a positive semidefinite linear matrix inequality,, IEEE Transactions on Automatic Control, 42 (1997), 239.  doi: 10.1109/9.554402.  Google Scholar

[28]

Y. Nesterov, Smooth minimization of non-smooth functions,, Math. Program. Serie A, 103 (2005), 127.   Google Scholar

[29]

S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising,, Comm. in Math. Sciences, 1 (2010), 93.   Google Scholar

[30]

B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum rank solutionsof matrix equations via nuclear norm minimization,, SIAM Review, 52 (2010), 471.  doi: 10.1137/070697835.  Google Scholar

[31]

B. Recht, W. Xu and B. Hassibi, Necessary and sufficient conditions forsuccess of the nuclear norm heuristic for rank minimization,, Proceedings of the 47th IEEE Conference on Decision and Control, (2008), 3065.   Google Scholar

[32]

B. Recht, W. Xu and B. Hassibi, Null space conditions and thresholds for rank minimization,, Mathematics Programming, 127 (2011), 175.  doi: 10.1007/s10107-010-0422-2.  Google Scholar

[33]

B. Recht, A simpler approach to matrix completion,, J. Machine Learning Res., 12 (2011), 3413.   Google Scholar

[34]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970).   Google Scholar

[35]

K. C. Toh and S. Yun, An accelerated proximal gradient algorithm fornuclear norm regularized least squares problems,, Pacific Journal of Optimization, 6 (2009), 615.   Google Scholar

[36]

C. Tomasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method,, International Journal of Computer Vision, 9 (1992), 137.   Google Scholar

[37]

J. Wright, A. Ganesh, S. Rao and Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization,, submitted to Journal of the ACM, (2009).   Google Scholar

[38]

W. Yin, Analysis and generalizations of the linearized Bregman method,, SIAM Journal on Image Science, 3 (2010), 856.   Google Scholar

[39]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$ minimization with applications to compressed sensing,, SIAM J. Imaging Sciences, 1 (2008), 143.   Google Scholar

[40]

Z. D. Zhang, X. Liang, A. Ganesh and Y. Ma, TILT: Transform invariant low-rank textures,, Computer Vision-ACCV, (2010), 314.   Google Scholar

[41]

H. Zhang and L. Z. Cheng, Projected Landweber iteration for matrix completion,, Journal of Computational and Applied Mathematics, 235 (2010), 593.  doi: 10.1016/j.cam.2010.06.010.  Google Scholar

[42]

H. Zhang, L. Z. Cheng and W. Zhu, A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm,, Applied and Computational Harmonic Analysis, 31 (2011), 454.  doi: 10.1016/j.acha.2011.04.004.  Google Scholar

[43]

H. Zhang, L. Z. Cheng and W. Zhu, Nuclear norm regularization with low-rank constraint for matrix completion,, Inverse Problems, 26 (2010).  doi: 10.1088/0266-5611/26/11/115009.  Google Scholar

[1]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[2]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067

[3]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[4]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[5]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[6]

Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021003

[7]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021001

[8]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[9]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[10]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435

[11]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[12]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356

[13]

Yueh-Cheng Kuo, Huan-Chang Cheng, Jhih-You Syu, Shih-Feng Shieh. On the nearest stable $ 2\times 2 $ matrix, dedicated to Prof. Sze-Bi Hsu in appreciation of his inspiring ideas. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020358

[14]

Lingju Kong, Roger Nichols. On principal eigenvalues of biharmonic systems. Communications on Pure & Applied Analysis, 2021, 20 (1) : 1-15. doi: 10.3934/cpaa.2020254

[15]

Thomas Bartsch, Tian Xu. Strongly localized semiclassical states for nonlinear Dirac equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 29-60. doi: 10.3934/dcds.2020297

[16]

Jérôme Lohéac, Chaouki N. E. Boultifat, Philippe Chevrel, Mohamed Yagoubi. Exact noise cancellation for 1d-acoustic propagation systems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020055

[17]

Charlotte Rodriguez. Networks of geometrically exact beams: Well-posedness and stabilization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021002

[18]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081

[19]

Jian-Xin Guo, Xing-Long Qu. Robust control in green production management. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021011

[20]

Xi Zhao, Teng Niu. Impacts of horizontal mergers on dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020173

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (27)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]