Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery

MaRDI QIDQ5214201zbMATH OpenFDO

Authors Richard Zhang, Somayeh Sojoudi, Javad Lavaei

Publication date 7 February 2020

Full work available at URL https://arxiv.org/abs/1901.01631, http://jmlr.csail.mit.edu/papers/v20/19-020.html

zbMATH Keywords

matrix factorizationnonconvex optimizationrestricted isometry propertyspurious local minimamatrix sensing

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant $delta$. If $delta$ is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capable of establishing sharp thresholds on $delta$ to guarantee the inexistence of spurious local minima. Using the technique, we prove that in the case of a rank-1 ground truth, an RIP constant of $delta<1/2$ is both necessary and sufficient for exact recovery from any arbitrary initial point (such as a random point). We also prove a local recovery result: given an initial point $x_0$ satisfying $f(x_0)le(1-delta{)}^{2}f(0)$, any descent algorithm that converges to second-order optimality guarantees exact recovery.

Recommendations

• On critical points of quadratic low-rank matrix optimization problems
• Stable recovery of low-rank matrix via nonconvex Schatten \(p\)-minimization
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery
• The local convexity of solving systems of quadratic equations

Cites work

• scientific article; zbMATH DE number 1489799 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A flexible convex relaxation for phase retrieval
• Complexity bounds for second-order optimality in unconstrained optimization
• Cubic regularization of Newton method and its global performance
• Exact matrix completion via convex optimization
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Fundamental limits of weak recovery with applications to phase retrieval
• Global rates of convergence for nonconvex optimization on manifolds
• Guaranteed Matrix Completion via Non-Convex Factorization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Low-rank matrix completion using alternating minimization
• Matrix Completion From a Few Entries
• Matrix completion from noisy entries
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Rang revealing QR factorizations
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Some NP-complete problems in quadratic and nonlinear programming
• Spurious Local Minima in Power System State Estimation
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The bounds of restricted isometry constants for low rank matrices recovery
• The local convexity of solving systems of quadratic equations
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Trust Region Methods

Cited in

(6)

• Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
• Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
• Certifying the Absence of Spurious Local Minima at Infinity
• A new complexity metric for nonconvex rank-one generalized matrix completion
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Nonsmooth rank-one matrix factorization landscape

Describes a project that uses

Uses Software

• Wirtinger Flow
• PhaseLift
• PhaseMax
• Mosek
• YALMIP

This page was built for publication: Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery

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