No Spurious Solutions in Non-convex Matrix Sensing: Structure Compensates for Isometry
Citations Over Time
Abstract
The paper is concerned with the theoretical explanation of the recent empirical success of solving the low-rank matrix sensing problem via nonconvex optimization. It is known that under an incoherence assumption (namely, RIP) on the sensing operator, the optimization problem has no spurious local minima. This assumption is too strong for real-world applications where the amount of data cannot be sufficiently high. We develop the notion of Kernel Structure Property (KSP), which can be used alone or combined with RIP in this context. KSP explains how the inherent structure of an operator contributes to the non-existence of spurious local minima. As a special case, we study sparse sensing operators that have a low-dimensional representation. Using KSP, we obtain novel necessary and sufficient conditions for no spurious solutions in matrix sensing and demonstrate their usefulness in analytical and numerical studies.
Related Papers
- On the Absence of Spurious Local Minima in Nonlinear Low-Rank Matrix Recovery Problems(2020)
- → Searching critical points of fitted potential energy surfaces(1996)7 cited
- → Neural Networks with Complex-Valued Weights Have No Spurious Local Minima(2021)1 cited
- → Preventing local minima by decorrelation(2002)