TY - JOUR
T1 - On block Gaussian sketching for the Kaczmarz method
AU - Rebrova, Elizaveta
AU - Needell, Deanna
N1 - Funding Information:
The authors are grateful to and were partially supported by NSF CAREER DMS no. 1348721 and NSF BIGDATA DMS no. 1740325. We also acknowledge sponsorship by Capital Fund Management.
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2021/1
Y1 - 2021/1
N2 - 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.
AB - 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.
KW - Block Kaczmarz
KW - Concentration of measure
KW - Gaussian sketching
KW - Noisy linear systems
KW - Random matrices
KW - Randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=85081922777&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081922777&partnerID=8YFLogxK
U2 - 10.1007/s11075-020-00895-9
DO - 10.1007/s11075-020-00895-9
M3 - Article
AN - SCOPUS:85081922777
SN - 1017-1398
VL - 86
SP - 443
EP - 473
JO - Numerical Algorithms
JF - Numerical Algorithms
IS - 1
ER -