# Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate arXiv: https://arxiv.org/abs/2203.03899 ยท HTML: https://mlsanity.com/paper/2203.03899/ ## 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 (most cited first, 22 of 22) - [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016) - [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017) - [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017) - [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019) - [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015) - [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016) - [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015) - [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017) - [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016) - [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019) - [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017) - [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (2016) - [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016) - [Learning tensors from partial binary measurements](https://mlsanity.com/paper/1804.00108/) (2018) - [Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis](https://mlsanity.com/paper/1812.11466/) (2018) - [General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds](https://mlsanity.com/paper/2104.10356/) (2021) - [How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?](https://mlsanity.com/paper/2006.06915/) (2020) - [Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems](https://mlsanity.com/paper/2104.13348/) (2021) - [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021) - [Conic Relaxations for Power System State Estimation with Line Measurements](https://mlsanity.com/paper/1704.00133/) (2017) - [An equivalence between critical points for rank constraints versus low-rank factorizations](https://mlsanity.com/paper/1812.00404/) (2018) - [Global Optimality Guarantees for Nonconvex Unsupervised Video Segmentation](https://mlsanity.com/paper/1907.04409/) (2019) ## Built on by (most cited first, 8 of 8) - [Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing](https://mlsanity.com/paper/2208.07469/) (2022) - [Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points](https://mlsanity.com/paper/2302.07828/) (2023) - [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022) - [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025) - [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026) - [Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing](https://mlsanity.com/paper/2310.15549/) (2023) - [Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses](https://mlsanity.com/paper/2403.06056/) (2024) - [Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness](https://mlsanity.com/paper/2610.18318/) (2026) ## 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.