ScaledGD for Underparameterized Matrix Factorization: Global Convergence and Stepsize Universality

We study the dynamics and convergence of scaled gradient descent (ScaledGD), a preconditioned gradient method, for underparameterized nonconvex matrix factorization. Given a symmetric positive semidefinite matrix $M$ of rank $d$, we seek to identify its best rank-$k$ approximation, $k<d$, namely, the leading $k$-dimensional eigenspace and its associated eigenvalues. Assuming an eigengap at rank $k$, we prove that ScaledGD converges almost surely to a single global minimizer from a normalized randomized range initialization, for every fixed step size $\eta \in (0,1)$. This interval is independent of the target spectrum; the explicit asymptotic contraction factor depends on the relative eigengap. A fixed linear change of coordinates reveals that ScaledGD is exactly ordinary gradient descent on a hidden objective. This representation exposes the coupled dynamics of subspace selection and eigenvalue recovery, enabling a global convergence analysis throughout the full step-size interval. We extend the analysis to rectangular matrices through symmetric dilation, under a suitable initialization and a spectrum-dependent step-size bound. For rank-one approximation in both the symmetric and rectangular settings, we obtain stronger, explicit geometric rates from initialization under a strict leading gap. We also establish gap-free $O(1/t)$ bounds on excess reconstruction error. Both guarantees hold for every fixed $\eta \in (0,1)$ under the respective initialization conditions.