No Access

KACZMARZ ALGORITHM AND FRAMES

WOJCIECH CZAJA

Department of Mathematics, University of Maryland, College Park, MD 20742, USA

Search for more papers by this author

and

JAMES H. TANIS

Department of Mathematics, Rice University, Houston, TX 77251, USA

Search for more papers by this author

https://doi.org/10.1142/S0219691313500367Cited by:5 (Source: Crossref)

Abstract

Sequences of unit vectors for which the Kaczmarz algorithm always converges in Hilbert space can be characterized in frame theory by tight frames with constant 1. We generalize this result to the context of frames and bases. In particular, we show that the only effective sequences which are Riesz bases are orthonormal bases. Moreover, we consider the infinite system of linear algebraic equations Ax = b and characterize the (bounded) matrices A for which the Kaczmarz algorithm always converges to a solution.

Keywords:

AMSC: 22E46, 53C35, 57S20

References

J. P. Antoine, P. Balazs and A. Gryboś, Int. J. Wavelets, Multiresolut. Inf. Process. 8(1), 109 (2010). Link, Web of Science, Google Scholar
P. Balazs, P. Søndergaard and B. Torrésani, Int. J. Wavelets, Multiresolut. Inf. Process. 10(4), 1250032 (2012). Link, Web of Science, Google Scholar
R. Bender , R. Gordon and G. T. Herman , J. Theoretical Biol. 29 , 471 ( 1970 ) . Crossref, Web of Science, Google Scholar
J. J. Benedetto, Wavelets: A Tutorial in Theory and Applications, ed. C. K. Chui (CRC Press, Boca Raton, 1992) pp. 445–507. Crossref, Google Scholar
J. J. Benedetto, Wavelets: Mathematics and Applications, eds. J. Benedetto and M. Frazier (CRC Press, Boca Raton, FL, 1994) pp. 247–304. Google Scholar
J. J. Benedetto, C. Heil and D. F. Walnut, J. Fourier Anal. Appl. 1(4), 355 (1995). Crossref, Google Scholar
Y. Cai , Y. Tang and Y. Zhao , Adv. Intell. Soft Comput. 145 , 467 ( 2012 ) . Crossref, Google Scholar
H. X. Cao and Y. Zhang, Acta Mathematica Sinica (Chinese Series) 53(2), 209 (2010). Google Scholar
A. Cegielski, A list of publications on the Kaczmarz method (2013), http://www.wmie.uz.zgora.pl/acegiels/Publikacje-Kaczmarz.pdf . Google Scholar
Y. Censor, G. T. Herman and M. Jiang, J. Fourier Anal. Appl. 15(4), 431 (2009). Crossref, Web of Science, Google Scholar
X. Chen and A. M. Powell, J. Fourier Anal. Appl. 18(6), 1195 (2012). Crossref, Web of Science, Google Scholar
O. Christensen , An introduction to frames and Riesz bases , Applied and Numer. Harmonic Anal ( Birkhäuser , Boston , 2003 ) . Crossref, Google Scholar
R. J. Duffin and A. C. Schaeffer , Trans. Amer. Math. Soc. 72 , 341 ( 1952 ) . Crossref, Web of Science, Google Scholar
M. Ehler, Int. J. Wavelets, Multiresolut. Inf. Process. 6(2), 183 (2008). Link, Web of Science, Google Scholar
Y. C. Eldar and D. Needell, Numerical Algorithms 58(2), 163 (2011). Crossref, Web of Science, Google Scholar
R. Haller and R. Szwarc, Studia Math. 169(2), 123 (2005). Crossref, Web of Science, Google Scholar
G. T. Herman , Fundamentals of Computerized Tomography: Image Reconstruction from Projections , 2nd edn. ( Springer , Berlin-Heidelburg , 2010 ) . Google Scholar
D. Needell, BIT Numer. Math. 50(2), 395 (2010). Crossref, Web of Science, Google Scholar
D. Needell and J. A. Tropp, Paved with good intentions: Analysis of a randomized block kaczmarz method, to appear in Linear Algebra and its Appl . Google Scholar
S. Kaczmarz , Bull. Acad. Polon. Sci. Lett. A 35 , 355 ( 1937 ) . Google Scholar
S. Kaczmarz, Int. J. Control 57(6), 1269 (1993). Crossref, Web of Science, Google Scholar
S. Kwapień and J. Mycielski, Studia Math. 148(1), 75 (2001). Crossref, Web of Science, Google Scholar
S. F. McCormick, Indiana Univ. Math. J. 26(6), 1137 (1977). Crossref, Web of Science, Google Scholar
T. Strohmer and R. Vershynin, J. Fourier Anal. Appl. 15(2), 262 (2009). Crossref, Web of Science, Google Scholar
T. Strohmer and R. Vershynin, A randomized solver for linear systems with exponential convergence, Proc. RANDOM 2006, 10th Int. Workshop on Randomization and Computation4110, Lecture Notes in Comp. Sci (Springer, Berlin-Heidelburg, 2006) pp. 499–507. Google Scholar
T. Strohmer and R. Vershynin, J. Fourier Anal. Appl. 15(4), 437 (2009). Crossref, Web of Science, Google Scholar
R. Szwarc, Appl. Comput. Harmon. Anal. 22(3), 382 (2007). Crossref, Web of Science, Google Scholar