PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Convex Phase Retrieval from STFT Measurements

Tamir Bendory, Yonina C. Eldar, Nicolas Boumal

arXiv:1607.08218v3cs.ITmath.IT

TL;DR

Recovering a one-dimensional signal from Fourier magnitudes is generally ill-posed, while phaseless STFT measurements arise in applications such as laser pulse characterization and ptychography. The paper uses a least-squares-derived spectral initialization for closed-form recovery or to start two non-convex algorithms, which perform well with small measurement redundancy and noise.

  • Problem

    One-dimensional Fourier phase retrieval is ill-posed except for minimum-phase signals, and phaseless STFT recovery is relevant to applications including laser pulse characterization and ptychography.

    Source: §I · p. 1

  • Method

    The paper constructs a least-squares approximation matrix and uses its principal eigenvector for closed-form recovery under conditions or to initialize ER minimization and NCPC phase-manifold optimization.

    Source: §I · p. 2, 1) The Algorithm · p. 6

  • Results

    The algorithms perform well with small measurement redundancy and noise; experiments report NCPC’s highest success rate as window length varies, ER’s advantage at low SNR, and NCPC’s advantage for short-window Poisson noise.

    Source: §I · p. 2, §V · p. 9

  • Takeaways & Limitations

    The proposed STFT approach combines conditional closed-form recovery with local optimization methods that perform well in the reported small-redundancy and noisy settings.

    Source: §I · p. 2

    The theoretical basin result is useful only for long windows, and the gap between its bound and the larger basin observed numerically limits theoretical understanding.

    Source: §VI · p. 11, §VIII · p. 14

Abstract

from arXiv · show

The problem of recovering a one-dimensional signal from its Fourier transform magnitude, called Fourier phase retrieval, is ill-posed in most cases. We consider the closely-related problem of recovering a signal from its phaseless short-time Fourier transform (STFT) measurements. This problem arises naturally in several applications, such as ultra-short laser pulse characterization and ptychography. The redundancy offered by the STFT enables unique recovery under mild conditions. We show that in some cases the unique solution can be obtained by the principal eigenvector of a matrix, constructed as the solution of a simple least-squares problem. When these conditions are not met, we suggest using the principal eigenvector of this matrix to initialize non-convex local optimization algorithms and propose two such methods. The first is based on minimizing the empirical risk loss function, while the second maximizes a quadratic function on the manifold of phases. We prove that under appropriate conditions, the proposed initialization is close to the underlying signal. We then analyze the geometry of the empirical risk loss function and show numerically that both gradient algorithms converge to the underlying signal even with small redundancy in the measurements. In addition, the algorithms are robust to noise.

I. INTRODUCTION

The introduction motivates signal recovery from phaseless STFT measurements and presents a least-squares-based spectral initialization followed, when needed, by non-convex optimization. The problem formulation expresses transformed measurements through the signal’s correlation matrix and casts recovery as constrained least squares.

I. INTRODUCTION

  • STFT magnitude recovery is motivated by applications including ultra-short laser pulse characterization and ptychography.The paper notes that, at equal measurement counts, STFT magnitude performs better than an oversampled DFT.Source: §I · p. 1
  • Earlier approaches include Griffin–Lim, SDP recovery, and phase-synchronization methods, with cited drawbacks including computational cost, long random windows, or reliance on reliable temporal-magnitude estimates.The cited SDP approach requires high computational resources, while some phase-synchronization methods depend on temporal-magnitude estimates that may not exist.Source: §I · pp. 1–2
  • For L = 1 and sufficiently long windows, under mild conditions, the signal can be recovered from the principal eigenvector of a matrix obtained by solving a linear least-squares problem.The matrix approximates the signal correlation matrix.Source: §I · p. 2
  • When closed-form conditions fail, the approximation matrix’s principal eigenvector initializes ER loss minimization or NCPC optimization over phases.ER is more stable at low SNR, while NCPC is superior at high SNR and for short windows.Source: §I · p. 2
  • For L = 1, the initialization approaches the target as window length increases; for unit-modulus signals, a modification recovers exactly when W ≥ 2.Under the stated unit-modulus conditions, the ER loss has a basin of attraction with geometric convergence; experiments show good performance with small redundancy and noise.Source: §I · p. 2

