Recovery of Sparse 1-D Signals from the Magnitudes of their Fourier Transform

• Phase retrieval arises in applications including X-ray crystallography, astronomical imaging, and speech recognition.Source: §1 · p. 1
• In one dimension, autocorrelation is not a one-to-one map, so recovering a signal generally requires additional prior information.Source: §1 · p. 1
• Sparsity limits the valid phase combinations, and naturally sparse signals occur in applications such as astronomy and electron microscopy.Source: §1 · p. 2
• The paper proves almost-sure recovery conditions and proposes two non-iterative algorithms for extracting sparse signals from autocorrelation.Source: §1 · p. 2

• The autocorrelation definition uses cyclic indexing before it is rewritten in the z-domain.Source: §2 · p. 2
• For real signals, conjugate and reciprocal symmetries make autocorrelation zeros occur in quadruples.Source: §2 · p. 2
• Spectral factorization assigns each zero quadruple between X(z) and X(z−1), yielding exponentially many valid factorizations as the number of quadruples grows.Source: §2 · p. 2
• Lemma 2.1 frames distinct real signals with identical autocorrelation through finite-length signals g and h, including the time reversal of h.Source: §2 · p. 3

• Uniform support means the support indices form an arithmetic progression, and sparsity is the support size.Source: §3 · p. 3
• For f=g*h, support sparsity kgh equals kg+kh−1 iff both factor supports are uniform; missing support locations reduce the resulting manifold dimension by γ=kgh−k.Source: §3 · p. 4
• Dimension counting shows that added zero constraints lower the dimension of ambiguous factorizations when both the signal and its alternative have non-uniform support.Source: §3 · p. 4, Case II: kgh = kg + kh −1 · p. 5
• Signals are uniquely recoverable from autocorrelation almost surely iff their support is non-uniform.Source: §3 · p. 4
• When f or its alternative has uniform support, there is no additional dimension reduction, and unique recovery is almost surely not possible.Source: Case II: kgh = kg + kh −1 · p. 5

4.1 Algorithm 1

• At sparsity o(n^1/3), Algorithm 1 recovers support and then the signal from autocorrelation with very high probability.Its support-recovery guarantee and endpoint-gap recovery both hold in this regime.Source: §4.1 · p. 5, Algorithm 1 · pp. 6–7

Algorithm 1

• Algorithm 1 identifies support using autocorrelation distances and set intersections, then recovers the signal from a connected graph with an odd cycle.The graph's weighted edges encode autocorrelation values for support pairs whose separation is unique.Source: Algorithm 1 · p. 7
• The graph needed for signal extraction is connected and contains an odd cycle with very high probability when sparsity is o(n^1/3).Under these conditions, the signal is recovered up to a global sign.Source: Algorithm 1 · p. 7

4.2 Algorithm 2

• Algorithm 2 uses semidefinite relaxation and separates recovery into support estimation followed by signal estimation on that support.The paper assumes the signal's sparsity is known for support estimation.Source: §4.2 · p. 8, §4.2.1 · p. 8

4.2.1 Support Recovery

• For support recovery, the method assumes signal support is contained in autocorrelation support (no cancellation); it lifts binary support u to PSD S=uuT with entries in [0, 1].It assumes the signal’s sparsity, meaning its number of nonzero locations, is known.Source: §4.2.1 · p. 8

4.2.2 Signal Recovery

• For signal recovery, Algorithm 2 lifts x to X=xxT, zero-pads the signal for an m=2n DFT, and uses squared Fourier magnitudes and support constraints in L1-minimization.The Fourier-domain constraints equate measured squared magnitudes with traces involving X.Source: §4.2.2 · p. 9

5 Simulation Results

• Figure 1 reports successful recovery using Algorithm 1 for signals with sparsity s = o(n^1/3), plotting success rate against sparsity at n = 8192 (n^1/3 ≈ 20).Source: §5 · p. 9, Figure 1 · p. 9
• Algorithm 1 is computationally very cheap but is not robust to noise because of error propagation.Source: §5 · p. 10
• Numerical simulations suggest Algorithm 2 recovers signals up to sparsity s = o(n^1/2) and is robust to noise.Figure 2 plots success rate against sparsity for n = 64, where n^1/2 = 8.Source: §5 · p. 10, Figure 2 · p. 10

6 Appendix

• Lemma 6.1 bounds P(X1 − pX2 = c) by s/n for geometric random variables when s = n^alpha, alpha < 1.The stated condition also requires n > n(ε).Source: §6 · p. 10

6.1 Proof of Lemma 6.1

• The proof of Lemma 6.1 states its condition for n > n(ε).Source: §6.1 · p. 11

6.2 Proof of Corollary 4.2

• The proof of Corollary 4.2 invokes Lemma 6.1.Source: §6.2 · p. 11