PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse Phase Retrieval from Short-Time Fourier Measurements

Yonina C. Eldar, Pavel Sidorenko, Dustin G. Mixon, Shaby Barel, Oren Cohen

arXiv:1411.1380v1cs.ITmath.IT

TL;DR

Fourier-magnitude phase retrieval can be non-unique, and efficient, robust recovery remains difficult. This paper uses STFT-magnitude measurements, proves uniqueness for nonvanishing inputs under stated conditions, and adapts GESPAR for sparse recovery. Simulations report better performance than oversampled Fourier magnitude recovery with the same number of measurements when STFT redundancy is introduced.

  • Problem

    Many 1D signals share a Fourier magnitude, and efficient, robust recovery can remain unclear even when a unique solution exists.

    Source: §I · p. 1

  • Method

    The paper establishes an STFT-magnitude uniqueness result for nonvanishing inputs under conditions and adapts GESPAR to recover sparse inputs from STFT measurements.

    Source: §I · p. 1, B. Phase Retrieval · p. 2

  • Results

    STFT measurements can give far better sparse-recovery performance than oversampled DFT measurements at the same measurement count; simulations report improved performance when L < 16 introduces redundancy.

    Source: §V · p. 4, §IV · p. 4

  • Takeaways & Limitations

    GESPAR can exploit STFT measurement redundancy and input sparsity, with high recovery probability when sufficient redundancy is introduced.

    Source: §V · p. 4

    The uniqueness theorem covers nonvanishing signals with L = 1; it provides no guarantee for sparse signals.

    Source: B. Phase Retrieval · p. 2

Abstract

from arXiv · show

We consider the classical 1D phase retrieval problem. In order to overcome the difficulties associated with phase retrieval from measurements of the Fourier magnitude, we treat recovery from the magnitude of the short-time Fourier transform (STFT). We first show that the redundancy offered by the STFT enables unique recovery for arbitrary nonvanishing inputs, under mild conditions. An efficient algorithm for recovery of a sparse input from the STFT magnitude is then suggested, based on an adaptation of the recently proposed GESPAR algorithm. We demonstrate through simulations that using the STFT leads to improved performance over recovery from the oversampled Fourier magnitude with the same number of measurements.

I. INTRODUCTION

The introduction frames 1D phase retrieval as both non-unique from Fourier magnitudes and difficult to solve efficiently, then motivates STFT measurements and sparse recovery as a route to broader recovery. The paper proposes an STFT-based uniqueness result and a sparse GESPAR adaptation, evaluated against oversampled Fourier measurements.

I. INTRODUCTION

  • Many 1D signals share the same Fourier magnitude, even after excluding trivial equivalences and restricting support to a known range.Phase retrieval also arises in applications including electron microscopy, crystallography, optical imaging, and ultra-short laser-pulse diagnostics.Source: §I · p. 1
  • Sparse Fourier-magnitude recovery has uniqueness results under conditions including collision-free autocorrelation and restrictions on sparsity and measurement length.One cited result requires M ≥ 2N − 1 and k ≠ 6; another gives a prime-length condition M ≥ k^2 − k + 1.Source: §I · p. 1
  • Even when a solution is unique, efficient and robust recovery remains unclear; alternating-projection methods can require precise support information and may converge to erroneous results.Sparse GESPAR had previously been reported to outperform SDP and Fienup-based algorithms at low computational complexity.Source: §I · p. 1
  • STFT-magnitude phase retrieval has been used in speech and audio processing, ultrashort-pulse characterization, and ptychographical CDI.Both Fienup-type methods and SDP approaches have been extended to STFT-magnitude recovery.Source: §I · p. 1
  • STFT redundancy enables unique recovery for arbitrary nonvanishing inputs under mild conditions, while adapted GESPAR recovers sparse inputs even in cases where Fourier-magnitude recovery fails.The comparison uses the same number of measurements in both settings.Source: §I · p. 1

A. The STFT

The section defines the STFT for a length-N signal using a window and a time-spacing parameter. It also introduces inversion through an inverse DFT and subsequent recovery of x[n].

A. The STFT

  • The STFT is defined for a length-N signal x[n] over 0 ≤ n ≤ N − 1.The definition uses a window g[n] and parameter L; L is the separation in time between adjacent sections.Source: A. The STFT · p. 1
  • The window g[n] is assumed to be periodically extended over the boundaries in the STFT definition.Source: A. The STFT · p. 1
  • Inversion begins by taking the inverse DFT of Xg(m, k), followed by a step to obtain x[n].Source: A. The STFT · p. 2

B. Phase Retrieval

With L = 1, STFT magnitude uniquely determines every nonvanishing signal up to a global phase under stated window and length conditions. Sparse signals can nevertheless remain ambiguous: separated support intervals can produce identical STFT magnitudes even for any L.

