# General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds

arXiv: https://arxiv.org/abs/2104.10356 · HTML: https://mlsanity.com/paper/2104.10356/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2021.

## Built on by (most cited first, 12 of 12)

- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [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 Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [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)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [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)

## Abstract (arXiv)

This paper considers the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach. For the rank-1 case, we prove that there is no spurious second-order critical point for both symmetric and asymmetric problems if the rank-2 RIP constant δ is less than 1/2. Combining with a counterexample with δ=1/2, we show that the derived bound is the sharpest possible. For the arbitrary rank-r case, the same property is established when the rank-2r RIP constant δ is at most 1/3. We design a counterexample to show that the non-existence of spurious second-order critical points may not hold if δ is at least 1/2. In addition, for any problem with δ between 1/3 and 1/2, we prove that all second-order critical points have a positive correlation to the ground truth. Finally, the strict saddle property, which can lead to the polynomial-time global convergence of various algorithms, is established for both the symmetric and asymmetric problems when the rank-2r RIP constant δ is less than 1/3. The results of this paper significantly extend several existing bounds in the literature.