mlsanityData to 14 Oct 2026

Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate

arXiv 2203.03899 ↗First posted 8 Mar 2022math.OC cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

This paper is concerned with low-rank matrix optimization, which has found a wide range of applications in machine learning. This problem in the special case of matrix sensing has been studied extensively through the notion of Restricted Isometry Property (RIP), leading to a wealth of results on the geometric landscape of the problem and the convergence rate of common algorithms. However, the existing results can handle the problem in the case with a general objective function subject to noisy data only when the RIP constant is close to 0. In this paper, we develop a new mathematical framework to solve the above-mentioned problem with a far less restrictive RIP constant. We prove that as long as the RIP constant of the noiseless objective is less than 1/3, any spurious local solution of the noisy optimization problem must be close to the ground truth solution. By working through the strict saddle property, we also show that an approximate solution can be found in polynomial time. We characterize the geometry of the spurious local minima of the problem in a local region around the ground truth in the case when the RIP constant is greater than 1/3. Compared to the existing results in the literature, this paper offers the strongest RIP bound and provides a complete theoretical analysis on the global and local optimization landscapes of general low-rank optimization problems under random corruptions from any finite-variance family.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 22 of its 44 references that are in the map. First posted on arXiv 8 Mar 2022.

Builds on

22 of 44 references.

References · 22

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  2. 2017How to Escape Saddle Points Efficientlycited by 285
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  4. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  7. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  8. 2017Global Optimality in Low-rank Matrix Optimizationcited by 36
  9. 2016Nonconvex phase synchronizationcited by 30
  10. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 27
  11. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 25
  12. 2016Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provablycited by 22
10 more
  1. 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
  2. 2018Learning tensors from partial binary measurementscited by 13
  3. 2018Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysiscited by 13
  4. 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
  5. 2020How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?cited by 10
  6. 2021Local and Global Linear Convergence of General Low-rank Matrix Recovery Problemscited by 8
  7. 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
  8. 2017Conic Relaxations for Power System State Estimation with Line Measurementscited by 5
  9. 2018An equivalence between critical points for rank constraints versus low-rank factorizationscited by 4
  10. 2019Global Optimality Guarantees for Nonconvex Unsupervised Video Segmentationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 2; 2024: 1; 2025: 1; 2026: 2.

8 papers.

  1. 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
  2. 2023Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Pointscited by 5
  3. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 4
  4. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  5. 2026Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Liftingcited by 3
  6. 2023Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensingcited by 1
  7. 2024Absence of spurious solutions far from ground truth: A low-rank analysis with high-order lossescited by 1
  8. 2026Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustnesscited by 0