Abstract
We consider convergence of alternating projections between non-convex sets and obtain applications to convergence of the Gerchberg-Saxton error reduction method, of the Gaussian expectation-maximization algorithm, and of Cadzow’s algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aamari, E., Kim, J., Chazal, F., Michel, B., Rinaldo, A., Wasserman, L.: Estimating the reach of a manifold. arXiv:1705.04565v3 [math.ST] 8 Apr 2019
Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)
Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)
Bauschke, H.H., Noll, D.: On cluster points of alternating projections. Serdica Math. J. 39, 355–364 (2013)
Bauschke, H.H., Noll, D.: On the local convergence of the Douglas-Rachford algorithm. Archiv Math. 102(6), 589–600 (2014)
Bauschke, H.H., Noll, D., Celler, A., Borwein, J.M.: An EM-algorithm for dynamic SPECT. IEEE Trans. Med. Imaging 18(3), 252–261 (1999)
Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and the method of alternating projections: theory. Set-Valued Var. Anal. 21, 431–473 (2013)
Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Transversality and alternating projections on non-convex sets. Found. Comput. Math. 15(6), 1637–1651 (2015)
Bolte, J., Daniilidis, A., Lewis, A.S.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Opt. 17(4), 1205–1223 (2007)
Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions. arXiv:1510.08234v3 [math.OC] 20 Jul 2016
Cadzow, J.A.: Signal enhancement: a composite property mapping algorithm. IEEE Trans. Acoust. Speech Signal Process. 36(2), 49–62 (1988)
Cadzow, J.A.: Blind deconvolution via cumulant extrema. IEEE Signal Proc. Mag. 6(13), 24–42 (1996)
Csiszár, I., Tusnády, G.: Information geometry and alternating minimization procedures. Stat. Decis. 1(1), 205–237 (1984)
Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Alternating projections and coupling slope. arXiv:1401.7569v1 [math.OC] 29 Jan 2014
Feenham, P.M., Maridakis, M.: Łojasiewicz-Simon gradient inequalities for analytic and Morse-Bott functions on Banach spaces. arXiv:1510.03817v10 [math.DG] 23 Sept 2019
Fienup, J.R.: Phase retrieval algorithms: a comparison. Appl. Opt. 21, 2758–2769 (1982)
Fienup, J.R.: Reconstruction and synthesis applications of an iterative algorithm. In: Rhodes, W.T., Fienup, J.R., Salch, B.E.A. (eds.) Transformations in Optical Signal Processing. Society of Photo-Optical Instrumentation Engineering, Washington (1982)
Gerchberg, R.W., Saxton, W.O.: A practical algorithm for the determination of the phase from image and diffraction plane pictures. Optik 35, 237–246 (1972)
Hesse, R., Luke, D.R.: Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems. SIAM J. Opt. 23(4), 2397–2419 (2013)
Kleinman, S., Landolfi, J.: Geometry and deformation of special Schubert varieties. Compos. Math. 23, 407–434 (1971)
Kruger, A.Y.: On Fréchet subdifferentials. Optimization and Related Topics, 3. J. Math. Sci. (N. Y.) 116(3), 3325–3358 (2003)
Lewis, A.S., Malick, J.: Alternating projections on manifolds. Math. Oper. Res. 33, 216–234 (2008)
Lewis, A.S., Luke, R., Malick, J.: Local linear convergence for alternating and averaged non convex projections. Found. Comput. Math. 9, 485–513 (2009)
Luke, D.R.: Phase Retrieval, What’s New? Research Gate. Essays. Research Training Group 2088 “Discovering structure in complex data: Statistics meets Optimization and Inverse Problems” (2017)
Maeght, J., Boyd, S.P., Noll, D.: Dynamic emission tomography–regularization and inversion. Can. Math. Soc. Conf. Proc. 27, 211–234 (2000)
Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation. Springer, New York (2006)
Noll, D., Rondepierre, A.: On local convergence of the method of alternating projections. arXiv:1312.5681v1 [math.OC] 19 Dec 2013
Noll, D., Rondepierre, A.: On local convergence of the method of alternating projections. Found. Comput. Math. 16(2), 425–455 (2016)
Phan, H.M.: Linear convergence of the Douglas-Rachford method for two closed sets. Optimization 65, 369–385 (2016)
Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Grundlehren der Mathematischen Wissenschaften, p 317. Springer, Berlin (2009)
Schwarz, H.A.: Über einige Abbildungsaufgaben. Gesammelte Math. Abh. 11, 65–83 (1869)
Shiota, M.: Geometry of Subanalytic and Semialgebraic Sets. Birkhäuser, Boston (1997)
Thao, N.H., Luke, D.R., Soloviev, O., Verhaegen, M.: Phase retrieval with sparse phase constraint. arXiv:1804.01878v2
Zhu, Z., Li, X.: Convergence analysis of alternating projection method for nonconvex sets. arXiv:1802.03889
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to R.T. Rockafellar on the occasion of his 85th anniversary
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Noll, D. Alternating Projections with Applications to Gerchberg-Saxton Error Reduction. Set-Valued Var. Anal 29, 771–802 (2021). https://doi.org/10.1007/s11228-021-00585-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-021-00585-1
Keywords
- Alternating projections
- Subanalytic sets
- Phase retrieval
- Gerchberg-Saxton
- Douglas-Rachford
- Gaussian EM-algorithm
- Cadzow algorithm