Abstract

This paper is a summary of more detailed mathematical work by the authors on recovery of partially known Fourier transforms. These problems of inversion of the finite Fourier transform and of phase retrieval are known to be ill posed. We draw a distinction in the resultant ill conditioning of the problems between global ill conditioning (which is due to the existence of multiple exact solutions) and local ill conditioning (which is due to the existence of large neighborhoods of the true solution, all of whose members are indistinguishable from the true solution if the data are noisy). We then develop extensions of known algorithms that attempt to reduce at least the effects of local ill conditioning on numerical solutions by using the idea of filtered singular-value decomposition and present some numerical examples of the use of those algorithms in the context of optical-diffraction theory.

© 1985 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. Gerschberg, W. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35, 237–246 (1972).
  2. A. Papoulis, “A new algorithm in spectral analysis and bandlimited extrapolation,” IEEE Trans. Circuits Syst. CAS-22, 735–742 (1975).
    [CrossRef]
  3. D. C. Youla, “Generalized image restoration by the method of alternating orthogonal projections,” IEEE Trans. Circuits Syst. CAS-25, 695–702 (1978).
  4. J. A. Cadzow, “An extrapolation procedure for bandlimited signals,” IEEE Trans. Acoust. Speech Signal Process. ASSP-27, 4–12 (1979).
    [CrossRef]
  5. M. S. Sabri, W. Steenart, “An approach to bandlimited extrapolation: The extrapolation matrix,” IEEE Trans. Circuits Syst. CAS-25, 74–78 (1978).
    [CrossRef]
  6. R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
    [CrossRef]
  7. J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic, New York, 1970), pp. 494–500.
  8. J. R. Fienup, “Space–object imaging through the atmosphere,” Opt. Eng. 18, 529–534 (1979).
    [CrossRef]
  9. R. Barakat, G. Newsam, “A numerically stable iterative method for the inversion of wave-front aberrations from measured point-spread-function data,” J. Opt. Soc. Am. 70, 1255–1263 (1980).
    [CrossRef]
  10. A. N. Tikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).
  11. L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-39, 381–391 (1981).
  12. D. L. Misell, “The phase problem in electron microscopy,” in Advances in Optics and Electron Microscopy, Vol. 7, V. E. Coslett, R. Barer, eds. (Academic, New York, 1978).
  13. H. A. Ferwerda, “The phase reconstruction problem for wave amplitudes and coherence functions,” in Inverse Source Problems in Optics, H. P. Baltes, ed. (Springer-Verlag, New York, 1978).
    [CrossRef]
  14. R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem,” J. Integral Eq. 9, 49–76 (1985).
  15. R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: II The nonlinear problem of phase retrieval,” J. Integral Eq. Suppl. 9, 77–125 (1985).
  16. G. Newsam, “Numerical reconstruction of partially known transforms,” Ph.D. dissertation (Harvard University, Cambridge, Mass., 1982).
  17. C. T. Baker, The Numerical Treatment of Integral Equations (Oxford U. Press, Oxford, 1977).
  18. G. Newsam, R. Barakat, “Essential dimension as a well-defined number of degrees of freedom of finite-convolution operators appearing in optics,” J. Opt. Soc. Am. A 2, 2040–2045 (1985).
    [CrossRef]
  19. R. H. Hanson, “A numerical method for solving Fredholm integral equations of the first kind using singular values.” J. Soc. Ind. Appl. Math. Num. Anal. 8, 616–622 (1971).
  20. D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: I,” Bell Syst. Tech. J. 40, 43–64 (1961).
    [CrossRef]
  21. H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: II,” Bell Syst. Tech. J. 40, 65–84 (1961).
    [CrossRef]
  22. H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: III,” Bell Syst. Tech. J. 41, 1295–1336 (1962).
    [CrossRef]
  23. H. J. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).
  24. H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
    [CrossRef]
  25. H. J. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
    [CrossRef]
  26. H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations: II,” Arch. Rat. Mech. Anal. 17, 215–229 (1964).
    [CrossRef]
  27. E. J. Akutowicz, “On the determination of the phase of a Fourier integral—I,” Trans. Am. Math. Soc. 83, 179–192 (1956).
  28. E. J. Akutowicz, “On the determination of the phase of a Fourier integral—II,” Proc. Am. Math. Soc. 84, 234–238 (1957).
  29. A. Walther, “The question of phase retrieval in optics,” Opt. Acta 10, 41–49 (1963).
    [CrossRef]
  30. E. M. Hofstetter, “Construction of time-limited functions with specified autocorrelation functions,” IEEE Trans. Inf. Theory IT-10, 119–126 (1964).
    [CrossRef]
  31. R. Barakat, G. Newsam, “Necessary conditions for a unique solution to two-dimensional phase recovery,” J. Math. Phys. N. Y. 25, 3190–3193 (1984).
    [CrossRef]
  32. P. P. Boas, Entire Functions (Academic, New York, 1954).
  33. P. J. Napier, “The brightness temperature distributions defined by a measured intensity interferogram,” N.Z. J. Sci. 15, 342–355.
  34. L. Ronkin, Introduction to the Theory of Entire Functions of Several Complex Variables (American Mathematical Society, Providence, R.I., 1974).
  35. W. Lawton, “Uniqueness results for the phase-retrieval problem for radial functions,” J. Opt. Soc. Am. 71, 1519–1522 (1981).
    [CrossRef]
  36. J. R. Fienup, “Phase retrieval algorithms: a comparison,” Appl. Opt. 21, 2758–2769 (1982).
    [CrossRef] [PubMed]
  37. L. Gubin, B. Polyak, E. Raik, “The method of projections for finding the common point of convex sets,” USSR Comp. Math. Math. Phys. 7, 1–24 (1967).
    [CrossRef]
  38. Y. Censor, G. T. Herman, “Row generation methods for feasibility and optimization problems involving sparse matrices and their applications,” in Sparse Matrix Proceedings 1978, I. Duff, G. Stewart, eds. (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1979).
  39. G. Walsh, Methods of Optimization (Wiley, New York, 1975).
  40. R. B. Holmes, “Smoothness of certain metric projections on Hilbert spaces,” Trans. Am. Math. Soc. 183, 87–100 (1973).
    [CrossRef]
  41. R. Barakat, L. Riseberg, “Diffraction theory of the aberrations of a slit aperture,” J. Opt. Soc. Am. 55, 878–881 (1965).
    [CrossRef]

