nach oben

Calcolo

Erschienen in:

01.06.2021

Randomized double and triple Kaczmarz for solving extended normal equations

verfasst von: Kui Du, Xiao-Hui Sun

Erschienen in: Calcolo | Ausgabe 2/2021

Einloggen, um Zugang zu erhalten

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

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel On maximum residual block and two-step Gauss–Seidel algorithms for linear least-squares problems

Nächster Artikel Pressure-robust error estimate of optimal order for the Stokes equations: domains with re-entrant edges and anisotropic mesh grading

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

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

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

Calandra, H., Gratton, S., Riccietti, E., Vasseur, X.: On a multilevel Levenberg–Marquardt method for the training of artificial neural networks and its application to the solution of partial differential equations. Optim. Methods Softw. (2020). https://doi.org/10.1080/10556788.2020.1775828CrossRefMATH

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

Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1–25 (2011)MathSciNetMATH

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

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

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.

Moorman, J.D., Tu, T.K., Molitor, D., Needell, D.: Randomized Kaczmarz with averaging. BIT Numer. Math. (2020). https://doi.org/10.1007/s10543-020-00824-1CrossRefMATH

14.

Necoara, I.: Faster randomized block Kaczmarz algorithms. SIAM J. Matrix Anal. Appl. 40(4), 1425–1452 (2019)MathSciNetCrossRef

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.

Wu, N., Xiang, H.: Projected randomized Kaczmarz methods. J. Comput. Appl. Math. 372, 112672 (2020)MathSciNetCrossRef

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

Titel: Randomized double and triple Kaczmarz for solving extended normal equations
verfasst von: Kui Du
Xiao-Hui Sun
Publikationsdatum: 01.06.2021
Verlag: Springer International Publishing
Erschienen in: Calcolo / Ausgabe 2/2021
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-021-00406-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2021

A weighted and balanced FEM for singularly perturbed reaction-diffusion problems

Correction to: Unified compact numerical quadrature formulas for Hadamard finite parts of singular integrals of periodic functions

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

-conforming finite element cochain complexes and commuting quasi-interpolation operators on Cartesian meshes

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

Pressure-robust error estimate of optimal order for the Stokes equations: domains with re-entrant edges and anisotropic mesh grading