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

DOI10.3934/IPI.2012.6.357MaRDI QIDQ435847zbMATH OpenOpenAlexFDO

Authors Jian-Feng Cai, Hui Zhang, Li-zhi Cheng, Jubo Zhu

Publication date 12 July 2012

Published in Inverse Problems and Imaging (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1112.3946

zbMATH Keywords

dual certificateexact matrix completionlow-rank matrixrobust principal component analysisstrongly convex programming

Mathematics Subject Classification ID

Matrix completion problems (15A83) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Convex programming (90C25) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: 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`es 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.

Review text

The common task in matrix completion (MC) and robust principal component analysis (RPCA) is to recover a low-rank matrix from a given data matrix. These problems attracted great attention from various areas in applied sciences recently, especially after the publication of the pioneering works of Candès et al. [\textit{E. J. Candès} and \textit{B. Recht}, Found. Comput. Math. 9, No. 6, 717--772 (2009; Zbl 1219.90124); \textit{E. J. Candès} et al., ``Robust principal component analysis?, J. ACM 58, No. 1, 1--37 (2011), \url{arXiv:0912.3599}] One fundamental result in MC and RPCA is that the nuclear-norm-based convex optimizations lead to the exact low-rank matrix recovery under suitable conditions. In this paper, this result is extended 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 strong convex models lead to the exact low-rank matrix recovery, but also guides the user on how to choose suitable parameters in practical algorithms.

Recommendations

• Robust principal component pursuit via inexact alternating minimization on matrix manifolds
• A new model for sparse and low-rank matrix decomposition
• An alternating minimization method for robust principal component analysis
• Proximity point algorithm for low-rank matrix recovery from sparse noise corrupted data
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Matrix rigidity and the ill-posedness of robust PCA and matrix completion
• Efficient algorithms for robust and stable principal component pursuit problems
• Compressed sensing of low-rank plus sparse matrices
• Fast algorithms for robust principal component analysis with an upper bound on the rank
• Conditions for robust principal component analysis

Cited in

(17)

• Linear convergence of the randomized sparse Kaczmarz method
• A short note on strongly convex programming for exact matrix completion and robust principal component analysis
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem
• Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems
• Projected shrinkage algorithm for box-constrained \(\ell _1\)-minimization
• Restricted isometry property of principal component pursuit with reduced linear measurements
• Robust principal component pursuit via inexact alternating minimization on matrix manifolds
• Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
• Accelerated Uzawa methods for convex optimization
• Applications of gauge duality in robust principal component analysis and semidefinite programming
• Matrix completion and related problems via strong duality
• Matrix rigidity and the ill-posedness of robust PCA and matrix completion
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Non-convex matrix completion and related problems via strong duality
• Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity
• Convergence of three-block ADMM for weakly convex optimization problems

This page was built for publication: Strongly convex programming for exact matrix completion and robust principal component analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q435847)