Abstract

The phase retrieval problem is of paramount importance in various areas of applied physics and engineering. The state of the art for solving this problem in two dimensions relies heavily on the pioneering work of Gerchberg, Saxton, and Fienup. Despite the widespread use of the algorithms proposed by these three researchers, current mathematical theory cannot explain their remarkable success. Nevertheless, great insight can be gained into the behavior, the shortcomings, and the performance of these algorithms from their possible counterparts in convex optimization theory. An important step in this direction was made two decades ago when the error reduction algorithm was identified as a nonconvex alternating projection algorithm. Our purpose is to formulate the phase retrieval problem with mathematical care and to establish new connections between well-established numerical phase retrieval schemes and classical convex optimization methods. Specifically, it is shown that Fienup’s basic input–output algorithm corresponds to Dykstra’s algorithm and that Fienup’s hybrid input–output algorithm can be viewed as an instance of the Douglas–Rachford algorithm. We provide a theoretical framework to better understand and, potentially, to improve existing phase recovery algorithms.

© 2002 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Barty, D. Paganin, K. Nugent, “Phase retrieval in Lorentz microscopy,” Exp. Methods Phys. Sci. 36, 137–166 (2001).
    [CrossRef]
  2. J.-F. Brun, D. de Sousa Meneses, B. Rousseau, P. Echegut, “Dispersion relations and phase retrieval in infrared reflection spectra analysis,” Appl. Spectrosc. 55, 774–780 (2001).
    [CrossRef]
  3. J. C. Dainty, J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp. 231–275.
  4. L. D. Marks, W. Sinkler, E. Landree, “A feasible set approach to the crystallographic phase problem,” Acta Crystallogr. Sect. A 55, 601–612 (1999).
    [CrossRef]
  5. R. P. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A 7, 394–411 (1990).
    [CrossRef]
  6. P. Jaming, “Phase retrieval techniques for radar ambiguity problems,” J. Fourier Anal. Appl. 5, 309–329 (1999).
    [CrossRef]
  7. W. O. Saxton, Computer Techniques for Image Processing in Electron Microscopy (Academic, New York, 1978).
  8. L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
    [CrossRef]
  9. P. Roman, A. S. Marathay, “Analyticity and phase retrieval,” Nuovo Cimento 30, 1452–1464 (1963).
    [CrossRef]
  10. A. Walther, “The question of phase retrieval in optics,” Opt. Acta 10, 41–49 (1963).
    [CrossRef]
  11. E. Wolf, “Is a complete determination of the energy spectrum of light possible from measurements of degree of coherence?” Proc. Phys. Soc. London 80, 1269–1272 (1962).
    [CrossRef]
  12. Rayleigh, J. W. Strutt, “On the interference bands of approximately homogeneous light; in a letter to Prof. A. Michelson,” Philos. Mag. 34, 407–411 (1892).
    [CrossRef]
  13. R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237–246 (1972).
  14. J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758–2769 (1982).
    [CrossRef] [PubMed]
  15. D. C. Youla, H. Webb, “Image restoration by the method of convex projections: Part I—theory,” IEEE Trans. Med. Imaging MI-1, 81–94 (1982).
    [CrossRef]
  16. A. Lent, H. Tuy, “An iterative method for the extrapolation of band-limited functions,” J. Math. Anal. Appl. 83, 554–565 (1981).
    [CrossRef]
  17. A. Levi, H. Stark, “Signal reconstruction from phase by projection onto convex sets,” J. Opt. Soc. Am. 73, 810–822 (1983).
    [CrossRef]
  18. H. J. Trussell, M. R. Civanlar, “The feasible solution in signal restoration,” IEEE Trans. Acoust. Speech Signal Process. ASP-32, 201–212 (1984).
    [CrossRef]
  19. L. M. Brègman, “The method of successive projection for finding a common point of convex sets,” Sov. Math. Dokl. 6, 688–692 (1965).
  20. P. L. Combettes, “The foundations of set theoretic estimation,” Proc. IEEE 81, 182–208 (1993).
    [CrossRef]
  21. P. L. Combettes, “The convex feasibility problem in image recovery,” in Advances in Imaging and Electron Physics, P. W. Hawkes, ed. (Academic, Orlando, Fla., 1996), Vol. 95, pp. 155–270.
  22. H. Stark, ed., Image Recovery: Theory and Application (Academic, Orlando, Fla., 1987).
  23. H. Stark, Y. Yang, Vector Space Projections: A Numerical Approach to Signal and Image Processing, Neural Nets, and Optics (Wiley, New York, 1998).
  24. P. L. Combettes, H. J. Trussell, “Stability of the linear prediction filter: a set theoretic approach,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 2288–2291.
  25. M. Hedley, H. Yan, D. Rosenfeld, “Motion artifact correction in MRI using generalized projections,” IEEE Trans. Med. Imaging 10, 40–46 (1991).
    [CrossRef] [PubMed]
  26. R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
    [CrossRef]
  27. B. E. A. Saleh, K. M. Nashold, “Image construction: optimum amplitude and phase masks in photolithography,” Appl. Opt. 24, 1432–1437 (1985).
    [CrossRef] [PubMed]
  28. A. Levi, H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A 1, 932–943 (1984).
    [CrossRef]
  29. A. Levi, H. Stark, “Restoration from phase and magnitude by generalized projections,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp 277–320.
  30. J. A. Cadzow, “Signal enhancement—a composite property mapping algorithm,” IEEE Trans. Acoust. Speech Signal Process. 36, 49–62 (1988).
    [CrossRef]
  31. P. L. Combettes, H. J. Trussell, “Method of successive projections for finding a common point of sets in metric spaces,” J. Optim. Theory Appl. 67, 487–507 (1990).
    [CrossRef]
  32. N. E. Hurt, “Signal enhancement and the method of successive projections,” Acta Appl. Math. 23, 145–162 (1991).
    [CrossRef]
  33. S. Chrétien, P. Bondon, “Cyclic projection methods on a class of nonconvex sets,” Numer. Funct. Anal. Optim. 17, 37–56 (1996).
    [CrossRef]
  34. R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data,” J. Opt. Soc. Am. A 2, 2027–2039 (1985).
    [CrossRef]
  35. R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data. II. The nonlinear problem of phase retrieval,” J. Integral Eq. 9, 77–125 (1985).
  36. The issue of nonuniqueness of the projection is not to be confused with the uniqueness of solutions to the phase problem. The results surveyed, for instance, in Ref. 37, are not affected by the multivaluedness of the projection operators.
  37. M. H. Hayes, “The unique reconstruction of multidimensional sequences from Fourier transform magnitude or phase,” in Image Recovery: Theory and Application, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp. 195–230.
  38. D. R. Luke, “Analysis of wavefront reconstruction and deconvolution in adaptive optics,” Ph.D. thesis (University of Washington, Seattle, Wash., June2001), ftp://amath.washington.edu/pub/russell/Dissertation.ps.gz.
  39. D. R. Luke, J. V. Burke, R. Lyon, “Optical wavefront reconstruction: theory and numerical methods,” SIAM Rev.44(2) (2002), ftp://amath.washington.edu/pub/russell/Luke_Burke_Lyon_01.ps.gz.
  40. J. R. Fienup, “Reconstruction of an object from the modulus of its Fourier transform,” Opt. Lett. 3, 27–29 (1978).
    [CrossRef] [PubMed]
  41. J. R. Fienup, “Space object imaging through the turbulent atmosphere,” Opt. Eng. 18, 529–534 (1979).
    [CrossRef]
  42. J. R. Fienup, “Iterative method applied to image reconstruction and to computer-generated holograms,” Opt. Eng. 19, 297–305 (1980).
    [CrossRef]
  43. J. W. Goodman, Statistical Optics (Wiley Interscience, New York, 1985).
  44. “a.e.” stands for “almost everywhere” in the sense of measure theory, since, strictly speaking, the elements of Lare classes of equivalence of signals that may differ on a set of zero measure. For technical details on L, see, for instance, Ref. 45.
  45. C. D. Aliprantis, K. C. Border, Infinite-Dimensional Analysis, 2nd ed. (Springer-Verlag, Berlin, 1999).
  46. J. N. Cederquist, J. R. Fienup, C. C. Wackerman, S. R. Robinson, D. Kryskowski, “Wave-front phase estimation from Fourier intensity measurements,” J. Opt. Soc. Am. A 6, 1020–1026 (1989).
    [CrossRef]
  47. P. L. Combettes, “Inconsistent signal feasibility problems: least-squares solutions in a product space,” IEEE Trans. Signal Process. 42, 2955–2966 (1994).
    [CrossRef]
  48. G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980).
  49. J. H. Seldin, J. R. Fienup, “Numerical investigation of the uniqueness of phase retrieval,” J. Opt. Soc. Am. A 7, 412–427 (1990).
    [CrossRef]
  50. H. H. Bauschke, “The composition of finitely many projections onto closed convex sets in Hilbert space is asymptotically regular,” Proc. Am. Math. Soc. (to be published).
  51. H. H. Bauschke, J. M. Borwein, “On the convergence of von Neumann’s alternating projection algorithm for two sets,” Set-Valued Anal. 1, 185–212 (1993).
    [CrossRef]
  52. H. H. Bauschke, J. M. Borwein, A. S. Lewis, “The method of cyclic projections for closed convex sets in Hilbert space,” in Recent Developments in Optimization Theory and Nonlinear Analysis (American Mathematical Society, Providence, R.I., 1997), pp. 1–38.
  53. P. L. Combettes, P. Bondon, “Hard-constrained inconsistent signal feasibility problems,” IEEE Trans. Signal Process. 47, 2460–2468 (1999).
    [CrossRef]
  54. L. G. Gubin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets,” USSR Comput. Math. Math. Phys. 7, 1–24 (1967).
    [CrossRef]
  55. D. C. Youla, V. Velasco, “Extensions of a result on the synthesis of signals in the presence of inconsistent constraints,” IEEE Trans. Circuits Syst. CAS-33, 465–468 (1986).
    [CrossRef]
  56. Iterative signal recovery projection algorithms have also been implemented optically without sampling the continuous waveforms (e.g., Ref. 57). In such instances, the underlying signal space is Litself.
  57. R. J. Marks, “Coherent optical extrapolation of 2-D band-limited signals: processor theory,” Appl. Opt. 19, 1670–1672 (1980).
    [CrossRef]
  58. Let Rbe a set of real numbers. If R≠∅,then inf(R)stands for the infimum of R, i.e., the largest number in [-∞, +∞] that is smaller than or equal to all elements of R. By convention, inf(∅)=+∞.
  59. J.-P. Aubin, H. Frankowska, Set-Valued Analysis (Birkhäuser, Boston, Mass., 1990).
  60. For theoretical reasons, the sets (and functions) that we deal with must be “measurable”—this is not the same as being “physically measurable” or “observable”! For our purposes, measurable sets and functions constitute a sufficiently large class to work with; thus all closed and open subsets (and all continuous functions) are measurable, as well as various combinations of those.
  61. Mathematically, this set is assumed to have nonzero measure.
  62. The complex Hilbert space Lfrom the phase retrieval problem is also a real Hilbert space, provided that we use the real part of the inner product as the new inner product.
  63. C. Tisseron, Notions de Topologie—Introduction aux Espaces Fonctionnels (Hermann, Paris, 1985).
  64. Recall the notation from Remark 3.4.
  65. F. Deutsch, Best Approximation in Inner Product Spaces (Springer-Verlag, New York, 2001).
  66. In our setting, this means that the set {t∈RN:A(t)∩Z≠ ∅}is measurable for every closed (or, equivalently, open) set Zin ℂ ; see Section 8.1 in Ref. 59and Section 14.A in Ref. 67.
  67. R. T. Rockafellar, R. J.-B. Wets, Variational Analysis (Springer-Verlag, Berlin, 1998).
  68. If x∈L,then Re(x)denotes the function defined by Re(x):t ↦ Re[x(t)],and [Re(x)]+subsequently denotes the positive part: [Re(x)]+: t ↦ max{0, Re[x(t)]}.
  69. R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
    [CrossRef]
  70. D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
    [CrossRef]
  71. A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
    [CrossRef]
  72. A. E. Çetin, R. Ansari, “Convolution-based framework for signal recovery and applications,” J. Opt. Soc. Am. A 5, 1193–1200 (1988).
    [CrossRef]
  73. K. Goebel, W. A. Kirk, Topics in Metric Fixed Point Theory (Cambridge U. Press, Cambridge, UK, 1990).
  74. Z. Opial, “Weak convergence of the sequence of successive approximations for nonexpansive mappings,” Bull. Am. Math. Soc. 73, 591–597 (1967).
    [CrossRef]
  75. A. Genel, J. Lindenstrauss, “An example concerning fixed points,” Isr. J. Math. 22, 81–86 (1975).
    [CrossRef]
  76. Alternative descriptions of these algorithms have been proposed; see, for instance, Ref. 77.
  77. G. T. Herman, D.-W. Ro, “Image recovery using iterative data refinement with relaxation,” Opt. Eng. 29, 513–523 (1990).
    [CrossRef]
  78. Another formulation of the algorithm also includes a nonnegativity constraint.14
  79. The reason for this difference is that Fienup, on page 2763 of Ref. 14, defines γ as the set of all points where (in our notation) PM(xn)violates the object domain constraints. Hence γ={t∈∁D: (PM(xn))(t)≠0},or t∈γif and only if t∈Dand PM(xn)(t)≠0.It follows that tbelongs to the complement of γ if and only if t∈Dor PM(xn)(t)=0.The latter condition then leads to this different interpretation of the HIO algorithm. Sticking with this interpretation for another moment, we could set D(n)=D∪{t∈ ∁D: PM(xn)(t)=0}and S(n)={z∈L: z ⋅ 1∁D(n)= 0}and obtain analogously xn+1=(PS(n)(2PM-I)+(I-PM))(xn).In practical experiments for problem (5), however, this ambiguity has hardly an impact, as the sets γ and ∁Dalmost always coincide.
  80. H. Takajo, T. Shizuma, T. Takahashi, S. Takahata, “Reconstruction of an object from its noisy Fourier modulus: ideal estimate of the object to be constructed and a method that attempts to find that object,” Appl. Opt. 38, 5568–5576 (1999).
    [CrossRef]
  81. H. Takajo, T. Takahashi, T. Shizuma, “Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A 16, 2163–2168 (1999).
    [CrossRef]
  82. H. Takajo, T. Takahashi, R. Ueda, M. Taninaka, “Study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A 15, 2849–2861 (1998).
    [CrossRef]
  83. The corresponding mask is certainly much easier to implement.
  84. J. R. Fienup, C. C. Wackerman, “Phase retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A 3, 1897–1907 (1986).
    [CrossRef]
  85. The algorithms discussed here for solving problem (25) can be viewed in the broader context of finding a zero of the sum of two maximal monotone operators. Good starting points are Refs. 86-88.
  86. P. L. Combettes, “Fejér-monotonicity in convex optimization,” in Encyclopedia of Optimization, C. A. Floudas, P. M. Pardalos, eds. (Kluwer, New York, 2001), Vol. 2, pp. 106–114.
  87. J. Eckstein, “Splitting methods for monotone operators with applications to parallel optimization,” Ph.D. thesis (Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, Mass., 1989), available as (Laboratory for Information and Decision Sciences, MIT).
  88. J. Eckstein, D. P. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program. (Ser. A) 55, 293–318 (1992).
    [CrossRef]
  89. Unfortunately, PAPBis generally notfirmly nonexpansive. However, it is strongly nonexpansive (see Ref. 90for a precise definition and further information), and, for this class of mappings, a result corresponding to Fact 3.20 does exist.90
  90. R. E. Bruck, S. Reich, “Nonexpansive projections and resolvents of accretive operators in Banach spaces,” Houston J. Math. 3, 459–470 (1977).
  91. H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Rev. 38, 367–426 (1996).
    [CrossRef]
  92. H. H. Bauschke, “Projection algorithms: results and open problems,” in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Studies in Computational Mathematics, D. Butnariu, Y. Censor, S. Reich, eds. (Elsevier, Amsterdam, 2001), Vol. 8, pp. 11–22.
  93. P. L. Combettes, “Quasi-Fejérian analysis of some optimization algorithms,” in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Studies in Computational Mathematics, D. Butnariu, Y. Censor, S. Reich, eds. (Elsevier, Amsterdam, 2001), Vol. 8, pp. 115–152.
  94. R. L. Dykstra, “An algorithm for restricted least squares regression,” J. Am. Stat. Assoc. 78, 837–842 (1983).
    [CrossRef]
  95. J. P. Boyle, R. L. Dykstra, “A method for finding projections onto the intersection of convex sets in Hilbert spaces,” in Advances in Order Restricted Statistical Inference (Springer, Berlin, 1986), pp. 28–47.
  96. In the aforementioned context of maximal monotone operators,85Dykstra’s algorithm can be interpreted as a tight version of the Peaceman–Rachford algorithm. See page 77 in Ref. 87for further information. Let us also note that in the standard linear case, the Peaceman–Rachford and Douglas–Rachford algorithms can be viewed from a unifying standpoint (see Section 7.4 in Ref. 97).
  97. R. S. Varga, Matrix Iterative Analysis, 2nd ed. (Springer-Verlag, New York, 2000).
  98. H. H. Bauschke, J. M. Borwein, “Dykstra’s alternating projection algorithm for two sets,” J. Approx. Theory 79, 418–443 (1994).
    [CrossRef]
  99. H. H. Bauschke, A. S. Lewis, “Dykstra’s algorithm with Bregman projections: a convergence proof,” Optimization 48, 409–427 (2000).
    [CrossRef]
  100. N. Gaffke, R. Mathar, “A cyclic projection algorithm via duality,” Metrika 36, 29–54 (1989).
    [CrossRef]
  101. S.-P. Han, “A successive projection method,” Math. Program. (Ser. A) 40, 1–14 (1988).
    [CrossRef]
  102. H. Hundal, F. Deutsch, “Two generalizations of Dykstra’s cyclic projections algorithm,” Math. Program. (Ser. A) 77, 335–355 (1997).
    [CrossRef]
  103. P. L. Combettes, “Signal recovery by best feasible approximation,” IEEE Trans. Image Process. 2, 269–271 (1993).
    [CrossRef] [PubMed]
  104. The Douglas–Rachford algorithm was originally developed as a linear implicit iterative method to solve partial differential equations in Ref. 105(see also Chap. 7 in Ref. 97). It was extended to an operator splitting method for finding a zero of the sum of two maximal monotone operators by Lions and Mercier in Ref. 106. When it is applied to the normal cone maps of the constraint sets, one obtains a method for solving problem (25). See Refs. 86-88and 106for further information.
  105. J. Douglas, H. H. Rachford, “On the numerical solution of heat conduction problems in two or three space variables,” Trans. Am. Math. Soc. 82, 421–439 (1956).
    [CrossRef]
  106. P.-L. Lions, B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. 16, 964–979 (1979).
    [CrossRef]
  107. uis a weak cluster point of a sequence (un)if there exists a subsequence (ukn)such that ukn⇀u.
  108. If we had used the literal update rule for the HIO algorithm, the present observation would change only in one respect: the set Awould be replaced with S(n)(see Remark 4.1 and Ref. 79) and hence vary with n.
  109. E. H. Zarantonello, “Projections on convex sets in Hilbert space and spectral theory,” in Contributions to Nonlinear Functional Analysis, E. H. Zarantonello, ed. (Academic, New York, 1971), pp. 237–424.
  110. L. Debnath, P. Mikusiński, Introduction to Hilbert Spaces with Applications, 2nd ed. (Academic, San Diego, Calif., 1999).
  111. However, as shown in Property 4.1 in Ref. 39, the set Mis not weakly closed; i.e., if a sequence (xn)of points in Mconverges weakly to a point x, then xmay not be in M.
  112. While PBis nonexpansive and therefore Lipschitz continuous, this property is not sufficient to draw the conclusion advertised in Corollary 6.1 in Ref. 88, namely (in our context), that (PBxn)converges weakly to a point in A∩B.Such a conclusion requires additional assumptions, e.g., that PBbe weakly continuous (if so, then PBxn⇀PBx), as is the case when dim H<+∞(or when Bis a closed affine subspace). Note, however, that the projector onto a closed convex set may fail to be weakly continuous. An example is on page 245 in Ref. 109.

