TY - JOUR
T1 - Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
AU - Tao, Min
AU - Yuan, Xiaoming
N1 - Funding information:
Department of Mathematics, Nanjing University, Nanjing, China; School of Science, Nanjing University of Posts and Telecommunications, Nanjing, China ([email protected]). This author was supported by the fund NY210049.
$ Department of Mathematics, Hong Kong Baptist University, Hong Kong, China (xmyuan@hkbu. edu.hk). This author was supported by the Hong Kong General Research fund 202610 and the NSFC grant 10701055.
Publisher copyright:
Copyright © 2011 Society for Industrial and Applied Mathematics
PY - 2011/1/4
Y1 - 2011/1/4
N2 - 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 l1 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.
AB - 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 l1 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.
KW - Alternating direction method
KW - Augmented Lagrangian method
KW - Low-rank
KW - Matrix recovery
KW - Principal component analysis
KW - Sparse
UR - http://www.scopus.com/inward/record.url?scp=79957510064&partnerID=8YFLogxK
U2 - 10.1137/100781894
DO - 10.1137/100781894
M3 - Journal article
AN - SCOPUS:79957510064
SN - 1052-6234
VL - 21
SP - 57
EP - 81
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 1
ER -