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.

翻译：限制的等离子属性(RIP ), 基本上表明线性测量大致保持规范, 在研究低级矩阵回收问题方面发挥着关键作用。 但是, RIP 在稳健的环境中失败, 当一组测量严重腐蚀了噪音。 在这项工作中, 我们提出一个强大的限制的等离子属性, 称为 Sign- RIP, 并展示其在稳健的低级矩阵回收中的广泛应用。 特别是, 我们显示 Sign- RIP 能够保证强性矩阵回收的次偏向性与非显性损失功能的统一一致, 即使存在任意密度和任意的大型外星。 根据 Sign- RIP, 我们在稳健的第1 级矩阵回收中描述临界点的位置, 并证明它们要么接近于真正的解决方案, 要么有小的规范。 此外, 在超度的系统中, 真实解决方案的等级被高估, 我们显示次偏向方法会以( 早期) 的维度速度接近于真正的解决方案。 最后, 我们显示信号- 相对于典型的对应方来说具有几乎相同的复杂度, 。