Global Optimality of Local Search for Low Rank Matrix Recovery
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 from random initialization.
In this paper the authors consider a low-rank matrix approximation problem where the low-rank constraint is enforced directly by working in the factorized space and optimizing over a matrix U to solve a problem of the form min_U |A(UU^T) –y |_F^2 where A() is a linear operator.  Since working in the factorized space obviously makes the problem non-convex, the main contribution of the paper is to show under what conditions a local descent algorithm will converge to a global optimum, with the key requirements being that the linear operator, A(), needs to satisfy the restricted isometry property. 
Prior work has shown that local descent is guaranteed to converge to a global minimum for the same problem under similar conditions.  This prior work, however, relied on a careful initialization of the variables in order to guarantee their results, while the current work does not have this requirement and the variables can be initialized randomly.  Additionally, the current work also achieves slightly better bounds on the necessary level of restricted isometry required by the linear operator than some of the prior work.  While the contribution is thus in some sense an incremental improvement over this prior work, the authors clearly review the relevant literature and establish where their contribution falls relative to this work.  In addition to the theoretical contribution, the authors also provide experimental evidence that performing local descent from random initializations successfully achieves the global optimum under the same conditions as using a specially chosen initialization (based on a SVD), which was necessary for results from the prior work.   1) Overall, the technical content of the paper appears to be well established, and I do not have many significant comments in that regard.  I do, however, have a question regarding the proofs of some of the lemmas.  First, the proof of Lemma 4.2 begins by requiring a factorization of U into U=QR where U has orthonormal columns and R is invertible; however, if U is rank-deficient it seems that such a factorization will not exist.  Please discuss the correctness of Lemma 4.2 in the case where U is rank-deficient.  2) In the proof of Lemma 4.3, I did not work out the algebra in detail, but it would seem that in the equations following line 202 there should be terms that contain UR^T(U^*)^T and U^*RU^T that arise from the ZZ^T term.  Where have these gone?  In general, many of the proofs skip significant steps and would be much clearer if more of the intermediate steps are shown.  3) Given comment 2 I would suggest perhaps moving more the proofs into the supplement where they could be expanded and described in more detail.  Then, the description of the experiments (which only appear in the supplement) can be moved into the main body of the paper.