# Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 6 May 2025.

## Builds on (most cited first, 19 of 19)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019)
- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [Escaping Saddle Points in Constrained Optimization](https://mlsanity.com/paper/1809.02162/) (2018)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?](https://mlsanity.com/paper/1805.10251/) (2018)
- [Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy](https://mlsanity.com/paper/2107.03877/) (2021)
- [Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization](https://mlsanity.com/paper/1810.02024/) (2018)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Non-Convex Optimization](https://mlsanity.com/paper/1904.06784/) (2019)

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

- [Scalable Second-order Riemannian Optimization for K-means Clustering](https://mlsanity.com/paper/2509.21675/) (2025)

## Abstract (arXiv)

Low-rank matrix recovery is well-known to exhibit benign nonconvexity under the restricted isometry property (RIP): every second-order critical point is globally optimal, so local methods provably recover the ground truth. Motivated by the strong empirical performance of projected gradient methods for nonnegative low-rank recovery problems, we investigate whether this benign geometry persists when the factor matrices are constrained to be elementwise nonnegative. In the simple setting of a rank-1 nonnegative ground truth, we confirm that benign nonconvexity holds in the fully-observed case with RIP constant δ=0. This benign nonconvexity, however, is unstable. It fails to extend to the partially-observed case with any arbitrarily small RIP constant δ>0, and to higher-rank ground truths rstar>1, regardless of how much the search rank r≥ rstar is overparameterized. Together, these results undermine the standard stability-based explanation for the empirical success of nonconvex methods and suggest that fundamentally different tools are needed to analyze nonnegative low-rank recovery.