1985 (3)

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem,” J. Integral Eq. 9, 49–76 (1985).

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

G. Newsam, R. Barakat, “Essential dimension as a well-defined number of degrees of freedom of finite-convolution operators appearing in optics,” J. Opt. Soc. Am. A 2, 2040–2045 (1985).
[CrossRef]

1984 (1)

R. Barakat, G. Newsam, “Necessary conditions for a unique solution to two-dimensional phase recovery,” J. Math. Phys. N. Y. 25, 3190–3193 (1984).
[CrossRef]

1982 (1)

1981 (2)

W. Lawton, “Uniqueness results for the phase-retrieval problem for radial functions,” J. Opt. Soc. Am. 71, 1519–1522 (1981).
[CrossRef]

L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-39, 381–391 (1981).

1980 (2)

1979 (2)

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

J. A. Cadzow, “An extrapolation procedure for bandlimited signals,” IEEE Trans. Acoust. Speech Signal Process. ASSP-27, 4–12 (1979).
[CrossRef]

1978 (2)

M. S. Sabri, W. Steenart, “An approach to bandlimited extrapolation: The extrapolation matrix,” IEEE Trans. Circuits Syst. CAS-25, 74–78 (1978).
[CrossRef]

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

1976 (1)

R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
[CrossRef]

1975 (1)

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

1973 (1)

R. B. Holmes, “Smoothness of certain metric projections on Hilbert spaces,” Trans. Am. Math. Soc. 183, 87–100 (1973).
[CrossRef]

1972 (1)

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

1971 (1)

R. H. Hanson, “A numerical method for solving Fredholm integral equations of the first kind using singular values.” J. Soc. Ind. Appl. Math. Num. Anal. 8, 616–622 (1971).

1967 (2)

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

H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
[CrossRef]

1965 (1)

1964 (3)

E. M. Hofstetter, “Construction of time-limited functions with specified autocorrelation functions,” IEEE Trans. Inf. Theory IT-10, 119–126 (1964).
[CrossRef]

H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations: II,” Arch. Rat. Mech. Anal. 17, 215–229 (1964).
[CrossRef]

H. J. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).

1963 (1)

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

