Accelerating the convergence of the method of alternating projections
Authors:
Heinz H. Bauschke, Frank Deutsch, Hein Hundal and SungHo Park
Journal:
Trans. Amer. Math. Soc. 355 (2003), 34333461
MSC (2000):
Primary 41A65
Published electronically:
May 29, 2003
MathSciNet review:
1990157
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The powerful von NeumannHalperin method of alternating projections (MAP) is an algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces. It achieves this by reducing the problem to an iterative scheme which involves only computing best approximations from the individual subspaces which make up the intersection. The main practical drawback of this algorithm, at least for some applications, is that the method is slowly convergent. In this paper, we consider a general class of iterative methods which includes the MAP as a special case. For such methods, we study an ``accelerated'' version of this algorithm that was considered earlier by Gubin, Polyak, and Raik (1967) and by Gearhart and Koshy (1989). We show that the accelerated algorithm converges faster than the MAP in the case of two subspaces, but is, in general, not faster than the MAP for more than two subspaces! However, for a ``symmetric'' version of the MAP, the accelerated algorithm always converges faster for any number of subspaces. Our proof seems to require the use of the Spectral Theorem for selfadjoint mappings.
 1.
N.
Aronszajn, Theory of reproducing
kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 0051437
(14,479c), http://dx.doi.org/10.1090/S00029947195000514377
 2.
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
(98c:49069), http://dx.doi.org/10.1090/conm/204/02620
 3.
John
B. Conway, A course in functional analysis, 2nd ed., Graduate
Texts in Mathematics, vol. 96, SpringerVerlag, New York, 1990. MR 1070713
(91e:46001)
 4.
Lokenath
Debnath and Piotr
Mikusiński, Introduction to Hilbert spaces with
applications, 2nd ed., Academic Press, Inc., San Diego, CA, 1999. MR 1670332
(99k:46001)
 5.
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
(88d:41026)
 6.
Frank
Deutsch, The method of alternating orthogonal projections,
Approximation theory, spline functions and applications (Maratea, 1991),
NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 356, Kluwer Acad.
Publ., Dordrecht, 1992, pp. 105–121. MR 1165964
(93a:41047)
 7.
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
(96e:46027)
 8.
Frank
Deutsch and Hein
Hundal, The rate of convergence of Dykstra’s cyclic
projections algorithm: the polyhedral case, Numer. Funct. Anal. Optim.
15 (1994), no. 56, 537–565. MR 1281561
(95f:49047), http://dx.doi.org/10.1080/01630569408816580
 9.
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
(97i:41025), http://dx.doi.org/10.1006/jmaa.1997.5202
 10.
J. Dyer, Acceleration of the convergence of the Kaczmarz method and iterated homogeneous transformations, doctoral dissertation (1965).
 11.
C.
Franchetti and W.
Light, On the von Neumann alternating algorithm in Hilbert
space, J. Math. Anal. Appl. 114 (1986), no. 2,
305–314. MR
833588 (87f:41058), http://dx.doi.org/10.1016/0022247X(86)900855
 12.
K. Friedrichs, On certain inequalities and characteristic value problems for analytic functions and functions of two variables, Trans. Amer. Math. Soc. 41 (1937), 321364.
 13.
William
B. Gearhart and Mathew
Koshy, Acceleration schemes for the method of alternating
projections, J. Comput. Appl. Math. 26 (1989),
no. 3, 235–249. MR 1010558
(90h:65095), http://dx.doi.org/10.1016/03770427(89)902963
 14.
L. G. Gubin, B. T. Polyak, and E. V. Raik, The method of projections for finding the common point of convex sets, USSR Computational Mathematics and Mathematical Physics 7(6) (1967), 124.
 15.
