ADMiRA: Atomic Decomposition for Minimum Rank Approximation

DOI10.1109/TIT.2010.2054251zbMATH Open1366.94112arXiv0905.0044MaRDI QIDQ5281301FDOQ5281301

Authors: Kiryung Lee, Yoram Bresler 

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We address the inverse problem that arises in compressed sensing of a low-rank matrix. Our approach is to pose 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 that provides an analogy between parsimonious representations of a sparse vector and a low-rank matrix. Efficient greedy algorithms to solve the inverse problem for the vector case are extended to the matrix case through this atomic decomposition. In particular, we propose an efficient and guaranteed algorithm named ADMiRA that extends CoSaMP, its analogue for the vector case. The performance guarantee is given in terms of the rank-restricted isometry property and bounds both the number of iterations and the error in the approximate solution for the general case where the solution is approximately low-rank and the measurements are noisy. With a sparse measurement operator such as the one arising in the matrix completion problem, the computation in ADMiRA is linear in the number of measurements. The numerical experiments for the matrix completion problem show that, although the measurement operator in this case does not satisfy the rank-restricted isometry property, ADMiRA is a competitive algorithm for matrix completion.

Full work available at URL: https://arxiv.org/abs/0905.0044

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Matrix completion problems (15A83) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cited In (36)

• Enhancing matrix completion using a modified second-order total variation
• Exact minimum rank approximation via Schatten \(p\)-norm minimization
• An adaptation for iterative structured matrix completion
• Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
• Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery
• A non-convex algorithm framework based on DC programming and DCA for matrix completion
• Guarantees of Riemannian optimization for low rank matrix recovery
• Learning non-parametric basis independent models from point queries via low-rank methods
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Low-rank matrix recovery with Ky Fan 2-\(k\)-norm
• Matrix completion under interval uncertainty
• Stable low-rank matrix recovery via null space properties
• Minimum \( n\)-rank approximation via iterative hard thresholding
• Uniqueness conditions for low-rank matrix recovery
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Convergence of projected Landweber iteration for matrix rank minimization
• Fixed-rank matrix factorizations and Riemannian low-rank optimization
• ADMiRA
• Matrix rigidity and the ill-posedness of robust PCA and matrix completion
• Low-rank dynamic mode decomposition: an exact and tractable solution
• Orthogonal rank-one matrix pursuit for low rank matrix completion
• Low rank matrix recovery from rank one measurements
• Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
• Matrix recipes for hard thresholding methods
• Penalty decomposition methods for rank minimization
• A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
• An alternating minimization method for matrix completion problems
• A penalty decomposition method for rank minimization problem with affine constraints
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Smooth singular value thresholding algorithm for low-rank matrix completion problem
• Rank-constrained optimization and its applications
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Guarantees of Riemannian optimization for low rank matrix completion

Uses Software

• PROPACK
• CoSaMP

This page was built for publication: ADMiRA: Atomic Decomposition for Minimum Rank Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281301)