How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?

2018-05-25 · NeurIPS 2018 12 · Richard Y. Zhang, Cédric Josz, Somayeh Sojoudi, Javad Lavaei

When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP)---i.e. they are approximately norm-preserving---the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to eliminate spurious local minima, so existing results can only hold for near-perfect RIP. In fact, counterexamples are ubiquitous: we prove that every x is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant $\delta=1/2$, but causes randomly initialized stochastic gradient descent (SGD) to fail 12% of the time. SGD is frequently able to avoid and escape spurious local minima, but this empirical result shows that it can occasionally be defeated by their existence. Hence, while exact recovery guarantees will likely require a proof of no spurious local minima, arguments based solely on norm preservation will only be applicable to a narrow set of nearly-isotropic instances.

📄 PDF Abstract BibTeX arXiv:1805.10251

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery

2019-01-07 · Richard Y. Zhang, Somayeh Sojoudi, Javad Lavaei

Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant $\delta$. If $\delta$ is too large, however, then counterexamples c…

Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima

2025-05-06 · Richard Y. Zhang

The classical low-rank matrix recovery problem is well-known to exhibit \emph{benign nonconvexity} under the restricted isometry property (RIP): local optimization is guaranteed to converge to the global optimum, where t…

How many samples is a good initial point worth in Low-rank Matrix Recovery?

2020-12-01 · NeurIPS 2020 12 · Jialun Zhang, Richard Zhang

Given a sufficiently large amount of labeled data, the nonconvex low-rank matrix recovery problem contains no spurious local minima, so a local optimization algorithm is guaranteed to converge to a global minimum startin…

Restricted Isometry Property under High Correlations

2019-04-11 · Shiva Prasad Kasiviswanathan, Mark Rudelson

Matrices satisfying the Restricted Isometry Property (RIP) play an important role in the areas of compressed sensing and statistical learning. RIP matrices with optimal parameters are mainly obtained via probabilistic ar…

compressed sensing Dimensionality Reduction Vocal Bursts Intensity Prediction

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

2021-02-05 · Jianhao Ma, Salar Fattahi

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 …