Phaseless sampling on square-root lattices

Philipp Grohs, Lukas Liehr

TL;DR

This paper overcomes a fundamental "discretization barrier" in signal processing by proving that square-root lattices—sampling sets where points cluster more densely as they move away from the origin—guarantee the unique recovery of signals from phaseless Short-Time Fourier Transform (STFT) measurements. This provides a theoretical foundation for robust phase retrieval using discrete samples, a feat previously thought impossible using standard regular lattices.

What Problem Does This Paper Address?

In many fields like audio processing and coherent diffraction imaging, we can measure the magnitude (intensity) of a signal's STFT but lose the phase information. The goal of STFT phase retrieval is to recover the original signal $f$ from these phaseless samples $|V_gf(\Lambda)|$.

While we have a well-established theory for recovering signals from full STFT samples on a regular lattice (like a grid), a troubling "discretization barrier" was recently discovered: if you only have magnitudes, a standard lattice $\Lambda = A\mathbb{Z}^{2d}$ can never guarantee a unique solution for all square-integrable functions. There will always be distinct functions that produce the exact same phaseless samples on a grid. The authors aim to find a discrete sampling set that breaks this barrier.

Methods

The authors introduce and analyze square-root lattices, defined by the set $\sqrt{\mathbb{Z}} = \{\pm\sqrt{n} : n \in \mathbb{N}_0\}$. Unlike standard lattices where points are equally spaced, square-root lattices become increasingly dense as you move further from the origin.

To prove uniqueness, the authors:

  1. Define a specific function space $\mathcal{O}_a^b(\mathbb{C}^d)$ of entire functions with Gaussian-type decay on the real line and specific growth rates in the complex plane.
  2. Leverage Complex Analysis: They show that the squared magnitude of the STFT, $|V_\phi f|^2$, can be extended to an entire function of several complex variables.
  3. Apply Jensen’s Formula: They use this classical result from complex analysis to relate the distribution of zeros of these analytic functions to their growth, proving that if a function vanishes on a sufficiently dense square-root lattice, it must be zero everywhere.
  4. Metaplectic Operators: To move beyond simple rectangular grids, they use the theory of symplectic matrices and metaplectic operators (related to the Fractional Fourier Transform) to extend their results to rotated and sheared square-root lattices.

Datasets

As a theoretical mathematics paper, no empirical datasets were used. The "evaluation" consists of rigorous mathematical proofs.

Key Insights and Ideas

  • The Density Shift: The "aha moment" is that the failure of standard lattices isn't just about the number of points, but their distribution. By using a square-root lattice, the sampling points cluster more tightly at higher frequencies/times. This added "irregularity" provides the extra information needed to resolve phase ambiguities.
  • Analyticity is Key: The STFT with a Gaussian window is essentially an analytic function. By viewing the phase retrieval problem through the lens of the zeros of entire functions, the authors transform a signal processing problem into a problem of complex geometry.
  • Universality: While Gaussians are the most common windows, the results hold for a much broader class of window functions (the $\mathcal{O}_a^b$ space), which is actually dense in $L^2(\mathbb{R}^d)$.

Key Results

  • Theorem 1.1 (Main Result): For a window function in the $\mathcal{O}_a^b$ space, a rectangular square-root lattice guarantees uniqueness (up to a global phase factor) if the generating matrix satisfies specific density conditions: $$\tau_j < \sqrt{\frac{1}{2b_je}}, \quad \nu_j < \sqrt{\frac{a_j}{2\pi^2e}}$$
  • Gaussian and Hermite Corollaries: The paper provides explicit bounds for the most common window functions. For example, using a standard Gaussian window, uniqueness is guaranteed if the sampling density parameter $\alpha$ is less than $1/\sqrt{2\pi e} \approx 0.24$.
  • Geometric Flexibility: The authors prove that uniqueness is preserved even if the square-root lattice is rotated or sheared, provided the deformation isn't too extreme (Theorem 4.1).

Limitations and Future Work

  • Stability: The paper focuses on uniqueness (can we distinguish two functions?). It does not address stability (if the measurements have a tiny bit of noise, does the reconstruction fall apart?). Given that Gabor phase retrieval is often ill-posed, investigating the stability of square-root sampling is a vital next step.
  • Algorithm Design: The paper provides the "what" (square-root lattices) but not the "how" (an efficient numerical algorithm to perform the reconstruction).
  • Density Constraints: The current results require the lattice to be "sufficiently dense." Finding the absolute minimum density required for uniqueness 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