Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate

Abstract

We develop a mathematical framework for low-rank matrix optimization with noisy data under a less restrictive restricted-isometry condition than prior work. When the noiseless RIP constant is below one third, spurious local solutions of the noisy problem must remain close to the ground truth, while the strict-saddle analysis gives polynomial-time search guarantees. The results characterize local-minimum geometry across both favorable and difficult regimes.