In plain words: To rebuild a low-rank matrix from limited measurements, the method splits it into two smaller pieces and tweaks them by gradient descent. It proves this search never gets stuck in a bad answer, so from a random start it recovers the matrix in polynomial time.

Abstract

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em from random initialization}.

Srinadh Bhojanapalli, Behnam Neyshabur, Nathan Srebro
arXiv:1605.07221 · stat.ML, cs.LG, math.OC · submitted May 23, 2016 · updated May 27, 2016
abstract · pdf · html · 21 pages, 3 figures