Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
Top Cited Papers
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 21 (1), 57-81
- https://doi.org/10.1137/100781894
Abstract
Many problems can be characterized by the task of recovering the low-rank and sparse components of a given matrix. Recently, it was discovered that this nondeterministic polynomial-time hard (NP-hard) task can be well accomplished, both theoretically and numerically, via heuristically solving a convex relaxation problem where the widely acknowledged nuclear norm and $l_1$ norm are utilized to induce low-rank and sparsity. This paper studies the recovery task in the general settings that only a fraction of entries of the matrix can be observed and the observation is corrupted by both impulsive and Gaussian noise. We show that the resulting model falls into the applicable scope of the classical augmented Lagrangian method. Moreover, the separable structure of the new model enables us to solve the involved subproblems more efficiently by splitting the augmented Lagrangian function. Hence, some splitting numerical algorithms are developed for solving the new recovery model. Some preliminary numerical experiments verify that these augmented-Lagrangian-based splitting algorithms are easily implementable and surprisingly efficient for tackling the new recovery model.
Keywords
This publication has 24 references indexed in Scilit:
- The Power of Convex Relaxation: Near-Optimal Matrix CompletionIEEE Transactions on Information Theory, 2010
- A Singular Value Thresholding Algorithm for Matrix CompletionSIAM Journal on Optimization, 2010
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and ImagesSIAM Review, 2009
- A Weak-to-Strong Convergence Principle for Fejér-Monotone Methods in Hilbert SpacesMathematics of Operations Research, 2001
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- A proximal-based decomposition method for convex minimization problemsMathematical Programming, 1994
- Some Saddle-function splitting methods for convex programmingOptimization Methods and Software, 1994
- Application of the alternating direction method of multipliers to separable convex programming problemsComputational Optimization and Applications, 1992
- On the numerical solution of heat conduction problems in two and three space variablesTransactions of the American Mathematical Society, 1956