# Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2018.

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

- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (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)
- [Simple Alternating Minimization Provably Solves Complete Dictionary Learning](https://mlsanity.com/paper/2210.12816/) (2022)
- [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)
- [Personalized Dictionary Learning for Heterogeneous Datasets](https://mlsanity.com/paper/2305.15311/) (2023)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution](https://mlsanity.com/paper/2207.07612/) (2022)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [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)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)

## Abstract (arXiv)

This work is concerned with the non-negative rank-1 robust principal component analysis (RPCA), where the goal is to recover the dominant non-negative principal components of a data matrix precisely, where a number of measurements could be grossly corrupted with sparse and arbitrary large noise. Most of the known techniques for solving the RPCA rely on convex relaxation methods by lifting the problem to a higher dimension, which significantly increase the number of variables. As an alternative, the well-known Burer-Monteiro approach can be used to cast the RPCA as a non-convex and non-smooth ℓ1 optimization problem with a significantly smaller number of variables. In this work, we show that the low-dimensional formulation of the symmetric and asymmetric positive rank-1 RPCA based on the Burer-Monteiro approach has benign landscape, i.e., 1) it does not have any spurious local solution, 2) has a unique global solution, and 3) its unique global solution coincides with the true components. An implication of this result is that simple local search algorithms are guaranteed to achieve a zero global optimality gap when directly applied to the low-dimensional formulation. Furthermore, we provide strong deterministic and probabilistic guarantees for the exact recovery of the true principal components. In particular, it is shown that a constant fraction of the measurements could be grossly corrupted and yet they would not create any spurious local solution.