Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent

Low-rank matrix estimation is a canonical problem that finds numerous in signal processing, machine learning and imaging science. A approach in practice is to factorize the matrix into two compact-rank factors, and then optimize these factors directly via simple iterative such as gradient descent and alternating minimization. Despite, recent literatures have shown that these simple heuristics in achieve linear convergence when initialized properly for a growing number problems of interest. However, upon closer examination, existing approaches still be computationally expensive especially for ill-conditioned matrices: convergence rate of gradient descent depends linearly on the condition of the low-rank matrix, while the per-iteration cost of alternating is often prohibitive for large matrices. The goal of this paper is set forth a competitive algorithmic approach dubbed Scaled Gradient Descent(ScaledGD) which can be viewed as pre-conditioned or diagonally-scaled gradient, where the pre-conditioners are adaptive and iteration-varying with a computational overhead. With tailored variants for low-rank matrix, robust principal component analysis and matrix completion, we show that ScaledGD achieves the best of both worlds: it converges at a rate independent of the condition number of the low-rank matrix as alternating minimization, while maintaining the low per-iteration of gradient descent. Our analysis is also applicable to general loss that are restricted strongly convex and smooth over low-rank. To the best of our knowledge, ScaledGD is the first algorithm that has such properties over a wide range of low-rank matrix estimation.