The rate of convergence in the method of alternating projections

Badea, C.; Grivaux, S.; Müller, V.

doi:10.1090/S1061-0022-2012-01202-1

The rate of convergence in the method of alternating projections
HTML articles powered by AMS MathViewer

by C. Badea, S. Grivaux and V. Müller

St. Petersburg Math. J. 23 (2012), 413-434

DOI: https://doi.org/10.1090/S1061-0022-2012-01202-1

Published electronically: March 2, 2012

PDF | Request permission

Abstract:

The cosine of the Friedrichs angle between two subspaces is generalized to a parameter associated with several closed subspaces of a Hilbert space. This parameter is employed to analyze the rate of convergence in the von Neumann–Halperin method of cyclic alternating projections. General dichotomy theorems are proved, in the Hilbert or Banach space situation, providing conditions under which the alternative QUC/ASC (quick uniform convergence versus arbitrarily slow convergence) holds. Several meanings for ASC are proposed.

References

I. Amemiya and T. Andô, Convergence of random products of contractions in Hilbert space, Acta Sci. Math. (Szeged) 26 (1965), 239–244. MR 187116
N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
Catalin Badea and Yuri I. Lyubich, Geometric, spectral and asymptotic properties of averaged products of projections in Banach spaces, Studia Math. 201 (2010), no. 1, 21–35. MR 2733272, DOI 10.4064/sm201-1-2
C. Badea and V. Müller, On weak orbits of operators, Topology Appl. 156 (2009), no. 7, 1381–1385. MR 2502014, DOI 10.1016/j.topol.2008.12.020
Heinz H. Bauschke, Frank Deutsch, and Hein Hundal, Characterizing arbitrarily slow convergence in the method of alternating projections, Int. Trans. Oper. Res. 16 (2009), no. 4, 413–425. MR 2538248, DOI 10.1111/j.1475-3995.2008.00682.x
Heinz H. Bauschke and Jonathan M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev. 38 (1996), no. 3, 367–426. MR 1409591, DOI 10.1137/S0036144593251710
Heinz H. Bauschke, Jonathan M. Borwein, and Adrian S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995) Contemp. Math., vol. 204, Amer. Math. Soc., Providence, RI, 1997, pp. 1–38. MR 1442992, DOI 10.1090/conm/204/02620
Earl Berkson, Hermitian projections and orthogonality in Banach spaces, Proc. London Math. Soc. (3) 24 (1972), 101–118. MR 295123, DOI 10.1112/plms/s3-24.1.101
Ronald E. Bruck and Simeon Reich, Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston J. Math. 3 (1977), no. 4, 459–470. MR 470761
Frank Deutsch, Best approximation in inner product spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 7, Springer-Verlag, New York, 2001. MR 1823556, DOI 10.1007/978-1-4684-9298-9
Frank Deutsch, Rate of convergence of the method of alternating projections, Parametric optimization and approximation (Oberwolfach, 1983) Internat. Schriftenreihe Numer. Math., vol. 72, Birkhäuser, Basel, 1985, pp. 96–107. MR 882199
Frank Deutsch, The angle between subspaces of a Hilbert space, Approximation theory, wavelets and applications (Maratea, 1994) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 454, Kluwer Acad. Publ., Dordrecht, 1995, pp. 107–130. MR 1340886
Frank Deutsch and Hein Hundal, The rate of convergence for the method of alternating projections. II, J. Math. Anal. Appl. 205 (1997), no. 2, 381–405. MR 1428355, DOI 10.1006/jmaa.1997.5202
John Dye, Convergence of random products of compact contractions in Hilbert space, Integral Equations Operator Theory 12 (1989), no. 1, 12–22. MR 973044, DOI 10.1007/BF01199754
J. Dye, M. A. Khamsi, and S. Reich, Random products of contractions in Banach spaces, Trans. Amer. Math. Soc. 325 (1991), no. 1, 87–99. MR 989572, DOI 10.1090/S0002-9947-1991-0989572-5
Israel Halperin, The product of projection operators, Acta Sci. Math. (Szeged) 23 (1962), 96–99. MR 141978
Selahattin Kayalar and Howard L. Weinert, Error bounds for the method of alternating projections, Math. Control Signals Systems 1 (1988), no. 1, 43–59. MR 923275, DOI 10.1007/BF02551235
Tosio Kato, Perturbation theory for linear operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition. MR 1335452
Bernd Kirchheim, Eva Kopecká, and Stefan Müller, Do projections stay close together?, J. Math. Anal. Appl. 350 (2009), no. 2, 859–871. MR 2474817, DOI 10.1016/j.jmaa.2008.09.039
Y. Katznelson and L. Tzafriri, On power bounded operators, J. Funct. Anal. 68 (1986), no. 3, 313–328. MR 859138, DOI 10.1016/0022-1236(86)90101-1
Ulrich Krengel, Ergodic theorems, De Gruyter Studies in Mathematics, vol. 6, Walter de Gruyter & Co., Berlin, 1985. With a supplement by Antoine Brunel. MR 797411, DOI 10.1515/9783110844641
Michael Lin, On the uniform ergodic theorem, Proc. Amer. Math. Soc. 43 (1974), 337–340. MR 417821, DOI 10.1090/S0002-9939-1974-0417821-6
Joram Lindenstrauss and Lior Tzafriri, Classical Banach spaces. I, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 92, Springer-Verlag, Berlin-New York, 1977. Sequence spaces. MR 0500056
V. Müller, Power bounded operators and supercyclic vectors, Proc. Amer. Math. Soc. 131 (2003), no. 12, 3807–3812. MR 1999927, DOI 10.1090/S0002-9939-03-06962-4
V. Müller, Power bounded operators and supercyclic vectors. II, Proc. Amer. Math. Soc. 133 (2005), no. 10, 2997–3004. MR 2159778, DOI 10.1090/S0002-9939-05-07829-9
Vladimir Müller, Spectral theory of linear operators and spectral systems in Banach algebras, 2nd ed., Operator Theory: Advances and Applications, vol. 139, Birkhäuser Verlag, Basel, 2007. MR 2355630
John von Neumann, On rings of operators. Reduction theory, Ann. of Math. (2) 50 (1949), 401–485. MR 29101, DOI 10.2307/1969463
N. K. Nikol′skiĭ, Lektsii ob operatore sdviga, “Nauka”, Moscow, 1980 (Russian). MR 575166
G. Pierra, Decomposition through formalization in a product space, Math. Programming 28 (1984), no. 1, 96–115. MR 727421, DOI 10.1007/BF02612715
Makoto Sakai, Strong convergence of infinite products of orthogonal projections in Hilbert space, Appl. Anal. 59 (1995), no. 1-4, 109–120. MR 1378029, DOI 10.1080/00036819508840393
Kennan T. Smith, Donald C. Solmon, and Sheldon L. Wagner, Practical and mathematical aspects of the problem of reconstructing objects from radiographs, Bull. Amer. Math. Soc. 83 (1977), no. 6, 1227–1270. MR 490032, DOI 10.1090/S0002-9904-1977-14406-6
Jinchao Xu and Ludmil Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc. 15 (2002), no. 3, 573–597. MR 1896233, DOI 10.1090/S0894-0347-02-00398-3