Israel
Halperin, The product of projection operators, Acta Sci. Math.
(Szeged) 23 (1962), 96–99. MR 0141978
(25 #5373)
 16.
Martin
Hanke and Wilhelm
Niethammer, On the acceleration of Kaczmarz’s method for
inconsistent linear systems, Linear Algebra Appl. 130
(1990), 83–98. Linear algebra in image reconstruction from
projections. MR
1057802 (91f:65065), http://dx.doi.org/10.1016/00243795(90)90207S
 17.
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
(89b:65137), http://dx.doi.org/10.1007/BF02551235
 18.
John
von Neumann, Functional Operators. II. The Geometry of Orthogonal
Spaces, Annals of Mathematics Studies, no. 22, Princeton University
Press, Princeton, N. J., 1950. MR 0034514
(11,599e)
 19.
Friedrich
Riesz and Béla
v. Sz. Nagy, Über Kontraktionen des Hilbertschen Raumes,
Acta Univ. Szeged. Sect. Sci. Math. 10 (1943),
202–205 (German). MR 0016556
(8,35a)
 20.
Frigyes
Riesz and Béla
Sz.Nagy, Functional analysis, Frederick Ungar Publishing Co.,
New York, 1955. Translated by Leo F. Boron. MR 0071727
(17,175i)
 21.
R. Smarzewski, Iterative recovering of orthogonal projections, preprint (December, 1996).
 22.
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 0490032
(58 #9394a), http://dx.doi.org/10.1090/S000299041977144066
 1.
 N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc., 68(1950), 337404. MR 14:479c
 2.
 H. H. Bauschke, J. M. Borwein, and A. S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995), 138, Contemporary Mathematics 204, Amer. Math. Soc., Providence, R.I., 1997. MR 98c:49069
 3.
 J. B. Conway, A Course in Functional Analysis (second edition), Graduate Texts in Mathematics 96, SpringerVerlag, New York, 1990. MR 91e:46001
 4.
 L. Debnath and P. Mikusinski, Introduction to Hilbert Spaces with Applications (second edition), Academic Press, San Diego, CA, 1999. MR 99k:46001
 5.
 F. Deutsch, Rate of convergence of the method of alternating projections, Parametric Optimization and Approximation, ISNM 72 (B. Brosowski and F. Deutsch, eds.), Birkhäuser, Basel, 1985, pp. 96107. MR 88d:41026
 6.
 F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications (S. P. Singh, ed.), Kluwer Academic Publ., Dordrecht, 1992, pp. 105121. MR 93a:41047
 7.
 F. Deutsch, The angle between subspaces of a Hilbert space, in Approximation Theory, Wavelets and Applications (S.P. Singh, ed.), Kluwer Academic Publ., Dordrecht, pp. 107130. MR 96e:46027
 8.
 F. Deutsch and H. Hundal, The rate of convergence of Dykstra's cyclic projections algorithm: the polyhedral case, Numer. Funct. Anal. and Optimiz. 15 no. 56 (1994), 537565. MR 95f:49047
 9.
 F. Deutsch and H. Hundal, The rate of convergence for the method of alternating projections, II, J. Math. Anal. Appl. 205 (1997), 381405. MR 97i:41025
 10.
 J. Dyer, Acceleration of the convergence of the Kaczmarz method and iterated homogeneous transformations, doctoral dissertation (1965).
 11.
 C. Franchetti and W. Light, On the von Neumann alternating algorithm in Hilbert space, J. Math. Anal. Appl. 114 (1986), 305314. MR 87f:41058
 12.
 K. Friedrichs, On certain inequalities and characteristic value problems for analytic functions and functions of two variables, Trans. Amer. Math. Soc. 41 (1937), 321364.
 13.
 W. B. Gearhart and M. Koshy, Acceleration schemes for the method of alternating projections, J. Comp. Appl. Math. 26 (1989), 235249. MR 90h:65095
 14.
 L. G. Gubin, B. T. Polyak, and E. V. Raik, The method of projections for finding the common point of convex sets, USSR Computational Mathematics and Mathematical Physics 7(6) (1967), 124.
 15.
 I. Halperin, The product of projection operators, Acta. Sci. Math. (Szeged) 23 (1962), 9699. MR 25:5373
 16.
 M. Hanke and W. Niethammer, On the acceleration of Kaczmarz's method for inconsistent linear systems, Linear Algebra Appl. 130 (1990), 8398. MR 91f:65065
 17.
 S. Kayalar and H. Weinert, Error bounds for the method of alternating projections, Math. Control Signals Systems 1 (1988), 4359. MR 89b:65137
 18.
 J. von Neumann, Functional Operators. II, Princeton University Press, Princeton, NJ, 1950. [This is a reprint of mimeograghed lecture notes first distributed in 1933.] MR 11:599e
 19.
 F. Riesz and B. Sz.Nagy, Über Kontraktionen des Hilbertschen Raumes, Acta. Sci. Math. 10 (19411943), 202205. MR 8:35a
 20.
 F. Riesz and B. Sz.Nagy, Functional Analysis, Ungar, New York, 1955. MR 17:175i
 21.
 R. Smarzewski, Iterative recovering of orthogonal projections, preprint (December, 1996).
 22.
 K. T. Smith, D. C. Solmon, and S. L. Wagner, Practical and mathematical aspects of the problem of reconstructing objects from radiographs, Bull. Amer. Math. Soc. 83 (1976), 12271270. MR 58:9394a
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2000):
41A65
Retrieve articles in all journals
with MSC (2000):
41A65
Additional Information
Heinz H. Bauschke
Affiliation:
Department of Mathematics and Statistics, Okanagan University College, Kelowna, British Columbia, Canada V1V 1V7
Address at time of publication:
Department of Mathematics and Statistics, University of Guelph, Guelph, Ontario, Canada N1G 2W1
Email:
bauschke@cecm.sfu.ca
Frank Deutsch
Affiliation:
Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802
Email:
deutsch@math.psu.edu
Hein Hundal
Affiliation:
NONRAND, 12100 Wiltshire #1650, Los Angeles, California 90025
Address at time of publication:
146 Cedar Ridge Drive, Port Matilda, Pennsylvania 16870
Email:
hundalhm@vicon.net
SungHo Park
Affiliation:
Department of Mathematics, Sogang University, Seoul, Korea
Email:
shpark@ccs.sogang.ac.kr
DOI:
http://dx.doi.org/10.1090/S0002994703031362
PII:
S 00029947(03)031362
Keywords:
Alternating projections,
cyclic projections,
accelerating convergence,
best approximation from an intersection of subspaces,
Hilbert space
Received by editor(s):
July 30, 1999
Published electronically:
May 29, 2003
Article copyright:
© Copyright 2003
American Mathematical Society
