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

zbMATH Open1440.90056arXiv1901.01631MaRDI QIDQ5214201FDOQ5214201

Authors: Richard Zhang, Somayeh Sojoudi, Javad Lavaei 

Publication date: 7 February 2020

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.

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

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

zbMATH Keywords

matrix factorizationnonconvex optimizationrestricted isometry propertyspurious local minimamatrix sensing

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cites Work

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

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

Uses Software

• YALMIP
• Mosek
• PhaseMax
• PhaseLift
• Wirtinger Flow

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)