Optimization over bounded-rank matrices through a desingularization enables joint global and local guarantees

Convergence guarantees for optimization over bounded-rank matrices are delicate to obtain because the feasible set is a nonsmooth and nonconvex algebraic variety. Existing techniques include direct optimization over bounded-rank matrices (e.g., projected gradient descent), fixed-rank optimization (over the maximal-rank stratum), and the LR parameterization. They all lack either global guarantees (the ability to accumulate only at stationary points) or fast local convergence (e.g., if the limit has non-maximal rank). We study a lifted geometry that allows algorithms to enjoy both. Khrulkov and Oseledets [2018] parameterize the bounded-rank variety via a desingularization to recast the optimization problem onto a smooth manifold. Building on their ideas, we develop a Riemannian geometry for this desingularization, also with care for numerical considerations. We use it to ensure conditions that, for many standard algorithms, yield global convergence to stationary points with fast local rates. On matrix completion tasks, we find that this approach is comparable to others.