Title | ||
---|---|---|
No Spurious Solutions in Non-convex Matrix Sensing: Structure Compensates for Isometry |
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. |
Year | DOI | Venue |
---|---|---|
2021 | 10.23919/ACC50511.2021.9483256 | 2021 AMERICAN CONTROL CONFERENCE (ACC) |
DocType | ISSN | Citations |
Conference | 0743-1619 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Igor Molybog | 1 | 1 | 2.04 |
Somayeh Sojoudi | 2 | 94 | 23.25 |
Javad Lavaei | 3 | 587 | 71.90 |