GDSVD: Scalable k-SVD via Gradient Descent

We show that a gradient-descent with a simple, universal rule for step-size selection provably finds k-SVD, i.e., the k ≥ 1 largest singular values and corresponding vectors, of any matrix, despite nonconvexity. There has been substantial progress towards this in the past few years where existing results are able to establish such guarantees for the exact-parameterized and over-parameterized settings, with choice of oracle-provided step size. But guarantees for generic setting with a step size selection that does not require oracle-provided information has remained a challenge. We overcome this challenge and establish that gradient descent with an appealingly simple adaptive step size (akin to preconditioning) and random initialization enjoys global linear convergence for generic setting. Our convergence analysis reveals that the gradient method has an attracting region, and within this attracting region, the method behaves like Heron’s method (a.k.a. the Babylonian method). Empirically, we validate the theoretical results. The emergence of a modern compute infrastructure for iterative optimization coupled with this work is likely to provide a means of solving k-SVD for very large matrices.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Gan, Emily

Advisor dc:contributor.advisor

• Shah, Devavrat

Statement dc:rights

• Attribution 4.0 International (CC BY 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

• https://creativecommons.org/licenses/by/4.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/162688

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/162688