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

Fingerprint

Decomposition
guarantee
Compressed sensing
Inverse problems
experiment
performance
Sampling
Experiments

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

Cite this

ADMiRA : Atomic decomposition for minimum rank approximation. / Lee, Kiryung; Bresler, Yoram.

In: IEEE Transactions on Information Theory, Vol. 56, No. 9, 5550497, 01.09.2010, p. 4402-4416.

Research output: Contribution to journalArticle

@article{5f90331ded244705a5ff22719e3ef926,
title = "ADMiRA: Atomic decomposition for minimum rank approximation",
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.",
keywords = "Compressed sensing, matrix completion, performance guarantee, rank minimization, singular value decomposition (SVD)",
author = "Kiryung Lee and Yoram Bresler",
year = "2010",
month = "9",
day = "1",
doi = "10.1109/TIT.2010.2054251",
language = "English (US)",
volume = "56",
pages = "4402--4416",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

TY - JOUR

T1 - ADMiRA

T2 - Atomic decomposition for minimum rank approximation

AU - Lee, Kiryung

AU - Bresler, Yoram

PY - 2010/9/1

Y1 - 2010/9/1

N2 - 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.

AB - 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.

KW - Compressed sensing

KW - matrix completion

KW - performance guarantee

KW - rank minimization

KW - singular value decomposition (SVD)

UR - http://www.scopus.com/inward/record.url?scp=77955747588&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955747588&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2054251

DO - 10.1109/TIT.2010.2054251

M3 - Article

AN - SCOPUS:77955747588

VL - 56

SP - 4402

EP - 4416

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 9

M1 - 5550497

ER -