Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations

Min Tao, Xiaoming Yuan

Research output: Contribution to journalJournal articlepeer-review

349 Citations (Scopus)
33 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)57-81
Number of pages25
JournalSIAM Journal on Optimization
Issue number1
Publication statusPublished - 4 Jan 2011

Scopus Subject Areas

  • Software
  • Theoretical Computer Science

User-Defined Keywords

  • Alternating direction method
  • Augmented Lagrangian method
  • Low-rank
  • Matrix recovery
  • Principal component analysis
  • Sparse


Dive into the research topics of 'Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations'. Together they form a unique fingerprint.

Cite this