2001 (2)

2000 (1)

H. H. Bauschke, A. S. Lewis, “Dykstra’s algorithm with Bregman projections: a convergence proof,” Optimization 48, 409–427 (2000).
[CrossRef]

1999 (5)

H. Takajo, T. Takahashi, T. Shizuma, “Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A 16, 2163–2168 (1999).
[CrossRef]

H. Takajo, T. Shizuma, T. Takahashi, S. Takahata, “Reconstruction of an object from its noisy Fourier modulus: ideal estimate of the object to be constructed and a method that attempts to find that object,” Appl. Opt. 38, 5568–5576 (1999).
[CrossRef]

L. D. Marks, W. Sinkler, E. Landree, “A feasible set approach to the crystallographic phase problem,” Acta Crystallogr. Sect. A 55, 601–612 (1999).
[CrossRef]

P. Jaming, “Phase retrieval techniques for radar ambiguity problems,” J. Fourier Anal. Appl. 5, 309–329 (1999).
[CrossRef]

P. L. Combettes, P. Bondon, “Hard-constrained inconsistent signal feasibility problems,” IEEE Trans. Signal Process. 47, 2460–2468 (1999).
[CrossRef]

1998 (1)

1997 (1)

H. Hundal, F. Deutsch, “Two generalizations of Dykstra’s cyclic projections algorithm,” Math. Program. (Ser. A) 77, 335–355 (1997).
[CrossRef]

