Phaseless Sampling on Square-Root Lattices

Philipp Grohs, Lukas Liehr

TL;DR

This paper overcomes a major theoretical hurdle in signal processing: the "discretization barrier" of the short-time Fourier transform (STFT) phase retrieval problem. By replacing standard regular lattices with "square-root lattices" (where points are spaced according to $\pm\sqrt{n}$), the authors prove that any square-integrable function can be uniquely recovered from its phaseless samples, even when using common window functions like Gaussians.

What Problem Does This Paper Address?

In many fields—from audio processing to coherent diffraction imaging—we often only have access to the magnitude of a signal's transform, losing the phase information. This is the "phase retrieval" problem. Specifically, this paper looks at the Short-Time Fourier Transform (STFT), which provides a time-frequency representation of a signal.

For years, researchers have tried to determine which discrete sets of sampling points allow us to uniquely reconstruct a signal (up to a global phase factor) from these magnitude-only measurements. A natural choice is a lattice—a regular, grid-like arrangement of points. However, recent "discretization barriers" proved that if you sample on a standard lattice, uniqueness is impossible for general signals. No matter how dense your grid is, there will always be different signals that produce the exact same phaseless samples. This paper seeks a structured sampling scheme that breaks this barrier.

Methods

The authors introduce a novel sampling geometry called square-root lattices. Instead of the linear spacing of a standard lattice ($n, 2n, 3n...$), these sets are defined by the square roots of integers ($\pm\sqrt{1}, \pm\sqrt{2}, \pm\sqrt{3}...$).

To prove that these sets work, the authors:

  1. Define a specific function space ($\mathcal{O}_a^b$): They identify a class of analytic window functions (including Gaussians and Hermite functions) that have specific growth and decay properties.
  2. Leverage Complex Analysis: They show that the squared magnitude of the STFT (the spectrogram) can be extended into an entire function of several complex variables.
  3. Apply Jensen’s Formula: By using classical results from complex analysis regarding the distribution of zeros of analytic functions, they prove that square-root lattices are "uniqueness sets." If an analytic function is zero on these points, it must be zero everywhere.
  4. Metaplectic Operators: In the final section, they use the machinery of symplectic geometry and metaplectic operators (like the Fractional Fourier Transform) to extend their results from simple rectangular grids to rotated and sheared square-root lattices.

Datasets

Not discussed in the paper. This is a theoretical mathematical study providing rigorous proofs and does not utilize empirical datasets or benchmarks.

Key Insights and Ideas

  • The Geometry of Uniqueness: The "aha moment" is that the failure of standard lattices isn't due to a lack of points, but rather their specific algebraic structure. By slightly warping the grid into a square-root distribution, you "hit" enough points to uniquely lock down the underlying analytic function.
  • Clustering Matters: Square-root lattices have a unique property: the points become more "clustered" (denser) the further you move from the origin in the time-frequency plane. This density at infinity is key to satisfying the uniqueness conditions for the associated complex functions.
  • Gaussian Compatibility: The results are particularly powerful because they apply to Gaussian windows. In time-frequency analysis, Gaussians are the "gold standard" due to their optimal concentration in both time and frequency, yet they were previously thought to be problematic for discrete phaseless sampling.
  • Beyond the Diagonal: The authors show that uniqueness isn't just a property of axis-aligned grids. Through rotation and shearing (Example 4.2 and 4.3), they demonstrate that the square-root principle is robust to linear transformations of the sampling space.

Key Results

  • Theorem 1.1: Provides the fundamental equivalence. For a wide class of window functions, two signals are identical (up to global phase) if and only if their phaseless STFT samples match on a sufficiently dense rectangular square-root lattice.
  • Corollary 1.2 & 1.3: Specifically confirm that this holds for Gaussian windows and Hermite functions, which are staples of signal processing.
  • Density Conditions: The paper provides explicit bounds on the "density" required for the square-root lattice (the $\alpha$ and $\beta$ parameters) to guarantee recovery. For example, for a standard Gaussian, the sampling parameter $\alpha$ must be less than $1/\sqrt{2\pi e}$.

Limitations and Future Work

  • Stability: While the paper proves uniqueness (the solution is theoretically one-of-a-kind), it does not address stability. In the real world, small amounts of noise in the measurements could potentially lead to large errors in reconstruction. The authors note that the "clustering" of points at infinity might present challenges for numerical stability.
  • Algorithm Design: This is a "uniqueness" paper, not an "algorithm" paper. While it proves recovery is possible, it doesn't provide a specific, computationally efficient algorithm to actually perform the reconstruction from these square-root samples.
  • Window Constraints: While the class of windows is broad, it still requires the window to be analytic with specific growth bounds. Extending this to non-analytic or compactly supported windows remains an open question.

Summary updated

Abstract

Due to its appearance in a remarkably wide field of applications, such as audio processing and coherent diffraction imaging, the short-time Fourier transform (STFT) phase retrieval problem has seen a great deal of attention in recent years. A central problem in STFT phase retrieval concerns the question for which window functions $g \in L^2(\mathbb{R}^d)$ and which sampling sets $Λ\subseteq \mathbb{R}^{2d}$ is every $f \in L^2(\mathbb{R}^d)$ uniquely determined (up to a global phase factor) by phaseless samples of the form $$ |V_gf(Λ)| = \left \{ |V_gf(λ)| : λ\in Λ\right \}, $$ where $V_gf$ denotes the short-time Fourier transform (STFT) of $f$ with respect to $g$. The investigation of this question constitutes a key step towards making the problem computationally tractable. However, it deviates from ordinary sampling tasks in a fundamental and subtle manner: recent results demonstrate that uniqueness is unachievable if $Λ$ is a lattice, i.e $Λ= A\mathbb{Z}^{2d}, A \in \mathrm{GL}(2d,\mathbb{R})$. Driven by this discretization barrier, the present article centers around the initiation of a novel sampling scheme which allows for unique recovery of any square-integrable function via phaseless STFT-sampling. Specifically, we show that square-root lattices, i.e., sets of the form $$ Λ= A \left ( \sqrt{\mathbb{Z}} \right )^{2d}, \ \sqrt{\mathbb{Z}} = \{ \pm \sqrt{n} : n \in \mathbb{N}_0 \}, $$ guarantee uniqueness of the STFT phase retrieval problem. The result holds for a large class of window functions, including Gaussians.
BibTeX
@article{grohs2025phaseless,
  author = {Philipp Grohs and Lukas Liehr},
  title = {{Phaseless Sampling on Square-Root Lattices}},
  journal = {Found. Comput. Math.},
  year = {2025},
  doi = {10.1007/s10208-024-09640-3},
}
Figure