Reconstructing real-valued functions from unsigned coefficients with\n respect to wavelet and other frames

Rima Alaifari, Ingrid Daubechies, Philipp Grohs, Gaurav ThakurarXiv 2016 · DOI · arXiv

Abstract

In this paper we consider the following problem of phase retrieval: Given a collection of real-valued band-limited functions $\{\psi_{\lambda}\}_{\lambda\in \Lambda}\subset L^2(\mathbb{R}^d)$ that constitutes a semi-discrete frame, we ask whether any real-valued function $f \in L^2(\mathbb{R}^d)$ can be uniquely recovered from its unsigned convolutions ${\{|f \ast \psi_\lambda|\}_{\lambda \in \Lambda}}$. We find that under some mild assumptions on the semi-discrete frame and if $f$ has exponential decay at $\infty$, it suffices to know $|f \ast \psi_\lambda|$ on suitably fine lattices to uniquely determine $f$ (up to a global sign factor). We further establish a local stability property of our reconstruction problem. Finally, for two concrete examples of a (discrete) frame of $L^2(\mathbb{R}^d)$, $d=1,2$, we show that through sufficient oversampling one obtains a frame such that any real-valued function with exponential decay can be uniquely recovered from its unsigned frame coefficients.

Introduction

The core challenge addressed in this research is phase retrieval: the reconstruction of a signal from the absolute values of its measurements. While classic Fourier phase retrieval (recovering a function from its Fourier modulus $|\hat{f}|$) is generally non-unique, this paper explores whether a function $f$ can be uniquely recovered from the magnitudes of its convolutions with a set of filters, such as wavelets, denoted as $\{|f * \psi_\lambda|\}$. This shifts the problem into the domain of frame theory, seeking a generalized framework for multivariate functions ($d > 1$) and semi-discrete frames.

Methods

The reconstruction approach combines harmonic analysis with complex analysis, relying on several key technical components:

  • Semi-discrete Frames: The system uses filters where the "scale" or "type" ($\lambda$) is discrete, but translation ($u$) is continuous, mirroring practical signal processing tools like the Continuous Wavelet Transform.
  • Sign-blind Sampling: The authors define sampling lattices dense enough to recover the sign of a band-limited function. For a function with bandwidth $B$, sampling at twice the Nyquist rate is shown to be necessary and sufficient for recovery up to a global sign.
Illustration of a sampling lattice $\Lambda$ used for sign-blind reconstruction.
  • Analytic Continuation: By assuming exponential decay for $f$, its Fourier transform $\hat{f}$ becomes real-analytic. This property allows a local sign choice to be propagated across the entire frequency domain.
  • Good F-support Overlap: Global recovery requires that the supports of the filters' Fourier transforms $\{\text{supp } \hat{\psi}_\lambda\}$ overlap significantly and cover the entire frequency space.
The frequency support $F$ of a filter $\psi_\lambda$ within a semi-discrete frame.

Key Insights

  • The "Stitching" Argument: The unknown signs $\sigma_\lambda \in \{-1, 1\}$ for each filter are resolved by ensuring frequency supports overlap. Consistent matches in these regions allow for global sign alignment.
  • Exponential Decay as a Regularizer: This assumption ensures the Fourier transform is analytic, preventing "zeros" from obstructing the reconstruction process.
  • Mandatory Oversampling: Standard Nyquist-rate sampling is insufficient for phase retrieval. Redundancy is required; for Meyer wavelets, a specific oversampling bound ($\alpha \le 3/16$) is derived to guarantee uniqueness.

Results

The paper establishes a Uniqueness Theorem stating that real-valued functions with exponential decay are uniquely determined (up to a global sign) by unsigned convolutions with a semi-discrete frame, provided the frame has "good F-support overlap" and is sampled on a sign-blind lattice.

Furthermore, the authors prove Local Stability, showing the reconstruction operator is injective with a continuous inverse, ensuring robustness against small measurement errors. Concrete redundancy bounds are provided for two benchmark examples:

  1. 1D Meyer Wavelets: Sign retrieval is guaranteed if the oversampling factor $\alpha$ is $\le 3/16$.
  2. 2D Curvelets: Sign retrieval is guaranteed if the oversampling in the two dimensions satisfies $\alpha_1 \le 3 \cdot 2^{-5}$ and $\alpha_2 \le 9/20\pi$, resulting in a total redundancy factor of approximately 4.58.

Discussion

The current framework is restricted to real-valued functions; complex-valued phase retrieval remains a significant open challenge. Additionally, while local stability is proven, global stability in infinite-dimensional spaces is inherently difficult. Future research may explore relaxing the exponential decay condition to broader "quasi-analytic" classes.

Summary updated

Abstract

In this paper we consider the following problem of phase retrieval: Given a\ncollection of real-valued band-limited functions\n$\\{\\psi_{\\lambda}\\}_{\\lambda\\in \\Lambda}\\subset L^2(\\mathbb{R}^d)$ that\nconstitutes a semi-discrete frame, we ask whether any real-valued function $f\n\\in L^2(\\mathbb{R}^d)$ can be uniquely recovered from its unsigned convolutions\n${\\{|f \\ast \\psi_\\lambda|\\}_{\\lambda \\in \\Lambda}}$.\n We find that under some mild assumptions on the semi-discrete frame and if\n$f$ has exponential decay at $\\infty$, it suffices to know $|f \\ast\n\\psi_\\lambda|$ on suitably fine lattices to uniquely determine $f$ (up to a\nglobal sign factor).\n We further establish a local stability property of our reconstruction\nproblem. Finally, for two concrete examples of a (discrete) frame of\n$L^2(\\mathbb{R}^d)$, $d=1,2$, we show that through sufficient oversampling one\nobtains a frame such that any real-valued function with exponential decay can\nbe uniquely recovered from its unsigned frame coefficients.\n
BibTeX
@misc{alaifari2016reconstructing,
  author = {Rima Alaifari and Ingrid Daubechies and Philipp Grohs and Gaurav Thakur},
  title = {{Reconstructing real-valued functions from unsigned coefficients with\textbackslash\{\}n respect to wavelet and other frames}},
  year = {2016},
  eprint = {1601.07579},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.07579},
}
Figure