Skip to main content
Top
Published in: Memetic Computing 4/2020

12-10-2020 | Regular Research Paper

A unified linear convergence analysis of k-SVD

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

Published in: Memetic Computing | Issue 4/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Footnotes
1
They use a different term “generalized gap-dependent analysis”.
 
2
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.
 
3
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.
 
Literature
1.
go back to reference Absil PA, Mahony R, Sepulchre R (2008) Optimization algorithms on matrix manifolds. Princeton University Press, PrincetonCrossRef Absil PA, Mahony R, Sepulchre R (2008) Optimization algorithms on matrix manifolds. Princeton University Press, PrincetonCrossRef
2.
go back to reference Allen-Zhu Z, Li Y (2016) Even faster SVD decomposition yet without agonizing pain. In: Advances in Neural Information Processing Systems, pp 974–982 Allen-Zhu Z, Li Y (2016) Even faster SVD decomposition yet without agonizing pain. In: Advances in Neural Information Processing Systems, pp 974–982
3.
go back to reference 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 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
4.
go back to reference Dai W, Xu T, Wang W (2012) Simultaneous codeword optimization (simco) for dictionary update and learning. IEEE Trans Signal Process 60(12):6340–6353MathSciNetCrossRef Dai W, Xu T, Wang W (2012) Simultaneous codeword optimization (simco) for dictionary update and learning. IEEE Trans Signal Process 60(12):6340–6353MathSciNetCrossRef
5.
go back to reference Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2):303–353MathSciNetCrossRef Edelman A, Arias TA, Smith ST (1998) The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 20(2):303–353MathSciNetCrossRef
8.
go back to reference 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 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
9.
go back to reference Golub G, Van Loan C (2013) Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore Golub G, Van Loan C (2013) Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore
11.
go back to reference 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 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.
go back to reference Hardt M, Price E (2014) The noisy power method: A meta algorithm with applications. In: Advances in neural information processing systems, pp 2861–2869 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.
go back to reference Helmke U, Moore JB (2012) Optimization and dynamical systems. Springer, BerlinMATH Helmke U, Moore JB (2012) Optimization and dynamical systems. Springer, BerlinMATH
14.
go back to reference Mohar B, Poljak S (1993) Combinatorial and graph-theoretical problems in linear algebra. Eigenvalues in combinatorial optimization. Springer, New York, pp 107–151CrossRef Mohar B, Poljak S (1993) Combinatorial and graph-theoretical problems in linear algebra. Eigenvalues in combinatorial optimization. Springer, New York, pp 107–151CrossRef
15.
go back to reference 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 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.
go back to reference 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 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
18.
20.
go back to reference 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 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.
go back to reference Shamir O (2016) Convergence of stochastic gradient descent for PCA. In: ICML, pp. 257–265 Shamir O (2016) Convergence of stochastic gradient descent for PCA. In: ICML, pp. 257–265
22.
go back to reference Shamir O (2016) Fast stochastic algorithms for SVD and PCA: convergence properties and convexity. In: International Conference on Machine Learning, pp. 248–256 Shamir O (2016) Fast stochastic algorithms for SVD and PCA: convergence properties and convexity. In: International Conference on Machine Learning, pp. 248–256
23.
25.
go back to reference Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math Program 142(1–2):397–434MathSciNetCrossRef Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math Program 142(1–2):397–434MathSciNetCrossRef
27.
go back to reference 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 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.
go back to reference 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 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
Metadata
Title
A unified linear convergence analysis of k-SVD
Authors
Zhiqiang Xu
Yiping Ke
Xin Cao
Chunlai Zhou
Pengfei Wei
Xin Gao
Publication date
12-10-2020
Publisher
Springer Berlin Heidelberg
Published in
Memetic Computing / Issue 4/2020
Print ISSN: 1865-9284
Electronic ISSN: 1865-9292
DOI
https://doi.org/10.1007/s12293-020-00315-4

Other articles of this Issue 4/2020

Memetic Computing 4/2020 Go to the issue

Premium Partner