Abstract
In this paper, we focus on the approximation of smooth functions $f: [-\pi, \pi] \rightarrow \mathbb{C}$, up to an unresolvable global phase ambiguity, from a finite set of Short Time Fourier Transform (STFT) magnitude (i.e., spectrogram) measurements. Two algorithms are developed for approximately inverting such measurements, each with theoretical error guarantees establishing their correctness. A detailed numerical study also demonstrates that both algorithms work well in practice and have good numerical convergence behavior.
Introduction
Phase retrieval is a fundamental challenge in signal processing, occurring whenever a complex-valued signal must be reconstructed from measurements that capture only its intensity or magnitude. This problem is ubiquitous in fields such as ptychography, astronomy, and speech processing, where physical sensors often lose the phase information of the incoming wave or signal.
While engineers have traditionally relied on heuristic iterative methods—such as the Hybrid Input-Output (HIO) algorithm—these approaches frequently lack convergence guarantees and are prone to stagnation in local minima. Furthermore, most existing theoretical frameworks treat signals as finite-dimensional vectors. This paper addresses the "continuous-to-discrete" gap, providing a rigorous mathematical framework to provably recover a continuous, smooth function $f(x) \in L^2([-\pi, \pi])$ from a finite set of noisy, discrete spectrogram measurements.
Methodology
The authors propose a four-step reconstruction pipeline designed to handle two distinct types of measurement "masks" (windows): periodic trigonometric polynomials and compactly supported masks. This pipeline is implemented through two specific algorithms: Algorithm 1 (for periodic masks) and Algorithm 2 (for compactly supported masks).
- Discretization: The continuous STFT integral is approximated using discrete sums. The authors provide rigorous bounds on the error introduced during this step, ensuring the discrete model remains faithful to the continuous signal.
- Wigner Distribution Deconvolution: This represents the core innovation of the work. By exploiting the properties of the Wigner distribution, the non-linear phase retrieval problem is transformed into a linear deconvolution problem. This allows for the recovery of the autocorrelation of the signal's Fourier coefficients without the need for iterative projections.
- Greedy Angular Synchronization: Once the relationships between phases (autocorrelations) are established, a greedy algorithm "stitches" these phases together to recover the individual Fourier coefficients.
- Trigonometric Approximation: Finally, the recovered coefficients are used to construct a trigonometric polynomial that serves as a high-fidelity approximation of the original continuous function.
Theoretical Insights
A critical contribution of this work is the definition of the "Beta-Fourier Decay" class. Phase retrieval is inherently impossible if a signal contains too many consecutive zero Fourier coefficients, as the phase connection is "broken." By defining a regularity class of functions with $\beta$ Fourier decay, the authors ensure the signal is sufficiently "connected" in the frequency domain to allow for stable recovery.
By linearizing the quadratic measurement process through Wigner deconvolution, the search for a signal vector is replaced by a structured matrix inversion. The paper introduces explicit "Stability Constants" ($\mu_1, \mu_2$). If these constants are non-zero for a chosen mask, the algorithm is guaranteed to converge. The authors further prove that such robust masks are readily constructible.
Experimental Results
The algorithms were evaluated using synthetic datasets consisting of $C^\infty$-smooth "bump" functions (weighted sums of shifted Gaussian-like peaks) and various mask configurations.
- Theoretical Guarantees: Theorems 1 and 2 establish explicit error bounds, showing that as the number of measurements ($d$) increases, the reconstruction error vanishes at a rate determined by the smoothness ($k$) of the function.
- Computational Efficiency: Both algorithms demonstrate high efficiency with a complexity of approximately $O(dL)$, where $d$ is the number of frequencies and $L$ is the number of shifts. In practice, these methods run significantly faster than standard iterative methods like HIO combined with Error Reduction (ER).
- Noise Robustness: Numerical experiments under varying Signal-to-Noise Ratios (SNRs) show that the algorithms are stable under Gaussian noise. Notably, a refined version of the proposed method outperformed the industry-standard HIO+ER algorithm in terms of robustness across a wide range of noise levels.
Conclusion and Future Work
This research provides a provably accurate path for continuous-to-discrete phase retrieval. However, several avenues for future work remain. The current theoretical error bounds are somewhat pessimistic compared to the actual numerical performance observed. Additionally, while the greedy angular synchronization is effective, more sophisticated synchronization techniques could further enhance accuracy. Finally, extending these 1D guarantees to 2D signals is essential for broader applications in ptychographic imaging.
Summary updated