V. Elser, “Random projections and the optimization of an algorithm for phase retrieval,” J. Phys. A. Math. Gen. 35, 1–13 (2002).

H. H. Bauschke, P. L. Combettes, D. R. Luke, “Phase retrieval, Gerchberg–Saxton algorithm, and Fienup vari ants: a view from convex optimization,” J. Opt. Soc. Am. A 19, 1334–1345 (2002).

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[CrossRef]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

T. Debaerdemaeker, C. Tate, M. M. Woolfson, “On the application of phase relationships to complex structures. XXVI. Developments of the Sayre-equation tangent formula,” Acta Crystallogr., Sect. A 44, 353–357 (1988).

[CrossRef]

D. Sayre, “On least-squares refinement of the phases of crystallographic structure factors,” Acta Crystallogr., Sect. A 28, 210–212 (1972).

[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).

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

[CrossRef]

D. Sayre, “The squaring method: a new method for phase determination,” Acta Crystallogr. 5, 60–65 (1952).

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[CrossRef]

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), Chap. 7, pp. 231–275.

H. A. David, Order Statistics, 2nd ed. (Wiley, New York, 1981).

T. Debaerdemaeker, C. Tate, M. M. Woolfson, “On the application of phase relationships to complex structures. XXVI. Developments of the Sayre-equation tangent formula,” Acta Crystallogr., Sect. A 44, 353–357 (1988).

[CrossRef]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

V. Elser, “Random projections and the optimization of an algorithm for phase retrieval,” J. Phys. A. Math. Gen. 35, 1–13 (2002).

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

[CrossRef]
[PubMed]

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), Chap. 7, pp. 231–275.

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

C. Giacovazzo, Direct Phasing in Crystallography (Oxford U. Press, Oxford, UK, 1998).

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[CrossRef]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

K. Y. J. Zhang, P. Main, “Histogram matching as a new density modification technique for phase refinement and extension of protein molecules,” Acta Crystallogr. Sect. A 46, 41–46 (1990).

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[CrossRef]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

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

D. Sayre, “On least-squares refinement of the phases of crystallographic structure factors,” Acta Crystallogr., Sect. A 28, 210–212 (1972).

[CrossRef]

D. Sayre, “The squaring method: a new method for phase determination,” Acta Crystallogr. 5, 60–65 (1952).

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[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]

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]

T. Debaerdemaeker, C. Tate, M. M. Woolfson, “On the application of phase relationships to complex structures. XXVI. Developments of the Sayre-equation tangent formula,” Acta Crystallogr., Sect. A 44, 353–357 (1988).

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[CrossRef]

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

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[CrossRef]

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

T. Debaerdemaeker, C. Tate, M. M. Woolfson, “On the application of phase relationships to complex structures. XXVI. Developments of the Sayre-equation tangent formula,” Acta Crystallogr., Sect. A 44, 353–357 (1988).

[CrossRef]

H. Stark, Y. Yang, Vector Space Projections (Wiley, New York, 1998).

K. Y. J. Zhang, P. Main, “Histogram matching as a new density modification technique for phase refinement and extension of protein molecules,” Acta Crystallogr. Sect. A 46, 41–46 (1990).

[CrossRef]

D. Sayre, “The squaring method: a new method for phase determination,” Acta Crystallogr. 5, 60–65 (1952).

[CrossRef]

K. Y. J. Zhang, P. Main, “Histogram matching as a new density modification technique for phase refinement and extension of protein molecules,” Acta Crystallogr. Sect. A 46, 41–46 (1990).

[CrossRef]

T. Debaerdemaeker, C. Tate, M. M. Woolfson, “On the application of phase relationships to complex structures. XXVI. Developments of the Sayre-equation tangent formula,” Acta Crystallogr., Sect. A 44, 353–357 (1988).

[CrossRef]

D. Sayre, “On least-squares refinement of the phases of crystallographic structure factors,” Acta Crystallogr., Sect. A 28, 210–212 (1972).

[CrossRef]

C. M. Weeks, H. A. Hauptman, G. D. Smith, R. H. Blessing, M. M. Teeter, R. Miller, “Crambin: a direct solution for a 400 atom structure,” Acta Crystallogr., Sect. D 51, 33–38 (1995).

[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, 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]

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]

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

[CrossRef]

H. H. Bauschke, P. L. Combettes, D. R. Luke, “Phase retrieval, Gerchberg–Saxton algorithm, and Fienup vari ants: a view from convex optimization,” J. Opt. Soc. Am. A 19, 1334–1345 (2002).

[CrossRef]

V. Elser, “Random projections and the optimization of an algorithm for phase retrieval,” J. Phys. A. Math. Gen. 35, 1–13 (2002).

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

[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).

R. Miller, G. T. DeTitta, R. Jones, D. A. Langs, C. M. Weeks, H. A. Hauptman, “On the application of the minimal principle to solve unknown structures,” Science 259, 1430–1433 (1993).

[CrossRef]
[PubMed]

For a smooth subspace C with tangent space X at a∈C, the affine approximation to C at a is the space C′=X+a. By taking the set of all differences of elements in C′, one recovers the linear space: X=C′-C′.

V. Elser, “Linear time heuristic for the bipartite Euclidean matching problem,” (manuscript available from the author: ve10@cornell.edu).

In the case of support constraint with positivity, the constraint subspace is a smooth space with boundary, and the relevant dimensionality is that of the space without boundary.

H. A. David, Order Statistics, 2nd ed. (Wiley, New York, 1981).

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), Chap. 7, pp. 231–275.

C. Giacovazzo, Direct Phasing in Crystallography (Oxford U. Press, Oxford, UK, 1998).

H. Stark, Y. Yang, Vector Space Projections (Wiley, New York, 1998).

The “difference map” considered here should not be confused with the “map” of the electron density studied by crystallographers in “difference Fourier synthesis.” The latter, in our notation, corresponds to πmod(ρ)-ρ, whereas the difference that we consider involves a projection on a prioriconstraints as well.

The term “stagnation” is interpreted to be the vanishing of the change between iterates.

The term “subspace” denotes a general subset of EN and in almost all cases of interest is a smooth submanifold, possibly with boundary. When encountered in the discussion, linear or affine subspaces will be explicitly identified as such.