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

本文提出一种新算法 ScaledGD，它是梯度下降方法的预处理或对角线缩放版本，其预处理器是自适应且具有最小的计算开销，在低秩矩阵感知，鲁棒主成分分析和矩阵完成等任务中实现了线性收敛，具有优秀的性能表现。