### 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 language | English (US) |
---|---|

Article number | 5550497 |

Pages (from-to) | 4402-4416 |

Number of pages | 15 |

Journal | IEEE Transactions on Information Theory |

Volume | 56 |

Issue number | 9 |

DOIs | |

State | Published - Sep 1 2010 |

### Fingerprint

### 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

*IEEE Transactions on Information Theory*,

*56*(9), 4402-4416. [5550497]. https://doi.org/10.1109/TIT.2010.2054251

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

Research output: Contribution to journal › Article

*IEEE Transactions on Information Theory*, vol. 56, no. 9, 5550497, pp. 4402-4416. https://doi.org/10.1109/TIT.2010.2054251

}

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 -