A unified linear convergence analysis of k-SVD
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,...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/155195 |
| _version_ | 1826117354274160640 |
|---|---|
| author | Xu, Zhiqiang Ke, Yiping Cao, Xin Zhou, Chunlai Wei, Pengfei Gao, Xin |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Xu, Zhiqiang Ke, Yiping Cao, Xin Zhou, Chunlai Wei, Pengfei Gao, Xin |
| author_sort | Xu, Zhiqiang |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T04:26:13Z |
| format | Journal Article |
| id | ntu-10356/155195 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:26:13Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | ntu-10356/1551952022-02-17T08:03:12Z A unified linear convergence analysis of k-SVD Xu, Zhiqiang Ke, Yiping Cao, Xin Zhou, Chunlai Wei, Pengfei Gao, Xin School of Computer Science and Engineering Science Eigenvector Computation k-SVD 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. 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). 2022-02-17T08:03:12Z 2022-02-17T08:03:12Z 2020 Journal Article Xu, Z., Ke, Y., Cao, X., Zhou, C., Wei, P. & Gao, X. (2020). A unified linear convergence analysis of k-SVD. Memetic Computing, 12(4), 343-353. https://dx.doi.org/10.1007/s12293-020-00315-4 1865-9284 https://hdl.handle.net/10356/155195 10.1007/s12293-020-00315-4 2-s2.0-85092469950 4 12 343 353 en Memetic Computing © 2020 Springer-Verlag GmbH Germany, part of Springer Nature. All rights reserved. |
| spellingShingle | Science Eigenvector Computation k-SVD Xu, Zhiqiang Ke, Yiping Cao, Xin Zhou, Chunlai Wei, Pengfei Gao, Xin A unified linear convergence analysis of k-SVD |
| title | A unified linear convergence analysis of k-SVD |
| title_full | A unified linear convergence analysis of k-SVD |
| title_fullStr | A unified linear convergence analysis of k-SVD |
| title_full_unstemmed | A unified linear convergence analysis of k-SVD |
| title_short | A unified linear convergence analysis of k-SVD |
| title_sort | unified linear convergence analysis of k svd |
| topic | Science Eigenvector Computation k-SVD |
| url | https://hdl.handle.net/10356/155195 |
| work_keys_str_mv | AT xuzhiqiang aunifiedlinearconvergenceanalysisofksvd AT keyiping aunifiedlinearconvergenceanalysisofksvd AT caoxin aunifiedlinearconvergenceanalysisofksvd AT zhouchunlai aunifiedlinearconvergenceanalysisofksvd AT weipengfei aunifiedlinearconvergenceanalysisofksvd AT gaoxin aunifiedlinearconvergenceanalysisofksvd AT xuzhiqiang unifiedlinearconvergenceanalysisofksvd AT keyiping unifiedlinearconvergenceanalysisofksvd AT caoxin unifiedlinearconvergenceanalysisofksvd AT zhouchunlai unifiedlinearconvergenceanalysisofksvd AT weipengfei unifiedlinearconvergenceanalysisofksvd AT gaoxin unifiedlinearconvergenceanalysisofksvd |