ADMiRA: Atomic Decomposition for Minimum Rank Approximation

By Kiryung Lee, Yoram Bresler. IEEE Transactions on Information Theory, 2009

308 citations recorded by the source corpus.

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.

Subfields: Biomedical Engineering, Computational Mechanics, Radiology, Nuclear Medicine and Imaging

View Paper: https://www.semanticscholar.org/paper/712ee4cf411949e0263acb0292e3cd2e81de5d30

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Radiology, Nuclear Medicine and Imaging

Citations in the corpus

Guaranteed Rank Minimization via Singular Value Projection (2009, methodology): “Recently, Lee and Bresler [17] proposed an algorithm (ADMiRA) motivated by the orthogonal matching pursuit line of work in compressed sensing and show that for affine constraints with isometry constant δ4k ≤ 0.”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, unknown): “This difference is critical for large-scale applications.”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “It combines CoSaMP [271] for sparse vector recovery and ADMiRA [212] for low-rank matrix recovery.”
Accelerated dynamic MRI exploiting sparsity and low-rank structure: k-t SLR (2011, unknown): “The recent theoretical results indicate that a matrix of rank can be perfectly recovered from its measurements by solving the constrained optimization problem [15], [26]”
Low-rank matrix completion using alternating minimization (2012, methodology): “Subsequently, several other methods [10, 19] were proposed for this problem that also recovers the underlying matrix with optimal number of measurements and can give an -additive approximation in time O(log(1/ ).”
Blind Deconvolution Using Convex Programming (2012, background): “While this paper is only concerned with recovery by nuclear norm minimization, other types of recovery techniques have proven effective both in theory and in practice; see for example [28]–[30].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “A few other nonconvex matrix factorization algorithms have been left out due to space, including but not limited to normalized iterative hard thresholding (NIHT) [113], atomic decomposition for minimum rank approximation (Admira) [114], composite optimization (e.”
Matrix Completion from Noisy Entries (2009, background): “A related approach was also developed in [10], although wi t out performance guarantees for matrix completion.”
A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion (2009, methodology): “Also plotted are the reconstruction rates obtained for the convex relaxation approach of [10] solved using the Singular Value Thresholding algorithm [7], the FPCA algorithm from [22] and ADMiRA [21].”
Sparse Bayesian Methods for Low-Rank Matrix Estimation (2011, methodology): “In terms of computation time, ADMIRA provided the best performance in most of the simulations, whereas execution times for VSBL were stable throughout the testing conditions and were comparable to those of the other methods.”
Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements (2011, background): “Several different algorithms have been proposed, with many drawing their roots from standard compressive sensing techniques [3], [4], [6], [8], [9], [11], [14]–[16].”
Non-convex Optimization for Machine Learning (2017, methodology): “Also similar to sparse recovery, there exist pursuit-style techniques for matrix recovery, most notable among them being the ADMiRA method [Lee and Bresler, 2010] that extends the orthogonal matching pursuit approach to the matrix recovery setting.”