Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Calcolo
Published in: Calcolo 2/2021

01-06-2021

Randomized double and triple Kaczmarz for solving extended normal equations

Authors: Kui Du, Xiao-Hui Sun

Published in: Calcolo | Issue 2/2021

Login to get access

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

search-config
loading …

Abstract

The randomized Kaczmarz algorithm has received considerable attention recently because of its simplicity, speed, and the ability to approximately solve large-scale linear systems of equations. In this paper we propose randomized double and triple Kaczmarz algorithms to solve extended normal equations of the form \(\mathbf{A}^\top \mathbf{Ax}=\mathbf{A}^\top \mathbf{b}-\mathbf{c}\). The proposed algorithms avoid forming \(\mathbf{A}^\top \mathbf{A}\) explicitly and work for arbitrary \(\mathbf{A}\in \mathbb {R}^{m\times n}\) (full rank or rank-deficient, \(m\ge n\) or \(m<n\)). Tight upper bounds showing exponential convergence in the mean square sense of the proposed algorithms are presented and numerical experiments are given to illustrate the theoretical results.
previous article On maximum residual block and two-step Gauss–Seidel algorithms for linear least-squares problems
next article Pressure-robust error estimate of optimal order for the Stokes equations: domains with re-entrant edges and anisotropic mesh grading
Literature
1.
Bai, Z.-Z., Wu, W.-T.: On greedy randomized Kaczmarz method for solving large sparse linear systems. SIAM J. Sci. Comput. 40(1), A592–A606 (2018)MathSciNetCrossRef
2.
Bai, Z.-Z., Wu, W.-T.: On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems. Appl. Math. Lett. 83, 21–26 (2018)MathSciNetCrossRef
3.
Bai, Z.-Z., Wu, W.-T.: On partially randomized extended Kaczmarz method for solving large sparse overdetermined inconsistent linear systems. Linear Algebra Appl. 578, 225–250 (2019)MathSciNetCrossRef
4.
5.
Calandra, H., Gratton, S., Riccietti, E., Vasseur, X.: On iterative solution of the extended normal equations. SIAM J. Matrix Anal. Appl. 41(4), 1571–1589 (2020)MathSciNetCrossRef
6.
Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1–25 (2011)MathSciNetMATH
7.
Du, K.: Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms. Numer. Linear Algebra Appl. 26(3), e2233 (2019)MathSciNetCrossRef
8.
Du, K., Si, W.-T., Sun, X.-H.: Randomized Extended Average Block Kaczmarz for Solving Least Squares. SIAM J. Sci. Comput. 42(6), A3541–A3559 (2020)MathSciNetCrossRef
9.
Fletcher, R.: A class of methods for non-linear programming. III. Rates of convergence. In: Numerical Methods for Non-linear Optimization (Conference, Dundee, 1971) 371–381 (1972)
10.
Leventhal, D., Lewis, A.S.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35(3), 641–654 (2010)MathSciNetCrossRef
11.
Ma, A., Needell, D., Ramdas, A.: Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods. SIAM J. Matrix Anal. Appl. 36(4), 1590–1604 (2015)MathSciNetCrossRef
12.
Ma, A., Needell, D., Ramdas, A.: Iterative methods for solving factorized linear systems. SIAM J. Matrix Anal. Appl. 39(1), 104–122 (2018)MathSciNetCrossRef
13.
14.
15.
Needell, D., Zhao, R., Zouzias, A.: Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl. 484, 322–343 (2015)MathSciNetCrossRef
16.
Niu, Y.-Q., Zheng, B.: A greedy block Kaczmarz algorithm for solving large-scale linear systems. Appl. Math. Lett. 104, 106294–106298 (2020)MathSciNetCrossRef
17.
Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262–278 (2009)MathSciNetCrossRef
18.
19.
Zhang, J., Guo, J.: On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems. Appl. Numer. Math. 157, 372–384 (2020)MathSciNetCrossRef
20.
Zhang, J.-J.: A new greedy Kaczmarz algorithm for the solution of very large linear systems. Appl. Math. Lett. 91, 207–212 (2019)MathSciNetCrossRef
21.
Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34(2), 773–793 (2013)MathSciNetCrossRef
Metadata
Title
Randomized double and triple Kaczmarz for solving extended normal equations
Authors
Kui Du
Xiao-Hui Sun
Publication date
01-06-2021
Publisher
Springer International Publishing
Published in
Calcolo / Issue 2/2021
Print ISSN: 0008-0624
Electronic ISSN: 1126-5434
DOI
https://doi.org/10.1007/s10092-021-00406-9

Other articles of this Issue 2/2021

Calcolo 2/2021 Go to the issue

OriginalPaper

Error control for statistical solutions of hyperbolic systems of conservation laws

OriginalPaper

Lopsided scaled HSS preconditioner for steady-state space-fractional diffusion equations

OriginalPaper

Structure-preserving Gauss methods for the nonlinear Schrödinger equation

OriginalPaper

Second-order finite difference approximation for a nonlinear size-structured population model with an indefinite growth rate coupled with the environment

OriginalPaper

Improved error estimates for Hybrid High-Order discretizations of Leray–Lions problems

OriginalPaper

A priori error analysis for a mixed VEM discretization of the spectral problem for the Laplacian operator

Premium Partner

    Image Credits