The row-oriented form of the regularized Kaczmarz’s method


Cite item

Full Text

Abstract

This paper presents the new iterative method for solving the standard Tikhonov regularization problem. The basis of the method is the application the projection Kaczmarz algorithm to the augmented regularized normal system of equations. The use of the augmented regularized normal system of equations, instead the system of regularized normal equations, makes it possible to significantly reduce the spectral condition number of the original problem. The paper presents the row-oriented form of the regularized Kaczmarz algorithm. This form of the regularized Kaczmarz algorithm allows to solve problems in which the data are received sequentially (line by line). The proposed algorithm makes it possible to effectively calculate solutions of problems with sparse matrices of large and superlarge dimensions. The comparison’s results of the proposed row-oriented form of the algorithm with the column-oriented form of this algorithm are presented. By considering a certain classes of problems, the paper demonstrates that the proposed form of the regularized algorithm allows to reduce the number of iterations in comparison with the column-oriented form of the algorithm.

About the authors

Alexander I Zhdanov

Samara State Technical University

Email: zhdanovaleksan@yandex.ru
Dr. Phys. & Math. Sci., Professor; Head of Department; Dept. of Higher Mathematics & Applied Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

Yuri V Sidorov

Samara State Technical University

Email: linuxboy2007@gmail.com
Senior Lecturer; Dept. of Higher Mathematics & Applied Computer Science 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

  1. Saad Y. Iterative Methods for Sparse Linear Systems. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2003. xviii+528 pp. doi: 10.1137/1.9780898718003.
  2. Kaczmarz S. Angenäherte Auflösung von Systemen linearer Gleichungen // Bull. Int. Acad. Polon. Sci. A, 1937. no. 35. pp. 355-357 ; Kaczmarz S. Approximate solution of systems of linear equations // Int. J. Control, 1993. vol. 57, no. 6. pp. 1269-1271. doi: 10.1080/00207179308934446.
  3. Gordon R., Bender R., Herman G. T. Algebraic Reconstruction Techniques (ART) for threedimensional electron microscopy and X-ray photography // J. Theor. Biol., 1970. vol. 29, no. 3. pp. 477-481. doi: 10.1016/0022-5193(70)90109-8.
  4. Strohmer T., Vershynin R. A Randomized Kaczmarz Algorithm with Exponential Convergence // J. Fourier Anal. Appl., 2009. vol. 15. pp. 262-278, arXiv: math/0702226 [math.NA]. doi: 10.1007/s00041-008-9030-4.
  5. Needell D. Randomized Kaczmarz solver for noisy linear systems // BIT Numer. Math., 2010. vol. 50, no. 2. pp. 395-403, arXiv: 0902.0958 [math.NA]. doi: 10.1007/s10543-010-0265-5.
  6. Needell D., Tropp J. A. Paved with good intentions: Analysis of randomized block Kaczmarz method // Linear Alg. Appl., 2014. vol. 441. pp. 199-221, arXiv: 1208.3805 [math.NA]. doi: 10.1016/j.laa.2012.12.022.
  7. Needell D., Zhao R., Zouzias A. Randomized block Kaczmarz method with projection for solving least squares // Linear Alg. Appl., 2015. vol. 484. pp. 322-343, arXiv: 1403.4192 [math.NA]. doi: 10.1016/j.laa.2015.06.027.
  8. Gower R., Richtarik P. Randomized Iterative Methods for Linear Systems // SIAM. J. Matrix Anal. Appl., 2015. vol. 36, no. 4. pp. 1660-1690, arXiv: 1506.03296 [math.NA]. doi: 10.1137/15M1025487.
  9. Wei K. Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study // Inverse Problems, 2015. vol. 31, no. 12, 125008, arXiv: 1502.01822 [math.NA]. doi: 10.1088/0266-5611/31/12/125008.
  10. Shin Y., Xiu D. A Randomized Algorithm for Multivariate Function Approximation // SIAM J. Sci. Comput., 2017. vol. 39, no. 3. pp. A983-A1002. doi: 10.1137/16M1075193.
  11. Ivanov A., Zhdanov A. Kaczmarz algorithm for Tikhonov regularization problem // Appl. Math. E-Notes, 2013. vol. 13. pp. 270-276.
  12. Жданов А. И. Метод расширенных регуляризованных нормальных уравнений // Ж. вычисл. матем. и матем. физ., 2012. Т. 52, № 2. С. 205-208.
  13. Tanabe K. Projection Method for Solving a Singular System of Linear Equations and its Applications // Numer. Math., 1971. vol. 17, no. 3. pp. 203-214. doi: 10.1007/BF01436376.
  14. Ильин В. П. Об итерационном методе Качмажа и его обобщениях // Сиб. журн. индустр. матем., 2006. Т. 9, № 3. С. 39-49.
  15. Жданов А. И., Сидоров Ю. В. Параллельная реализация рандомизированного регуляризованного алгоритма Качмажа // Комп. оптика, 2015. Т. 39, № 4. С. 536-541. doi: 10.18287/0134-2452-2015-39-4-536-541.
  16. Liu Ji, Wright S. J., Sridhar S. An Asynchronous Parallel Randomized Kaczmarz Algorithm, 2014, arXiv: 1401.4780 [math.NA].
  17. Hefny A., Needell D., Ramdas A. Rows versus Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression // SIAM J. Sci. Comput., 2017. vol. 39, no. 5. pp. S528-S542, arXiv: 1507.05844 [math.NA]. doi: 10.1137/16M1077891.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2017 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).