Lecture notes on non-convex algorithms for low-rank matrix recovery
arXiv:2105.10318
Abstract
Low-rank matrix recovery problems are inverse problems which naturally arise in various fields like signal processing, imaging and machine learning. They are non-convex and NP-hard in full generality. It is therefore a delicate problem to design efficient recovery algorithms and to provide rigorous theoretical insights on the behavior of these algorithms. The goal of these notes is to review recent progress in this direction for the class of so-called "non-convex algorithms", with a particular focus on the proof techniques. Although they aim at presenting very recent research works, these notes have been written with the intent to be, as much as possible, accessible to non-specialists.
References in corpus (18)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- An overview of low-rank matrix recovery from incomplete observations
- Global rates of convergence for nonconvex optimization on manifolds
- Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
- Low-rank optimization for semidefinite convex problems
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Incoherence-Optimal Matrix Completion
- Nonconvex phase synchronization
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Gradient Descent Converges to Minimizers
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Near-optimal bounds for phase synchronization
- A Partial Derandomization of PhaseLift using Spherical Designs
- A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
- From Symmetry to Geometry: Tractable Nonconvex Problems
- An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
- Exact Minimax Estimation for Phase Synchronization