Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably

Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis +1

A rank-$r$ matrix $X\in {\mathbb{R}}^{m\times n}$ can be written as a product $U{V}^{\top }$, where $U\in {\mathbb{R}}^{m\times r}$ and $V\in {\mathbb{R}}^{n\times r}$. One could explo…