The Non convex Geometry of Low rank Matrix Optimization
This work considers two popular minimization problems: (i) the minimization of a general convex function $f(\mathbf{X} with the domain being positive semi definite matrices; (ii) the minimization of a general convex function $f(\mathbf{X} regularized by the matrix nuclear norm \mathbf{X}|_* with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low rank variable \mathbf{X} \mathbf{U}\mathbf{U}\top (for semi definite matrices) or \mathbf{X}\mathbf{U}\mathbf{V}\top (for general matrices) and also replace the nuclear norm \mathbf{X}|_* with \mathbf{U}|_F^2+\mathbf{V}|_F^2)/2$ In spite of the non convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.