Kaczmarz algorithm revisited

• Autorzy: Sznajder R.

Identyfikatory

DOI

10.4467/2353737XCT.15.220.4425

Warianty tytułu

PL

Jeszcze o algorytmie Kaczmarza

• Języki publikacji: EN

Abstrakty

EN

In 1937, Stefan Kaczmarz proposed a simple method, called the Kaczmarz algorithm, to solve iteratively systems of linear equations Ax = b in Euclidean spaces. This procedure employs cyclic orthogonal projections onto the hyperplanes associated with such a system. In the case of a nonsingular matrix A, Kaczmarz showed that his method guarantees convergence to the solution of Ax = b. The Kaczmarz algorithm was rediscovered in 1948 and became an important tool in medical engineering. We briefly discuss generalizations of this method and its ramifications, including applications in computer tomography, image processing and contemporary harmonic analysis.

PL

W 1937 roku Stefan Kaczmarz zaproponował prostą metodę [KA], zwaną obecnie algorytmem Kaczmarza, za pomocą której można rozwiązywać iteracyjnie układy równań liniowych Ax = b w przestrzeniach euklidesowych. Metoda ta używa cyklicznego ciągu rzutów ortogonalnych na hiperpłaszczyzny związane z tym układem. W przypadku macierzy odwracalnej A Kaczmarz pokazał, że jego metoda gwarantuje zbieżność do rozwiązania układu równań Ax = b. Metoda ta została ponownie odkryta w 1948 roku i stała się ważnym narzędziem w inżynierii medycznej. Omawiamy tutaj pokrótce uogólnienia tej metody i ich zastosowania w tomografii komputerowej, przetwarzaniu obrazów i we współczesnej analizie harmonicznej.

Słowa kluczowe

EN

Kaczmarz method; systems of linear equations; computer tomography; image reconstruction

PL

metoda Kaczmarza; układy równań liniowych; tomografia komputerowa; rekonstrukcja obrazu

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Nauki Podstawowe
• Rocznik: 2015
• Tom: Y. 112, iss. 2-NP
• Strony: 247--254
• Opis fizyczny: Bibliogr. 33 poz., wz., il.

Twórcy

autor

Sznajder R.

• Department of Mathematics, Bowie State University, USA

Bibliografia

• [1] Bauschke H.H., Borwein J.M., On projection algorithms for solving convex feasibility problems, SIAM Rev., 38(3), 1996, 367-426.
• [2] Bodewig E., Bericht über die verschiedenen Methoden zur Lösung eines System linearer Gleichungen mit reellen Koeffizienten. IV, V, Nederl. Akad. Wetensch., Proc. 51, 1948, 53-64, 211-219.
• [3] Briskman J., Block Kaczmarz Method with Inequalities, CMC Senior Theses. Paper 862, 2014, http://scholarship.claremont.edu/cmc_theses/862.
• [4] Brooks M.A., A Survey of Algebraic Algorithms in Computerized Tomography, MSc thesis, University of Ontario Insitute of Technology, 2010.
• [5] Byrne C.L., Iterative Algorithms in Tomography, University of Massachusetts Lowell, October 2005.
• [6] Byrne C.L., Applied Iterative Methods, A.K. Peters, Wellesley, MA, 2008.
• [7] Cegielski A., O algorytmie Kaczmarza, Wiad. Matematyczne, 46 (1), 2010, 27-35.
• [8] Cegielski A., Bibliography on the Kaczmarz method (up to 2010), www.wmie.uz.zgora.pl/pracownicy/ACegielski/index.html.
• [9] Cegielski A., Iterative Methods for Fixed Point Problems in Hilbert Spaces, LNM 2057, Springer, 2012.
• [10] Cimmino G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica, XVI, Series II, Anno IX 1, 1938, 326-333.
• [11] Czaja W., Tanis J., Kaczmarz Algorithm and Frames, International Journal of Wavelets, Multiresolution and Information Processing, September 11(5), 2013, 13 pages.
• [12] Dupont M., Tomographie spectrale à comptage de photons: développement du prototype PIXSCAN et preuve de concept, Thèse de doctorat, Aix-Marseille Université, Faculté des Sciences, CPPM-T, 2014.
• [13] Eldar Y.C., Needell D., Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma, Numerical Algorithms, 58(2) 2011, 163-177.
• [14] Forsythe G.E., Solving linear algebraic equations can be interesting, Bull. Amer. Math. Soc. 59, 1953, 299-329.
• [15] Gordon R., Bender R., Herman G.T., Algebraic Reconstruction Techniques (ART) for three-dimensional electron microscopy and X-ray photography, Journal of Theoretical Biology 29, 1970, 471-481.
• [16] Grangeat P., Analyse d’un systeme d’imagerie 3D par reconstruction à partir de radiographies X en géométrie conique, These de Doctorat, l’Ecole Nationale Superieure dés Télécommunications, 1987.
• [17] Haller R., Szwarc R., Kaczmarz algorithm in Hilbert paces, Studia Mathematica, 169(2), 2005, 123-132.
• [18] Jamil N., Needell D., Müller J., Lutteroth Ch., Weber G., Kaczmarz algorithm with soft constraints for user interface layout, arXiv:1309.7001v2, 2013.
• [19] Johnson W.B., Lindenstrauss J., Extensions of Lipschitz mappings into a Hilbert space, Conf. in Modern Analysis and Probability, 1984, 189-206.
• [20] Kaczmarz S., Steinhaus H., Theorie der Orthogonalreichen, Monografie Matematyczne, Tom VI, Warszawa‒Lwów 1935.
• [21] Kaczmarz S., Angenäherte Auflösung von Systemen linearer Gleichingen, Bull. Intern. Acad. Polonaise Sci. Lett., Cl. Sci. Math. Nat. A, 35, 1937, 355-357.
• [22] Kaczmarz S., Approximate solution of systems of linear equations, International Journal of Control 57, 1993, 1269-1271.
• [23] Kiwiel K., Block-iterative surrogate projection methods for convex feasibility problems, Linear Algebra Appl., 215, 1995, 225-259.
• [24] Kwapień S., Mycielski J., On the Kaczmarz algorithm of approximation in infinite-dimensional spaces, Studia Mathematica, 148(1), 2001, 75-86.
• [25] Maligranda L., Stefan Kaczmarz (1895‒1939), Antiquitates Mathematicae, 1, 2007, 15-62.
• [26] McCormick S.F., The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space, Indiana Univ. Math. J., 26(6), 1977, 1137-1150.
• [27] Needell D., Randomized Kaczmarz solver for noisy linear systems, BIT Numerical Mathematics, 50(2), 2010, 395-403.
• [28] Needell D., Tropp J.A., Paved with good intentions: Analysis of randomized block Kaczmarz method, Linear Algebra and its Applications, 441, 2014, 199-221.
• [29] Needell D., Srebro N., Ward R., Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm, Math. Progrogramming Series A, to appear.
• [30] Strohmer T., Vershynin R., A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 2009, 262-278.
• [31] Tanabe K., Projection method for solving a singular system of linear equations and its applications, Numer. Math. 17, 1971, 203-214.
• [32] Tompkins C., Projection methods in calculation of some linear problems, Bull. Amer. Math. Soc. 55, 1949, 520.
• [33] Zahavi A., Super Resoluton project, ISL Center for Intelligent System, 2001, http://www.cs.technion.ac.il/cis/Project/Projects_done/superResolution/Kaczmarz_real_good_example.htm.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.