1962 (1)

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: III,” Bell Syst. Tech. J. 41, 1295–1336 (1962).
[CrossRef]

1961 (2)

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

1957 (1)

E. J. Akutowicz, “On the determination of the phase of a Fourier integral—II,” Proc. Am. Math. Soc. 84, 234–238 (1957).

1956 (1)

E. J. Akutowicz, “On the determination of the phase of a Fourier integral—I,” Trans. Am. Math. Soc. 83, 179–192 (1956).

Akutowicz, E. J.

E. J. Akutowicz, “On the determination of the phase of a Fourier integral—II,” Proc. Am. Math. Soc. 84, 234–238 (1957).

E. J. Akutowicz, “On the determination of the phase of a Fourier integral—I,” Trans. Am. Math. Soc. 83, 179–192 (1956).

Arsenin, V. Y.

A. N. Tikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).

Baker, C. T.

C. T. Baker, The Numerical Treatment of Integral Equations (Oxford U. Press, Oxford, 1977).

Barakat, R.

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

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem,” J. Integral Eq. 9, 49–76 (1985).

G. Newsam, R. Barakat, “Essential dimension as a well-defined number of degrees of freedom of finite-convolution operators appearing in optics,” J. Opt. Soc. Am. A 2, 2040–2045 (1985).
[CrossRef]

R. Barakat, G. Newsam, “Necessary conditions for a unique solution to two-dimensional phase recovery,” J. Math. Phys. N. Y. 25, 3190–3193 (1984).
[CrossRef]

R. Barakat, G. Newsam, “A numerically stable iterative method for the inversion of wave-front aberrations from measured point-spread-function data,” J. Opt. Soc. Am. 70, 1255–1263 (1980).
[CrossRef]

R. Barakat, L. Riseberg, “Diffraction theory of the aberrations of a slit aperture,” J. Opt. Soc. Am. 55, 878–881 (1965).
[CrossRef]

Boas, P. P.

P. P. Boas, Entire Functions (Academic, New York, 1954).

Burge, R.

R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
[CrossRef]

Cadzow, J. A.

J. A. Cadzow, “An extrapolation procedure for bandlimited signals,” IEEE Trans. Acoust. Speech Signal Process. ASSP-27, 4–12 (1979).
[CrossRef]

Censor, Y.

Y. Censor, G. T. Herman, “Row generation methods for feasibility and optimization problems involving sparse matrices and their applications,” in Sparse Matrix Proceedings 1978, I. Duff, G. Stewart, eds. (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1979).

Ferwerda, H. A.

H. A. Ferwerda, “The phase reconstruction problem for wave amplitudes and coherence functions,” in Inverse Source Problems in Optics, H. P. Baltes, ed. (Springer-Verlag, New York, 1978).
[CrossRef]

Fiddy, M.

R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
[CrossRef]

Fienup, J. R.

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

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

Gerschberg, R.

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

Greenway, A.

R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
[CrossRef]

Gubin, L.

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

Hanson, R. H.

R. H. Hanson, “A numerical method for solving Fredholm integral equations of the first kind using singular values.” J. Soc. Ind. Appl. Math. Num. Anal. 8, 616–622 (1971).

Herman, G. T.

Y. Censor, G. T. Herman, “Row generation methods for feasibility and optimization problems involving sparse matrices and their applications,” in Sparse Matrix Proceedings 1978, I. Duff, G. Stewart, eds. (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1979).

Hofstetter, E. M.

E. M. Hofstetter, “Construction of time-limited functions with specified autocorrelation functions,” IEEE Trans. Inf. Theory IT-10, 119–126 (1964).
[CrossRef]

Holmes, R. B.

R. B. Holmes, “Smoothness of certain metric projections on Hilbert spaces,” Trans. Am. Math. Soc. 183, 87–100 (1973).
[CrossRef]

Landau, H. J.

H. J. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
[CrossRef]

H. J. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: III,” Bell Syst. Tech. J. 41, 1295–1336 (1962).
[CrossRef]

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

Lawton, W.

Misell, D. L.

D. L. Misell, “The phase problem in electron microscopy,” in Advances in Optics and Electron Microscopy, Vol. 7, V. E. Coslett, R. Barer, eds. (Academic, New York, 1978).

Napier, P. J.

P. J. Napier, “The brightness temperature distributions defined by a measured intensity interferogram,” N.Z. J. Sci. 15, 342–355.

