×

A Kaczmarz algorithm for sequences of projections, infinite products, and applications to frames in IFS \(L^2\) spaces. (English) Zbl 1444.47078

Summary: We show that an idea, originating initially with a fundamental recursive iteration scheme (usually referred as “the” Kaczmarz algorithm), admits important applications in such infinite-dimensional, and non-commutative, settings as are central to spectral theory of operators in Hilbert space, to optimization, to large sparse systems, to iterated function systems (IFS), and to fractal harmonic analysis. We present a new recursive iteration scheme involving as input a prescribed sequence of selfadjoint projections. Applications include random Kaczmarz recursions, their limits, and their error-estimates.

MSC:

47L60 Algebras of unbounded operators; partial algebras of operators
46N30 Applications of functional analysis in probability theory and statistics
46N50 Applications of functional analysis in quantum physics
42C15 General harmonic expansions, frames
65R10 Numerical methods for integral transforms
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alpay, D., Jorgensen, P., Lewkowicz, I.: \(W\)-Markov measures, transfer operators, wavelets and multiresolutions. In: Frames and harmonic analysis, volume 706 of Contemp. Math., pp. 293-343. Amer. Math. Soc., Providence, RI (2018) · Zbl 1398.37020
[2] Aronszajn, N., Theory of reproducing kernels, Trans. Am. Math. Soc., 68, 337-404 (1950) · Zbl 0037.20701
[3] Baranov, A., Sarason, D.: Quotient representations of inner functions. In: Recent Trends in Analysis, volume 16 of Theta Ser. Adv. Math., pp. 35-46. Theta, Bucharest (2013) · Zbl 1299.30135
[4] Barnsley, MF; Hutchinson, JE; Stenflo, Ö., \(V\)-variable fractals: fractals with partial self similarity, Adv. Math., 218, 6, 2051-2088 (2008) · Zbl 1169.28006
[5] Bauschke, HH, A norm convergence result on random products of relaxed projections in Hilbert space, Trans. Am. Math. Soc., 347, 4, 1365-1373 (1995) · Zbl 0832.47055
[6] Bemrose, T.; Casazza, PG; Kaftal, V.; Lynch, RG, The unconditional constants for Hilbert space frame expansions, Linear Algebra Appl., 521, 1-18 (2017) · Zbl 1360.42018
[7] Candès, EJ; Eldar, YC; Strohmer, T.; Voroninski, V., Phase retrieval via matrix completion [reprint of MR3032952], SIAM Rev., 57, 2, 225-251 (2015) · Zbl 1344.49057
[8] Casazza, PG; Haas, JI, On Grassmannian frames with spectral constraints, Sample Theory Signal Image Process., 17, 1, 17-28 (2018) · Zbl 1417.42033
[9] Casazza, P.G., Kutyniok, G.: Frames of subspaces. In: Wavelets, Frames and Operator Theory, volume 345 of Contemp. Math., pp. 87-113. Amer. Math. Soc., Providence, RI (2004) · Zbl 1058.42019
[10] Casazza, P.G., Kutyniok, G.: Robustness of fusion frames under erasures of subspaces and of local frame vectors. In: Radon Transforms, Geometry, and Wavelets, volume 464 of Contemp. Math., pp. 149-160. Amer. Math. Soc., Providence, RI (2008) · Zbl 1256.94017
[11] Casazza, PG; Kutyniok, G.; Li, S., Fusion frames and distributed processing, Appl. Comput. Harmon. Anal., 25, 1, 114-132 (2008) · Zbl 1258.42029
[12] Chen, X.: The Kaczmarz algorithm, row action methods, and statistical learning algorithms. In: Frames and harmonic analysis, volume 706 of Contemp. Math., pp. 115-127. Amer. Math. Soc., Providence, RI (2018) · Zbl 1401.65032
[13] Chen, Y.; Candès, EJ, The projected power method: an efficient algorithm for joint alignment from pairwise differences, Comm. Pure Appl. Math., 71, 8, 1648-1714 (2018) · Zbl 1480.90199
[14] Czaja, W.; Tanis, JH, Kaczmarz algorithm and frames, Int. J. Wavelets Multiresolut. Inf. Process, 11, 5, 1350036 (2013) · Zbl 1279.65057
[15] Dutkay, DE; Jorgensen, PET, Fourier frequencies in affine iterated function systems, J. Funct. Anal., 247, 1, 110-137 (2007) · Zbl 1128.42013
[16] Ehler, M., Okoudjou, K.A.: Probabilistic frames: an overview. In: Finite frames, Appl. Numer. Harmon. Anal., pp. 415-436. Birkhäuser/Springer, New York (2013) · Zbl 1262.42013
[17] Eldar, YC; Needell, D., Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, Numer. Algorithms, 58, 2, 163-177 (2011) · Zbl 1230.65051
[18] Evans, DJ; Popa, C., Projections and preconditioning for inconsistent least-squares problems, Int. J. Comput. Math., 78, 4, 599-616 (2001) · Zbl 1005.65037
[19] Fickus, M.; Johnson, BD; Kornelson, K.; Okoudjou, KA, Convolutional frames and the frame potential, Appl. Comput. Harmon. Anal., 19, 1, 77-91 (2005) · Zbl 1067.42017
[20] Friedlander, B., A subspace method for space time adaptive processing, IEEE Trans. Signal Process., 53, 1, 74-82 (2005) · Zbl 1370.94122
[21] Führ, H.; Lemvig, J., System bandwidth and the existence of generalized shift-invariant frames, J. Funct. Anal., 276, 2, 563-601 (2019) · Zbl 1407.42023
[22] Haller, R.; Szwarc, R., Kaczmarz algorithm in Hilbert space, Stud. Math., 169, 2, 123-132 (2005) · Zbl 1102.41031
[23] Han, D., Kornelson, K., Larson, D., Weber, E.: Frames for undergraduates. Student Mathematical Library, vol. 40. American Mathematical Society, Providence, RI (2007) · Zbl 1143.42001
[24] Han, D.; Larson, DR; Liu, R., Dilations of operator-valued measures with bounded \(p\)-variations and framings on Banach spaces, J. Funct. Anal., 274, 5, 1466-1490 (2018) · Zbl 1391.46052
[25] Herr, J.E., Jorgensen, P.E.T., Weber, E.S.: A matrix characterization of boundary representations of positive matrices in the Hardy space. In: Frames and harmonic analysis, volume 706 of Contemp. Math., pp. 255-270. Amer. Math. Soc., Providence, RI, (2018) · Zbl 1407.46021
[26] Herr, JE; Jorgensen, PET; Weber, ES, Positive matrices in the Hardy space with prescribed boundary representations via the Kaczmarz algorithm, J. Anal. Math., 138, 1, 209-234 (2019) · Zbl 1428.30044
[27] Herr, JE; Jorgensen, PET; Weber, ES, A characterization of boundary representations of positive matrices in the hardy space via the abel product, Linear Algebra Appl, 576, 51-66 (2019) · Zbl 1429.46019
[28] Hida, T.: Brownian motion, volume 11 of Applications of Mathematics. Springer-Verlag, New York-Berlin, 1980. Translated from the Japanese by the author and T. P. Speed · Zbl 0423.60063
[29] Hotovy, R.; Larson, DR; Scholze, S., Binary frames, Houston J. Math., 41, 3, 875-899 (2015) · Zbl 1342.42032
[30] Huang, J.; Huang, T-Z, A nonstationary accelerating alternating direction method for frame-based Poissonian image deblurring, J. Comput. Appl. Math., 352, 181-193 (2019) · Zbl 1454.94016
[31] Hutchinson, JE, Fractals and self-similarity, Indiana Univ. Math. J., 30, 5, 713-747 (1981) · Zbl 0598.28011
[32] Hutchinson, JE, Fractals: a mathematical framework, Complex. Int., 2, 14 (1995) · Zbl 0971.28501
[33] Ivanov, AI; Zhdanov, AI, Kaczmarz algorithm for Tikhonov regularization problem, Appl. Math. E-Notes, 13, 270-276 (2013) · Zbl 1288.65056
[34] Jorgensen, P., Tian, F.: Non-commutative Analysis. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2017. With a foreword by Wayne Polyzou · Zbl 1371.46003
[35] Jorgensen, PET; Song, M-S, Entropy encoding, Hilbert space, and Karhunen-Loève transforms, J. Math. Phys., 48, 10, 103503 (2007) · Zbl 1152.81498
[36] Jorgensen, PET; Song, M-S, Infinite-dimensional measure spaces and frame analysis, Acta Appl. Math., 155, 41-56 (2018) · Zbl 1405.60006
[37] Jorgensen, PET; Song, M-S, Markov chains and generalized wavelet multiresolutions, J. Anal., 26, 2, 259-283 (2018) · Zbl 1402.60094
[38] Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bulletin International de l’Académie Polonaise des Sciences et des Lettres, 35, 355-357 (1937) · Zbl 0017.31703
[39] Kaftal, V.; Larson, DR, Admissible sequences of positive operators, Trans. Am. Math. Soc., 371, 5, 3721-3742 (2019) · Zbl 1507.47043
[40] Kakutani, S., Notes on infinite product measure spaces, II. Proc. Imp. Acad. Tokyo, 19, 184-188 (1943) · Zbl 0061.09701
[41] Kakutani, S., On equivalence of infinite product measures, Ann. Math., 2, 49, 214-224 (1948) · Zbl 0030.02303
[42] Khader, MM; Adel, M., Introducing the windowed Fourier frames technique for obtaining the approximate solution of the coupled system of differential equations, J. Pseudo-Differ. Oper. Appl., 10, 1, 241-256 (2019) · Zbl 1416.34014
[43] Kolmogorov, A. N.: On logical foundations of probability theory. In Probability theory and mathematical statistics (Tbilisi, 1982), volume 1021 of Lecture Notes in Math., pp. 1-5. Springer, Berlin, (1983) · Zbl 0519.60002
[44] Kwapień, S., Mycielski, J.: Erratum to the paper: “On the Kaczmarz algorithm of approximation in infinite-dimensional spaces” [Studia Math. 148 (2001), no. 1, 75-86; mr1881441]. Studia Math., 176(1):93, (2006) · Zbl 0987.41020
[45] Lin, J.; Zhou, D-X, Learning theory of randomized Kaczmarz algorithm, J. Mach. Learn. Res., 16, 3341-3365 (2015) · Zbl 1351.62133
[46] Ling, S.; Strohmer, T., Self-calibration and biconvex compressive sensing, Inverse Probl., 31, 11, 115002 (2015) · Zbl 1327.93183
[47] Needell, D.; Srebro, N.; Ward, R., Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Math. Program., 155, 1-2, 549-573 (2016) · Zbl 1333.65070
[48] Netyanun, A.; Solmon, DC, Iterated products of projections in Hilbert space, Am. Math. Mon, 113, 7, 644-648 (2006) · Zbl 1154.46011
[49] Okoudjou, K.A.: Preconditioning techniques in frame theory and probabilistic frames. In Finite frame theory, volume 73 of Proc. Sympos. Appl. Math., pp. 105-142. Amer. Math. Soc., Providence, RI, (2016) · Zbl 1356.42024
[50] Okoudjou, KA; Strichartz, RS, Asymptotics of eigenvalue clusters for Schrödinger operators on the Sierpiński gasket, Proc. Am. Math. Soc., 135, 8, 2453-2459 (2007) · Zbl 1117.35059
[51] Popa, C.: Oblique projections as preconditioner in Kaczmarz-like algorithms. In Proceedings of the Ninth Symposium of Mathematics and its Applications, pp. 118-122. Rom. Acad., Timişoara, (2001)
[52] Popa, C., A hybrid Kaczmarz-conjugate gradient algorithm for image reconstruction, Math. Comput. Simul., 80, 12, 2272-2285 (2010) · Zbl 1194.94038
[53] Popa, C., Convergence rates for Kaczmarz-type algorithms, Numer. Algorithms, 79, 1, 1-17 (2018) · Zbl 1398.65049
[54] Ruelle, D., Analycity properties of the characteristic exponents of random matrix products, Adv. Math., 32, 1, 68-80 (1979) · Zbl 0426.58018
[55] Ruelle, D., Characteristic exponents and invariant manifolds in Hilbert space, Ann. Math., 115, 2, 243-290 (1982) · Zbl 0493.58015
[56] Ruelle, D.: Thermodynamic formalism. Cambridge Mathematical Library. Cambridge University Press, Cambridge, second edition, 2004. The mathematical structures of equilibrium statistical mechanics · Zbl 1062.82001
[57] Ruelle, D.; Takens, F., On the nature of turbulence, Comm. Math. Phys., 20, 167-192 (1971) · Zbl 0223.76041
[58] Sarason, D.: Sub-Hardy Hilbert spaces in the unit disk, volume 10 of University of Arkansas Lecture Notes in the Mathematical Sciences. Wiley, New York, 1994. A Wiley-Interscience Publication · Zbl 1253.30002
[59] Soltanolkotabi, M.; Elhamifar, E.; Candès, EJ, Robust subspace clustering, Ann. Stat., 42, 2, 669-699 (2014) · Zbl 1360.62353
[60] Strohmer, T.; Vershynin, R., A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 2, 262-278 (2009) · Zbl 1169.68052
[61] Szwarc, R., Kaczmarz algorithm in Hilbert space and tight frames, Appl. Comput. Harmon. Anal., 22, 3, 382-385 (2007) · Zbl 1109.41022
[62] Wickman, C.; Okoudjou, K., Duality and geodesics for probabilistic frames, Linear Algebra Appl., 532, 198-221 (2017) · Zbl 1376.42046
[63] Zhang, J-J, A new greedy Kaczmarz algorithm for the solution of very large linear systems, Appl. Math. Lett., 91, 207-212 (2019) · Zbl 1409.65020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.