Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach

Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, Sujay Sanghavi
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:65-74, 2017.

Abstract

We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-r matrix $X ∈R^m x n$ is represented as $UV^T$, where $U ∈R^m x r$ and $V ∈R^n x r$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP.

Cite this Paper

BibTeX
@InProceedings{pmlr-v54-park17a, title = {{Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach}}, author = {Park, Dohyung and Kyrillidis, Anastasios and Carmanis, Constantine and Sanghavi, Sujay}, booktitle = {Proceedings of the 20th International Conference on Artificial Intelligence and Statistics}, pages = {65--74}, year = {2017}, editor = {Singh, Aarti and Zhu, Jerry}, volume = {54}, series = {Proceedings of Machine Learning Research}, month = {20--22 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v54/park17a/park17a.pdf}, url = {https://proceedings.mlr.press/v54/park17a.html}, abstract = {We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-r matrix $X ∈R^m x n$ is represented as $UV^T$, where $U ∈R^m x r$ and $V ∈R^n x r$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP. } }
Endnote
%0 Conference Paper %T Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach %A Dohyung Park %A Anastasios Kyrillidis %A Constantine Carmanis %A Sujay Sanghavi %B Proceedings of the 20th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2017 %E Aarti Singh %E Jerry Zhu %F pmlr-v54-park17a %I PMLR %P 65--74 %U https://proceedings.mlr.press/v54/park17a.html %V 54 %X We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-r matrix $X ∈R^m x n$ is represented as $UV^T$, where $U ∈R^m x r$ and $V ∈R^n x r$. In this paper, we complement recent findings on the non-convex geometry of the analogous PSD setting [5], and show that matrix factorization does not introduce any spurious local minima, under RIP.
APA
Park, D., Kyrillidis, A., Carmanis, C. & Sanghavi, S.. (2017). Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 54:65-74 Available from https://proceedings.mlr.press/v54/park17a.html.

Related Material