Skip to main content
Erschienen in: Numerical Algorithms 1/2021

12.03.2020 | Original Paper

On block Gaussian sketching for the Kaczmarz method

verfasst von: Elizaveta Rebrova, Deanna Needell

Erschienen in: Numerical Algorithms | Ausgabe 1/2021

Einloggen

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

search-config
loading …

Abstract

The Kaczmarz algorithm is one of the most popular methods for solving large-scale over-determined linear systems due to its simplicity and computational efficiency. This method can be viewed as a special instance of a more general class of sketch and project methods. Recently, a block Gaussian version was proposed that uses a block Gaussian sketch, enjoying the regularization properties of Gaussian sketching, combined with the acceleration of the block variants. Theoretical analysis was only provided for the non-block version of the Gaussian sketch method. Here, we provide theoretical guarantees for the block Gaussian Kaczmarz method, proving a number of convergence results showing convergence to the solution exponentially fast in expectation. On the flip side, with this theory and extensive experimental support, we observe that the numerical complexity of each iteration typically makes this method inferior to other iterative projection methods. We highlight only one setting in which it may be advantageous, namely when the regularizing effect is used to reduce variance in the iterates under certain noise models and convergence for some particular matrix constructions.

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

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!

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+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!

Fußnoten
1
Sampling is called with replacement when a unit selected at random from the collection is returned to the collection and then a second element is selected at random. So, the same element may be selected more than once.
 
