Sharp Restricted Isometry Property Bounds for Low-Rank Matrix Recovery Problems with Corrupted Measurements

Authors

  • Ziye Ma UC Berkeley
  • Yingjie Bi UC Berkeley
  • Javad Lavaei UC Berkeley
  • Somayeh Sojoudi UC Berkeley

DOI:

https://doi.org/10.1609/aaai.v36i7.20734

Keywords:

Machine Learning (ML), Search And Optimization (SO)

Abstract

In this paper, we study a general low-rank matrix recovery problem with linear measurements corrupted by some noise. The objective is to understand under what conditions on the restricted isometry property (RIP) of the problem local search methods can find the ground truth with a small error. By analyzing the landscape of the non-convex problem, we first propose a global guarantee on the maximum distance between an arbitrary local minimizer and the ground truth under the assumption that the RIP constant is smaller than 1/2. We show that this distance shrinks to zero as the intensity of the noise reduces. Our new guarantee is sharp in terms of the RIP constant and is much stronger than the existing results. We then present a local guarantee for problems with an arbitrary RIP constant, which states that any local minimizer is either considerably close to the ground truth or far away from it. Next, we prove the strict saddle property, which guarantees the global convergence of the perturbed gradient descent method in polynomial time. The developed results demonstrate how the noise intensity and the RIP constant of the problem affect the landscape of the problem.

Downloads

Published

2022-06-28

How to Cite

Ma, Z., Bi, Y., Lavaei, J., & Sojoudi, S. (2022). Sharp Restricted Isometry Property Bounds for Low-Rank Matrix Recovery Problems with Corrupted Measurements. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7), 7672-7681. https://doi.org/10.1609/aaai.v36i7.20734

Issue

Section

AAAI Technical Track on Machine Learning II