Projected Gradient Descent Algorithm for Low-Rank Matrix Estimation

Understand

Most existing methodologies of estimating low-rank matrices rely on Burer-Monteiro factorization, but these approaches can suffer from slow convergence, especially when dealing with solutions characterized by a large condition number, defined by the ratio of the largest to the $r$-th singular values, where $r$ is the search rank.

• While methods such as Scaled Gradient Descent have been proposed to address this issue, such methods are more complicated and sometimes have weaker theoretical guarantees, for example, in the rank-deficient setting.
• In contrast, this paper demonstrates the effectiveness of the projected gradient descent algorithm.
• Firstly, its local convergence rate is independent of the condition number.