II. PROBLEM FORMULATION

  • Measurements cannot distinguish x from x multiplied by any global phase, so recovery is defined up to that ambiguity.The paper introduces a distance that minimizes over global phase.Source: §II · pp. 2–3
  • Taking a 1D DFT of the measurements along frequency yields transformed data that, for each fixed window position, represent the autocorrelation of a windowed signal.The transformed data are bandlimited in the lag variable, and the correlation matrix maps linearly to them.Source: §II · p. 3
  • Recovery is posed as constrained least squares over Hermitian matrices; dropping the rank constraint gives an SDP with N^2 variables, motivating the proposed lower-load route.The authors describe a unique solution under moderate conditions and a closed-form least-squares solution for sufficiently long windows.Source: §II · p. 3

III. UNIQUENESS AND BASIC ALGORITHMS

This section establishes conditions for unique STFT-magnitude recovery and presents a least-squares matrix whose principal eigenvector can recover the signal. When a closed-form solution is unavailable, it motivates eigenvector initialization for non-convex recovery algorithms.

Window conditions

  • Rectangular windows are admissible for 2 ≤ W ≤ N/2 when every α from 2 through W is coprime with N; this holds automatically when N is prime.Admissibility is equivalent to the relevant shifted-window DFTs being non-vanishing.Source: §III · pp. 3–4

Uniqueness

  • For L = 1, a non-vanishing signal is uniquely determined up to global phase when the DFTs of g⊙(P−ℓg) are non-vanishing for ℓ = 0, 1.This result provides an explicit recovery scheme under the stated conditions.Source: §III · p. 4

Basic algorithms

  • For a unit-modulus signal and an admissible window with W ≥ 2, the constructed matrix X0 has x as a principal eigenvector, up to global phase.A slight modification of the initialization recovers the signal exactly in this case.Source: §III · p. 4
  • Algorithm 1 builds X0 by solving least-squares problems for its diagonals; when every Gℓ is invertible, X0 equals xx∗.It estimates x from X0's principal eigenvector; FFTs can efficiently perform the matrix inversions because Gℓ is circulant.Source: §III · p. 4
  • For L = 1, Algorithm 1 uniquely recovers any complex signal up to global phase under sufficiently long-window and additional technical conditions.The passage identifies the result as constructive but does not provide the full window-length bound here.Source: §III · p. 4

Non-convex recovery

  • When windows are too short for a closed-form least-squares solution, ER minimization suits low-SNR regimes, while phase-manifold quadratic maximization performs better for short windows and high SNR.The principal eigenvector of the approximation matrix, with appropriate normalization, initializes both algorithms.Source: §III · pp. 4–5

IV. LOCAL NON-CONVEX ALGORITHMS

The section proposes a data-driven initialization followed by non-convex gradient refinement for STFT phase retrieval. It details empirical-risk minimization and illustrates the loss landscape for one signal and measurement setting.

IV. LOCAL NON-CONVEX ALGORITHMS

  • The proposed approach initializes from a data-driven estimate, then refines it with a gradient algorithm minimizing empirical risk or with Non-Convex PhaseCut.The refinement begins from Algorithm 1 for L = 1 or Algorithm 5 for L > 1.Source: §IV · p. 5, A. Empirical Risk Minimization · p. 6

A. Empirical Risk Minimization

  • The empirical-risk loss is based on the STFT measurements or their 1D DFT across frequency, and can be minimized with gradient descent.For complex signals, the paper points to Wirtinger derivatives for gradient computation.Source: A. Empirical Risk Minimization · p. 5
  • In the illustrated two-coordinate slice, the loss has two saddle points and two global minima, attributed to global phase ambiguity.The example uses N = 5, L = 1, and a rectangular window of length W = 2; the view covers only two of five dimensions.Source: Figure IV · p. 5

B. Non-Convex PhaseCut (NCPC)

Non-Convex PhaseCut (NCPC) recasts recovery as optimization over STFT phases, then applies local optimization on the phase manifold. Its objective favors phases whose magnitude-weighted STFT is close to a valid STFT, and it is initialized from the proposed signal estimate.

1) The Algorithm:

  • The phase-only objective follows by eliminating the signal from a joint least-squares fit of the signal and unknown STFT phases.For fixed phases, the least-squares signal estimate is obtained using the STFT adjoint.Source: 1) The Algorithm · p. 6
  • NCPC maximizes a quadratic function over complex phases, favoring phase choices whose magnitude-weighted matrix is closest to an STFT of a signal.The STFT followed by its adjoint projects onto the subspace of valid STFT matrices.Source: 1) The Algorithm · p. 6
  • NCPC initializes phase optimization with the phases of the STFT of the signal estimate produced by the initialization algorithm.The paper uses local optimization over the phase manifold, including Riemannian gradient ascent and, in practice, a Riemannian trust-region method.Source: 1) The Algorithm · pp. 6–7
  • With an appropriate line search, Riemannian gradient ascent and trust-region methods converge to first-order critical points regardless of initialization, not necessarily global minima.At such a point, the Riemannian gradient is zero.Source: 1) The Algorithm · p. 7
  • Riemannian gradient steps use the gradient component tangent to the phase manifold, then retract the iterate back onto that manifold.This differs from projected gradient, which follows the unconstrained gradient before projection.Source: 1) The Algorithm · pp. 6–7

2) Relation to Fienup’s Algorithm:

The paper relates Fienup’s algorithm to an iterative phase-optimization method and uses that connection to discuss suboptimal fixed points. For initialization with L > 1, it proposes upsampling measurements before extracting a principal eigenvector.

2) Relation to Fienup’s Algorithm:

  • Some stable Fienup fixed points map to suboptimal critical points, whereas such points are unstable for reasonable Riemannian optimization algorithms, partly explaining NCPC’s stronger empirical performance.Fienup’s iterations are equivalent to the projected power method under the mapping from signal iterates to STFT phases.Source: 2) Relation to Fienup’s Algorithm · p. 7

C. Initialization

  • The initialization is data-driven, unlike signal-structure or random starts; a Gaussian-pulse model start may bias estimates toward model characteristics.The paper notes that the specific initialization used in practice can depend on the application.Source: 1) Initialization for L = 1 · p. 8
  • For L > 1, the downsampled measurement system is underdetermined and its minimum-norm least-squares solution is generally a poor approximation.The proposed initialization upsamples the measurements to approximate the maximal-overlap case before extracting a principal eigenvector.Source: 2) Initialization for L > 1 · p. 8
  • With an ideal low-pass window of integer bandwidth N/L, upsampling by expansion and low-pass interpolation loses no information relative to maximal overlap.In practice, smooth interpolation approximates this construction and reduces computational complexity; simulations use linear and cubic interpolation.Source: 2) Initialization for L > 1 · p. 8

V. NUMERICAL RESULTS

Across the reported experiments, NCPC achieves the highest noise-free success rate and performs well with short windows, while ER can perform better in low-SNR Gaussian noise. The results also examine interpolation choices and the empirical basin of attraction.

V. NUMERICAL RESULTS

  • Experiments use Gaussian signals and compare ER and NCPC objectives optimized with a trust-region algorithm under Gaussian or Poisson measurement noise.Recovery error is normalized by the signal norm.Source: §V · pp. 8–9
  • For larger L, when there are fewer measurements, cubic interpolation outperforms linear interpolation; at low L, their performance is similar.The authors use cubic interpolation in subsequent experiments.Source: §V · p. 9
  • The ER optimizer converges to the global minimum for perturbations up to σ = 0.3 at L = 1, 2 and σ = 0.25 at L = 4.These experimental basin estimates exceed the paper’s theoretical estimate.Source: §V · p. 9
  • NCPC achieves the highest noise-free success rate, indicating less redundancy is needed; for low-SNR Gaussian noise, ER performs better, while NCPC leads for short-window Poisson noise.With low-pass data, NCPC performs significantly better than ER when SNR is not too bad, but ER is better in the low-SNR Gaussian-noise regime.Source: §V · p. 9

VI. THEORY

The theory bounds the proposed initialization error and establishes geometric convergence near the global minimum for a gradient method under stated conditions. The basin guarantee is narrow theoretically, while experiments indicate broader performance, including with greater window spacing and suppressed high frequencies.

Scope and limitations

  • The theoretical analysis focuses on maximum overlap, L = 1, while experiments indicate the non-convex methods also work well for L > 1 and with suppressed high frequencies.The authors identify bridging the theory–practice gap for short windows as future work because the stated corollary is good merely for long windows.Source: §VI · pp. 9, 11

Basin of attraction

  • For unit-modulus signals, a gradient method with thresholding converges geometrically to a global minimum from within the established basin of attraction.The basin is estimated to be small, placing the theoretical guarantee in the same region where a closed linear LS solution exists.Source: §VI · p. 9

Initialization error

  • For bounded signals with L = 1, the proposed initialization error tends to zero as W approaches (N+1)/2.The result is stated for a normalized signal; its norm can be estimated from the main diagonal of xx∗.Source: §VI · p. 10

Basin of attraction

  • In practice, the basin of attraction is described as quite large for a broad family of signals.The section points to Figure V.2 for numerical evidence on minimizing the ER loss from perturbed initializations.Source: §VI · p. 10, Figure V.2 · p. 10

VII. PROOFS

The proofs relate the approximation matrix to the target signal through its sparse error structure and eigenvector perturbation. They establish gradient convergence by verifying a regularity condition for the ER loss near its global minimum.

