Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery

Richard Y. Zhang, Somayeh Sojoudi, Javad Lavaei

Research output: Contribution to journalArticlepeer-review

Abstract

Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant δ. If δ is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capable of establishing sharp thresholds on δ to guarantee the inexistence of spurious local minima. Using the technique, we prove that in the case of a rank-1 ground truth, an RIP constant of δ < 1=2 is both necessary and sufficient for exact recovery from any arbitrary initial point (such as a random point). We also prove a local recovery result: Given an initial point x0 satisfying f(x0) ≤(1-δ)2f(0), any descent algorithm that converges to second-order optimality guarantees exact recovery.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume20
StatePublished - Jun 1 2019

Keywords

  • Matrix factorization
  • Matrix sensing
  • Nonconvex optimization
  • Restricted Isometry Property
  • Spurious local minima

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery'. Together they form a unique fingerprint.

Cite this