1996 (2)

H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Rev. 38, 367–426 (1996).
[CrossRef]

S. Chrétien, P. Bondon, “Cyclic projection methods on a class of nonconvex sets,” Numer. Funct. Anal. Optim. 17, 37–56 (1996).
[CrossRef]

1994 (2)

P. L. Combettes, “Inconsistent signal feasibility problems: least-squares solutions in a product space,” IEEE Trans. Signal Process. 42, 2955–2966 (1994).
[CrossRef]

H. H. Bauschke, J. M. Borwein, “Dykstra’s alternating projection algorithm for two sets,” J. Approx. Theory 79, 418–443 (1994).
[CrossRef]

1993 (3)

P. L. Combettes, “Signal recovery by best feasible approximation,” IEEE Trans. Image Process. 2, 269–271 (1993).
[CrossRef] [PubMed]

H. H. Bauschke, J. M. Borwein, “On the convergence of von Neumann’s alternating projection algorithm for two sets,” Set-Valued Anal. 1, 185–212 (1993).
[CrossRef]

P. L. Combettes, “The foundations of set theoretic estimation,” Proc. IEEE 81, 182–208 (1993).
[CrossRef]

1992 (1)

J. Eckstein, D. P. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program. (Ser. A) 55, 293–318 (1992).
[CrossRef]

1991 (2)

N. E. Hurt, “Signal enhancement and the method of successive projections,” Acta Appl. Math. 23, 145–162 (1991).
[CrossRef]

M. Hedley, H. Yan, D. Rosenfeld, “Motion artifact correction in MRI using generalized projections,” IEEE Trans. Med. Imaging 10, 40–46 (1991).
[CrossRef] [PubMed]

1990 (4)

P. L. Combettes, H. J. Trussell, “Method of successive projections for finding a common point of sets in metric spaces,” J. Optim. Theory Appl. 67, 487–507 (1990).
[CrossRef]

G. T. Herman, D.-W. Ro, “Image recovery using iterative data refinement with relaxation,” Opt. Eng. 29, 513–523 (1990).
[CrossRef]

R. P. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A 7, 394–411 (1990).
[CrossRef]

J. H. Seldin, J. R. Fienup, “Numerical investigation of the uniqueness of phase retrieval,” J. Opt. Soc. Am. A 7, 412–427 (1990).
[CrossRef]

1989 (3)

J. N. Cederquist, J. R. Fienup, C. C. Wackerman, S. R. Robinson, D. Kryskowski, “Wave-front phase estimation from Fourier intensity measurements,” J. Opt. Soc. Am. A 6, 1020–1026 (1989).
[CrossRef]

N. Gaffke, R. Mathar, “A cyclic projection algorithm via duality,” Metrika 36, 29–54 (1989).
[CrossRef]

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

1988 (3)

J. A. Cadzow, “Signal enhancement—a composite property mapping algorithm,” IEEE Trans. Acoust. Speech Signal Process. 36, 49–62 (1988).
[CrossRef]

S.-P. Han, “A successive projection method,” Math. Program. (Ser. A) 40, 1–14 (1988).
[CrossRef]

A. E. Çetin, R. Ansari, “Convolution-based framework for signal recovery and applications,” J. Opt. Soc. Am. A 5, 1193–1200 (1988).
[CrossRef]

1986 (2)

J. R. Fienup, C. C. Wackerman, “Phase retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A 3, 1897–1907 (1986).
[CrossRef]

D. C. Youla, V. Velasco, “Extensions of a result on the synthesis of signals in the presence of inconsistent constraints,” IEEE Trans. Circuits Syst. CAS-33, 465–468 (1986).
[CrossRef]

1985 (3)

1984 (2)

A. Levi, H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A 1, 932–943 (1984).
[CrossRef]

H. J. Trussell, M. R. Civanlar, “The feasible solution in signal restoration,” IEEE Trans. Acoust. Speech Signal Process. ASP-32, 201–212 (1984).
[CrossRef]

1983 (2)

R. L. Dykstra, “An algorithm for restricted least squares regression,” J. Am. Stat. Assoc. 78, 837–842 (1983).
[CrossRef]

A. Levi, H. Stark, “Signal reconstruction from phase by projection onto convex sets,” J. Opt. Soc. Am. 73, 810–822 (1983).
[CrossRef]

1982 (2)

J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758–2769 (1982).
[CrossRef] [PubMed]

D. C. Youla, H. Webb, “Image restoration by the method of convex projections: Part I—theory,” IEEE Trans. Med. Imaging MI-1, 81–94 (1982).
[CrossRef]

1981 (2)

A. Lent, H. Tuy, “An iterative method for the extrapolation of band-limited functions,” J. Math. Anal. Appl. 83, 554–565 (1981).
[CrossRef]

L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
[CrossRef]

1980 (2)

J. R. Fienup, “Iterative method applied to image reconstruction and to computer-generated holograms,” Opt. Eng. 19, 297–305 (1980).
[CrossRef]

R. J. Marks, “Coherent optical extrapolation of 2-D band-limited signals: processor theory,” Appl. Opt. 19, 1670–1672 (1980).
[CrossRef]

1979 (2)

P.-L. Lions, B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. 16, 964–979 (1979).
[CrossRef]

J. R. Fienup, “Space object imaging through the turbulent atmosphere,” Opt. Eng. 18, 529–534 (1979).
[CrossRef]

1978 (2)

D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
[CrossRef]

J. R. Fienup, “Reconstruction of an object from the modulus of its Fourier transform,” Opt. Lett. 3, 27–29 (1978).
[CrossRef] [PubMed]

1977 (1)

R. E. Bruck, S. Reich, “Nonexpansive projections and resolvents of accretive operators in Banach spaces,” Houston J. Math. 3, 459–470 (1977).

