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

DOI10.3934/IPI.2012.6.357zbMATH Open1252.15042arXiv1112.3946OpenAlexW2964352004MaRDI QIDQ435847FDOQ435847

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)

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.

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

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

zbMATH Keywords

robust principal component analysisdual certificatelow-rank matrixexact matrix completionstrongly convex programming

Mathematics Subject Classification ID

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

Cited In (16)

• 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
• Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity
• Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
• Non-convex matrix completion and related problems via strong duality
• Matrix completion and related problems via strong duality
• Restricted isometry property of principal component pursuit with reduced linear measurements
• Projected shrinkage algorithm for box-constrained \(\ell _1\)-minimization
• Accelerated Uzawa methods for convex optimization
• Matrix rigidity and the ill-posedness of robust PCA and matrix completion
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Applications of gauge duality in robust principal component analysis and semidefinite programming
• A short note on strongly convex programming for exact matrix completion and robust principal component analysis
• Robust principal component pursuit via inexact alternating minimization on matrix manifolds
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Linear convergence of the randomized sparse Kaczmarz method

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)