Convergence of fixed-point continuation algorithms for matrix rank minimization

DOI10.1007/S10208-011-9084-6zbMath1219.90195arXiv0906.3499OpenAlexW2001801912MaRDI QIDQ535287

Donald Goldfarb, Shi-Qian Ma

Publication date: 11 May 2011

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

singular value decompositionmatrix completiongreedy algorithmrestricted isometry propertyfixed-point methodmatrix rank minimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52)

Related Items (29)

On linear convergence of projected gradient method for a class of affine rank minimization problems ⋮ Low-Rank and Sparse Multi-task Learning ⋮ Minimum \( n\)-rank approximation via iterative hard thresholding ⋮ Guarantees of Riemannian optimization for low rank matrix completion ⋮ Fast alternating linearization methods for minimizing the sum of two convex functions ⋮ Iterative hard thresholding for low-rank recovery from rank-one projections ⋮ An approximation theory of matrix rank minimization and its application to quadratic equations ⋮ Nonnegative Low Rank Matrix Completion by Riemannian Optimalization Methods ⋮ Accelerated linearized Bregman method ⋮ CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion ⋮ Compressive Sensing ⋮ Krylov Methods for Low-Rank Regularization ⋮ Learning semidefinite regularizers ⋮ Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion ⋮ Convergence of iterative hard-thresholding algorithm with continuation ⋮ Matrix recipes for hard thresholding methods ⋮ Convergence of projected Landweber iteration for matrix rank minimization ⋮ Low-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT) ⋮ Fixed point and Bregman iterative methods for matrix rank minimization ⋮ Homotopy method for matrix rank minimization based on the matrix hard thresholding method ⋮ Low-rank matrix recovery via regularized nuclear norm minimization ⋮ Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery ⋮ A simple prior-free method for non-rigid structure-from-motion factorization ⋮ Guarantees of Riemannian Optimization for Low Rank Matrix Recovery ⋮ Minimization of the difference of Nuclear and Frobenius norms for noisy low rank matrix recovery ⋮ An adaptation for iterative structured matrix completion ⋮ Quasi-linear Compressed Sensing ⋮ Weighted lp − l1 minimization methods for block sparse recovery and rank minimization ⋮ Stable recovery of low rank matrices from nuclear norm minimization

Uses Software

• SDPT3
• PROPACK
• SPGL1
• CoSaMP
• L1-MAGIC
• ADMiRA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An implementable proximal point algorithmic framework for nuclear norm minimization
• Fixed point and Bregman iterative methods for matrix rank minimization
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• The geometry of graphs and some of its algorithmic applications
• Exact matrix completion via convex optimization
• A Singular Value Thresholding Algorithm for Matrix Completion
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Just relax: convex programming methods for identifying sparse signals in noise
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Gradient Pursuits
• Sparse Approximate Solutions to Linear Systems
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Compressed sensing

This page was built for publication: Convergence of fixed-point continuation algorithms for matrix rank minimization