1975 (2)

A. Genel, J. Lindenstrauss, “An example concerning fixed points,” Isr. J. Math. 22, 81–86 (1975).
[CrossRef]

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
[CrossRef]

1974 (1)

R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
[CrossRef]

1972 (1)

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237–246 (1972).

1967 (2)

Z. Opial, “Weak convergence of the sequence of successive approximations for nonexpansive mappings,” Bull. Am. Math. Soc. 73, 591–597 (1967).
[CrossRef]

L. G. Gubin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets,” USSR Comput. Math. Math. Phys. 7, 1–24 (1967).
[CrossRef]

1965 (1)

L. M. Brègman, “The method of successive projection for finding a common point of convex sets,” Sov. Math. Dokl. 6, 688–692 (1965).

1963 (2)

P. Roman, A. S. Marathay, “Analyticity and phase retrieval,” Nuovo Cimento 30, 1452–1464 (1963).
[CrossRef]

A. Walther, “The question of phase retrieval in optics,” Opt. Acta 10, 41–49 (1963).
[CrossRef]

1962 (1)

E. Wolf, “Is a complete determination of the energy spectrum of light possible from measurements of degree of coherence?” Proc. Phys. Soc. London 80, 1269–1272 (1962).
[CrossRef]

1956 (1)

J. Douglas, H. H. Rachford, “On the numerical solution of heat conduction problems in two or three space variables,” Trans. Am. Math. Soc. 82, 421–439 (1956).
[CrossRef]

1892 (1)

Rayleigh, J. W. Strutt, “On the interference bands of approximately homogeneous light; in a letter to Prof. A. Michelson,” Philos. Mag. 34, 407–411 (1892).
[CrossRef]

Aliprantis, C. D.

C. D. Aliprantis, K. C. Border, Infinite-Dimensional Analysis, 2nd ed. (Springer-Verlag, Berlin, 1999).

Ansari, R.

Aubin, J.-P.

J.-P. Aubin, H. Frankowska, Set-Valued Analysis (Birkhäuser, Boston, Mass., 1990).

Barakat, R.

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data,” J. Opt. Soc. Am. A 2, 2027–2039 (1985).
[CrossRef]

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data. II. The nonlinear problem of phase retrieval,” J. Integral Eq. 9, 77–125 (1985).

Barty, A.

A. Barty, D. Paganin, K. Nugent, “Phase retrieval in Lorentz microscopy,” Exp. Methods Phys. Sci. 36, 137–166 (2001).
[CrossRef]

Bauschke, H. H.

H. H. Bauschke, A. S. Lewis, “Dykstra’s algorithm with Bregman projections: a convergence proof,” Optimization 48, 409–427 (2000).
[CrossRef]

H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Rev. 38, 367–426 (1996).
[CrossRef]

H. H. Bauschke, J. M. Borwein, “Dykstra’s alternating projection algorithm for two sets,” J. Approx. Theory 79, 418–443 (1994).
[CrossRef]

H. H. Bauschke, J. M. Borwein, “On the convergence of von Neumann’s alternating projection algorithm for two sets,” Set-Valued Anal. 1, 185–212 (1993).
[CrossRef]

H. H. Bauschke, “Projection algorithms: results and open problems,” in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Studies in Computational Mathematics, D. Butnariu, Y. Censor, S. Reich, eds. (Elsevier, Amsterdam, 2001), Vol. 8, pp. 11–22.

H. H. Bauschke, “The composition of finitely many projections onto closed convex sets in Hilbert space is asymptotically regular,” Proc. Am. Math. Soc. (to be published).

H. H. Bauschke, J. M. Borwein, A. S. Lewis, “The method of cyclic projections for closed convex sets in Hilbert space,” in Recent Developments in Optimization Theory and Nonlinear Analysis (American Mathematical Society, Providence, R.I., 1997), pp. 1–38.

Bertsekas, D. P.

J. Eckstein, D. P. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program. (Ser. A) 55, 293–318 (1992).
[CrossRef]

Bondon, P.

P. L. Combettes, P. Bondon, “Hard-constrained inconsistent signal feasibility problems,” IEEE Trans. Signal Process. 47, 2460–2468 (1999).
[CrossRef]

S. Chrétien, P. Bondon, “Cyclic projection methods on a class of nonconvex sets,” Numer. Funct. Anal. Optim. 17, 37–56 (1996).
[CrossRef]

Border, K. C.

C. D. Aliprantis, K. C. Border, Infinite-Dimensional Analysis, 2nd ed. (Springer-Verlag, Berlin, 1999).

Borwein, J. M.

H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Rev. 38, 367–426 (1996).
[CrossRef]

H. H. Bauschke, J. M. Borwein, “Dykstra’s alternating projection algorithm for two sets,” J. Approx. Theory 79, 418–443 (1994).
[CrossRef]

H. H. Bauschke, J. M. Borwein, “On the convergence of von Neumann’s alternating projection algorithm for two sets,” Set-Valued Anal. 1, 185–212 (1993).
[CrossRef]

H. H. Bauschke, J. M. Borwein, A. S. Lewis, “The method of cyclic projections for closed convex sets in Hilbert space,” in Recent Developments in Optimization Theory and Nonlinear Analysis (American Mathematical Society, Providence, R.I., 1997), pp. 1–38.

Boyle, J. P.

J. P. Boyle, R. L. Dykstra, “A method for finding projections onto the intersection of convex sets in Hilbert spaces,” in Advances in Order Restricted Statistical Inference (Springer, Berlin, 1986), pp. 28–47.

Brègman, L. M.

L. M. Brègman, “The method of successive projection for finding a common point of convex sets,” Sov. Math. Dokl. 6, 688–692 (1965).

Bruck, R. E.

R. E. Bruck, S. Reich, “Nonexpansive projections and resolvents of accretive operators in Banach spaces,” Houston J. Math. 3, 459–470 (1977).

Brun, J.-F.

Burge, R. E.

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

Cadzow, J. A.

J. A. Cadzow, “Signal enhancement—a composite property mapping algorithm,” IEEE Trans. Acoust. Speech Signal Process. 36, 49–62 (1988).
[CrossRef]

Cederquist, J. N.

Çetin, A. E.

Chrétien, S.

S. Chrétien, P. Bondon, “Cyclic projection methods on a class of nonconvex sets,” Numer. Funct. Anal. Optim. 17, 37–56 (1996).
[CrossRef]

Civanlar, M. R.

H. J. Trussell, M. R. Civanlar, “The feasible solution in signal restoration,” IEEE Trans. Acoust. Speech Signal Process. ASP-32, 201–212 (1984).
[CrossRef]

Combettes, P. L.

P. L. Combettes, P. Bondon, “Hard-constrained inconsistent signal feasibility problems,” IEEE Trans. Signal Process. 47, 2460–2468 (1999).
[CrossRef]

P. L. Combettes, “Inconsistent signal feasibility problems: least-squares solutions in a product space,” IEEE Trans. Signal Process. 42, 2955–2966 (1994).
[CrossRef]

P. L. Combettes, “Signal recovery by best feasible approximation,” IEEE Trans. Image Process. 2, 269–271 (1993).
[CrossRef] [PubMed]

P. L. Combettes, “The foundations of set theoretic estimation,” Proc. IEEE 81, 182–208 (1993).
[CrossRef]

P. L. Combettes, H. J. Trussell, “Method of successive projections for finding a common point of sets in metric spaces,” J. Optim. Theory Appl. 67, 487–507 (1990).
[CrossRef]

P. L. Combettes, “Fejér-monotonicity in convex optimization,” in Encyclopedia of Optimization, C. A. Floudas, P. M. Pardalos, eds. (Kluwer, New York, 2001), Vol. 2, pp. 106–114.

P. L. Combettes, “Quasi-Fejérian analysis of some optimization algorithms,” in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Studies in Computational Mathematics, D. Butnariu, Y. Censor, S. Reich, eds. (Elsevier, Amsterdam, 2001), Vol. 8, pp. 115–152.

P. L. Combettes, “The convex feasibility problem in image recovery,” in Advances in Imaging and Electron Physics, P. W. Hawkes, ed. (Academic, Orlando, Fla., 1996), Vol. 95, pp. 155–270.

P. L. Combettes, H. J. Trussell, “Stability of the linear prediction filter: a set theoretic approach,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 2288–2291.

Dainty, J. C.

J. C. Dainty, J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp. 231–275.

de Sousa Meneses, D.

Debnath, L.

L. Debnath, P. Mikusiński, Introduction to Hilbert Spaces with Applications, 2nd ed. (Academic, San Diego, Calif., 1999).

Deutsch, F.

H. Hundal, F. Deutsch, “Two generalizations of Dykstra’s cyclic projections algorithm,” Math. Program. (Ser. A) 77, 335–355 (1997).
[CrossRef]

F. Deutsch, Best Approximation in Inner Product Spaces (Springer-Verlag, New York, 2001).

Douglas, J.

J. Douglas, H. H. Rachford, “On the numerical solution of heat conduction problems in two or three space variables,” Trans. Am. Math. Soc. 82, 421–439 (1956).
[CrossRef]

Dykstra, R. L.

