Abstract
The Kaczmarz algorithm is an iterative method to reconstruct an unknown vector f from inner products \(\langle f , \varphi _{n} \rangle \). We consider the problem of how additive noise affects the reconstruction under the assumption that \(\{ \varphi _{n} \}\) form a stationary sequence. Unlike other reconstruction methods, such as frame reconstructions, the Kaczmarz reconstruction is unstable in the presence of noise. We show, however, that the reconstruction can be stabilized by relaxing the Kaczmarz algorithm; this relaxation corresponds to Abel summation when viewed as a reconstruction on the unit disc. We show, moreover, that for certain noise profiles, such as those that lie in \(H^{\infty }(\mathbb {D})\) or certain subspaces of \(H^{2}(\mathbb {D})\), the relaxed version of the Kaczmarz algorithm can fully remove the corruption by noise in the inner products. Using the spectral representation of stationary sequences, we show that our relaxed version of the Kaczmarz algorithm also stabilizes the reconstruction of Fourier series expansions in \(L^2(\mu )\) when \(\mu \) is singular.
Similar content being viewed by others
References
Aboud, A., Curl, E., Harding, S.N., Vaughan, M., Weber, E.S.: The dual Kaczmarz algorithm. Acta Appl. Math. (2019). https://doi.org/10.1007/s10440-019-00244-6
Aleksandrov, A.B.: Inner functions and related spaces of pseudocontinuable functions. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 170 (1989). no. Issled. Lineĭn. Oper. Teorii Funktsiĭ. 17, 7–33, 321
Beurling, A.: On two problems concerning linear transformations in Hilbert space. Acta Math. 81, 17 (1948)
Casazza, P.: The art of frame theory. Taiwan. J. Math. 4(2), 129–201 (2000)
Clark, D.N.: One dimensional perturbations of restricted shifts. J. Anal. Math. 25, 169–191 (1972)
Chen, X., Powell, A.M.: Randomized subspace actions and fusion frames. Constr. Approx. 43(1), 103–134 (2016)
Czaja, W., Tanis, J.H.: Kaczmarz algorithm and frames. Int. J. Wavelets Multiresolut. Inf. Process. 11(5), 1350036 (2013)
de Branges, L., Rovnyak, J.: Square Summable Power Series. Holt, Rinehart and Winston, New York (1966)
Daubechies, I., Grossmann, A., Meyer, Y.: Painless nonorthogonal expansions. J. Math. Phys. 27(5), 1271–1283 (1986)
Dutkay, D.E., Han, D., Weber, E.: Continuous and discrete Fourier frames for fractal measures. Trans. Am. Math. Soc. 366(3), 1213–1235 (2014)
Duffin, R., Schaeffer, A.: A class of nonharmonic Fourier series. Trans. Am. Math. Soc. 72, 341–366 (1952)
Eggermont, P.P.B., Herman, G.T., Lent, A.: Iterative algorithms for large partitioned linear systems, with applications to image reconstruction. Linear Algebra Appl. 40, 37–67 (1981)
Gordon, R., Bender, R., Herman, G.: Algebraic reconstruction techniques (ART) for threedimensional electron microscopy and x-ray photography. J. Theor. Biol. 29(3), 471–481 (1970)
Herr, J.E.: Fourier series for singular measures and the Kaczmarz algorithm. Thesis (Ph.D.), Iowa State University. ProQuest LLC, Ann Arbor (2016). http://lib.dr.iastate.edu/etd/14978/. Accessed 5 Apr 2019
Herr, J.E., Jorgensen, P.E.T., Weber, E.S.: Positive matrices in the Hardy space with prescribed boundary representations via the Kaczmarz algorithm. To appear in J. Anal. Math. (2016). arXiv:1603.08852v1
Herr, J.E., Jorgensen, P.E.T., Weber, E.S.: A matrix characterization of boundary representations of positive matrices in the Hardy space. In: Kim, Y., Narayan, S., Picioroaga, G., Weber, E.S. (eds.) Frames and Harmonic Analysis, Contemp. Math., vol. 706. American Mathematical Society, Providence, pp. 255–270 (2018)
Herr, J.E., Jorgensen, P.E.T., Weber, E.S.: Harmonic analysis of fractal measures: basis and frame algorithms. To appear in Analysis, Probability and Mathematical Physics on Fractals. Fractals and Dynamics in Mathematics, Science, and the Arts (2019)
Hegde, C., Keinert, F., Weber, E.S.: A Kaczmarz algorithm for tree based distributed systems of equations. Preprint (2019). arXiv:1904.05732
Haller, R., Szwarc, R.: Kaczmarz algorithm in Hilbert space. Studia Math. 169(2), 123–132 (2005)
Herr, J.E., Weber, E.S.: Fourier series for singular measures. Axioms 6(2), 7 (2017). https://doi.org/10.3390/axioms6020007
Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bulletin International de l’Académie Plonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A. Sciences Mathématiques 35, 355–357 (1937)
Kwapień, S., Mycielski, J.: On the Kaczmarz algorithm of approximation in infinite-dimensional spaces. Studia Math. 148(1), 75–86 (2001)
Koosis, P.: Introduction to \(H_p\) Spaces. Cambridge Tracts in Mathematics, vol. 115, 2nd edn. Cambridge University Press, Cambridge (1998). (With two appendices by V. P. Havin [Viktor Petrovich Khavin])
Natterer, F.: The Mathematics of Computerized Tomography. Teubner, Stuttgart (1986)
Nikol’skiĭ, N.K.: Treatise on the Shift Operator. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Berlin (1986). (Spectral function theory, With an appendix by S. V. Hruščev [S. V. Khrushchëv] and V. V. Peller, Translated from the Russian by Jaak Peetre)
Needell, D., Srebro, N., Ward, R.: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program. 155(1–2), 549–573 (2016)
Needell, D., Zhao, R., Zouzias, A.: Randomized block Kaczmarz method with projection for solving least squares. Linear Algebra Appl. 484, 322–343 (2015)
Poltoratskiĭ, A.G.: Boundary behavior of pseudocontinuable functions. Algebra i Analiz 5(2), 189–210 (1993). English translation in St. Petersburg Math. 5(2), 389–406 (1994)
Sarason, D.: Sub-Hardy Hilbert Spaces in the Unit Disk. University of Arkansas Lecture Notes in the Mathematical Sciences, vol. 10. Wiley, New York (1994)
Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262–278 (2009)
Szwarc, R.: Kaczmarz algorithm in Hilbert space and tight frames. Appl. Comput. Harmon. Anal. 22(3), 382–385 (2007)
Tanabe, K.: Projection method for solving a singular system of linear equations and its application. Numer. Math. 17, 203–214 (1971)
Acknowledgements
Lee Przybylski and Eric Weber were supported in part by the National Science Foundation and National Geospatial-Intelligence Agency under award #1830254.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Daniel Aron Alpay.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
Proof of Proposition 2
The first statement follows from the second, but an alternative proof can be found in [10, Theorem 3.10]. The second statement follows from Fatou’s construction [23, Section II.A]. \(\square \)
Proof of Lemma 3
For the inner function \(b^{K}\), let \(\mu ^{K}\) denote the corresponding singular measure. By the Herglotz Representation, \(\mu<< \mu ^{K}\). Since by [28] every \(f \in H^2 \ominus b^{K} H^2\) has convergent Fourier series in \(L^2(\mu ^{K})\), it follows that the Fourier series also converges in \(L^2(\mu )\). \(\square \)
Rights and permissions
About this article
Cite this article
Camrud, C., Camrud, E., Przybylski, L. et al. Stability of the Kaczmarz Reconstruction for Stationary Sequences. Complex Anal. Oper. Theory 13, 3405–3427 (2019). https://doi.org/10.1007/s11785-019-00945-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11785-019-00945-8