mlsanityData to 7 Oct 2026

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

arXiv 1901.01631 ↗First posted 7 Jan 2019cs.LG math.OC stat.MLcited by 26

Not on the map. Why?

Abstract (arXiv)

Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant δ. If δ 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 δ 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 δ<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 x0 satisfying f(x0)≤(1-δ)2f(0), any descent algorithm that converges to second-order optimality guarantees exact recovery.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 6; 2023: 3; 2024: 3; 2025: 3; 2026: 3.

26 papers.

Sort:

  1. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  2. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  3. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  4. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  5. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  6. 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10
  7. 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
  8. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 7
  9. 2021Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methodscited by 6
  10. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  11. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  12. 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
14 more
  1. 2023Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Pointscited by 5
  2. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  3. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 3
  4. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  5. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  6. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  7. 2024Interacting Particle Systems on Networks: joint inference of the network and the interaction kernelcited by 2
  8. 2023Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensingcited by 1
  9. 2024Absence of spurious solutions far from ground truth: A low-rank analysis with high-order lossescited by 1
  10. 2025Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minimacited by 1
  11. 2026Learning Multi-type heterogeneous interacting particle systemscited by 1
  12. 2026Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Liftingcited by 1
  13. 2026When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networkscited by 1
  14. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0