Top

BIT Numerical Mathematics

Published in:

13-08-2018

The randomized Kaczmarz method with mismatched adjoint

Authors: Dirk A. Lorenz, Sean Rose, Frank Schöpfer

Published in: BIT Numerical Mathematics | Issue 4/2018

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

search-config

AI-assisted search

Off

Abstract

This paper investigates the randomized version of the Kaczmarz method to solve linear systems in the case where the adjoint of the system matrix is not exact—a situation we refer to as “mismatched adjoint”. We show that the method may still converge both in the over- and underdetermined consistent case under appropriate conditions, and we calculate the expected asymptotic rate of linear convergence. Moreover, we analyze the inconsistent case and obtain results for the method with mismatched adjoint as for the standard method. Finally, we derive a method to compute optimized probabilities for the choice of the rows and illustrate our findings with numerical examples.

previous article Regular solutions of DAE hybrid systems and regularization techniques

next article Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

If \(\langle a_{i} \,,\, v_{i}\rangle = 0\), Algorithm 1 is not defined and in the case of \(\langle a_{i} \,,\, v_{i}\rangle <0\), the probabilities \(p_{i}\) below in Remark 2.4 would not be non-negative. However, in the case \(\langle a_{i} \,,\, v_{i}\rangle <0\) we could switch the sign of the \(v_{i}\)s, and the expressions in (2.1) and (2.2) would not change).

The code to produce the figures in this article is available at https://github.com/dirloren/rkma.

We could also add a perturbation to A - the numerical results would be rather similar. Setting entries to zero would be numerically beneficial if A would have many small entries, but this was not be the motivation here.

Agaskar, A., Wang, C., Lu, Y.M.: Randomized Kaczmarz algorithms: exact MSE analysis and optimal sampling probabilities. In: 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 389–393. IEEE (2014)

De Man, B., Basu, S.: Distance-driven projection and backprojection in three dimensions. Phys. Med. Biol. 49(11), 2463 (2004)CrossRef

Golub, G.H., Van Loan, C.F.: Matrix Computations, fourth edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013)

Gordon, R., Bender, R., Herman, G.T.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29(3), 471–481 (1970)CrossRef

Hansen, P.C., Saxild-Hansen, M.: AIR tools—a MATLAB package of algebraic iterative reconstruction methods. J. Comput. Appl. Math. 236(8), 2167–2178 (2012)MathSciNetCrossRef

Kak, A.C., Slaney, M., Wang, G.: Principles of computerized tomographic imaging. Med. Phys. 29(1), 107–107 (2002)CrossRef

Liu, J., Wright, S.J., Sridhar, S.: An Asynchronous Parallel Randomized Kaczmarz Algorithm. arXiv:1401.4780 (2014)

Needell, D.: Randomized Kaczmarz solver for noisy linear systems. BIT Numer. Math. 50(2), 395–403 (2010). https://doi.org/10.1007/s10543-010-0265-5 MathSciNetCrossRefMATH

Siddon, R.L.: Fast calculation of the exact radiological path for a three-dimensional CT array. Med. Phys. 12(2), 252–255 (1985)CrossRef

10.

Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262–278 (2009)MathSciNetCrossRef

11.

Watson, G.A.: Characterization of the subdifferential of some matrix norms. Linear Algebra Its Appl. 170, 33–45 (1992)MathSciNetCrossRef

12.

Zeng, G.L., Gullberg, G.T.: Unmatched projector/backprojector pairs in an iterative reconstruction algorithm. IEEE Trans. Med. Imaging 19(5), 548–555 (2000)CrossRef

13.

Zouzias, A., Freris, N.M.: Randomized extended Kaczmarz for solving least squares. SIAM J. Matrix Anal. Appl. 34(2), 773–793 (2013)MathSciNetCrossRef

Title: The randomized Kaczmarz method with mismatched adjoint
Authors: Dirk A. Lorenz
Sean Rose
Frank Schöpfer
Publication date: 13-08-2018
Publisher: Springer Netherlands
Published in: BIT Numerical Mathematics / Issue 4/2018
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-018-0717-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2018

On the spectral problem for trivariate functions

Energy behaviour of the Boris method for charged-particle dynamics

Regular solutions of DAE hybrid systems and regularization techniques

Multiple orthogonal polynomials applied to matrix function evaluation

Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices

Weak convergence of Galerkin approximations for fractional elliptic stochastic PDEs with spatial white noise

Premium Partner