# Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2020.

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

- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (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)
- [An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function](https://mlsanity.com/paper/2503.23832/) (2025)

## Abstract (arXiv)

The restricted isometry property (RIP) is a well-known condition that guarantees the absence of spurious local minima in low-rank matrix recovery problems with linear measurements. In this paper, we introduce a novel property named bound difference property (BDP) to study low-rank matrix recovery problems with nonlinear measurements. Using RIP and BDP jointly, we first focus on the rank-1 matrix recovery problem, for which we propose a new criterion to certify the nonexistence of spurious local minima over the entire space. We then analyze the general case with an arbitrary rank and derive a condition to rule out the possibility of having a spurious solution in a ball around the true solution. The developed conditions lead to much stronger theoretical guarantees than the existing bounds on RIP.