Newsam, G.

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem,” J. Integral Eq. 9, 49–76 (1985).

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

G. Newsam, R. Barakat, “Essential dimension as a well-defined number of degrees of freedom of finite-convolution operators appearing in optics,” J. Opt. Soc. Am. A 2, 2040–2045 (1985).
[CrossRef]

R. Barakat, G. Newsam, “Necessary conditions for a unique solution to two-dimensional phase recovery,” J. Math. Phys. N. Y. 25, 3190–3193 (1984).
[CrossRef]

R. Barakat, G. Newsam, “A numerically stable iterative method for the inversion of wave-front aberrations from measured point-spread-function data,” J. Opt. Soc. Am. 70, 1255–1263 (1980).
[CrossRef]

G. Newsam, “Numerical reconstruction of partially known transforms,” Ph.D. dissertation (Harvard University, Cambridge, Mass., 1982).

Ortega, J. M.

J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic, New York, 1970), pp. 494–500.

Papoulis, A.

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

Pollak, H.

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: III,” Bell Syst. Tech. J. 41, 1295–1336 (1962).
[CrossRef]

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

Polyak, B.

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

Raik, E.

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

Rheinboldt, W. C.

J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic, New York, 1970), pp. 494–500.

Riseberg, L.

Ronkin, L.

L. Ronkin, Introduction to the Theory of Entire Functions of Several Complex Variables (American Mathematical Society, Providence, R.I., 1974).

Ross, G.

R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
[CrossRef]

Sabri, M. S.

M. S. Sabri, W. Steenart, “An approach to bandlimited extrapolation: The extrapolation matrix,” IEEE Trans. Circuits Syst. CAS-25, 74–78 (1978).
[CrossRef]

Saxton, W.

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

Slepian, D.

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

Steenart, W.

M. S. Sabri, W. Steenart, “An approach to bandlimited extrapolation: The extrapolation matrix,” IEEE Trans. Circuits Syst. CAS-25, 74–78 (1978).
[CrossRef]

Taylor, L. S.

L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-39, 381–391 (1981).

Tikhonov, A. N.

A. N. Tikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).

Walsh, G.

G. Walsh, Methods of Optimization (Wiley, New York, 1975).

Walther, A.

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

Widom, H.

H. J. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations: II,” Arch. Rat. Mech. Anal. 17, 215–229 (1964).
[CrossRef]

Youla, D. C.

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

Acta Math. (1)

H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37–52 (1967).
[CrossRef]

Appl. Opt. (1)

Arch. Rat. Mech. Anal. (1)

H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations: II,” Arch. Rat. Mech. Anal. 17, 215–229 (1964).
[CrossRef]

Bell Syst. Tech. J. (3)

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

H. J. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty: III,” Bell Syst. Tech. J. 41, 1295–1336 (1962).
[CrossRef]

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

J. A. Cadzow, “An extrapolation procedure for bandlimited signals,” IEEE Trans. Acoust. Speech Signal Process. ASSP-27, 4–12 (1979).
[CrossRef]

IEEE Trans. Antennas Propag. (1)

L. S. Taylor, “The phase retrieval problem,” IEEE Trans. Antennas Propag. AP-39, 381–391 (1981).

IEEE Trans. Circuits Syst. (3)

M. S. Sabri, W. Steenart, “An approach to bandlimited extrapolation: The extrapolation matrix,” IEEE Trans. Circuits Syst. CAS-25, 74–78 (1978).
[CrossRef]

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

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

IEEE Trans. Inf. Theory (1)

E. M. Hofstetter, “Construction of time-limited functions with specified autocorrelation functions,” IEEE Trans. Inf. Theory IT-10, 119–126 (1964).
[CrossRef]

J. Integral Eq. (1)

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem,” J. Integral Eq. 9, 49–76 (1985).

J. Integral Eq. Suppl. (1)

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

J. Math. Anal. Appl. (1)

H. J. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

J. Math. Phys. N. Y. (1)

R. Barakat, G. Newsam, “Necessary conditions for a unique solution to two-dimensional phase recovery,” J. Math. Phys. N. Y. 25, 3190–3193 (1984).
[CrossRef]

J. Opt. Soc. Am. (3)

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

J. Soc. Ind. Appl. Math. Num. Anal. (1)

