Fast Low-Rank Matrix Estimation for Ill-Conditioned Matrices

We study the general problem of optimizing a convex function of a matrix-valued variable subject to low-rank constraints. This problem has attracted significant attention; however, existing first-order methods for solving such problems either are too slow to converge, or require multiple invocations of singular value decompositions. On the other hand, factorization-based non-convex algorithms, while being much faster, require stringent assumptions on the condition number of the optimum. In this paper, we provide a novel algorithmic framework that achieves the best of both worlds: as fast as factorization methods, while requiring no spectral assumptions. We instantiate our framework for the nonlinear affine rank minimization (NLARM) problem. For this problem, we derive explicit bounds on the sample complexity as well as running time of our approach, and show that it achieves the best possible bounds for both cases. We also support our proposed algorithm via several experimental results.