R. L. Dykstra, “An algorithm for restricted least squares regression,” J. Am. Stat. Assoc. 78, 837–842 (1983).
[CrossRef]

J. P. Boyle, R. L. Dykstra, “A method for finding projections onto the intersection of convex sets in Hilbert spaces,” in Advances in Order Restricted Statistical Inference (Springer, Berlin, 1986), pp. 28–47.

Echegut, P.

Eckstein, J.

J. Eckstein, D. P. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program. (Ser. A) 55, 293–318 (1992).
[CrossRef]

J. Eckstein, “Splitting methods for monotone operators with applications to parallel optimization,” Ph.D. thesis (Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, Mass., 1989), available as (Laboratory for Information and Decision Sciences, MIT).

Fienup, J. R.

Frankowska, H.

J.-P. Aubin, H. Frankowska, Set-Valued Analysis (Birkhäuser, Boston, Mass., 1990).

Gaffke, N.

N. Gaffke, R. Mathar, “A cyclic projection algorithm via duality,” Metrika 36, 29–54 (1989).
[CrossRef]

Genel, A.

A. Genel, J. Lindenstrauss, “An example concerning fixed points,” Isr. J. Math. 22, 81–86 (1975).
[CrossRef]

Gerchberg, R. W.

R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
[CrossRef]

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237–246 (1972).

Goebel, K.

K. Goebel, W. A. Kirk, Topics in Metric Fixed Point Theory (Cambridge U. Press, Cambridge, UK, 1990).

Goodman, J. W.

J. W. Goodman, Statistical Optics (Wiley Interscience, New York, 1985).

Gubin, L. G.

L. G. Gubin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets,” USSR Comput. Math. Math. Phys. 7, 1–24 (1967).
[CrossRef]

Hall, T. J.

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

Han, S.-P.

S.-P. Han, “A successive projection method,” Math. Program. (Ser. A) 40, 1–14 (1988).
[CrossRef]

Hayes, M. H.

M. H. Hayes, “The unique reconstruction of multidimensional sequences from Fourier transform magnitude or phase,” in Image Recovery: Theory and Application, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp. 195–230.

Hedley, M.

M. Hedley, H. Yan, D. Rosenfeld, “Motion artifact correction in MRI using generalized projections,” IEEE Trans. Med. Imaging 10, 40–46 (1991).
[CrossRef] [PubMed]

Herman, G. T.

G. T. Herman, D.-W. Ro, “Image recovery using iterative data refinement with relaxation,” Opt. Eng. 29, 513–523 (1990).
[CrossRef]

G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980).

Hoptroff, R. G.

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

Hossak, W. J.

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

Hundal, H.

H. Hundal, F. Deutsch, “Two generalizations of Dykstra’s cyclic projections algorithm,” Math. Program. (Ser. A) 77, 335–355 (1997).
[CrossRef]

Hurt, N. E.

N. E. Hurt, “Signal enhancement and the method of successive projections,” Acta Appl. Math. 23, 145–162 (1991).
[CrossRef]

Jaming, P.

P. Jaming, “Phase retrieval techniques for radar ambiguity problems,” J. Fourier Anal. Appl. 5, 309–329 (1999).
[CrossRef]

Kirk, W. A.

K. Goebel, W. A. Kirk, Topics in Metric Fixed Point Theory (Cambridge U. Press, Cambridge, UK, 1990).

Kryskowski, D.

Landree, E.

L. D. Marks, W. Sinkler, E. Landree, “A feasible set approach to the crystallographic phase problem,” Acta Crystallogr. Sect. A 55, 601–612 (1999).
[CrossRef]

Lent, A.

A. Lent, H. Tuy, “An iterative method for the extrapolation of band-limited functions,” J. Math. Anal. Appl. 83, 554–565 (1981).
[CrossRef]

Levi, A.

Lewis, A. S.

H. H. Bauschke, A. S. Lewis, “Dykstra’s algorithm with Bregman projections: a convergence proof,” Optimization 48, 409–427 (2000).
[CrossRef]

H. H. Bauschke, J. M. Borwein, A. S. Lewis, “The method of cyclic projections for closed convex sets in Hilbert space,” in Recent Developments in Optimization Theory and Nonlinear Analysis (American Mathematical Society, Providence, R.I., 1997), pp. 1–38.

Lindenstrauss, J.

A. Genel, J. Lindenstrauss, “An example concerning fixed points,” Isr. J. Math. 22, 81–86 (1975).
[CrossRef]

Lions, P.-L.

P.-L. Lions, B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. 16, 964–979 (1979).
[CrossRef]

Marathay, A. S.

P. Roman, A. S. Marathay, “Analyticity and phase retrieval,” Nuovo Cimento 30, 1452–1464 (1963).
[CrossRef]

Marks, L. D.

L. D. Marks, W. Sinkler, E. Landree, “A feasible set approach to the crystallographic phase problem,” Acta Crystallogr. Sect. A 55, 601–612 (1999).
[CrossRef]

Marks, R. J.

Mathar, R.

N. Gaffke, R. Mathar, “A cyclic projection algorithm via duality,” Metrika 36, 29–54 (1989).
[CrossRef]

McOwan, P. W.

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

Mercier, B.

P.-L. Lions, B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. 16, 964–979 (1979).
[CrossRef]

Mikusinski, P.

L. Debnath, P. Mikusiński, Introduction to Hilbert Spaces with Applications, 2nd ed. (Academic, San Diego, Calif., 1999).

Millane, R. P.

Nashold, K. M.

Newsam, G.

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data. II. The nonlinear problem of phase retrieval,” J. Integral Eq. 9, 77–125 (1985).

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data,” J. Opt. Soc. Am. A 2, 2027–2039 (1985).
[CrossRef]

Nugent, K.

A. Barty, D. Paganin, K. Nugent, “Phase retrieval in Lorentz microscopy,” Exp. Methods Phys. Sci. 36, 137–166 (2001).
[CrossRef]

Opial, Z.

Z. Opial, “Weak convergence of the sequence of successive approximations for nonexpansive mappings,” Bull. Am. Math. Soc. 73, 591–597 (1967).
[CrossRef]

Paganin, D.

A. Barty, D. Paganin, K. Nugent, “Phase retrieval in Lorentz microscopy,” Exp. Methods Phys. Sci. 36, 137–166 (2001).
[CrossRef]

Papoulis, A.

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
[CrossRef]

Polyak, B. T.

L. G. Gubin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets,” USSR Comput. Math. Math. Phys. 7, 1–24 (1967).
[CrossRef]

Rachford, H. H.

J. Douglas, H. H. Rachford, “On the numerical solution of heat conduction problems in two or three space variables,” Trans. Am. Math. Soc. 82, 421–439 (1956).
[CrossRef]

Raik, E. V.

L. G. Gubin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets,” USSR Comput. Math. Math. Phys. 7, 1–24 (1967).
[CrossRef]

Rayleigh,

Rayleigh, J. W. Strutt, “On the interference bands of approximately homogeneous light; in a letter to Prof. A. Michelson,” Philos. Mag. 34, 407–411 (1892).
[CrossRef]

Reich, S.

R. E. Bruck, S. Reich, “Nonexpansive projections and resolvents of accretive operators in Banach spaces,” Houston J. Math. 3, 459–470 (1977).

Ro, D.-W.

G. T. Herman, D.-W. Ro, “Image recovery using iterative data refinement with relaxation,” Opt. Eng. 29, 513–523 (1990).
[CrossRef]

Robinson, S. R.

Rockafellar, R. T.

R. T. Rockafellar, R. J.-B. Wets, Variational Analysis (Springer-Verlag, Berlin, 1998).

Roman, P.

P. Roman, A. S. Marathay, “Analyticity and phase retrieval,” Nuovo Cimento 30, 1452–1464 (1963).
[CrossRef]

Rosenfeld, D.

M. Hedley, H. Yan, D. Rosenfeld, “Motion artifact correction in MRI using generalized projections,” IEEE Trans. Med. Imaging 10, 40–46 (1991).
[CrossRef] [PubMed]

Rousseau, B.

Saleh, B. E. A.

Saxton, W. O.

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237–246 (1972).

W. O. Saxton, Computer Techniques for Image Processing in Electron Microscopy (Academic, New York, 1978).

Seldin, J. H.

Shizuma, T.

Sinkler, W.

L. D. Marks, W. Sinkler, E. Landree, “A feasible set approach to the crystallographic phase problem,” Acta Crystallogr. Sect. A 55, 601–612 (1999).
[CrossRef]

Stark, H.

A. Levi, H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A 1, 932–943 (1984).
[CrossRef]

A. Levi, H. Stark, “Signal reconstruction from phase by projection onto convex sets,” J. Opt. Soc. Am. 73, 810–822 (1983).
[CrossRef]

H. Stark, Y. Yang, Vector Space Projections: A Numerical Approach to Signal and Image Processing, Neural Nets, and Optics (Wiley, New York, 1998).

A. Levi, H. Stark, “Restoration from phase and magnitude by generalized projections,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp 277–320.

Strutt, J. W.

Rayleigh, J. W. Strutt, “On the interference bands of approximately homogeneous light; in a letter to Prof. A. Michelson,” Philos. Mag. 34, 407–411 (1892).
[CrossRef]

