On block Gaussian sketching for the Kaczmarz method

Elizaveta Rebrova, Deanna Needell

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)443-473
Number of pages31
JournalNumerical Algorithms
Volume86
Issue number1
DOIs
StatePublished - Jan 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Keywords

  • Block Kaczmarz
  • Concentration of measure
  • Gaussian sketching
  • Noisy linear systems
  • Random matrices
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'On block Gaussian sketching for the Kaczmarz method'. Together they form a unique fingerprint.

Cite this