A unified linear convergence analysis of k-SVD

Zhiqiang Xu, Yiping Ke, Xin Cao, Chunlai Zhou, Pengfei Wei, Xin Gao

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Eigenvector computation, e.g., k-SVD for finding top-k singular subspaces, is often of central importance to many scientific and engineering tasks. There has been resurgent interest recently in analyzing relevant methods in terms of singular value gap dependence. Particularly, when the gap vanishes, the convergence of k-SVD is considered to be capped by a gap-free sub-linear rate. We argue in this work both theoretically and empirically that this is not necessarily the case, refreshing our understanding on this significant problem. Specifically, we leverage the recently proposed structured gap in a careful analysis to establish a unified linear convergence of k-SVD to one of the ground-truth solutions, regardless of what target matrix and how large target rank k are given. Theoretical results are evaluated and verified by experiments on synthetic or real data.
Original languageEnglish (US)
JournalMemetic Computing
StatePublished - Oct 12 2020

Bibliographical note

KAUST Repository Item: Exported on 2020-10-23
Acknowledgements: We thank the reviewers for their comments, which helped improve this paper considerably. The work is partially supported by a research project jointly funded by Hutchinson Research & Innovation Singapore Pte. Ltd. and Energy Research Institute @ NTU (ERI@N).


Dive into the research topics of 'A unified linear convergence analysis of k-SVD'. Together they form a unique fingerprint.

Cite this