Block regularization Kaczmarz method

E. Yu. Bogdanova

Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 20 (2016) no. 3, pp. 544-551.

Résumé

This article focuses on the modification of the iterative version of Kaczmarz block algorithm for solving the problem of regularization, which is a fairly effective method for large-scale problems. An important characteristic of iterative methods is the speed of convergence, which depends on the condition number of the original problem. The main drawback of many iterative methods is the large condition number, while methods based on normal equations have the condition number of the system equal to the square of the condition number of the original problem . At the present time to increase the speed of convergence of iterative methods different types of preconditioners are used reducing the condition number of the system. The disadvantages of this approach is manifested in high computational complexity and the lack of universal preconditioner, which could be applied to any iterative method. One of the most effective approaches for improving the convergence rate of the method is to use a block variant of the method used. In this regard, in this paper we propose a modification of the original block Kaczmarz method for the regularization of the problem, which will reduce the computational complexity, and thus increase the rate of convergence of the algorithm. The article provides a detailed derivation of the proposed modification of the method and the proof of the convergence of the proposed variant of the block Kaczmarz method.

Détail

Keywords: regularization problem, Kaczmarz method, regularized normal equations
Mots-clés : Euler equations.

Bibliographie

[1] Tikhonov A. N., Arsenii V. Ya., Metody resheniia nekorrektnykh zadach [Methods for the solution of ill-posed problems], Nauka, Moscow, 1979, 284 pp. (In Russian) | Zbl

[2] Gill P. E., Murray W., Saunders M. A., “Preconditioners for indefinite systems arising in optimization”, SIAM. J. Matrix Anal. Appl., 13:1 (1992), 292–311 | DOI | Zbl

[3] Benzi M., “Preconditioning Techniques for Large Linear Systems: A Survey”, J. Comput. Phys., 182:2 (2002), 418–477 | DOI | Zbl

[4] Benzi M., Tuma M., “A comparative study of sparse approximate inverse preconditioners”, Appl. Numer. Math., 30:1–2 (1999), 305–340 | DOI | Zbl

[5] Bergamaschi L., Pini G., Sartoretto F., “Aproximate inverse preconditioning in the parallel solution of sparse eigenproblems”, Numer. Linear Algebra Appl., 7:3 (2000), 99–116 | 3.0.CO;2-5 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | Zbl

[6] Benzi M., Joubert W. D., Mateescu G., “Numerical experiments with parallel orderings for ILU preconditioners”, ETNA. Electronic Transactions on Numerical Analysis, 8 (1999), 88–114 http://eudml.org/doc/119978 | Zbl

[7] Bocs̨an Gh., “Convergence of iterative methods for solving random operator equations”, J. Nonlinear Sci. Appl., 6:1 (2013), 2–6 http://www.tjnsa.com/includes/files/articles/Vol6_Iss1_2–6_Convergence_of_iterative_methods_fo.pdf

[8] Gower R. M., Richtárik P., “Randomized Iterative Methods for Linear Systems”, SIAM. J. Matrix Anal. Appl., 36:4 (2015), 1660–1690, arXiv: [math.NA] 1506.03296 | Zbl

[9] Zhdanov A. I., Sidorov Yu. V., “Parallel implementation of a randomized regularized Kaczmarz's algorithm”, Computer Optics, 39:4 (2015), 536–541 (In Russian) | DOI

[10] Ivanov A. A., Zhdanov A. I., “Kaczmarz algorithm for Tikhonov regularization problem”, Applied Mathematics E-Notes, 13 (2013), 270–276 http://www.math.nthu.edu.tw/~amen/2013/1302252(final).pdf | Zbl

[11] Vasil'chenko G. P., Svetlakov A. A., “A projection algorithm for solving systems of linear algebraic equations of high dimensionality”, U.S.S.R. Comput. Math. Math. Phys., 20:1 (1980), 1–8 | MR | Zbl

[12] Tanabe K., “Projection method for solving a singular system of linear equation and its applications”, Numer. Math., 17:3 (1971), 203–214 | DOI | Zbl

[13] Strohmer T. A., Vershynin R., “A randomized Kaczmarz algorithm for linear systems with exponential convergence”, J. Fourier Anal. Appl., 15 (2009), 262–278 | DOI | Zbl

[14] Kaczmarz S., “Angenäherte Auflösung von Systemen linearer Gleichungen”, Bull. Int. Acad. Polon. Sci. A, 35 (1937), 335–357 http://jasonstockmann.com/Jason_Stockmann/Welcome_files/kaczmarz_english_translation_1937.pdf | Zbl

[15] Morozov V. A., Methods of Solving Incorrectly Posed Problems, Springer Verlag, New York, 1984, xviii+257 pp | DOI | Zbl

[16] Hämarik U., Palm R., Raus T., “A family of rules for parameter choice in Tikhonov regularization of ill–posed problems with inexact noise level”, Comput. Appl. Math., 236:8 (2012), 2146–2157 | DOI | Zbl

[17] Dolishniy V. V., Zhdanov A. I., “Calculation of the parameter regularization method based on the importance of cross-equivalent normal extension systems”, Proceedings of the Seventh All-Russian Scientific Conference with international participation, Information technologies in mathematical modeling. Part 4 (3–6 June 2010), Matem. Mod. Kraev. Zadachi, Samara State Technical Univ., Samara, 2010, 52–55 (In Russian)

[18] Zhdanov A. I., “Optimal regularization of solutions of approximate stochastic systems of linear algebraic equations”, U.S.S.R. Comput. Math. Math. Phys., 30:5 (1990), 224–229 | DOI | MR | Zbl

[19] Zhdanov A. I., “The method of augmented regularized normal equations”, Comput. Math. Math. Phys., 52:2 (2012), 194–197 | DOI | MR | Zbl

[20] Zhdanov A. I., “A modification of the iterative algorithm Kaczmarz”, Proceedings of the Seventh All-Russian Scientific Conference with international participation, Information technologies in mathematical modeling. Part 4 (3–6 June 2010), Matem. Mod. Kraev. Zadachi, Samara State Technical Univ., Samara, 2010, 75–77 (In Russian)