# Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 5 Feb 2021.

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

- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019)
- [Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization](https://mlsanity.com/paper/2006.08857/) (2020)
- [Graphical Convergence of Subgradients in Nonconvex Optimization and Learning](https://mlsanity.com/paper/1810.07590/) (2018)
- [Subgradient Descent Learns Orthogonal Dictionaries](https://mlsanity.com/paper/1810.10702/) (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)
- [A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization](https://mlsanity.com/paper/1805.08204/) (2018)

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

- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution](https://mlsanity.com/paper/2207.07612/) (2022)
- [On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning](https://mlsanity.com/paper/2405.10289/) (2024)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing](https://mlsanity.com/paper/2303.14244/) (2023)
- [RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions](https://mlsanity.com/paper/2504.09648/) (2025)

## Abstract (arXiv)

Restricted isometry property (RIP), essentially stating that the linear measurements are approximately norm-preserving, plays a crucial role in studying low-rank matrix recovery problem. However, RIP fails in the robust setting, when a subset of the measurements are grossly corrupted with noise. In this work, we propose a robust restricted isometry property, called Sign-RIP, and show its broad applications in robust low-rank matrix recovery. In particular, we show that Sign-RIP can guarantee the uniform convergence of the subdifferentials of the robust matrix recovery with nonsmooth loss function, even at the presence of arbitrarily dense and arbitrarily large outliers. Based on Sign-RIP, we characterize the location of the critical points in the robust rank-1 matrix recovery, and prove that they are either close to the true solution, or have small norm. Moreover, in the over-parameterized regime, where the rank of the true solution is over-estimated, we show that subgradient method converges to the true solution at a (nearly) dimension-free rate. Finally, we show that sign-RIP enjoys almost the same complexity as its classical counterparts, but provides significantly better robustness against noise.