Literatur
1.
Zurück zum Zitat Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013)MATHCrossRef Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013)MATHCrossRef
2.
3.
Zurück zum Zitat Davidson, K.R., Szarek, S.J.: Local operator theory, random matrices and Banach spaces. In: Handbook of the geometry of Banach spaces, vol. 2, pp 1819–1820. North-Holland, Amsterdam (2003) Davidson, K.R., Szarek, S.J.: Local operator theory, random matrices and Banach spaces. In: Handbook of the geometry of Banach spaces, vol. 2, pp 1819–1820. North-Holland, Amsterdam (2003)
4.
Zurück zum Zitat De Loera, J.A., Haddock, J., Needell, D.: A sampling Kaczmarz-Motzkin algorithm for linear feasibility. SIAM J. Sci. Comput. 39(5), 66–87 (2017)MathSciNetMATHCrossRef De Loera, J.A., Haddock, J., Needell, D.: A sampling Kaczmarz-Motzkin algorithm for linear feasibility. SIAM J. Sci. Comput. 39(5), 66–87 (2017)MathSciNetMATHCrossRef
6.
Zurück zum Zitat Edelman, A.: Eigenvalues and condition numbers of random matrices. Ph.D. thesis Massachusetts Institute of Technology (1989) Edelman, A.: Eigenvalues and condition numbers of random matrices. Ph.D. thesis Massachusetts Institute of Technology (1989)
7.
8.
Zurück zum Zitat Feichtinger, H.G., Cenker, C., Mayer, M., Steier, H., Strohmer, T.: New variants of the POCS method using affine subspaces of finite codimension with applications to irregular sampling. In: P. Soc. Photo-Opt. Ins. International Society for Optics and Photonics, vol. 1818, pp 299–311 (1992) Feichtinger, H.G., Cenker, C., Mayer, M., Steier, H., Strohmer, T.: New variants of the POCS method using affine subspaces of finite codimension with applications to irregular sampling. In: P. Soc. Photo-Opt. Ins. International Society for Optics and Photonics, vol. 1818, pp 299–311 (1992)
9.
Zurück zum Zitat Feldheim, O.N., Sodin, S.: A universality result for the smallest eigenvalues of certain sample covariance matrices. Geom. Funct. Anal. 20(1), 88–123 (2010)MathSciNetMATHCrossRef Feldheim, O.N., Sodin, S.: A universality result for the smallest eigenvalues of certain sample covariance matrices. Geom. Funct. Anal. 20(1), 88–123 (2010)MathSciNetMATHCrossRef
11.
Zurück zum Zitat Gower, R.M., Richtárik, P.: Randomized iterative methods for linear systems. SIAM J. Matrix Anal. A. 36(4), 1660–1690 (2015)MathSciNetMATHCrossRef Gower, R.M., Richtárik, P.: Randomized iterative methods for linear systems. SIAM J. Matrix Anal. A. 36(4), 1660–1690 (2015)MathSciNetMATHCrossRef
12.
Zurück zum Zitat Gower, R.M., Richtárik, P.: Stochastic dual ascent for solving linear systems. arXiv:1512.06890 (2015) Gower, R.M., Richtárik, P.: Stochastic dual ascent for solving linear systems. arXiv:1512.​06890 (2015)
13.
Zurück zum Zitat Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE T. Med. Imaging 12(3), 600–609 (1993)CrossRef Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE T. Med. Imaging 12(3), 600–609 (1993)CrossRef
14.
Zurück zum Zitat Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. B. Int. Acad. Pol. Sci. Lett.: 335–357 (1937) Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. B. Int. Acad. Pol. Sci. Lett.: 335–357 (1937)
15.
Zurück zum Zitat Loizou, N., Richtárik, P.: Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. arXiv:1712.09677 (2017) Loizou, N., Richtárik, P.: Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. arXiv:1712.​09677 (2017)
16.
Zurück zum Zitat Loizou, N., Richtárik, P.: Convergence analysis of inexact randomized iterative methods. arXiv:1903.07971 (2019) Loizou, N., Richtárik, P.: Convergence analysis of inexact randomized iterative methods. arXiv:1903.​07971 (2019)
17.
Zurück zum Zitat Natterer, F.: The mathematics of computerized tomography. B. G. Teubner, Stuttgart; Wiley (1986) Natterer, F.: The mathematics of computerized tomography. B. G. Teubner, Stuttgart; Wiley (1986)
19.
Zurück zum Zitat Needell, D., Tropp, J.A.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199–221 (2014)MathSciNetMATHCrossRef Needell, D., Tropp, J.A.: Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra Appl. 441, 199–221 (2014)MathSciNetMATHCrossRef
20.
Zurück zum Zitat Needell, D., Ward, R.: Two-subspace projection method for coherent overdetermined systems. J. Fourier Anal. Appl. 19(2), 256–269 (2013)MathSciNetMATHCrossRef Needell, D., Ward, R.: Two-subspace projection method for coherent overdetermined systems. J. Fourier Anal. Appl. 19(2), 256–269 (2013)MathSciNetMATHCrossRef
21.
Zurück zum Zitat Needell, D., Ward, R., Srebro, N.: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. In: Adv. Neur. In., pp 1017–1025 (2014) Needell, D., Ward, R., Srebro, N.: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. In: Adv. Neur. In., pp 1017–1025 (2014)
22.
Zurück zum Zitat Rebrova, E., Tikhomirov, K.: Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries. Israel J. Math. 227(2), 507–544 (2018)MathSciNetMATHCrossRef Rebrova, E., Tikhomirov, K.: Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries. Israel J. Math. 227(2), 507–544 (2018)MathSciNetMATHCrossRef
23.
Zurück zum Zitat Rudelson, M., Vershynin, R.: The Littlewood-Offord problem and invertibility of random matrices. Adv. Math. 218(2), 600–633 (2008)MathSciNetMATHCrossRef Rudelson, M., Vershynin, R.: The Littlewood-Offord problem and invertibility of random matrices. Adv. Math. 218(2), 600–633 (2008)MathSciNetMATHCrossRef
24.
Zurück zum Zitat Rudelson, M., Vershynin, R.: Smallest singular value of a random rectangular matrix. Commun. Pur. Appl. Math. 62(12), 1707–1739 (2009)MathSciNetMATHCrossRef Rudelson, M., Vershynin, R.: Smallest singular value of a random rectangular matrix. Commun. Pur. Appl. Math. 62(12), 1707–1739 (2009)MathSciNetMATHCrossRef
25.
Zurück zum Zitat Sezan, M.I., Stark, H.: Incorporation of a priori moment information into signal recovery and synthesis problems. J. Math. Anal. Apl. 122(1), 172–186 (1987)MathSciNetMATHCrossRef Sezan, M.I., Stark, H.: Incorporation of a priori moment information into signal recovery and synthesis problems. J. Math. Anal. Apl. 122(1), 172–186 (1987)MathSciNetMATHCrossRef
26.
Zurück zum Zitat Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262 (2009)MathSciNetMATHCrossRef Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262 (2009)MathSciNetMATHCrossRef
28.
Zurück zum Zitat Tan, Y.S., Vershynin, R.: Phase retrieval via randomized Kaczmarz: theoretical guarantees. Information and Inference: A Journal of the IMA 8(1), 97–123 (2018)MathSciNetMATHCrossRef Tan, Y.S., Vershynin, R.: Phase retrieval via randomized Kaczmarz: theoretical guarantees. Information and Inference: A Journal of the IMA 8(1), 97–123 (2018)MathSciNetMATHCrossRef
29.
Zurück zum Zitat Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge (2018)MATHCrossRef Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge (2018)MATHCrossRef
30.
Metadaten
Titel
On block Gaussian sketching for the Kaczmarz method
verfasst von
Elizaveta Rebrova
Deanna Needell
Publikationsdatum
12.03.2020
Verlag
Springer US
Erschienen in
Numerical Algorithms / Ausgabe 1/2021
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-020-00895-9

Weitere Artikel der Ausgabe 1/2021

Numerical Algorithms 1/2021 Zur Ausgabe