R. H. Hanson, “A numerical method for solving Fredholm integral equations of the first kind using singular values.” J. Soc. Ind. Appl. Math. Num. Anal. 8, 616–622 (1971).

N.Z. J. Sci. (1)

P. J. Napier, “The brightness temperature distributions defined by a measured intensity interferogram,” N.Z. J. Sci. 15, 342–355.

Opt. Acta (1)

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

Opt. Eng. (1)

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

Optik (1)

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

Proc. Am. Math. Soc. (1)

E. J. Akutowicz, “On the determination of the phase of a Fourier integral—II,” Proc. Am. Math. Soc. 84, 234–238 (1957).

Proc. R. Soc. London Ser. A (1)

R. Burge, M. Fiddy, A. Greenway, G. Ross, “The phase problem,” Proc. R. Soc. London Ser. A 350, 191–212 (1976).
[CrossRef]

Trans. Am. Math. Soc. (3)

E. J. Akutowicz, “On the determination of the phase of a Fourier integral—I,” Trans. Am. Math. Soc. 83, 179–192 (1956).

H. J. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).

R. B. Holmes, “Smoothness of certain metric projections on Hilbert spaces,” Trans. Am. Math. Soc. 183, 87–100 (1973).
[CrossRef]

USSR Comp. Math. Math. Phys. (1)

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

Other (10)

Y. Censor, G. T. Herman, “Row generation methods for feasibility and optimization problems involving sparse matrices and their applications,” in Sparse Matrix Proceedings 1978, I. Duff, G. Stewart, eds. (Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1979).

G. Walsh, Methods of Optimization (Wiley, New York, 1975).

L. Ronkin, Introduction to the Theory of Entire Functions of Several Complex Variables (American Mathematical Society, Providence, R.I., 1974).

P. P. Boas, Entire Functions (Academic, New York, 1954).

J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic, New York, 1970), pp. 494–500.

A. N. Tikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).

D. L. Misell, “The phase problem in electron microscopy,” in Advances in Optics and Electron Microscopy, Vol. 7, V. E. Coslett, R. Barer, eds. (Academic, New York, 1978).

H. A. Ferwerda, “The phase reconstruction problem for wave amplitudes and coherence functions,” in Inverse Source Problems in Optics, H. P. Baltes, ed. (Springer-Verlag, New York, 1978).
[CrossRef]

G. Newsam, “Numerical reconstruction of partially known transforms,” Ph.D. dissertation (Harvard University, Cambridge, Mass., 1982).

C. T. Baker, The Numerical Treatment of Integral Equations (Oxford U. Press, Oxford, 1977).

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 (7)

Fig. 1
Fig. 1

Two sample realizations (— – —) and (—) of the reconstruction of G(ω) [Eq. (2.16)] in the presence of 3% noise in ℱcG [Eq. (2.14)].

Fig. 2
Fig. 2

Extrapolation of g(υ) [Eq. (2.15)] (see open circles) corresponding to — – — in Fig. 1.

Fig. 3
Fig. 3

Two examples of poor convergence of the alternating projection algorithm induced by ill conditioning.

Fig. 4
Fig. 4

Solution Ĝ to example 2 reached from an initial guess Ĝ0 with 1 = 20%: —, exact phase from Eq. (6.1); ○, reconstructed phase; – – –, exact modulus from Eq. (6.1); △, reconstructed modulus.

Fig. 5
Fig. 5

Solution Ĝ to example 2 reached from an initial guess Ĝ0 with 1 = 60%: —, exact phase from Eq. (6.1); ○, reconstructed phase; – – –, exact modulus from Eq. (6.1); △, reconstructed modulus.

Fig. 6
Fig. 6

Solution Ĝ to example 2a reached from an initial guess Ĝ0 with 1 = 60%: —, exact phase from Eq. (6.1); ○, reconstructed phase; – – –, exact modulus from Eq. (6.1); △, reconstructed modulus.

Fig. 7
Fig. 7

Solution Ĝ to example 2a reached from an initial guess Ĝ0 with 1 = 100%: —, exact phase from Eq. (6.1); ○, reconstructed phase; – – –, exact modulus from Eq. (6.1); △, reconstructed modulus.

Tables (2)

Tables Icon

Table 1 Relative Performance of Algorithms on Example 2 with Test Function G [Eq. (6.1)]a

Tables Icon