B. Phase Retrieval

  • For L = 1, STFT magnitude uniquely determines every nonvanishing signal up to global phase when the window conditions hold, N ≥ 2W − 1, and N and W − 1 are coprime.For the N-periodic square window, condition (i) holds when N and W are coprime.Source: B. Phase Retrieval · p. 2
  • Summing STFT power over frequency yields a circulant linear system for |x[n]|^2; after recovering magnitudes, endpoint autocorrelation values provide relative phases that can be propagated across the signal.The proof requires nonvanishing x[n] to divide out known magnitudes and determines the signal up to global phase.Source: B. Phase Retrieval · p. 2
  • The uniqueness proof relies on L = 1; for L > 1 its linear system is underdetermined, although simulations demonstrate feasible recovery and permit Fourier length equal to window length.The authors attribute this boundary to the proof technique, noting that the STFT has additional redundancy not used by the proof.Source: B. Phase Retrieval · p. 2
  • Signals supported on intervals separated by at least W can have identical STFT magnitudes after one component changes sign, so sparse recovery is not always unique for any L.For a rectangular window, the paper illustrates sparse segments that can shift within an interval and change phase without affecting the STFT magnitude; it also shows a 50-nonzero random signal recovered with GESPAR.Source: B. Phase Retrieval · pp. 2–3

C. Sparse Phase Retrieval

The section formulates sparse STFT phase retrieval as recovery of sparse coefficients from quadratic measurements. It applies GESPAR to those measurements to exploit sparsity.

C. Sparse Phase Retrieval

  • The section identifies Griffin–Lim as an iterative STFT phase-retrieval algorithm that updates window estimates and combines them into a signal estimate.Its listed inputs are squared STFT magnitudes and a window; it returns an estimate of x.Source: C. Sparse Phase Retrieval · p. 3
  • The goal is to recover the signal, or its sparse coefficients, from the STFT magnitude by exploiting sparsity.The signal is represented as x = Ds, where s has k nonzero entries and k ≪ N.Source: C. Sparse Phase Retrieval · p. 3
  • GESPAR is applied to the squared STFT magnitudes, expressed as quadratic functions of the sparse coefficients.The measurements use matrices formed from the window and DFT, with identity-matrix columns also specified.Source: C. Sparse Phase Retrieval · p. 3

III. RECOVERY ALGORITHMS

The section contrasts alternating-projection approaches with sparse GESPAR recovery from quadratic STFT measurements. Its comparison holds the number of measurements equal across STFT and oversampled Fourier applications of GESPAR.

III. RECOVERY ALGORITHMS

  • Griffin–Lim and PCGP are presented as alternating-projection approaches; PCGP updates its signal estimate using a rank-one approximation from an SVD.The DFT length K may be any integer at least as large as the window length W.Source: §III · p. 3
  • The proposed sparse-recovery approach applies GESPAR to quadratic measurements to exploit sparsity in the input.GESPAR uses a 2-opt local search that updates support using the objective gradient and minimizes the objective over the support with damped Gauss–Newton.Source: §III · pp. 3–4
  • STFT GESPAR applies GESPAR to squared STFT magnitudes, while PS GESPAR recovers from the squared Fourier magnitude using the same measurement count.The shared count is P = MK, where M is the number of windows and K is the DFT length per window.Source: §III · p. 4

IV. SIMULATIONS

The simulations compare sparse-recovery methods across sparsity, measurement count, noise, and DFT length. They report better performance from redundant STFT measurements than from oversampled Fourier measurements in the tested redundant settings, and improved NMSE as DFT length increases.

IV. SIMULATIONS

  • The simulations use random normalized Gaussian bases and sparse inputs with randomly chosen supports and Gaussian nonzero values.The STFT uses a square window of length W = 16.Source: §IV · p. 4
  • For L < 16, redundant STFT measurements improve recovery over oversampled DFT measurements, and GESPAR outperforms GLA and PCGP.Figure 2 plots recovery probability versus sparsity k for measurement counts of 64, 128, 256, and 512; success is normalized squared error below 10^-2 across 100 simulations.Source: §IV · p. 4, Figure 2 · p. 4
  • At L = 16, the STFT has no redundancy and shows no advantage over the Fourier approach.The first simulation uses N = 64, K = W = 16, and measurement counts P = 512, 256, 128, and 64 for L = 2, 4, 8, and 16.Source: §IV · p. 4
  • Increasing DFT length improves recovery, with a significant improvement when K ≥ 16 measures all Fourier components.Figure 3 reports normalized MSE versus sparsity for K = 2, 4, 8, 16, and 32 at SNR values of 5, 15, 25, and 35 dB.Source: §IV · p. 4, Figure 3 · p. 4

V. CONCLUSION

The conclusion argues that combining sparsity with STFT measurements can improve phase retrieval over oversampled DFT measurements at the same measurement count. It identifies recovery conditions for sparse inputs as an open theoretical direction.

V. CONCLUSION

  • With the same number of measurements, STFT can perform far better than oversampled DFT for phase retrieval.The conclusion attributes high recovery probability to exploiting both measurement redundancy and input sparsity, provided sufficient redundancy is introduced.Source: §V · p. 4
  • The conclusion identifies recovery conditions for sparse inputs, including sparsity level and basis, as open theoretical questions.It also leaves open how large L can be while still ensuring recovery for generic inputs.Source: §V · p. 4
  • The paper proposes exploiting sparsity together with the STFT to improve phase-retrieval performance.Source: §V · p. 4
Loading 1411.1380v1…