Convergence of Alternating Gradient Descent to Nuclear-Norm Minimizing Factorizations
This paper proves that alternating gradient descent with small random initialization converges linearly to the unique balanced factorization of a low-rank matrix, which minimizes the nuclear norm, by providing a rigorous analysis that clarifies why certain counterexamples do not apply and distinguishing this behavior from asymmetric or simultaneous gradient descent methods.