ADMiRA: Atomic decomposition for minimum rank approximation

Kiryung Lee, Yoram Bresler

Research output: Contribution to journalArticle

Abstract

In this paper, we address compressed sensing of a low-rank matrix posing the inverse problem as an approximation problem with a specified target rank of the solution. A simple search over the target rank then provides the minimum rank solution satisfying a prescribed data approximation bound. We propose an atomic decomposition providing an analogy between parsimonious representations of a sparse vector and a low-rank matrix and extending efficient greedy algorithms from the vector to the matrix case. In particular, we propose an efficient and guaranteed algorithm named atomic decomposition for minimum rank approximation (ADMiRA) that extends Needell and Tropp's compressive sampling matching pursuit (CoSaMP) algorithm from the sparse vector to the low-rank matrix case. The performance guarantee is given in terms of the rank-restricted isometry property (R-RIP) and bounds both the number of iterations and the error in the approximate solution for the general case of noisy measurements and approximately low-rank solution. With a sparse measurement operator as in the matrix completion problem, the computation in ADMiRA is linear in the number of measurements. Numerical experiments for the matrix completion problem show that, although the R-RIP is not satisfied in this case, ADMiRA is a competitive algorithm for matrix completion.

Original languageEnglish (US)
Article number5550497
Pages (from-to)4402-4416
Number of pages15
JournalIEEE Transactions on Information Theory
Volume56
Issue number9
DOIs
StatePublished - Sep 1 2010

Keywords

  • Compressed sensing
  • matrix completion
  • performance guarantee
  • rank minimization
  • singular value decomposition (SVD)

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'ADMiRA: Atomic decomposition for minimum rank approximation'. Together they form a unique fingerprint.

  • Cite this