Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery

zbMath1440.90056arXiv1901.01631MaRDI QIDQ5214201

Javad Lavaei, Somayeh Sojoudi, Richard Y. Zhang

Publication date: 7 February 2020

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

zbMATH Keywords

nonconvex optimizationmatrix factorizationrestricted isometry propertyspurious local minimamatrix sensing

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Related Items

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 ⋮ An Equivalence between Critical Points for Rank Constraints Versus Low-Rank Factorizations

Uses Software

• YALMIP
• Mosek
• PhaseMax
• PhaseLift
• Wirtinger Flow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The bounds of restricted isometry constants for low rank matrices recovery
• Rang revealing QR factorizations
• Complexity bounds for second-order optimality in unconstrained optimization
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• A flexible convex relaxation for phase retrieval
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• The local convexity of solving systems of quadratic equations
• Fundamental limits of weak recovery with applications to phase retrieval
• Cubic regularization of Newton method and its global performance
• Exact matrix completion via convex optimization
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Guaranteed Matrix Completion via Non-Convex Factorization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Some NP-complete problems in quadratic and nonlinear programming
• Trust Region Methods
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Global rates of convergence for nonconvex optimization on manifolds
• Spurious Local Minima in Power System State Estimation
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Matrix Completion From a Few Entries
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Low-rank matrix completion using alternating minimization

This page was built for publication: Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery