Source-linked AI summary
STFT Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
Kishore Jaganathan, Yonina C. Eldar, Babak Hassibi
TL;DR
Fourier-magnitude phase retrieval requires additional information for unique signal recovery. This paper studies STFT magnitude, proves almost-sure uniqueness under overlap, and analyzes STliFT recovery, with guarantees established for particular settings.
Problem
Fourier-magnitude phase retrieval is ill-posed, and additional information is needed to identify the underlying signal uniquely.
Source: §I · p. 1Method
The paper analyzes STFT-magnitude uniqueness and studies a semidefinite relaxation-based recovery algorithm, STliFT.
Source: §I · pp. 1–2Results
With L < W, almost all non-vanishing signals are uniquely identifiable up to global phase; STliFT recovery is proved for known-sample and L = 1 settings.
Source: §VI · p. 6Takeaways & Limitations
For W = o(N), super-resolution reduces the number of phaseless measurements to (4 + o(1))N.
Source: §VI · p. 6STliFT recovery guarantees are established for settings with a known signal portion or L = 1, rather than for the full conjectured regime.
Source: §VI · p. 6
Abstract
from arXiv · showhide
The problem of recovering a signal from its Fourier magnitude is of paramount importance in various fields of engineering and applied physics. Due to the absence of Fourier phase information, some form of additional information is required in order to be able to uniquely, efficiently and robustly identify the underlying signal. Inspired by practical methods in optical imaging, we consider the problem of signal reconstruction from the Short-Time Fourier Transform (STFT) magnitude. We first develop conditions under which the STFT magnitude is an almost surely unique signal representation. We then consider a semidefinite relaxation-based algorithm (STliFT) and provide recovery guarantees. Numerical simulations complement our theoretical analysis and provide directions for future work.
I. INTRODUCTION
STFT magnitude measurements address phase retrieval by adding overlap between adjacent time sections. The paper develops almost-sure uniqueness guarantees and studies STliFT recovery, with guarantees proved for specific settings.
Motivation
- Phase retrieval reconstructs signals from Fourier magnitude, a measurement used across engineering and applied-physics fields.The paper frames the underlying problem as ill-posed and notes that additional information is needed for unique identification.Source: §I · p. 1
- STFT measurements are motivated by applications including ultrashort-pulse measurement, Fourier ptychography, and speech, where spectral content changes over time.Overlap between adjacent short-time sections introduces measurement redundancy and mitigates uniqueness and algorithmic issues.Source: §I · p. 1
Uniqueness guarantees
- Almost all non-vanishing signals are uniquely identifiable up to global phase from STFT magnitude when adjacent sections overlap; sparse signals with limited consecutive zeros are also covered.The sparse-signal guarantee is stated for fewer than min{W − L, L} consecutive zeros.Source: §I · p. 1
Recovery algorithms
- STliFT is a semidefinite relaxation-based algorithm; earlier iterative methods such as Griffin-Lim [38] and STFT-GESPAR work in practice but lack theoretical guarantees.The paper reports numerical simulations and develops theoretical guarantees for STliFT.Source: §I · pp. 1–2
- STliFT is conjectured to recover most non-vanishing signals when adjacent sections differ in at most half their indices, using (4 + o(1))N phaseless measurements after super-resolution.The paper proves the conjecture when a small signal portion is known and when adjacent sections differ in one index, then extends these results to sparse signals.Source: §I · p. 2
II. PROBLEM SETUP
The setup represents a signal’s STFT as Fourier measurements of windowed signal sections. The magnitude-square measurements can be restricted to selected frequency indices, reducing their number when the window is short relative to the signal.
Notation
- The signal x has length N and the window w has length W; L is the time separation between adjacent sections, and R is the number of sections.The supplied passage introduces the STFT notation Y_w for x with respect to w.Source: §II · p. 2
STFT definition
- Each STFT column is the N-point DFT of the signal multiplied elementwise by a shifted, flipped window, yielding regularly sampled windowed sections.The window shifts by L time units; R denotes the number of short-time sections.Source: §II · p. 2
Measurements
- STFT phase retrieval uses magnitude-square measurements, and equivalent recovery can use only frequency indices 1 through M when 2W ≤ M ≤ N.The reduced measurement set is especially useful when W ≪ N; the algorithm section further reduces measurements per section through super-resolution.Source: §II · p. 2
III. UNIQUENESS GUARANTEES
The section reviews uniqueness results for STFT phase retrieval and states that overlap is necessary to identify most signals. Without overlap, relative ambiguities between windowed sections remain unresolved.
Prior results
- Table I summarizes uniqueness results for STFT phase retrieval in the range 2W ≤ M ≤ N.The supplied table passage gives its scope but not individual result values.Source: Table I · p. 3, §III · p. 3
Uniqueness conditions
- L < W is necessary for unique identification of most signals; at L = W, non-overlapping sections leave relative phase, time-shift, or conjugate-flip ambiguities unresolved.For a length-3 example with W=L=2 and an all-ones window, (1, 2, 3) and (1, −2, −3) have identical STFT magnitudes.Source: §III · p. 3
- When L > W, some signal locations are not measured, so the STFT magnitude cannot uniquely identify most signals.Source: §III · p. 3
A. Non-vanishing signals
Under conditions on the window and STFT parameters, the STFT magnitude uniquely identifies almost all non-vanishing signals up to a global phase. The proof links uniqueness across overlapping adjacent short-time sections.
A. Non-vanishing signals
- Almost all non-vanishing signals are uniquely identified up to a global phase when the window and parameters {w, L, M} satisfy the stated conditions.The supplied theorem states this result but does not include the conditions themselves.Source: A. Non-vanishing signals · p. 3
- The proof uses dimension counting to establish uniqueness from the compatible reconstructions of adjacent short-time sections.The proof outline considers adjacent sections and their overlap.Source: A. Non-vanishing signals · p. 3
- For almost all non-vanishing signals, each pair of adjacent sections has a singleton intersection, identifying the windowed signal up to phase.Because adjacent sections overlap, their phase-ambiguous reconstructions determine the signal up to a global phase.Source: A. Non-vanishing signals · p. 3
B. Sparse signals
Sparse signals can have ambiguities that non-vanishing signals do not, especially when long zero runs or widely separated support prevent phase information from linking sections. The paper gives a uniqueness guarantee for sparse signals with a bounded number of consecutive zeros.
B. Sparse signals
- For certain window and hop choices, a sparse signal and its time-shift can have identical STFT magnitudes, leaving the time-shift ambiguity unresolved.The example uses L ≥ 2, W a multiple of L, and a window equal to one across its support.Source: B. Sparse signals · pp. 3–4
- When nonzero support intervals are separated by more than W, the window cannot establish their relative phase, so x1 + x2 and x1 − x2 have equal STFT magnitudes.This ambiguity applies to the described non-overlapping intervals for any choice of L.Source: B. Sparse signals · p. 4
- Almost all sparse signals with fewer than min{W − L, L} consecutive zeros are uniquely identified up to global phase and time-shift when the stated parameters satisfy the conditions.The supplied condition also includes 2W ≤ M ≤ N.Source: B. Sparse signals · p. 4
- The zero-run bound ensures adjacent sections have nonzero values among their overlapping and non-overlapping indices for sufficient pairs of sections.This is the stated role of the min{W − L, L} bound in the proof.Source: B. Sparse signals · p. 4
IV. RECOVERY ALGORITHMS
The Griffin–Lim algorithm adapts alternating projections to STFT phase retrieval by minimizing a least-squares objective. Its objective decreases across iterations, but recovery guarantees are not available.
IV. RECOVERY ALGORITHMS
- Griffin–Lim alternates projections onto time-domain and STFT-magnitude constraints, starting from a random initialization to minimize a least-squares objective.The objective is shown to decrease monotonically as iterations progress.Source: §IV · p. 4
- With substantial overlap between adjacent sections, Griffin–Lim has an empirical ability to converge to the global minimum, but it has no theoretical recovery guarantees.Source: §IV · p. 4
A. Semidefinite relaxation-based algorithm
The section presents STliFT, a semidefinite-relaxation method for STFT phase retrieval, and conditions for unique recovery. It gives a conjecture, proves guarantees in specific settings, and reports simulation evidence for stable recovery in noise.
A. Semidefinite relaxation-based algorithm
- The method lifts x to X = xx⋆ and relaxes the rank-one constraint, yielding a convex program; unique feasibility makes the noiseless objective choice immaterial.Under the stated conditions, unique recovery of the matrix yields recovery of the signal up to global phase.Source: A. Semidefinite relaxation-based… · pp. 4–5
- STliFT is conjectured to have a unique solution for most non-vanishing signals when the window is non-vanishing, 2L ≤ W ≤ N/2, and 4L ≤ M ≤ N.The conjecture is based on extensive numerical simulations.Source: A. Semidefinite relaxation-based… · p. 4
- When W = o(N), the measurement count is (4 + o(1))N, which the paper describes as order-wise optimal.For L = 1, the count is 4(N + W).Source: A. Semidefinite relaxation-based… · p. 5
- The paper develops an STFT-specific proof technique because the cited RIP and concentration-based certificate techniques do not directly apply to these measurement vectors.The resulting proof establishes the conjecture only with additional assumptions.Source: A. Semidefinite relaxation-based… · p. 5
- With the first ⌈L/2⌉ signal samples known a priori, the convex program has a unique feasible matrix for almost all non-vanishing signals under Theorem IV.1’s conditions.When W = o(N), the required prior portion is less than W/N of the signal.Source: A. Semidefinite relaxation-based… · p. 5
- For L = 1, Theorem IV.2 requires no prior information; when W = 2, it uses at most 4N + 8 phaseless measurements.Source: A. Semidefinite relaxation-based… · p. 5
- For sparse signals with at most W − 2L consecutive zeros, the convex program has a unique feasible matrix under the stated conditions, including either L = 1 or prior knowledge of L samples from the first nonzero index.Source: A. Semidefinite relaxation-based… · p. 5
B. Noisy Setting
In the noisy setting, STliFT replaces the convex program’s constraints with noise-tolerant constraints. Simulations suggest stable recovery for most non-vanishing signals under certain conditions.
B. Noisy Setting
- The measurements in the noisy setting include additive noise for each short-time section.Source: B. Noisy Setting · p. 5
- With noise vectors bounded by η in ℓ2 norm, the convex-program constraints can be replaced to implement noisy STliFT.The authors recommend trace minimization as the objective.Source: B. Noisy Setting · p. 5
- Numerical simulations suggest STliFT can stably recover most non-vanishing signals in noise under certain conditions.Source: B. Noisy Setting · p. 5
V. NUMERICAL SIMULATIONS
The simulations examine STliFT’s recovery across window, shift, and measurement choices, then test its behavior under noise. They report high-probability recovery in specified noiseless regimes and stable recovery as SNR varies.
V. NUMERICAL SIMULATIONS
- STliFT recovers with very high probability when 2L ≤ W ≤ N/2 and fails with very high probability when 2L > W.The trials use N = 32 and M = 4L; the corresponding probability is plotted in Fig. 2a.Source: §V · pp. 5–6, Figure 2 · p. 6
- Recovery succeeds in the 4L ≤ M < 2W regime for N = 32 and W = 16.The probability across shift length and measurements per short-time section is plotted in Fig. 2b.Source: §V · p. 6
- A linear relationship between NMSE (dB) and SNR (dB) indicates stable recovery in noise, with greater overlap tending to yield more stable recovery.Fig. 3 plots NMSE versus SNR for N = 32 and M = 2W.Source: §V · p. 6, Figure 3 · p. 6
VI. CONCLUSIONS AND FUTURE DIRECTIONS
The conclusions state uniqueness conditions for STFT magnitude and summarize STliFT’s recovery guarantees and measurement reduction under stated assumptions. The authors identify proof of the broader conjecture and noisy stability analysis as future work.
VI. CONCLUSIONS AND FUTURE DIRECTIONS
- If L < W ≤ N/2, almost all non-vanishing signals are uniquely identified from their STFT magnitude up to a global phase.The result extends to sparse signals with fewer than min{W − L, L} consecutive zeros.Source: §VI · p. 6
- For W = o(N), super-resolution reduces the phaseless measurements to (4 + o(1))N, and the STliFT recovery conjecture is proved when the first samples are known or L = 1.The additional assumptions are argued to be asymptotically reasonable when W ≪ N.Source: §VI · p. 6
- The sparse-signal extension permits at most W − 2L consecutive zeros.Source: §VI · p. 6
- Future work includes proving the recovery conjecture without additional assumptions and analyzing stability in noise.The authors also call for a fuller analysis of the phase transition at 2L = W.Source: §VI · p. 6
VII. EQUIVALENT DEFINITION OF STFT PHASE RETRIEVAL
This section relates STFT magnitude recovery to short-time autocorrelation and develops uniqueness and semidefinite recovery arguments under non-vanishing and sparsity conditions, including a proof based on matching sampled entries and positive semidefinite completion.
VII. EQUIVALENT DEFINITION OF STFT PHASE RETRIEVAL
- The values Zw[m, r] for 1 ≤ m ≤ 2W − 1 determine the full short-time autocorrelation aw[m, r].The passages state that 2W phaseless measurements per short-time section suffice to infer the short-time autocorrelation.Source: §VII · p. 8
VIII. PROOF OF THEOREM III.1
- For non-vanishing windows with W ≤ N/2, the non-uniquely identifiable signals form a measure-zero set.The proof characterizes ambiguities through paired convolution factorizations and covers the exceptional signals by images of continuously differentiable maps from R2N−2 into a 2N−1-dimensional signal manifold.Source: §VIII · pp. 8–9
IX. PROOF OF COROLLARY III.1
- Sparse-signal uniqueness proof requires fewer than min{L, W − L} consecutive zeros in the support pattern.The proof uses the limits of L and W−L consecutive zeros to ensure nonzero signal entries in non-overlapping and overlapping short-time-section indices; it accommodates time-shift ambiguity by constraining hr[0] to at most T values.Source: §IX · p. 10
X. PROOF OF THEOREM IV.1
- With 2W ≤ M ≤ N, the proof incrementally fixes entries of every feasible matrix to those of x0x0*, yielding a unique positive semidefinite completion.The passage describes matching the diagonal and first W−L off-diagonals, then applying this argument across short-time sections.Source: §X · p. 10
- When 2L ≤ W, prior information and measurements for r = 1, 2 uniquely determine S0, and incremental constraints match the diagonal and first W − L off-diagonals of x0x⋆0.The proof also extends its arguments to sparse signals.Source: §X · p. 11
- A unique positive semidefinite completion exists from the diagonal and first W − L off-diagonals when x0 has fewer than W − L consecutive zeros.Source: §X · p. 11
- If x0 has at most W − 2L consecutive zeros, the determined window segment has length at least L, so a lower triangular Toeplitz matrix satisfying Ls1 + s2 = 0 exists.Source: §X · p. 11
- When M ≥ 4⌈L/2⌉, the constraint matrix is square or wide and almost always (pseudo)invertible, so the vector l almost always exists.The proof supports this by showing its determinant is a polynomial in x0 that is nonzero for a particular substitution.Source: §X · p. 11
- For r > 1, the proof applies its incremental argument when M ≥ 4L.Source: §X · p. 12