AISTATS 2017poster207 citations
Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach
Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, Sujay Sanghavi
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.
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. }
}