nach oben

Memetic Computing

Erschienen in:

12.10.2020 | Regular Research Paper

A unified linear convergence analysis of k-SVD

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

Erschienen in: Memetic Computing | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Cooperative co-evolutionary comprehensive learning particle swarm optimizer for formulation design of explosive simulant

Nächster Artikel Multi-task gradient descent for multi-task learning

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

They use a different term “generalized gap-dependent analysis”.

The k-th gap freeness, which does not depend on the k-th gap but still depends on a certain gap, is different from the gap freeness which does not depend on any gap.

Minor fluctuations occur in the convergence curves under setting II with \(\varDelta ''=0.30\). We believe that they are due to the relatively large step size compared to the small errors at the scale of \(10^{-15}\). Nevertheless, the overall trend of the convergence curves still concurs with our theoretical results.

www.cise.ufl.edu/research/sparse/matrices/.

Absil PA, Mahony R, Sepulchre R (2008) Optimization algorithms on matrix manifolds. Princeton University Press, PrincetonCrossRef

Allen-Zhu Z, Li Y (2016) Even faster SVD decomposition yet without agonizing pain. In: Advances in Neural Information Processing Systems, pp 974–982

Balsubramani A, Dasgupta S, Freund Y (2013) The fast convergence of incremental PCA. In: Advances in Neural Information Processing Systems 26, December 5-8, 2013, Lake Tahoe, Nevada, United States., 3174–3182

Dai W, Xu T, Wang W (2012) Simultaneous codeword optimization (simco) for dictionary update and learning. IEEE Trans Signal Process 60(12):6340–6353MathSciNetCrossRef

Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2):303–353MathSciNetCrossRef

Faddeeva V (1959) Computational methods of linear algebra. Dover books on advanced mathematics. Dover Publications. https://books.google.com.sa/books?id=WORQAAAAMAAJ

Fan J, Sun Q, Zhou WX, Zhu Z (2018) Principal component analysis for big data. arXiv preprint arXiv:1801.01602

Garber D, Hazan E, Jin C, Kakade SM, Musco C, Netrapalli P, Sidford A (2016) Faster eigenvector computation via shift-and-invert preconditioning. In: International Conference on Machine Learning, 2626–2634

Golub G, Van Loan C (2013) Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore

10.

Halko N, Martinsson P, Tropp JA (2011) Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev 53(2):217–288. https://doi.org/10.1137/090771806MathSciNetCrossRefMATH

11.

Hardt M, Price E (2014) The noisy power method: A meta algorithm with applications. In: Advances in Neural Information Processing Systems 27: 28th Annual Conference on Neural Information Processing Systems 2014, December 8–13, 2014 Montreal. Quebec, Canada, pp 2861–2869

12.

Hardt M, Price E (2014) The noisy power method: A meta algorithm with applications. In: Advances in neural information processing systems, pp 2861–2869

13.

Helmke U, Moore JB (2012) Optimization and dynamical systems. Springer, BerlinMATH

14.

Mohar B, Poljak S (1993) Combinatorial and graph-theoretical problems in linear algebra. Eigenvalues in combinatorial optimization. Springer, New York, pp 107–151CrossRef

15.

Musco C, Musco C, (2015) Randomized block krylov methods for stronger and faster approximate singular value decomposition. In: Advances in Neural Information Processing Systems 28: 29th Annual Conference on Neural Information Processing Systems 2015, December, 7–12, 2015 Montreal. Quebec, Canada, pp 1396–1404

16.

Ng AY, Jordan MI, Weiss Y (2001) On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada], pp. 849–856

17.

Pitaval R, Dai W, Tirkkonen O (2015) Convergence of gradient descent for low-rank matrix approximation. IEEE Trans Information Theory 61(8):4451–4457. https://doi.org/10.1109/TIT.2015.2448695MathSciNetCrossRefMATH

18.

Rudelson M, Vershynin, R (2010) Non-asymptotic theory of random matrices: extreme singular values. arXiv preprint arXiv:1003.2990

19.

Saad Y, Chelikowsky JR, Shontz SM (2010) Numerical methods for electronic structure calculations of materials. SIAM Rev 52(1):3–54. https://doi.org/10.1137/060651653MathSciNetCrossRefMATH

20.

Shamir O (2015) A stochastic PCA and SVD algorithm with an exponential convergence rate. In: Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, pp. 144–152

21.

Shamir O (2016) Convergence of stochastic gradient descent for PCA. In: ICML, pp. 257–265

22.

Shamir O (2016) Fast stochastic algorithms for SVD and PCA: convergence properties and convexity. In: International Conference on Machine Learning, pp. 248–256

23.

Torbjorn Ringertz U (1997) Eigenvalues in optimum structural design. Inst Math Appl 92:135MathSciNetMATH

24.

Wang J, Wang W, Garber D, Srebro N (2018) Efficient coordinate-wise leading eigenvector computation. In: Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, pp 806–820. http://proceedings.mlr.press/v83/wang18a.html

25.

Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math Program 142(1–2):397–434MathSciNetCrossRef

26.

Woodruff DP (2014) Sketching as a tool for numerical linear algebra. Found Trends Theor Comput Sci 10(1–2):1–157. https://doi.org/10.1561/0400000060MathSciNetCrossRefMATH

27.

Xu P, He BD, Sa CD, Mitliagkas I, Ré C (2018) Accelerated stochastic power iteration. In: International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pp. 58–67. http://proceedings.mlr.press/v84/xu18a.html

28.

Xu Z, Gao X (2018) On truly block eigensolvers via riemannian optimization. International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9–11 April 2018. Playa Blanca, Lanzarote, Canary Islands, Spain, pp 168–177

29.

Ye K, Lim L (2016) Schubert varieties and distances between subspaces of different dimensions. SIAM J Matrix Anal Appl 37(3):1176–1197. https://doi.org/10.1137/15M1054201MathSciNetCrossRefMATH

Titel: A unified linear convergence analysis of k-SVD
verfasst von: Zhiqiang Xu
Yiping Ke
Xin Cao
Chunlai Zhou
Pengfei Wei
Xin Gao
Publikationsdatum: 12.10.2020
Verlag: Springer Berlin Heidelberg
Erschienen in: Memetic Computing / Ausgabe 4/2020
Print ISSN: 1865-9284
Elektronische ISSN: 1865-9292
DOI: https://doi.org/10.1007/s12293-020-00315-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2020

Multi-task gradient descent for multi-task learning

Feature selection based bee swarm meta-heuristic approach for combinatorial optimisation problems: a case-study on MaxSAT

Designing optimal combination therapy for personalised glioma treatment

Evolution of biocoenosis through symbiosis with fitness approximation for many-tasking optimization

An efficient memetic genetic programming framework for symbolic regression

Cooperative co-evolutionary comprehensive learning particle swarm optimizer for formulation design of explosive simulant

Premium Partner