Takahashi, T.

Takahata, S.

Takajo, H.

Taninaka, M.

Taylor, L. S.

L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
[CrossRef]

Tisseron, C.

C. Tisseron, Notions de Topologie—Introduction aux Espaces Fonctionnels (Hermann, Paris, 1985).

Trussell, H. J.

P. L. Combettes, H. J. Trussell, “Method of successive projections for finding a common point of sets in metric spaces,” J. Optim. Theory Appl. 67, 487–507 (1990).
[CrossRef]

H. J. Trussell, M. R. Civanlar, “The feasible solution in signal restoration,” IEEE Trans. Acoust. Speech Signal Process. ASP-32, 201–212 (1984).
[CrossRef]

P. L. Combettes, H. J. Trussell, “Stability of the linear prediction filter: a set theoretic approach,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 2288–2291.

Tuy, H.

A. Lent, H. Tuy, “An iterative method for the extrapolation of band-limited functions,” J. Math. Anal. Appl. 83, 554–565 (1981).
[CrossRef]

Ueda, R.

Varga, R. S.

R. S. Varga, Matrix Iterative Analysis, 2nd ed. (Springer-Verlag, New York, 2000).

Velasco, V.

D. C. Youla, V. Velasco, “Extensions of a result on the synthesis of signals in the presence of inconsistent constraints,” IEEE Trans. Circuits Syst. CAS-33, 465–468 (1986).
[CrossRef]

Wackerman, C. C.

Walther, A.

A. Walther, “The question of phase retrieval in optics,” Opt. Acta 10, 41–49 (1963).
[CrossRef]

Webb, H.

D. C. Youla, H. Webb, “Image restoration by the method of convex projections: Part I—theory,” IEEE Trans. Med. Imaging MI-1, 81–94 (1982).
[CrossRef]

Wets, R. J.-B.

R. T. Rockafellar, R. J.-B. Wets, Variational Analysis (Springer-Verlag, Berlin, 1998).

Wolf, E.

E. Wolf, “Is a complete determination of the energy spectrum of light possible from measurements of degree of coherence?” Proc. Phys. Soc. London 80, 1269–1272 (1962).
[CrossRef]

Yan, H.

M. Hedley, H. Yan, D. Rosenfeld, “Motion artifact correction in MRI using generalized projections,” IEEE Trans. Med. Imaging 10, 40–46 (1991).
[CrossRef] [PubMed]

Yang, Y.

H. Stark, Y. Yang, Vector Space Projections: A Numerical Approach to Signal and Image Processing, Neural Nets, and Optics (Wiley, New York, 1998).

Youla, D. C.

D. C. Youla, V. Velasco, “Extensions of a result on the synthesis of signals in the presence of inconsistent constraints,” IEEE Trans. Circuits Syst. CAS-33, 465–468 (1986).
[CrossRef]

D. C. Youla, H. Webb, “Image restoration by the method of convex projections: Part I—theory,” IEEE Trans. Med. Imaging MI-1, 81–94 (1982).
[CrossRef]

D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
[CrossRef]

Zarantonello, E. H.

E. H. Zarantonello, “Projections on convex sets in Hilbert space and spectral theory,” in Contributions to Nonlinear Functional Analysis, E. H. Zarantonello, ed. (Academic, New York, 1971), pp. 237–424.

Acta Appl. Math. (1)

N. E. Hurt, “Signal enhancement and the method of successive projections,” Acta Appl. Math. 23, 145–162 (1991).
[CrossRef]

Acta Crystallogr. Sect. A (1)

L. D. Marks, W. Sinkler, E. Landree, “A feasible set approach to the crystallographic phase problem,” Acta Crystallogr. Sect. A 55, 601–612 (1999).
[CrossRef]

Appl. Opt. (4)

Appl. Spectrosc. (1)

Bull. Am. Math. Soc. (1)

Z. Opial, “Weak convergence of the sequence of successive approximations for nonexpansive mappings,” Bull. Am. Math. Soc. 73, 591–597 (1967).
[CrossRef]

Exp. Methods Phys. Sci. (1)

A. Barty, D. Paganin, K. Nugent, “Phase retrieval in Lorentz microscopy,” Exp. Methods Phys. Sci. 36, 137–166 (2001).
[CrossRef]

Houston J. Math. (1)

R. E. Bruck, S. Reich, “Nonexpansive projections and resolvents of accretive operators in Banach spaces,” Houston J. Math. 3, 459–470 (1977).

IEEE Trans. Acoust. Speech Signal Process. (2)

J. A. Cadzow, “Signal enhancement—a composite property mapping algorithm,” IEEE Trans. Acoust. Speech Signal Process. 36, 49–62 (1988).
[CrossRef]

H. J. Trussell, M. R. Civanlar, “The feasible solution in signal restoration,” IEEE Trans. Acoust. Speech Signal Process. ASP-32, 201–212 (1984).
[CrossRef]

IEEE Trans. Antennas Propag. (1)

L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-29, 386–391 (1981).
[CrossRef]

IEEE Trans. Circuits Syst. (3)

D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 694–702 (1978).
[CrossRef]

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
[CrossRef]

D. C. Youla, V. Velasco, “Extensions of a result on the synthesis of signals in the presence of inconsistent constraints,” IEEE Trans. Circuits Syst. CAS-33, 465–468 (1986).
[CrossRef]

IEEE Trans. Image Process. (1)

P. L. Combettes, “Signal recovery by best feasible approximation,” IEEE Trans. Image Process. 2, 269–271 (1993).
[CrossRef] [PubMed]

IEEE Trans. Med. Imaging (2)

D. C. Youla, H. Webb, “Image restoration by the method of convex projections: Part I—theory,” IEEE Trans. Med. Imaging MI-1, 81–94 (1982).
[CrossRef]

M. Hedley, H. Yan, D. Rosenfeld, “Motion artifact correction in MRI using generalized projections,” IEEE Trans. Med. Imaging 10, 40–46 (1991).
[CrossRef] [PubMed]

IEEE Trans. Signal Process. (2)

P. L. Combettes, “Inconsistent signal feasibility problems: least-squares solutions in a product space,” IEEE Trans. Signal Process. 42, 2955–2966 (1994).
[CrossRef]

P. L. Combettes, P. Bondon, “Hard-constrained inconsistent signal feasibility problems,” IEEE Trans. Signal Process. 47, 2460–2468 (1999).
[CrossRef]

Isr. J. Math. (1)

A. Genel, J. Lindenstrauss, “An example concerning fixed points,” Isr. J. Math. 22, 81–86 (1975).
[CrossRef]

J. Am. Stat. Assoc. (1)

R. L. Dykstra, “An algorithm for restricted least squares regression,” J. Am. Stat. Assoc. 78, 837–842 (1983).
[CrossRef]

J. Approx. Theory (1)

H. H. Bauschke, J. M. Borwein, “Dykstra’s alternating projection algorithm for two sets,” J. Approx. Theory 79, 418–443 (1994).
[CrossRef]

J. Fourier Anal. Appl. (1)

P. Jaming, “Phase retrieval techniques for radar ambiguity problems,” J. Fourier Anal. Appl. 5, 309–329 (1999).
[CrossRef]

J. Integral Eq. (1)

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data. II. The nonlinear problem of phase retrieval,” J. Integral Eq. 9, 77–125 (1985).

J. Math. Anal. Appl. (1)

A. Lent, H. Tuy, “An iterative method for the extrapolation of band-limited functions,” J. Math. Anal. Appl. 83, 554–565 (1981).
[CrossRef]

J. Opt. Soc. Am. (1)

J. Opt. Soc. Am. A (9)

A. E. Çetin, R. Ansari, “Convolution-based framework for signal recovery and applications,” J. Opt. Soc. Am. A 5, 1193–1200 (1988).
[CrossRef]

A. Levi, H. Stark, “Image restoration by the method of generalized projections with application to restoration from magnitude,” J. Opt. Soc. Am. A 1, 932–943 (1984).
[CrossRef]

H. Takajo, T. Takahashi, T. Shizuma, “Further study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A 16, 2163–2168 (1999).
[CrossRef]

H. Takajo, T. Takahashi, R. Ueda, M. Taninaka, “Study on the convergence property of the hybrid input–output algorithm used for phase retrieval,” J. Opt. Soc. Am. A 15, 2849–2861 (1998).
[CrossRef]

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, band-limited Fourier-transform pairs from noisy data,” J. Opt. Soc. Am. A 2, 2027–2039 (1985).
[CrossRef]

J. R. Fienup, C. C. Wackerman, “Phase retrieval stagnation problems and solutions,” J. Opt. Soc. Am. A 3, 1897–1907 (1986).
[CrossRef]

J. N. Cederquist, J. R. Fienup, C. C. Wackerman, S. R. Robinson, D. Kryskowski, “Wave-front phase estimation from Fourier intensity measurements,” J. Opt. Soc. Am. A 6, 1020–1026 (1989).
[CrossRef]

R. P. Millane, “Phase retrieval in crystallography and optics,” J. Opt. Soc. Am. A 7, 394–411 (1990).
[CrossRef]

J. H. Seldin, J. R. Fienup, “Numerical investigation of the uniqueness of phase retrieval,” J. Opt. Soc. Am. A 7, 412–427 (1990).
[CrossRef]