Table 2 Relative Performance of Algorithms on Example 2a with Test Function G [Eq. (6.1)]a

Equations (82)

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

Y = P T x y T and y x = inf z T z x .
( P D G ) ( ω ̂ ) = { G ( ω ̂ ) ω ̂ D 0 otherwise .
g ( υ ̂ ) = ( G ) ( ω ̂ ) = exp ( 2 π i υ ̂ ω ̂ ) G ( ω ̂ ) d ω ̂ .
P A P B G = P A g .
P A P B ψ i = σ i ϕ i .
G = i b i ψ i , P A g = i a i ϕ i .
P A P B G = P A g σ i b i = a i .
P A g = i a i ϕ i , with i | a i a i | 2 < 2 ,
G i p ( a i , σ i , γ ) ψ i ,
P ( a , σ , γ ) σ 1 for large σ 0 for small σ ,
p ( a , σ , γ ) = a σ 1 if σ γ = 0 σ < γ ,
p ( a , σ , γ ) = σ q σ q + 1 + γ q + 1 .
n ( c , α ) | D | · | E | c 2 N γ | D | | E | c 2 N 2 log ( α 1 1 ) log c + o ( c 2 N 3 ) ,
n = [ 4 c 2 + 2 b π 2 log ( 2 c 2 π ) ] ,
lim n σ n = ( 1 + e b ) 1 / 2 .
[ ( 1 t 2 ) ϕ ] + ( λ 4 π 2 c 2 t 2 ) ϕ = 0 ,
c G = ( P c g ) ( υ ) + μ ( υ )
g ( υ ) = 2 ( sin π υ π υ ) 2 .
G ( ω ) = 2 ( 1 | ω | ) .
g ( υ ) = | g ( 0 ) | exp [ i ( α + β υ ) ] k = 1 ( 1 υ υ k ) ,
g ( υ ) = exp [ i ( α + β υ ] B ( υ ) g ( υ ) , α , β IR ,
B ( υ ) = l = 1 B k l ( υ ) ,
B k ( υ ) = υ υ * k υ υ k .
( G ) = m , : 2 ( B ) L 2 ( A ) ,
1 ( G ) = | g | , 1 : 2 ( A ) L 2 ( A ) .
G i G j > 1 δ i ; but ( G i ) ( G j ) < .
G n + 1 = P i G n ,
i = ( n 1 ) mod M + 1 ,
S = { g L 2 ( IR ) : g ( υ ) = g ( υ ) for υ A }
S = { g L 2 ( IR ) : | g ( υ ) | = m ( υ ) for υ A }
T 1 = { G L 2 ( IR ) : G = 1 g , g S } ,
T M = { G L 2 ( IR : G ( ω ) = 0 for ω B } .
h = P S G H = 1 h = P 1 ( 1 g ) = P 1 G ,
T 2 = { G L 2 ( IR : G ( ω ) 0 for ω B }
T 2 = { G L 2 ( IR : | G ( ω ) | = n ( ω ) for ω B } .
Find G to minimize F ( G ) = i = 1 M 1 G P i G 2 .
H n + 1 = 1 M 1 i = 1 M 1 ( P i G n G n ) , G n + 1 = P M G n + λ n H n ,
λ m ( 0 , 2 ) if T M convex ( 0 , 1 ) otherwise .
F ( G n + 1 ) < F ( G n ) or G n + k = G n , k 1 .
F ( G ) = 2 i = 1 M ( G P i G ) .
P M ( G n + λ H n ) = G n + λ M 1 i = 1 M 1 P M P i G n ,
P c P 1 G = P c 1 F S G .
P S g = { m ( υ ) exp [ i arg g ( υ ) ] υ c I g ( υ ) otherwise ,
P S y = g P c g + P c P S P c g
P c P I G = G c * c G + c * P S c G .
( P c P 2 G ) ( ω ) = { n ( ω ) exp [ i arg g ( ω ) ] ω c I 0 otherwise ,
( P c P 2 G ) ( ω ) = { ( Re G ) ( ω ) if ( Re G ) ( ω ) and ω c I 0 otherwise .
d d λ F ( G n + λ H n ) = F ( G n + λ H n , H n ) = 2 i = 1 M 1 [ G n + λ H n P i ( G n + λ H n ) , H n ] .
minimize F n ( G ) = i = 1 M G P i G n 2 .
S n = { h : h = P c P S g n + ( g P c g ) , g S }
minimize F n ( G ) = G P T 1 n G 2 + i = 2 M G P i G n 2 .
[ c * c + ( M 2 ) ] L = c * P S g n + i = 2 M 1 P i G n
P i G P i G n + i ( G n ) ( G G n )
[ i ( G ) ] ( G P i G ) = 0 .
minimize F n ( G ) = i = 1 M 1 G P i G n i ( G n ) ( G G n ) 2 .
[ 1 ( G n M ( G n ) ] L = [ G n P 1 ( G n ) P M 1 G n ] .
F ( G ) F ( G n ) + F ( G n ) ( G G n ) + 1 2 ( G G n ) 2 F ( G n ) ( G G n ) .
F ( G ) = 2 i = 1 M ( g P i G ) , 2 F ( G ) = 2 i = 1 M ( i ( G ) ] .
minimize F n = F ( G n ) + F ( G n ( G G n ) + 1 2 ( G G n ) 2 F ( G n ) ( G G n ) ,
2 F ( G n ) L = F ( G n ) ,
P c 2 F ( G n ) P c L = P c F ( G n ) ,
f ( λ ) = λ 1 if | λ | 3 = 0 otherwise ,
f ( λ ) = λ 1 if λ 3 = 0 otherwise ,
[ i ( G ) ] ( G P i G ) = G P i G ,
{ i = 1 M 1 P c [ i ( G n ) ] P c } L = i = 1 M 1 ( G n P c P i G n )
{ i = 1 P c [ i ( G n ) ] 1 / 2 ] 2 P c } L = i = 1 M 1 P c [ i ( G n ) ] 1 / 2 G n P i G n ,
[ [ 1 ( G n ) ] 1 / 2 P c [ M 1 ( G n ) ] 1 / 2 P c ] L = [ G n P c P 1 G n G n P c P M 1 G n ] .
[ Re H ( ω ) Im H ( ω ) ]
[ 2 ( G ) ] ( ω ) = { [ sin θ cos θ cos θ sin θ ] [ 1 n ( ω ) | G ( ω ) | 0 0 1 ] [ sin θ cos θ cos θ sin θ ] ,
[ 2 ( G ) ] ( ω ) = { [ 0 0 0 1 ] if ( Re G ) ( ω ) > 0 and ω c I [ 1 0 0 1 ] otherwise .
f ( λ ) = | λ | 1 / 2 sign λ if | λ | 3 = 0 otherwise ,
f ( λ ) = | λ | 1 / 2 if λ 3 = 0 otherwise ,
P c [ 1 ( G ) ] P c = c * [ S ( g ) ] c ,
[ s ( g ) ] = [ cos ϕ sin ϕ sin ϕ cos ϕ ] [ 1 m ( υ ) | g ( υ ) | 0 1 0 ] [ cos ϕ sin ϕ sin ϕ cos ϕ ] ,
[ [ s ( g ) ] f 1 / 2 ( c ) f [ 2 ( G ) ] f 1 / 2 ] L = [ P c P S c G n P c G n G n ] f
Example 2 , | g k | = m k , Example 2 a , | g k | = m k , | G l | = n l , Example 2 b , | g k | = m k , G l 0 .
G ( ω ) = exp [ i 2 π W ( ω c ) ] ,
W ( ω c ) = W 3 S 3 ( ω c ) + W 4 W 4 ( ω c ) = W 3 [ ( ω c ) 3 3 5 ( ω c ) ] + W 4 [ ( ω c ) 4 6 7 ( ω c ) 2 ] .
G ̂ n + 1 = G ̂ n + λ n H ̂ n , g ̂ n + 1 = F ̂ W ̂ G ̂ n + 1 .
F ( G ̂ n ) < 10 5 or k = 0 2 λ n k H ̂ n k < 2 × 10 3 ,
| ( λ k n 3 λ k 1 n 3 λ k n 3 | × | F ( G ̂ n + λ k n 3 H ̂ n F ( G ̂ n ) | < 0.02 | F ( G ̂ n + λ k n 3 H ̂ n F ( G ̂ n ) | × | F ( G ̂ n + λ k n 3 H ̂ n ) F ( G ̂ n ) | < 0.02 k 5 .
= max { min { 4 γ n 1 H n 1 0.025 , 0.2 } , 0.002 } .

Metrics