Reproduce “$k$-SVD with Gradient Descent” on OpenResearch

About this paper

Yassir Jedra, Devavrat Shah

The method recovers singular values and vectors through norm-scaled gradient descent on a rank-one approximation loss, starting from a random vector transformed by matrix. It uses step size η=1/2 and extends sequentially to k-SVD. For symmetric positive-semidefinite matrices with a singular-value gap, it guarantees linear convergence, with recovery error at most ε; its iteration bound depends on the gap and initialization.

Key insights

• The proposed gradient descent method with its adaptive step-size behaves analogously to Heron's method for computing square roots, offering a novel explanation for its efficiency and robust convergence.
• Global linear convergence is achieved for k-SVD from random initialization by demonstrating that iterates remain bounded, align with the top singular vector, and converge in norm, avoiding saddle points.
• The method provides a unified theoretical framework, proving efficacy across all parametrization regimes (over-parameterized, exact-parameterized, and, critically, under-parameterized), which was a significant gap in prior work.

Summary by alphaXiv.