J. Optim. Theory Appl. (1)

P. L. Combettes, H. J. Trussell, “Method of successive projections for finding a common point of sets in metric spaces,” J. Optim. Theory Appl. 67, 487–507 (1990).
[CrossRef]

Math. Program. (Ser. A) (3)

J. Eckstein, D. P. Bertsekas, “On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators,” Math. Program. (Ser. A) 55, 293–318 (1992).
[CrossRef]

S.-P. Han, “A successive projection method,” Math. Program. (Ser. A) 40, 1–14 (1988).
[CrossRef]

H. Hundal, F. Deutsch, “Two generalizations of Dykstra’s cyclic projections algorithm,” Math. Program. (Ser. A) 77, 335–355 (1997).
[CrossRef]

Metrika (1)

N. Gaffke, R. Mathar, “A cyclic projection algorithm via duality,” Metrika 36, 29–54 (1989).
[CrossRef]

Numer. Funct. Anal. Optim. (1)

S. Chrétien, P. Bondon, “Cyclic projection methods on a class of nonconvex sets,” Numer. Funct. Anal. Optim. 17, 37–56 (1996).
[CrossRef]

Nuovo Cimento (1)

P. Roman, A. S. Marathay, “Analyticity and phase retrieval,” Nuovo Cimento 30, 1452–1464 (1963).
[CrossRef]

Opt. Acta (2)

A. Walther, “The question of phase retrieval in optics,” Opt. Acta 10, 41–49 (1963).
[CrossRef]

R. W. Gerchberg, “Super-resolution through error energy reduction,” Opt. Acta 21, 709–720 (1974).
[CrossRef]

Opt. Commun. (1)

R. G. Hoptroff, P. W. McOwan, T. J. Hall, W. J. Hossak, R. E. Burge, “Two optimization approaches to cohoe design,” Opt. Commun. 73, 188–194 (1989).
[CrossRef]

Opt. Eng. (3)

J. R. Fienup, “Space object imaging through the turbulent atmosphere,” Opt. Eng. 18, 529–534 (1979).
[CrossRef]

J. R. Fienup, “Iterative method applied to image reconstruction and to computer-generated holograms,” Opt. Eng. 19, 297–305 (1980).
[CrossRef]

G. T. Herman, D.-W. Ro, “Image recovery using iterative data refinement with relaxation,” Opt. Eng. 29, 513–523 (1990).
[CrossRef]

Opt. Lett. (1)

Optik (Stuttgart) (1)

R. W. Gerchberg, W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik (Stuttgart) 35, 237–246 (1972).

Optimization (1)

H. H. Bauschke, A. S. Lewis, “Dykstra’s algorithm with Bregman projections: a convergence proof,” Optimization 48, 409–427 (2000).
[CrossRef]

Philos. Mag. (1)

Rayleigh, J. W. Strutt, “On the interference bands of approximately homogeneous light; in a letter to Prof. A. Michelson,” Philos. Mag. 34, 407–411 (1892).
[CrossRef]

Proc. IEEE (1)

P. L. Combettes, “The foundations of set theoretic estimation,” Proc. IEEE 81, 182–208 (1993).
[CrossRef]

Proc. Phys. Soc. London (1)

E. Wolf, “Is a complete determination of the energy spectrum of light possible from measurements of degree of coherence?” Proc. Phys. Soc. London 80, 1269–1272 (1962).
[CrossRef]

Set-Valued Anal. (1)

H. H. Bauschke, J. M. Borwein, “On the convergence of von Neumann’s alternating projection algorithm for two sets,” Set-Valued Anal. 1, 185–212 (1993).
[CrossRef]

SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. (1)

P.-L. Lions, B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. 16, 964–979 (1979).
[CrossRef]

SIAM Rev. (1)

H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Rev. 38, 367–426 (1996).
[CrossRef]

Sov. Math. Dokl. (1)

L. M. Brègman, “The method of successive projection for finding a common point of convex sets,” Sov. Math. Dokl. 6, 688–692 (1965).

Trans. Am. Math. Soc. (1)

J. Douglas, H. H. Rachford, “On the numerical solution of heat conduction problems in two or three space variables,” Trans. Am. Math. Soc. 82, 421–439 (1956).
[CrossRef]

USSR Comput. Math. Math. Phys. (1)

L. G. Gubin, B. T. Polyak, E. V. Raik, “The method of projections for finding the common point of convex sets,” USSR Comput. Math. Math. Phys. 7, 1–24 (1967).
[CrossRef]

Other (50)

H. H. Bauschke, J. M. Borwein, A. S. Lewis, “The method of cyclic projections for closed convex sets in Hilbert space,” in Recent Developments in Optimization Theory and Nonlinear Analysis (American Mathematical Society, Providence, R.I., 1997), pp. 1–38.

Alternative descriptions of these algorithms have been proposed; see, for instance, Ref. 77.

K. Goebel, W. A. Kirk, Topics in Metric Fixed Point Theory (Cambridge U. Press, Cambridge, UK, 1990).

Iterative signal recovery projection algorithms have also been implemented optically without sampling the continuous waveforms (e.g., Ref. 57). In such instances, the underlying signal space is Litself.

Let Rbe a set of real numbers. If R≠∅,then inf(R)stands for the infimum of R, i.e., the largest number in [-∞, +∞] that is smaller than or equal to all elements of R. By convention, inf(∅)=+∞.

J.-P. Aubin, H. Frankowska, Set-Valued Analysis (Birkhäuser, Boston, Mass., 1990).

For theoretical reasons, the sets (and functions) that we deal with must be “measurable”—this is not the same as being “physically measurable” or “observable”! For our purposes, measurable sets and functions constitute a sufficiently large class to work with; thus all closed and open subsets (and all continuous functions) are measurable, as well as various combinations of those.

Mathematically, this set is assumed to have nonzero measure.

The complex Hilbert space Lfrom the phase retrieval problem is also a real Hilbert space, provided that we use the real part of the inner product as the new inner product.

C. Tisseron, Notions de Topologie—Introduction aux Espaces Fonctionnels (Hermann, Paris, 1985).

Recall the notation from Remark 3.4.

F. Deutsch, Best Approximation in Inner Product Spaces (Springer-Verlag, New York, 2001).

In our setting, this means that the set {t∈RN:A(t)∩Z≠ ∅}is measurable for every closed (or, equivalently, open) set Zin ℂ ; see Section 8.1 in Ref. 59and Section 14.A in Ref. 67.

R. T. Rockafellar, R. J.-B. Wets, Variational Analysis (Springer-Verlag, Berlin, 1998).

If x∈L,then Re(x)denotes the function defined by Re(x):t ↦ Re[x(t)],and [Re(x)]+subsequently denotes the positive part: [Re(x)]+: t ↦ max{0, Re[x(t)]}.

H. H. Bauschke, “Projection algorithms: results and open problems,” in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Studies in Computational Mathematics, D. Butnariu, Y. Censor, S. Reich, eds. (Elsevier, Amsterdam, 2001), Vol. 8, pp. 11–22.

P. L. Combettes, “Quasi-Fejérian analysis of some optimization algorithms,” in Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Studies in Computational Mathematics, D. Butnariu, Y. Censor, S. Reich, eds. (Elsevier, Amsterdam, 2001), Vol. 8, pp. 115–152.

J. P. Boyle, R. L. Dykstra, “A method for finding projections onto the intersection of convex sets in Hilbert spaces,” in Advances in Order Restricted Statistical Inference (Springer, Berlin, 1986), pp. 28–47.

In the aforementioned context of maximal monotone operators,85Dykstra’s algorithm can be interpreted as a tight version of the Peaceman–Rachford algorithm. See page 77 in Ref. 87for further information. Let us also note that in the standard linear case, the Peaceman–Rachford and Douglas–Rachford algorithms can be viewed from a unifying standpoint (see Section 7.4 in Ref. 97).

R. S. Varga, Matrix Iterative Analysis, 2nd ed. (Springer-Verlag, New York, 2000).

Another formulation of the algorithm also includes a nonnegativity constraint.14

The reason for this difference is that Fienup, on page 2763 of Ref. 14, defines γ as the set of all points where (in our notation) PM(xn)violates the object domain constraints. Hence γ={t∈∁D: (PM(xn))(t)≠0},or t∈γif and only if t∈Dand PM(xn)(t)≠0.It follows that tbelongs to the complement of γ if and only if t∈Dor PM(xn)(t)=0.The latter condition then leads to this different interpretation of the HIO algorithm. Sticking with this interpretation for another moment, we could set D(n)=D∪{t∈ ∁D: PM(xn)(t)=0}and S(n)={z∈L: z ⋅ 1∁D(n)= 0}and obtain analogously xn+1=(PS(n)(2PM-I)+(I-PM))(xn).In practical experiments for problem (5), however, this ambiguity has hardly an impact, as the sets γ and ∁Dalmost always coincide.

G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980).

The corresponding mask is certainly much easier to implement.

The algorithms discussed here for solving problem (25) can be viewed in the broader context of finding a zero of the sum of two maximal monotone operators. Good starting points are Refs. 86-88.