A. Proof of Theorem VI.1

  • The initialization proof bounds the matrix error using its limited nonzero diagonals, then relates a small matrix error to a small distance between the principal eigenvector and the target.The proof identifies the principal eigenvector of X0 as the initialization vector.Source: A. Proof of Theorem VI.1 · pp. 12–13

B. Proof of Theorem VI.2

  • When the regularity condition holds, a gradient update with step size 0 < µ ≤ 2/β converges to a global minimum at a geometric rate.The thresholding stage cannot increase the error when the signal is bounded; the stated constants include α ≥ 4N/W and β ≥ 256N^2W^3.Source: B. Proof of Theorem VI.2 · p. 13
  • For rectangular windows, the gradient points approximately toward the signal within the specified neighborhood; the analysis also extends to non-vanishing windows with bounds depending on their dynamic range.The proof uses the gradient behavior to establish the regularity condition for the ER loss.Source: B. Proof of Theorem VI.2 · p. 13

C. Proof of Corollary VI.3

The corollary proof checks that the proposed initialization lies within the basin of attraction under its stated conditions. The discussion presents two local optimization methods, describes the initialization strategy, and identifies limits to the current analysis.

C. Proof of Corollary VI.3

  • The proof concludes that Algorithm 1's initialization lies within the basin of attraction under the corollary's stated conditions.The derivation uses the initialization bound and standard algebraic calculations; the supplied passages do not preserve the full condition.Source: C. Proof of Corollary VI.3 · p. 13

VIII. DISCUSSION

  • The paper proposes local optimization by minimizing the empirical risk loss or optimizing a quadratic function on the manifold of phases.The manifold-based method accounts for the special geometry of phase retrieval.Source: §VIII · p. 14
  • For L > 1, the authors heuristically interpolate missing entries, but analyzing this setting remains a future research challenge.The interpolation works quite well because the window acts as an averaging operator, and its form depends on the window shape.Source: §VIII · p. 14
  • For unit-modulus signals, the ER loss has a basin of attraction, but the gap between its observed and theoretical size limits fuller theoretical understanding.The authors say improving Lemma VII.4 would tighten the estimate of the basin's size.Source: §VIII · p. 14

APPENDIX

The appendix establishes recovery and eigenvector properties under stated non-vanishing and invertibility assumptions. Its propositions connect STFT-derived diagonal data to recursive recovery or principal-eigenvector initialization.

A. Proof of Proposition III.4

  • With the stated non-vanishing assumptions, the proof sets the first entry to its magnitude and determines the remaining entries recursively.The first entry is chosen using the phase-retrieval ambiguity; the signal is assumed non-vanishing.Source: A. Proof of Proposition III.4 · p. 15

B. Proof of Proposition III.5

  • When the stated Gℓ matrices are invertible, the constructed matrix from two diagonals has the signal as a principal eigenvector, up to global phase.The proof uses the diagonals for ℓ = 0 and ℓ = M.Source: B. Proof of Proposition III.5 · p. 15

C. Proof of Proposition III.6

  • Under the stated invertibility assumptions, recovering all specified diagonals yields X0 = X, whose normalized principal eigenvector supplies the normalized signal.The proof then applies Algorithm 1's normalization stage.Source: C. Proof of Proposition III.6 · p. 16

D. Proof of the equality between the loss functions (IV.2) and (IV.1)

These proofs relate two loss formulations through a unitary DFT transformation, analyze expansion and interpolation for downsampled data, and bound a gradient near the target signal.

D. Proof of the equality between the loss functions (IV.2) and (IV.1)

E. Proof of Lemma IV.1

  • For L > 1, the proof treats a downsampled system and shows that the specified expansion and interpolation operation recovers y.The expansion is represented by multiplying both sides by F*FL.Source: E. Proof of Lemma IV.1 · p. 16

F. Proof of Lemma VII.3

  • For a rectangular window, the gradient-bound proof considers points close to x and combines bounds across shifts; the remark extends the approach to non-vanishing windows.For the extension, the inequalities must account for the window's maximum magnitude.Source: F. Proof of Lemma VII.3 · p. 17

G. Proof of Lemma VII.4

The proof bounds terms in the empirical-risk expression to obtain a local lower bound, with an explicit neighborhood condition and a stated extension to non-vanishing windows.

G. Proof of Lemma VII.4

  • The proof combines an upper bound on the second term and a lower bound on the first to derive a local bound when d(x, z) satisfies the stated radius condition.For non-vanishing windows, the inequalities must account for both the maximum and minimum window values.Source: G. Proof of Lemma VII.4 · pp. 17–18

Related papers

Loading 1607.08218v3…