P. L. Combettes, “Fejér-monotonicity in convex optimization,” in Encyclopedia of Optimization, C. A. Floudas, P. M. Pardalos, eds. (Kluwer, New York, 2001), Vol. 2, pp. 106–114.

J. Eckstein, “Splitting methods for monotone operators with applications to parallel optimization,” Ph.D. thesis (Department of Civil Engineering, Massachusetts Institute of Technology, Cambridge, Mass., 1989), available as (Laboratory for Information and Decision Sciences, MIT).

P. L. Combettes, “The convex feasibility problem in image recovery,” in Advances in Imaging and Electron Physics, P. W. Hawkes, ed. (Academic, Orlando, Fla., 1996), Vol. 95, pp. 155–270.

H. Stark, ed., Image Recovery: Theory and Application (Academic, Orlando, Fla., 1987).

H. Stark, Y. Yang, Vector Space Projections: A Numerical Approach to Signal and Image Processing, Neural Nets, and Optics (Wiley, New York, 1998).

P. L. Combettes, H. J. Trussell, “Stability of the linear prediction filter: a set theoretic approach,” in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 2288–2291.

W. O. Saxton, Computer Techniques for Image Processing in Electron Microscopy (Academic, New York, 1978).

J. W. Goodman, Statistical Optics (Wiley Interscience, New York, 1985).

“a.e.” stands for “almost everywhere” in the sense of measure theory, since, strictly speaking, the elements of Lare classes of equivalence of signals that may differ on a set of zero measure. For technical details on L, see, for instance, Ref. 45.

C. D. Aliprantis, K. C. Border, Infinite-Dimensional Analysis, 2nd ed. (Springer-Verlag, Berlin, 1999).

H. H. Bauschke, “The composition of finitely many projections onto closed convex sets in Hilbert space is asymptotically regular,” Proc. Am. Math. Soc. (to be published).

The issue of nonuniqueness of the projection is not to be confused with the uniqueness of solutions to the phase problem. The results surveyed, for instance, in Ref. 37, are not affected by the multivaluedness of the projection operators.

M. H. Hayes, “The unique reconstruction of multidimensional sequences from Fourier transform magnitude or phase,” in Image Recovery: Theory and Application, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp. 195–230.

D. R. Luke, “Analysis of wavefront reconstruction and deconvolution in adaptive optics,” Ph.D. thesis (University of Washington, Seattle, Wash., June2001), ftp://amath.washington.edu/pub/russell/Dissertation.ps.gz.

D. R. Luke, J. V. Burke, R. Lyon, “Optical wavefront reconstruction: theory and numerical methods,” SIAM Rev.44(2) (2002), ftp://amath.washington.edu/pub/russell/Luke_Burke_Lyon_01.ps.gz.

J. C. Dainty, J. R. Fienup, “Phase retrieval and image reconstruction for astronomy,” in Image Recovery: Theory and Application, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp. 231–275.

A. Levi, H. Stark, “Restoration from phase and magnitude by generalized projections,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), pp 277–320.

The Douglas–Rachford algorithm was originally developed as a linear implicit iterative method to solve partial differential equations in Ref. 105(see also Chap. 7 in Ref. 97). It was extended to an operator splitting method for finding a zero of the sum of two maximal monotone operators by Lions and Mercier in Ref. 106. When it is applied to the normal cone maps of the constraint sets, one obtains a method for solving problem (25). See Refs. 86-88and 106for further information.

uis a weak cluster point of a sequence (un)if there exists a subsequence (ukn)such that ukn⇀u.

If we had used the literal update rule for the HIO algorithm, the present observation would change only in one respect: the set Awould be replaced with S(n)(see Remark 4.1 and Ref. 79) and hence vary with n.

E. H. Zarantonello, “Projections on convex sets in Hilbert space and spectral theory,” in Contributions to Nonlinear Functional Analysis, E. H. Zarantonello, ed. (Academic, New York, 1971), pp. 237–424.

L. Debnath, P. Mikusiński, Introduction to Hilbert Spaces with Applications, 2nd ed. (Academic, San Diego, Calif., 1999).

However, as shown in Property 4.1 in Ref. 39, the set Mis not weakly closed; i.e., if a sequence (xn)of points in Mconverges weakly to a point x, then xmay not be in M.

While PBis nonexpansive and therefore Lipschitz continuous, this property is not sufficient to draw the conclusion advertised in Corollary 6.1 in Ref. 88, namely (in our context), that (PBxn)converges weakly to a point in A∩B.Such a conclusion requires additional assumptions, e.g., that PBbe weakly continuous (if so, then PBxn⇀PBx), as is the case when dim H<+∞(or when Bis a closed affine subspace). Note, however, that the projector onto a closed convex set may fail to be weakly continuous. An example is on page 245 in Ref. 109.

Unfortunately, PAPBis generally notfirmly nonexpansive. However, it is strongly nonexpansive (see Ref. 90for a precise definition and further information), and, for this class of mappings, a result corresponding to Fact 3.20 does exist.90

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (3)

Fig. 1
Fig. 1

POCS algorithm. The initial point a0 is projected onto B and then onto A. The point a1 thus obtained belongs to both sets, and the algorithm therefore converges in two steps. Note that the solution a1 is not the projection of a0 onto AB.

Fig. 2
Fig. 2

Dykstra’s algorithm. The first two steps of this algorithm are identical to those of the POCS algorithm (Fig. 1). Here, however, although a1AB, the algorithm does not reach convergence at this point, since the outward-pointing normal q0 pulls the vector a1+q0 out of B before it is projected onto B. Through this process, two infinite sequences (an) and (bn) are generated that converge to PAB(a0). Note that since A is an affine subspace in this example, pn  A and, therefore, an+1=PA(bn).

Fig. 3
Fig. 3

Douglas–Rachford algorithm. The update equation (32) is executed as follows: One first computes the reflection rn+(1/2) of xn with respect to B and then the reflection rn+1 of rn+(1/2) with respect to A. The update xn+1 is the midpoint of the segment between xn and rn+1. In this example, the algorithm converges in four iterations, since x4AB.

Equations (46)

Equations on this page are rendered with MathJax. Learn more.

|xˆ|=m,
L=L2[RN, C].
M={yL:|yˆ|=ma.e.}.
S={yL:y  1D=0}.
findsomexSM.
H isageneralHilbertspacewithinnerproduct,andnorm:x  x, x.
{yY:d(x, y)=d(x, Y)},
PS(x)=x  1D.
yˆ(ω)=m(ω) xˆ(ω)|xˆ(ω)|ifxˆ(ω)0m(ω)exp[iϕ(ω)]otherwise
d(xˆ(ω), m(ω)S)=d(xˆ(ω), yˆ(ω)) a.e.on RN,
y^0(ω)=m(ω) xˆ(ω)|xˆ(ω)|ifxˆ(ω)0m(ω)otherwise.
H isarealHilbertspacewithinnerproduct, andinducednorm.
PC(x)C,c-PC(x), x-PC(x)0
forallcC.
PC(x)-PC(y)2+(I-PC)(x)-(I-PC)(y)2
x-y2forallx, yH.
T(x)-T(y)2+(I-T)(x)-(I-T)(y)2
x-y2 forallx, yH,
T(x)-T(y)x-yforallx, yH.
Fix T={xH:T(x)=x}.
xn+1(t)=(PM(xn))(t)iftD0otherwise.
xn+1=(PSPM)(xn).
xn+1(t)=xn(t)iftDxn(t)-(PM(xn))(t)otherwise.
xn+1=(PSPM+I-PM)(xn).
xn+1(t)=(PM(xn))(t)iftDxn(t)-β(PM(xn))(t)otherwise.
xn+1=1D  PM(xn)+1D  [xn-PM(xn)]=1D  PM(xn)+(1-1D)  [xn-PM(xn)]=1D  [2PM(xn)-xn]+xn-PM(xn)=(PS(2PM-I)+(I-PM))(xn).
xn+1=(PSPM+(I-PS)(I-PM))(xn),
xn+1(t)
=(PM(xn))(t)iftDor (PM(xn))(t)=0xn(t)-(PM(xn))(t)otherwise.
findsomexAB.
bn=PB(an),an+1=PA(bn).
bn=PB(an+qn-1),
qn=(I-PB)(an+qn-1)=an+qn-1-bn,
an+1=PA(bn+pn),
pn+1=(I-PA)(bn+pn)=bn+pn-an+1.
bn=PB(an+qn-1),
qn=(I-PB)(an+qn-1),
an+1=PA(bn).
an+1+qn=(PAPB+I-PB)(an+qn-1)=(PAPB+I-PB)n+1(a0).
xn+1=(PA(2PB-I)+(I-PB))(xn).
T=PA(2PB-I)+(I-PB).
xn+1=12 (RARB+I)(xn).
d2(x, A)=x-y2=E|x(t)-y(t)|2dt+E|x(t)-y(t)|2dt>E|x(t)-z(t)|2dt+E|x(t)-z(t)|2dt=x-z2=d2(x, A),
RARB=(2PA-I)(2PB-I)=2PA(2PB-I)+2(I-PB)-I.
0xn-xn+1=PB(xn)-PA(2PB(xn)-xn).
xn+1=(PS(n)(2PM-I)+(I-PM))(xn).

Metrics