# Stable Gabor phase retrieval in Gaussian shift-invariant spaces via
biorthogonality

Philipp Grohs*,†,‡ *Faculty of Mathematics, University of Vienna, Oskar-
Morgenstern-Platz 1, 1090 Vienna, Austria  †Research Network
DataScience@UniVie, University of Vienna, Kolingasse 14-16, 1090 Vienna,
Austria  ‡Johann Radon Institute of Applied and Computational Mathematics,
Austrian Academy of Sciences, Altenbergstrasse 69, 4040 Linz, Austria
<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Lukas Liehr*
<EMAIL_ADDRESS>
###### Abstract.

We study the phase reconstruction of signals $f$ belonging to complex Gaussian
shift-invariant spaces $V^{\infty}(\varphi)$ from spectrogram measurements
$|\mathcal{G}f(X)|$ where $\mathcal{G}$ is the Gabor transform and
$X\subseteq{\mathbb{R}}^{2}$. An explicit reconstruction formula will
demonstrate that such signals can be recovered from measurements located on
parallel lines in the time-frequency plane by means of a Riesz basis
expansion. Moreover, connectedness assumptions on $|f|$ result in stability
estimates in the situation where one aims to reconstruct $f$ on compact
intervals. Driven by a recent observation that signals in Gaussian shift-
invariant spaces are determined by lattice measurements [Grohs, P., Liehr, L.,
_Injectivity of Gabor phase retrieval from lattice measurements_ ,
arXiv:2008.07238] we prove a sampling result on the stable approximation from
finitely many spectrogram samples. The resulting algorithm provides a non-
iterative, provably stable and convergent approximation technique. In
addition, it constitutes a method of approximating signals in function spaces
beyond $V^{\infty}(\varphi)$, such as Paley-Wiener spaces.

Keywords. phase retrieval, Gabor transform, shift-invariant spaces, dual
generator, Riesz bases, signal analysis

AMS subject classifications. 42C15, 46B15, 94A12, 94A20

##  1\. Introduction

Phaseless signal reconstruction deals with the problem of recovering a
function $f$ from intensity measurements of the form $\\{|Af(x)|:x\in X\\}$
where $A$ is a linear transformation and $X$ is a subset of the domain of
$Af$. This is known as the phase retrieval problem, a non-linear inverse
problem arising in numerous applications in science and engineering, such as
coherent diffraction imaging [13, 14, 31], speech recognition [5] and quantum
mechanics [12]. In the situation where $f$ belongs to an infinite-dimensional
Banach or Hilbert space, phase retrieval is known to be never uniformly stable
[2, 6], hence constituting a challenging problem for numerical reconstruction
approaches. See the surveys [15, 20] for a current overview on uniqueness,
stability and algorithms for phase retrieval. Recent attention was drawn to
signals having a shift-invariant structure, that is,

(1) $f\in
V_{\beta}^{p}(\phi)=\left\\{\sum_{n\in{\mathbb{Z}}}c_{n}\phi(\cdot-\beta
n):(c_{n})_{n}\in\ell^{p}({\mathbb{Z}})\right\\},$

where $\phi\in L^{p}({\mathbb{R}})$ is the so-called generator of
$V_{\beta}^{p}(\phi)$ and $p\in[1,\infty]$. The constant $\beta>0$ is a
regularity parameter, commonly referred to as the step-size. In a series of
papers, Chen et. al. studied the phase retrievability of a real-valued map $f$
from its modulus $|f|,A=\mathrm{Id}$, assuming that the generator has compact
support [7, 8, 9]. Shenoy et. el. investigated the situation where
$A={\mathcal{F}}$ is the Fourier transform and the defining sequence
$(c_{n})_{n}$ of $f$ obeys special properties [32]. In the situation where
$\phi=\mathrm{sinc}$ is the cardinal sine, i.e. the considered signals lie in
the classical Paley-Wiener space, Thakur demonstrated how to recover a real-
valued band-limited function from unsigned samples lying on a suitable dense
sampling set [33]. Similar results for real-valued maps were derived for
Gaussian generators as well as totally positive generators of Gaussian type
and are due to Gröchenig [19] and Romero [30]. Besides, it was shown that if
$\phi=\varphi^{\sigma}$ is the Gaussian

(2) $\varphi^{\sigma}(t)=e^{-\frac{t^{2}}{2\sigma^{2}}}$

with variance $\sigma^{2}$ then, in general, complex-valued maps are not
determined from samples of their absolute value. Hence, additional information
is needed to achieve injectivity for complex signals from measurements $|Af|$
with a suitably chosen signal-transformation $A$. The authors of the present
article proved in [21] that every complex-valued map in
$V_{\beta}^{1}(\varphi)$ is uniquely determined up to a global phase factor
from measurements of the form $|\mathcal{V}_{g}f(X)|$ where $\mathcal{V}_{g}$
is the short-time Fourier transform with Gaussian window $g=\varphi^{\sigma}$,

(3) $\mathcal{V}_{g}f(x,\omega)=\int_{\mathbb{R}}f(t)\overline{g(t-x)}e^{-2\pi
i\omega t}\,dt,$

and $X\subset{\mathbb{R}}^{2}$ is a separated set of sampling points in the
time-frequency plane. The resulting phase retrieval problem with
transformation $A=\mathcal{V}_{g}$ is known as the Gabor phase retrieval
problem which plays an important role in applications such as ptychography, a
popular and highly successful approach in coherent diffraction imaging. The
previous observations serve as the starting point for a more penetrating
investigation of the Gabor phase retrieval problem in a Gaussian shift-
invariant setting and motivate the work in hand. In particular, we derive an
explicit inversion formula and stability estimates as well as propose a new
reconstruction algorithm which approximates complex-valued signals in
$V_{\beta}^{\infty}(\varphi)$ from finitely many (deterministic) samples of
$|\mathcal{V}_{g}f|$ in a provable and stable manner.

Classical algorithmic approaches on solving the phase retrieval problem are
based on fixed point iterations, iterative projection methods and gradient
descent methods. Examples include the alternating projection method, the
Gerchberg–Saxton algorithm [18], error reduction [17], the Douglas-Rachford
algorithm [16], Hybrid Input-Output Algorithm [17] and the Averaged
Alternating Reflection Algorithm [29, 28]. The difficulty of analyzing
convergence and robustness of these methods lies in the non-convexity of the
phase retrieval problem. Heuristically, these methods perform well if one
chooses a right initialization which is close to a solution of the problem.
However, it is in general unclear how to perform the initialization step and
provide convergent results in a noise regime. Moreover, the discretization of
these methods in an infinite-dimensional setting constitutes a difficult task.
In contrast, the derived algorithm of the present paper overcomes these
difficulties by providing a non-iterative and provably convergent
approximation routine from noisy samples. Moreover, we quantify exactly how
many samples of $|\mathcal{V}_{g}f|$ need to be taken in order to guarantee a
given reconstruction error.

###  1.1. Notation

Throughout this article, the shift-invariant space $V_{\beta}^{p}(\phi)$, the
Gaussian $\varphi^{\sigma}$ and the short-time Fourier transform are defined
as in (1), (2) and (3), respectively. The cross-ambiguity function of $f$ and
$g$ is the map $A(f,g)(x,\omega)=e^{\pi ix\omega}\mathcal{V}_{g}f(x,\omega)$.
The spectrogram of $f$ w.r.t. to a window $g$ is given by the map
$(x,\omega)\mapsto|\mathcal{V}_{g}f(x,\omega)|^{2}$. If $g=\varphi^{\sigma}$
is a Gaussian then we set

$\mathcal{G}\coloneqq\mathcal{V}_{\varphi}\coloneqq\mathcal{V}_{\varphi^{\sigma}}$

and call $\mathcal{G}$ the Gabor transform of $f$. For clarity of the
exposition and simplicity of notation, we will drop the dependence on
$\sigma$. For a function $f:{\mathbb{R}}\to{\mathbb{C}}$ and an
$\omega\in{\mathbb{R}}$ we define its tensor product $f_{\omega}$ via

(4) $f_{\omega}\coloneqq(T_{\omega}f)\overline{f}$

where $T_{\omega}f=f(\cdot-\omega)$ is the shift-operator. Moreover, the
modulation operator $M_{\omega}$ is defined by $M_{\omega}f(t)=e^{2\pi i\omega
t}f(t)$. In Section 2 we will exhibit that under suitable assumptions on
$\phi$ the system of translates $(T_{\beta n}\phi)_{n\in{\mathbb{Z}}}$ forms a
Riesz basis for the space $V_{\beta}^{2}(\phi)$. Denoting by $S$ the frame
operator associated with $(T_{\beta n}\phi)_{n\in{\mathbb{Z}}}$ and making use
of the property that the operators $S$ and $T_{\beta n}$ commute for every
$n\in{\mathbb{Z}}$ implies that there exists a map $\tilde{\phi}$ such that
$(T_{\beta n}\tilde{\phi})_{n\in{\mathbb{Z}}}$ is the dual frame of $(T_{\beta
n}\phi)_{n\in{\mathbb{Z}}}$. The function $\tilde{\phi}$ given by

(5) $\tilde{\phi}\coloneqq S^{-1}\phi$

is called the dual generator of $\phi$. If $(T_{\beta
n}\phi)_{n\in{\mathbb{Z}}}$ forms a Riesz basis for $V_{\beta}^{2}(\phi)$ and
$f=\sum_{n}c_{n}T_{\beta n}\phi$ then we call
$c=(c_{n})_{n}\subset{\mathbb{C}}$ the defining sequence of $f$. In order to
study stability properties of the Gabor phase retrieval problem in a Gaussian
shift-invariant regime we define a mixed norm as follow. Let
$\alpha>0,p\in[1,\infty]$ and suppose that
$F:\alpha{\mathbb{Z}}\times{\mathbb{R}}\to{\mathbb{C}}$ is measurable. The
mixed norm $\|\cdot\|_{\alpha,p}$ is defined by

(6)
$\|F\|_{\alpha,p}\coloneqq\begin{cases}\left(\sum_{n\in{\mathbb{Z}}}\|F(\alpha
n,\cdot)\|_{L^{1}({\mathbb{R}})}^{p}\right)^{\tfrac{1}{p}},&p\in[1,\infty)\\\
\sup_{n\in{\mathbb{Z}}}\|F(\alpha
n,\cdot)\|_{L^{1}({\mathbb{R}})},&p=\infty\end{cases}.$

This is the $\ell^{p}$-norm of the sequence $(\|F(\alpha
n,\cdot)\|_{L^{1}({\mathbb{R}})})_{n\in{\mathbb{Z}}}$. If $F$ is defined on
${\mathbb{R}}^{2}$ we set
$\|F\|_{\alpha,p}\coloneqq\|F|_{\alpha{\mathbb{Z}}\times{\mathbb{R}}}\|_{\alpha,p}$
where $F|_{\alpha{\mathbb{Z}}\times{\mathbb{R}}}$ is the restriction of $F$ to
$\alpha{\mathbb{Z}}\times{\mathbb{R}}$. If not specified otherwise, all
indices will run over the integers ${\mathbb{Z}}$. Finally, we say that two
functions $f,h:{\mathbb{R}}\to{\mathbb{C}}$ equal up to a global phase (or: up
to a unimodular constant) if there exists a
$\tau\in{\mathbb{T}}\coloneqq\\{z\in{\mathbb{C}}:|z|=1\\}$ such that $f=\tau
h$.

###  1.2. Main results

The first main result, Theorem A, provides an explicit inversion formula of a
function $f\in V_{\beta}^{\infty}(\varphi)$ from its spectrogram
$|\mathcal{G}f(X)|$ where $X=\frac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}}$ is
a set of vertical lines in the time-frequency plane.

######  Theorem A.

Let $f\in V_{\beta}^{\infty}(\varphi)$ and let $p\in{\mathbb{R}}$ such that
$f(p)\neq 0$. Then there exists a unimodular constant $\tau\in{\mathbb{T}}$
such that

$f(p+\omega)=\tau
C^{-\frac{1}{2}}\sum_{n\in{\mathbb{Z}}}\left(\int_{\mathbb{R}}|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}e^{2\pi
i\omega
t}\,dt\right)T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)$

for every $\omega\in{\mathbb{R}}$ where
$C=\sum_{n\in{\mathbb{Z}}}\left(\int_{\mathbb{R}}|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}\,dt\right)T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(p)$
and $\widetilde{\varphi_{\omega}}$ is the dual generator of the Gaussian
tensor product $\varphi_{\omega}$.

In the previous theorem the maps
$\\{\widetilde{\varphi_{\omega}}:\omega\in{\mathbb{R}}\\}$ constitute a
parametrized system of dual generators. In particular, the statement shows
that two functions $f,h\in V_{\beta}^{\infty}(\varphi)$ agree up a global
phase provided that their spectrograms agree on
$X=\frac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}}$. Note, that this is a
uniqueness statement within the signal class $V_{\beta}^{\infty}(\varphi)$. A
similar statement does not hold if one replaces $V_{\beta}^{\infty}(\varphi)$
by ${L^{2}({\mathbb{R}})}$, as we have shown in [22].

Next, we study stability properties of the above inversion. Heuristically,
Theorem B assumes that the map $f$ has the property that $|f|$ is not too
small on large intervals. More precisely, it will be assumed that there exists
$J\in{\mathbb{N}},p_{1},\dots,p_{J}\in{\mathbb{R}}$ and $\gamma>0$ such that

$J\geq 2\ \ \land\ \ p_{1}<p_{2}<\cdots<p_{J}\ \ \land\ \
|f(p_{j})|\geq\gamma\ \forall j\in\\{1,\dots,J\\}.$

Condition (P) excludes examples of the form
$f^{+}_{s}=\varphi(\cdot-a)+\varphi(\cdot-b),f^{-}_{s}=\varphi(\cdot-a)-\varphi(\cdot-b),s=|a-b|$,
where it is known that exponential instabilities arise for growing $s$ [3].
These examples further show that an assumption on $|f|$ of the above form
cannot be dropped.

######  Theorem B.

Let $\gamma>0$, $f\in V_{\beta}^{\infty}(\varphi)$ and
$p_{1}<\cdots<p_{J}\in{\mathbb{R}}$ such that $|f(p_{j})|\geq\gamma$ for all
$j$. If $I=[p_{1}-r,p_{J}+r]$ and $r=\max_{1\leq j\leq J-1}(p_{j+1}-p_{j})$
then for every $g\in V_{\beta}^{\infty}(\varphi)$ we have

$\begin{split}&\min_{\tau\in{\mathbb{T}}}\|f-\tau g\|_{L^{\infty}(I)}\\\
&\lesssim_{\beta,\sigma}(J-1)e^{\frac{r^{2}}{4\sigma^{2}}}\frac{\max\\{\|f\|_{L^{\infty}(I)}^{2},\|f\|_{L^{\infty}(I)}+\|g\|_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{3}\\}}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}\end{split}$

and the implicit constant depends only on the step-size $\beta$ and the
standard-deviation $\sigma$ of the Gaussian $\varphi=\varphi^{\sigma}$.

Figure 1. Visualization of condition (P): the points $p_{1},\dots,p_{9}$
satisfy the properties $|f(p_{j})|\geq\gamma$ for all $j=1,\dots,9$ and
$p_{j+1}-p_{j}\leq r$ for all $j=1,\dots,8$.

We seek to discretize the previous regime in the sense that it yields an
algorithmic approximation of functions in $V_{\beta}^{\infty}(\varphi)$ from
finitely many measurements located on a grid of the form

(6) $X=\tfrac{\beta}{2}\\{-N,\dots,N\\}\times h\\{-H,\dots,H\\}$

where $N,H\in{\mathbb{N}},h,\beta>0$ rather than
$X=\frac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}}$. If
$\eta\in{\mathbb{R}}^{(2N+1)\times(2H+1)}$ denotes a noise matrix then the
given samples $\mathfrak{S}$ take the form

$\begin{split}&\mathfrak{S}=(|\mathcal{G}f(X)|^{2}+\eta_{n,k})_{n,k}\in{\mathbb{R}}^{(2N+1)\times(2H+1)},\\\
&\mathfrak{S}(n,k)=|\mathcal{G}f(\tfrac{\beta}{2}n,hk)|^{2}+\eta_{n,k}.\end{split}$

The contribution of the noise $\eta$ will be quantified in terms of the
$\ell^{\infty}$-operator norm of $\eta$, i.e. the maximum absolute row sum of
$\eta$. We denote this norm by $\|\eta\|_{\infty}$. The so-called numerical
approximation routine $\mathcal{R}$ depends only on $\mathfrak{S}$ and is
defined as follows: for $p_{1}<p_{2}<\cdots<p_{J}$ define constants $c_{j}$ by
$c_{j}=h\sum_{n}\sum_{k}\mathfrak{S}(n,k)T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(p_{j}),$
functions $L_{j}$ by

$L_{j}(\omega)=\frac{h}{\sqrt{c_{j}}}\sum_{n}\sum_{k}\mathfrak{S}(n,k)e^{2\pi
i\omega hk}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p_{j}+\omega)$

and phases $\nu_{0},\dots,\nu_{J-1}\in{\mathbb{T}}$ by

$\nu_{0}=1,\ \ \nu_{j}=\frac{L_{j}(p_{j+1}-p_{j})}{|L_{j}(p_{j+1}-p_{j})|}\
(j=1,\dots,J-1).$

Assuming that $L_{j}$ and $\nu_{j}$ are well-defined, i.e. $c_{j}>0$ and
$L_{j}(p_{j+1}-p_{j})\neq 0$ we define
$\mathcal{R}:[p_{1},p_{J}]\to{\mathbb{C}}$ by

(7) $\mathcal{R}(t)=\nu_{1}\cdots\nu_{j-1}L_{j}(\omega),$

if $t\in[p_{1},p_{J}]$ such that $t\in(p_{j},p_{j+1}]$ with $t=p_{j}+\omega$.
For $t=p_{1}$ we define $\mathcal{R}(t)=L_{1}(0)$. This function has the
property that it approximates $f$ from finitely many noisy samples. Figure 2
illustrates the reconstruction performance of the numerical reconstruction
routine $\mathcal{R}$ applied to finitely many noisy spectrogram samples of a
complex-valued signal. The following theorem proves stability and convergence
of this algorithm.

######  Theorem C.

Suppose that $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$ and that there exist

$-s\eqqcolon p_{1}<p_{2}<\cdots<p_{J}\coloneqq s$

with $|f(p_{j})|\geq\gamma$ and $\max_{1\leq j\leq J-1}(p_{j+1}-p_{j})\leq r$.
Let $I=[-s,s]$ and let
$0<\varepsilon\leq\min\left\\{\frac{\gamma^{2}}{2\sqrt{8}},\frac{\gamma^{3}}{4\|f\|_{L^{\infty}(I)}}\right\\}$
and assume that the parameters $h,H,N$ of the grid $X$ have the property that

$\frac{1}{h}\gtrsim_{\sigma,\beta,r}\log\left(\frac{J\|c\|_{\infty}^{2}}{\varepsilon}+1\right),\
N\gtrsim_{\sigma,\beta,r}s+\log\left(\frac{J\|c\|_{\infty}^{2}}{\varepsilon}\right),$
$\
H\gtrsim_{\sigma,\beta,r}\frac{1}{h}\left(\log\left(\frac{J\|c\|_{\infty}^{2}}{\varepsilon}\right)\right)^{1/2}.$

If the noise level satisfies
$\|\eta\|_{\infty}\lesssim_{\sigma,\beta,r}\frac{\varepsilon}{hJ}$ then

(8) $\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}(I)}\leq
32\frac{\max\\{1,\|f\|^{2}_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{5}\\}}(\varepsilon+\varepsilon^{2}).$

The numerical approximation routine $\mathcal{R}$ combined with Theorem C
results in a provably stable and convergent approximation algorithm as soon as
condition (P) is satisfied. Note that this is an assumption on $|f|$ which is
a-priori unknown if only samples of $|\mathcal{G}f|$ are available. However,
this information is encoded in the spectrogram of $f$: we will show that the
modulus $|f|$ of any $f\in V_{\beta}^{\infty}(\varphi)$ can be approximated in
a uniformly and _globally stable_ way without imposing any additional
assumption on $f$, see the discussion following Corollary 3.7, as well as
Lemma 3.8. Based on a reconstruction of $|f|$ the resulting algorithm
presented in Section 4 first detects points $p_{1},\dots,p_{J}$ such that
condition (P) is satisfied and finally uses the numerical approximation
routine $\mathcal{R}$ to provide a reconstruction of $f$. In this way, the
information on the location of points $p_{j}$ can be omitted.

Finally, we study the growth behavior of the number of spectrogram samples
needed to approximate a function on an interval $[-s,s]$. Assume that $f$ has
the property that there exists a partition $\cdots<p_{-1}<p_{0}<p_{1}<\cdots$
of the real line such that $|f(p_{j})|\geq\gamma$ for some $\gamma>0$ and all
$j\in{\mathbb{Z}}$. Suppose we aim to approximate $f$ on the interval $[-s,s]$
using the numerical approximation routine $\mathcal{R}=\mathcal{R}(s)$. How
does the minimal number of spectrogram samples $\mathcal{N}(s)$ grow so that
$\mathcal{R}(s)$ achieves the bound (8) for a fixed $\varepsilon>0$?

######  Theorem D.

Let $\cdots<p_{-1}<p_{0}<p_{1}<\cdots$ be a partition of the real line such
that $\sup_{j\in{\mathbb{Z}}}(p_{j+1}-p_{j})<\infty$. Let $\gamma>0$ and $f\in
V_{\beta}^{\infty}(\varphi)$ such that $|f(p_{j})|\geq\gamma$ for all
$j\in{\mathbb{Z}}$. Assume that the spectrogram samples $\mathfrak{S}$ are
noiseless, $\eta=0$, and $\varepsilon$ is given as in Theorem C. Then the
minimal number of spectrogram samples $\mathcal{N}(s)$ needed to achieve the
bound (8) on the interval $[-s,s]$ using the numerical approximation routine
$\mathcal{R}$ satisfies

$\mathcal{N}(s)\lesssim_{\sigma,\beta}\log\left(\frac{s\|c\|_{\infty}^{2}}{\varepsilon}\right)^{\frac{3}{2}}\left(s+\log\left(\frac{s\|c\|_{\infty}^{2}}{\varepsilon}\right)\right).$

Theorems A, B, C and D are a direct consequence of Theorems 3.6, 3.10, 4.6 and
Corollary 4.7 that will be proved in Sections 3.1, 3.2, 4.2 and 4.2,
respectively.

Figure 2. Reconstruction of a complex-valued function $f\in
V_{\beta}^{\infty}(\varphi)$ ($\beta=1,\varphi(t)=e^{-\pi t^{2}}$) on the
interval $[-16,16]$ using the numerical approximation routine $\mathcal{R}$
with spectrogram samples located at
$X=\tfrac{1}{2}\\{-40,\dots,40\\}\times\tfrac{1}{12}\\{-60,\dots,60\\}$. To
each spectrogram sample, Gaussian noise with mean zero and standard deviation
0.001 is added, i.e. the measurement matrix $\mathfrak{S}$ takes the form
$\mathfrak{S}=|\mathcal{G}f(X)|^{2}+\mathcal{N}(0,\sigma^{2}),\sigma=0.001$.

###  1.3. Outline

The article is structured as follows: in Section 2 we present the necessary
general theory on shift-invariant spaces which will be used throughout the
article. Section 3 starts with an abstract discussion on the reconstruction of
arbitrary maps from their tensor product. These ideas will be applied to
Gaussian shift-invariant spaces and lead to an explicit inversion formula from
spectrogram measurements which makes use of a biorthogonal expansion. The
section ends with a stability analysis of the derived reconstruction formula.
In the final section, Section 4, we present and analyze an algorithmic way of
approximating functions in Gaussian shift-invariant spaces from finitely many
spectrogram samples. Moreover, we elaborate that the obtained algorithm
approximates signals in Paley-Wiener spaces.

##  2\. Preliminaries on shift-invariant spaces

###  2.1. General theory

For $\beta>0,p\in[1,\infty]$ and $\phi\in L^{p}({\mathbb{R}})$ let the shift-
invariant space $V_{\beta}^{p}(\phi)$ be defined as in (1). Recall that a
sequence $(f_{n})_{n}\subset\mathcal{H}$ in a separable Hilbert space
$\mathcal{H}$ is said to be a Riesz basis for $\mathcal{H}$ if it is complete
in $\mathcal{H}$ and there exist positive constants $0<A\leq B$ such that for
arbitrary $n\in{\mathbb{N}}$ and arbitrary $c_{1},\dots,c_{n}\in{\mathbb{C}}$
one has

(9)
$A\sum_{j=1}^{n}|c_{j}|^{2}\leq\left\|\sum_{j=1}^{n}c_{j}f_{j}\right\|^{2}\leq
B\sum_{j=1}^{n}|c_{j}|^{2}.$

The optimal constants $A$ and $B$ are called the lower and upper bound of
$(f_{n})_{n}$. Every Riesz basis with lower and upper bounds $A$ and $B$ is a
frame with frame constants $A$ and $B$. Associate to a Riesz basis
$(f_{n})_{n}$ its frame operator $S:\mathcal{H}\to\mathcal{H}$, defined by
$Sf=\sum_{n\in{\mathbb{Z}}}\langle f,f_{n}\rangle f_{n}.$ Then $S$ is a
positive, invertible operator and $(S^{-1}f_{n})_{n}$ is biorthogonal to
$(f_{n})_{n}$, i.e.

$\langle f_{n},S^{-1}f_{k}\rangle=\delta_{nk}\coloneqq\begin{cases}1&n=k\\\
0&n\neq k\end{cases}.$

Now let $\mathcal{H}=V_{\beta}^{2}(\phi)$ be a shift-invariant space with a
square-integrable generator $\phi$. Define the 1-periodic map
$\Phi_{\beta}:{\mathbb{R}}\to{\mathbb{R}}$ via

(10)
$\Phi_{\beta}(t)=\sum_{n\in{\mathbb{Z}}}|\hat{\phi}(\tfrac{t+n}{\beta})|^{2}$

where $\hat{\phi}={\mathcal{F}}\phi$ denotes the Fourier transform of $\phi$
which is defined on $L^{1}({\mathbb{R}})\cap{L^{2}({\mathbb{R}})}$ by

$\hat{\phi}(\omega)={\mathcal{F}}\phi(\omega)=\int_{\mathbb{R}}\phi(t)e^{-2\pi
i\omega t}\,dt$

and extends to a unitary operator on ${L^{2}({\mathbb{R}})}$. The map
$\Phi_{\beta}$ characterizes the property of $(T_{\beta n}\phi)_{n}$ being a
Riesz basis for $V_{\beta}^{2}(\phi)$ [10, Theorem 9.2.5].

######  Theorem 2.1.

Let $\phi\in{L^{2}({\mathbb{R}})}$ and $\beta>0$. Suppose that there exists
$0<A\leq B<\infty$ such that

(11) $\beta A\leq\Phi_{\beta}(t)\leq\beta B$

for almost every $t\in[0,1]$. Then $V_{\beta}^{2}(\phi)$ is a closed subspace
of $L^{2}({\mathbb{R}})$ and $(T_{\beta n}\phi)_{n}$ is a Riesz basis for
$V_{\beta}^{2}(\phi)$ with bounds $A$ and $B$.

If $\phi$ satisfies condition (11) and if $S:V_{\beta}^{2}(\phi)\to
V_{\beta}^{2}(\phi)$ is the frame operator associated with $(T_{\beta
n}\phi)_{n}$ then $S$ commutes with $\beta{\mathbb{Z}}$-shifts, implying that
$(S^{-1}T_{\beta n}\phi)_{n}=(T_{\beta n}\tilde{\phi})_{n}$ with
$\tilde{\phi}=S^{-1}\phi$ [10, Lemma 9.4.1]. Accordingly, the canonical dual
frame $(S^{-1}T_{\beta n}\phi)_{n}$ has the same structure as $(T_{\beta
n}\phi)_{n}$.

######  Definition 2.2.

Let $\beta>0$ and $\phi\in{L^{2}({\mathbb{R}})}$ such that $(T_{\beta
n}\phi)_{n}$ is a Riesz basis for $V_{\beta}^{2}(\phi)$. If $S$ is the frame
operator associated with $(T_{\beta n}\phi)_{n}$ then
$\widetilde{\phi}\coloneqq S^{-1}\phi$ is called the dual generator of $\phi$.

Clearly, the dual generator generates the same shift-invariant space, i.e.
$V_{\beta}^{2}(\phi)=V_{\beta}^{2}(\widetilde{\phi})$. In the situation of
Theorem 2.1, the map $\widetilde{\phi}$ can be derived explicitly. To do so,
define in a similar fashion as above the $\frac{1}{\beta}$-periodization of
$|\hat{\phi}|^{2}$ as

$\Psi_{\beta}(t)=\sum_{n\in{\mathbb{Z}}}|\hat{\phi}(t+\tfrac{n}{\beta})|^{2}.$

The dual generator is then given as a formula of $\hat{\phi}$ and $\Psi$.

######  Theorem 2.3.

Suppose that $(T_{\beta n}\phi)_{n}$ is a Riesz basis for
$V_{\beta}^{2}(\phi)$ with frame operator $S$. Let
$D=\\{t\in{\mathbb{R}}:\Psi_{\beta}(t)\neq 0\\}$ and let ${\bm{1}}_{D}$ be the
indicator function of $D$. If the map $\theta$ is defined as

$\theta(\omega)=\frac{\beta\hat{\phi}(\omega)}{\Psi_{\beta}(\omega)}{\bm{1}}_{D}(\omega)$

then $\tilde{\phi}\coloneqq{\mathcal{F}^{-1}}\theta$ is the dual generator of
$\phi$.

###### Proof.

This follows from a generalization of [10, Proposition 9.4.2]. For the
convenience of the reader, we provide a proof in the Appendix A. ∎

Note that the structure of $V_{\beta}^{2}(\phi)$ can be enriched by imposing
further properties on the generator $\phi$. For instance, if $\phi$ is
continuous and belongs to the Wiener Amalgam space then $V_{\beta}^{2}(\phi)$
is a reproducing kernel Hilbert space (RKHS). We refer to [4, 10, 11] for
results in this direction.

###  2.2. Gaussian generators

We now specialize $\phi$ to be the Gaussian $\varphi^{\sigma}$ with variance
$\sigma^{2}$ as defined in Equation (2). For the sake of simplicity we write
$\varphi=\varphi^{\sigma}$ with the implicit understanding that $\varphi$ has
variance $\sigma^{2}$. Properties of $V_{\beta}^{2}(\varphi)$ can be expressed
in terms of the Jacobi theta function of third kind. Recall that this is the
map $\vartheta_{3}:{\mathbb{C}}\times(0,1)\to{\mathbb{C}}$,

$\vartheta_{3}(z,c)=\sum_{n\in{\mathbb{Z}}}c^{n^{2}}e^{2niz}.$

For every fixed $c\in(0,1)$, $\vartheta_{3}$ is an entire, $\pi$-periodic map
in $z$. Using the results of the previous subsection gives

######  Corollary 2.4.

Let $\varphi$ be a centred Gaussian with variance $\sigma^{2}$. Then the
$1$-periodization of $\varphi$ is given by

$\Phi_{\beta}(t)=\sigma\beta\sqrt{\pi}\vartheta_{3}(\pi
t,\varphi(\tfrac{\beta}{\sqrt{2}})).$

In particular, the system $(T_{\beta n}\varphi)_{n}$ constitutes a Riesz basis
for $V_{\beta}^{2}(\varphi)$. Moreover, if the function
$\Lambda:{\mathbb{R}}\to{\mathbb{C}}$ is defined as

$\Lambda(t)\coloneqq\frac{e^{-2\pi^{2}\sigma^{2}t^{2}}}{\vartheta_{3}(\pi\beta
t,\varphi(\frac{\beta}{\sqrt{2}}))}$

then the dual-generator of $\varphi$ is given by
$\widetilde{\varphi}=\sqrt{2}{\mathcal{F}^{-1}}\Lambda$.

###### Proof.

The identity
${\mathcal{F}}\varphi(t)=\sigma\sqrt{2\pi}e^{-2\pi^{2}\sigma^{2}t^{2}}$
implies that the 1-periodization $\Phi_{\beta}$ is given by

(12)
$\begin{split}\Phi_{\beta}(t)&=2\pi\sigma^{2}\sum_{n}e^{-\frac{4\pi^{2}\sigma^{2}}{\beta^{2}}(t+n)^{2}}=\sigma\beta\sqrt{\pi}\sum_{n}e^{-\frac{\beta^{2}n^{2}}{4\sigma^{2}}}e^{2\pi
int}\\\ &=\sigma\beta\sqrt{\pi}\vartheta_{3}(\pi
t,\varphi(\tfrac{\beta}{\sqrt{2}})),\end{split}$

where the second equality follows from Poisson’s summation formula. In a
similar fashion, we obtain

(13) $\Psi_{\beta}(t)=\sqrt{\pi}\sigma\beta\vartheta_{3}(\pi\beta
t,\varphi(\tfrac{\beta}{\sqrt{2}})),$

thereby proving the statement using Theorem 2.3. ∎

Figure 3. Dual generators of Gaussians $\varphi^{\sigma}(t)$ associated with
the shift-invariant space $V_{\beta}^{2}(\varphi)$ with step-sizes
$\beta=0.8,0.6,0.2$ and $\sigma=\beta$.

Note that the zeros of $\vartheta_{3}$ are bounded away from the real axis.
Hence, the reciprocal theta function $\frac{1}{\vartheta_{3}}$ defines an
analytic and periodic function in an open strip containing the real axis. It
follows that the Fourier coefficients $a_{n}=a_{n}(c)$ of
$\frac{1}{\vartheta_{3}}$ decay at least exponentially. If

(14) $\frac{1}{\vartheta_{3}(\pi\beta
t,c)}=\sum_{n\in{\mathbb{Z}}}a_{n}e^{2\pi i\beta nt}$

with $c=\varphi(\tfrac{\beta}{\sqrt{2}})$ then the identity
${\mathcal{F}}(s\mapsto
e^{-2\pi^{2}\sigma^{2}s^{2}})(t)=(\sigma\sqrt{2\pi})^{-1}\varphi(t)$ implies
that $\widetilde{\varphi}$ can be written as

$\widetilde{\varphi}(t)=\frac{1}{\sigma\sqrt{\pi}}\sum_{n}a_{n}T_{-\beta
n}\varphi(t).$

Hence, up to a multiplicative constant, the defining sequence of the dual
generator is given by the Fourier coefficients of the reciprocal theta
function and therefore the decay of $\widetilde{\varphi}$ matches with the
decay of $(a_{n})_{n}$. In fact, the Fourier coefficients of
$\frac{1}{\vartheta_{3}}$ satisfy precisely an exponential decay (see a
derivation by Janssen [27, p. 178] based on results of Whittaker and Watson
[35, p. 489]): if the constant $\xi=\xi(c)$ is defined by

(15) $\xi=\sum_{n\in\mathbb{Z}}(-1)^{n}(2n+1)c^{(n+\frac{1}{2})^{2}}$

then

(16)
$a_{n}=(-1)^{n}\frac{2}{\xi}\sum_{m=0}^{\infty}(-1)^{m}c^{(m+\frac{1}{2})(2|n|+m+\frac{1}{2})}.$

This explicit formula for the Fourier coefficients will be used in the
upcoming sections to derive decay estimates on the dual generator leading to
stability and approximation results of the Gabor phase retrieval problem. We
conclude the present section with the observation that if $f$ has a Gaussian
shift-invariant structure and is merely assumed to be bounded then the inner
products $\langle f,T_{\beta
n}\varphi\rangle\coloneqq\int_{\mathbb{R}}f(t)T_{\beta n}\varphi(t)\,dt$
remain well-defined and the map

(17) $t\mapsto\sum_{n}\langle f,T_{\beta n}\varphi\rangle T_{\beta
n}\widetilde{\varphi}(t)$

defines a smooth function. If $f\in V_{\beta}^{2}(\varphi)$ then the series in
(17) converges both in ${L^{2}({\mathbb{R}})}$ and in
$L^{\infty}({\mathbb{R}})$ to $f$. If $f\in V_{\beta}^{\infty}(\varphi)$ then
the following can be said.

######  Proposition 2.5.

If $f\in V_{\beta}^{\infty}(\varphi)$ then $f(t)=\sum_{n}\langle f,T_{\beta
n}\varphi\rangle T_{\beta n}\widetilde{\varphi}(t)$ where the series on the
right converges uniformly on compact intervals of the real line.

###### Proof.

See the Appendix B. ∎

We call $\sum_{n}\langle f,T_{\beta n}\varphi\rangle T_{\beta
n}\widetilde{\varphi}$ the biorthogonal expansion of $f\in
V_{\beta}^{\infty}(\varphi)$. Note that $V_{\beta}^{\infty}(\varphi)$ consists
of smooth functions and is the largest among the spaces
$V_{\beta}^{p}(\varphi)$ due to the inclusion $V_{\beta}^{p}(\varphi)\subset
V_{\beta}^{q}(\varphi)\subset C^{\infty}({\mathbb{R}}),1\leq p\leq
q\leq\infty$ [4, Corollary 2.5].

##  3\. Phase retrieval in Gaussian shift-invariant spaces

###  3.1. Uniqueness and explicit reconstruction

Let $g\in L^{2}({\mathbb{R}})$ be a window function, $\mathcal{V}_{g}f$ the
short-time Fourier transform of $f\in L^{\infty}({\mathbb{R}})$ and
$\mathcal{G}f$ the Gabor transform of $f$. We aim to recover $f$ from
$|\mathcal{V}_{g}f(X)|$ where $X\subseteq{\mathbb{R}}^{2}$. Clearly, this will
only be possible up to a global phase. In order to decide whether two
functions agree up to global phase one can study their tensor product
$f_{\omega}$ as defined in (4).

######  Proposition 3.1.

Let $f,h:{\mathbb{R}}\to{\mathbb{C}}$ be two complex-valued maps and denote by
$F,H:{\mathbb{R}}^{2}\to{\mathbb{C}}$ the functions $F(t,\omega)\coloneqq
f_{\omega}(t),H(t,\omega)=h_{\omega}(t)$.

  1. (1)

If $p\in{\mathbb{R}}$ such that $F(p,0)\neq 0$ then for every
$\omega\in{\mathbb{R}}$ we have

$f(p+\omega)=\tau F(p,0)^{-\frac{1}{2}}\overline{F(p+\omega,\omega)},\
\tau=\frac{f(p)}{|f(p)|}.$

  2. (2)

If $p\in{\mathbb{R}}$ such that $F(p,0)\neq 0$ and $H$ agrees with $F$ on the
diagonal segment $D^{r}=\\{(p+\omega,\omega):0\leq\omega\leq
r\\},r\in[0,\infty),$ then there exists a $\tau\in{\mathbb{T}}$ such that
$f(p+\omega)=\tau h(p+\omega)$ for every $|\omega|\leq r$.

  3. (3)

If $F=H$ on ${\mathbb{R}}^{2}$ then there exists a $\tau\in{\mathbb{T}}$ such
that $f=\tau h$ on the entire real line.

  4. (4)

Suppose that $p_{1}<p_{2}<\cdots<p_{J}\in{\mathbb{R}}$ such that
$F(p_{j},0)\neq 0$. For $j=1,\dots,J-1$ define function $L_{j}$ and phases
$\nu_{j}$ by

$L_{j}(\omega)=F(p_{j},0)^{-\frac{1}{2}}\overline{F(p_{j}+\omega,\omega)},\
\nu_{j}=\frac{L_{j}(p_{j+1}-p_{j})}{|L(p_{j+1}-p_{j})|},\ \nu_{0}=1.$

Then there exists a $\tau\in{\mathbb{T}}$ with the following property:
Whenever $t\in[p_{1},p_{J}]$ with $t=p_{j}+\omega$ where $p_{j}$ is the
largest value not exceeding $t$ then

(18) $f(t)=\tau\nu_{1}\nu_{2}\cdots\nu_{j-1}L_{j}(\omega).$

In particular, $f$ can be reconstructed on the interval $[p_{1},p_{J}]$ from
the values $F(X)$ where $X$ is the union of the diagonal line segments
$D_{j}=\\{(p_{j}+\omega,\omega):0\leq\omega\leq
p_{j+1}-p_{j}\\},j=1,\dots,J-1$.

###### Proof.

Observe that $F(p,0)=f_{0}(p)=|f(p)|^{2}$. The first statement then follows
directly from the equations

$F(p+\omega,\omega)=f_{\omega}(p+\omega)=f(p)\overline{f(p+\omega)}=\frac{|f(p)|}{\overline{f(p)}}F(p,0)^{\frac{1}{2}}\overline{f(p+\omega)}.$

The second statement follows directly from the first and the third follows
from the second. It remains to show Part 4. Let $L_{j}$ and $\nu_{j}$ be
defined as above. We have by definition

$L_{j}(p_{j+1}-p_{j})=\underbrace{F(p_{j},0)^{-\frac{1}{2}}}_{>0}\overline{f(p_{j})}f(p_{j+1}).$

Therefore, $\nu_{j}=\frac{f(p_{j+1})|f(p_{j})|}{f(p_{j})|f(p_{j+1})|}$ which
gives

$\nu_{1}\cdots\nu_{j-1}=\frac{|f(p_{1})|f(p_{j})}{f(p_{1})|f(p_{j})|}.$

Thus,

$\tau\nu_{1}\cdots\nu_{j-1}L_{j}(\omega)=f(p_{j}+\omega)$

with $\tau=\frac{f(p_{1})}{|f(p_{1})|}$ which further shows that $f$ can be
reconstructed on $[p_{1},p_{J}]$ up a global phase from the union of the
diagonal line segments $D_{j}$. ∎

Part 4 of the preceding proposition can be interpreted as follows: if the
tensor product is known on the diagonal line segments $D_{j},1\leq j\leq J-1$,
then $f$ can be reconstructed on the interval $[p_{j},p_{j+1}]$ up to a global
phase and this reconstruction is given by $L_{j}$. If on each such interval
the local reconstruction is multiplied by the phase
$\tau\nu_{1}\nu_{2}\cdots\nu_{j-1}$ then the resulting function defined on the
union of all the intervals $[p_{j},p_{j+1}]$ agrees up to the phase factor
$\tau$ with $f$. We call the multiplication by $\nu_{1}\nu_{2}\cdots\nu_{j-1}$
a phase synchronization. The phase synchronization is possible whenever
$f(p_{j})\neq 0$. This motivates

######  Definition 3.2.

Let $p_{1},\dots,p_{J}\in{\mathbb{R}}$ and $\gamma>0$. We say that
$f:{\mathbb{R}}\to{\mathbb{C}}$ satisfies condition (P) if

$J\geq 2\ \ \land\ \ p_{1}<p_{2}<\cdots<p_{J}\ \ \land\ \
|f(p_{j})|\geq\gamma\ \forall j\in\\{1,\dots,J\\}.$

Suppose now that $f$ is an element of the Gaussian shift-invariant space
$V_{\beta}^{\infty}(\varphi)$ where $\beta>0$ is an arbitrary step-size. An
important property of $V_{\beta}^{\infty}(\varphi)$ is that the shift-
invariant structure is invariant under the tensor product operation.

######  Proposition 3.3.

Let $\varphi=\varphi^{\sigma}$ be a Gaussian window function with variance
$\sigma^{2}$ and let $V_{\beta}^{\infty}(\varphi)$ be the corresponding shift-
invariant space with generator $\varphi$ and step-size $\beta>0$. If $f\in
V_{\beta}^{\infty}(\varphi)$ then $f_{\omega}\in
V_{\frac{\beta}{2}}^{\infty}(\varphi_{\omega})$ for every
$\omega\in{\mathbb{R}}$.

###### Proof.

Let $c=(c_{n})_{n}\in\ell^{\infty}({\mathbb{Z}})$ be the defining sequence of
$f$, i.e. $f=\sum_{n}c_{n}T_{\beta n}\varphi\in V_{\beta}^{\infty}(\varphi)$.
The tensor product of $f$ is given by

$f_{\omega}=(T_{\omega}f)\overline{f}=\sum_{n}\sum_{k}c_{n}\overline{c_{k}}T_{\beta
n+\omega}\varphi T_{\beta k}\varphi.$

Using the product formula

$\varphi(t-a)\varphi(t-b)=e^{-\frac{(a-b)^{2}}{4\sigma^{2}}}\varphi^{\frac{\sigma}{\sqrt{2}}}(t-\tfrac{a+b}{2}),\
\ a,b\in{\mathbb{R}},\ \ \sigma>0$

we obtain for every $n,k\in{\mathbb{Z}}$ the identity

$\begin{split}T_{\beta n+\omega}\varphi T_{\beta
k}\varphi&=e^{-\frac{(\beta(n-k)+\omega)^{2}}{4\sigma^{2}}}\varphi^{\tfrac{\sigma}{\sqrt{2}}}\left(t-\frac{\beta(n+k)}{2}-\frac{\omega}{2}\right)\\\
&=e^{-\frac{(\beta(n-k)+\omega)^{2}}{4\sigma^{2}}}e^{\frac{\omega^{2}}{4\sigma^{2}}}\varphi\left(t-\frac{\beta(n+k)}{2}-\omega\right)\varphi\left(t-\frac{\beta(n+k)}{2}\right)\\\
&=e^{-\frac{(\beta(n-k)+\omega)^{2}}{4\sigma^{2}}}e^{\frac{\omega^{2}}{4\sigma^{2}}}T_{\frac{\beta}{2}(n+k)}\varphi_{\omega}.\end{split}$

Setting $A(n,k)\coloneqq
e^{-\frac{(\beta(n-k)+\omega)^{2}}{4\sigma^{2}}}e^{\frac{\omega^{2}}{4\sigma^{2}}}$
and defining coefficients $(d_{\ell})_{\ell}\subset{\mathbb{C}}$ via

$d_{\ell}\coloneqq\sum_{n,k\in{\mathbb{Z}},n+k=\ell}A(n,k)c_{n}\overline{c_{k}}$

shows that $f_{\omega}$ takes the form

$f_{\omega}=\sum_{\ell}d_{\ell}T_{\frac{\beta}{2}\ell}\varphi_{\omega}.$

The statement follows at once from the bound
$|d_{\ell}|\leq\|c\|_{\infty}^{2}\sum_{n}A(n,\ell-n)$ and the fact that the
Gaussian sum $\sum_{n}A(n,\ell-n)$ is uniformly bounded in $\ell$. ∎

We aim to reconstruct $f$ from its tensor-product $f_{\omega}$ using the
abstract reconstruction result given in Proposition 3.1 (4). Since
$f_{\omega}$ is generated by $\varphi_{\omega}$ one could recover $f_{\omega}$
from the inner products $\langle
f_{\omega},T_{\frac{\beta}{2}n}\varphi_{\omega}\rangle,n\in{\mathbb{Z}},$
using a biorthogonal expansion as discussed in Section 2.2. We already
verified the Riesz basis property of
$(T_{\frac{\beta}{2}n}\varphi_{\omega})_{n}$ in Corollary 2.4. It remains open
how to gain access to the inner products $\langle
f_{\omega},T_{\frac{\beta}{2}n}\varphi_{\omega}\rangle\in{\mathbb{C}}$. This
information is encoded in the spectrogram of $f$.

######  Proposition 3.4.

For every $f\in L^{\infty}({\mathbb{R}})$ and every
$g\in{L^{2}({\mathbb{R}})}$ one has

${\mathcal{F}}|\mathcal{V}_{g}f(x,\cdot)|^{2}(\omega)=\langle
f_{\omega},T_{x}g_{\omega}\rangle.$

###### Proof.

Under the above assumptions we have
$f\overline{T_{x}g}\in{L^{2}({\mathbb{R}})}$ and therefore
$|{\mathcal{F}}(f\overline{T_{x}g})|^{2}\in L^{1}({\mathbb{R}})$.
Consequently, the Fourier transform of
$t\mapsto|\mathcal{V}_{g}f(x,t)|^{2}=|{\mathcal{F}}(f\overline{T_{x}g})(t)|^{2}$
is pointwise defined (as a continuous function). Now let $p_{x}(t)\coloneqq
f(t+x/2)\overline{g(t-x/2)}$. From the definition of the cross-ambiguity
function $A(f,g)=e^{\pi ix\omega}\mathcal{V}_{g}f(x,\omega)$ it follows that

$A(f,g)(x,\omega)\overline{A(f,g)(x,\omega)}={\mathcal{F}}p_{x}(\omega)\overline{{\mathcal{F}}p_{x}(\omega)}={\mathcal{F}^{-1}}({\mathcal{F}}^{2}p_{x}*\overline{p_{x}})(\omega).$

The convolution ${\mathcal{F}}^{2}p_{x}*\overline{p_{x}}$ can be written as

$({\mathcal{F}}^{2}p_{x}*\overline{p_{x}})(\omega)=\int_{\mathbb{R}}T_{\omega}f(k)\,\overline{f(k)}\,T_{x}[\overline{T_{\omega}g(k)}\,g(k)]\,dk=\langle
f_{\omega},T_{x}g_{\omega}\rangle,$

where we used the change of variables $k\mapsto k-\frac{x}{2}$ in the first
equality. It follows that

$|\mathcal{V}_{g}f(x,\omega)|^{2}=A(f,g)(x,\omega)\overline{A(f,g)(x,\omega)}={\mathcal{F}^{-1}}(t\mapsto\langle
f_{t},T_{x}g_{t}\rangle)(\omega)$

which yields the assertion. ∎

Denoting the dual-generator of $\varphi_{\omega}$ by
$\widetilde{\varphi_{\omega}}$, the following result is an immediate
consequence of Proposition 3.4.

######  Corollary 3.5.

Let $f\in V_{\beta}^{\infty}(\varphi)$. If

$f_{\omega}=\sum_{n\in{\mathbb{Z}}}c_{n}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}},\
(c_{n})_{n}\in\ell^{\infty}({\mathbb{Z}})$

is the biorthogonal expansion of $f_{\omega}$ w.r.t. the dual generator
$\widetilde{\varphi_{\omega}}$ then

(18) $c_{n}=\int_{\mathbb{R}}|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}e^{-2\pi
i\omega t}\,dt$

for every $n\in{\mathbb{Z}}$. In particular, every $f_{\omega}$ is determined
uniquely by $|\mathcal{G}f(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$
and every $f\in V_{\beta}^{\infty}(\varphi)$ is determined up to a global
phase by $|\mathcal{G}f(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$,
i.e. if $f,h\in V_{\beta}^{\infty}(\varphi)$ with
$|\mathcal{G}f(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|=|\mathcal{G}h(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$
then there exists a $\tau\in{\mathbb{T}}$ such that $f=\tau h$.

###### Proof.

The expansion
$f_{\omega}=\sum_{n\in{\mathbb{Z}}}c_{n}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}$
with $(c_{n})_{n}$ given as in (18) is a direct consequence of Proposition 3.3
and Proposition 3.4 above. In particular, this implies that $f_{\omega}$ is
determined uniquely by
$|\mathcal{G}f(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$. Since
$\omega$ was arbitrary, Proposition 3.1 shows that $f$ is determined up to a
global phase factor by
$|\mathcal{G}f(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$. ∎

Observe that if $f$ takes the form $f=\sum_{n}c_{n}T_{\beta n}\varphi$ with
$(c_{n})_{n}\subset{\mathbb{R}}$, i.e. $f$ is real-valued, then the Gabor
phase retrieval problem can be interpreted as a reconstruction of $f$ from its
modulus (up to a variance-change in the generator). For if the frequency
variable in the Gabor transform is set to zero then

(19) $|\mathcal{G}f(x,0)|=\left|\sum_{n}c_{n}(\varphi*T_{\beta
n}\varphi)(x)\right|=\left|\sum_{n}\sigma\sqrt{\pi}c_{n}T_{\beta
n}\varphi^{\sqrt{2}\sigma}(x)\right|=:|h(x)|.$

The map $h$ is an element of $V_{\beta}^{\infty}(\varphi^{\sqrt{2}\sigma})$
and a result due to Gröchenig shows that $h$ is determined by $|h(X)|$
whenever $X\subseteq{\mathbb{R}}$ has lower Beurling density $D^{-}(X)>2\beta$
[19, Theorem 1]. In particular, $f$ is determined by
$|\mathcal{G}f(\frac{\beta}{2+\varepsilon}{\mathbb{Z}}\times\\{0\\})|$. This
result is sharp and does not hold for complex-valued maps [19, Section 2].
Corollary 3.5 shows that in the complex case,
$(c_{n})_{n}\subset{\mathbb{C}}$, uniqueness can be guaranteed if we set
$\varepsilon=0$ and extend the grid $\frac{\beta}{2}{\mathbb{Z}}\times\\{0\\}$
to parallel lines $\frac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}}$ in the time-
frequency plane. In order to transform the uniqueness part of Theorem 2.3 into
a uniqueness result from measurements lying on a lattice, one may suppose
further properties on the step-size $\beta$ as in [21, Theorem 3.6]. We
conclude the present section with an explicit reconstruction formula from
spectrogram measurements.

######  Theorem 3.6.

Let $f\in V_{\beta}^{\infty}(\varphi)$ and let $p\in{\mathbb{R}}$ such that
$f(p)\neq 0$. Then there exists a unimodular constant $\tau\in{\mathbb{T}}$
such that

$f(p+\omega)=\tau|f_{0}(p)|^{-\frac{1}{2}}\sum_{n\in{\mathbb{Z}}}\left(\int_{\mathbb{R}}|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}e^{2\pi
i\omega
t}\,dt\right)T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)$

for every $\omega\in{\mathbb{R}}$ and

$f_{0}(p)=\sum_{n\in{\mathbb{Z}}}\left(\int_{\mathbb{R}}|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}\,dt\right)T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(p)$

###### Proof.

Combining Corollary 3.5 with Proposition 3.1 and fact that the dual generator
$\widetilde{\varphi_{\omega}}$ is real-valued yields the statement. ∎

Theorem 3.6 implies that in a Gaussian shift-invariant setting it suffices to
know the spectrogram on parallel vertical lines in order to reconstruct $f$
from its tensor product. In our further analysis it will be useful to work
with an explicit formula for the dual generator of the tensor product
$\varphi_{\omega}$. Such a formula can be readily established. The product
formula

$\varphi(t-a)\varphi(t-b)=e^{-\frac{(a-b)^{2}}{4\sigma^{2}}}\varphi^{\frac{\sigma}{\sqrt{2}}}(t-\tfrac{a+b}{2}),\
\ a,b\in{\mathbb{R}},\ \ \sigma>0$

implies that
$\varphi_{\omega}(t)=e^{-\frac{\omega^{2}}{4\sigma^{2}}}T_{\frac{\omega}{2}}\varphi^{\frac{\sigma}{\sqrt{2}}}(t)$.
Using Corollary 2.4 and substituting $\sigma$ with $\frac{\sigma}{\sqrt{2}}$
and $\beta$ with $\frac{\beta}{2}$ gives

(20)
$\widetilde{\varphi_{\omega}}=\sqrt{2}e^{-\frac{\omega^{2}}{4\sigma^{2}}}T_{\frac{\omega}{2}}{\mathcal{F}^{-1}}\Lambda,\
\
\Lambda(t)=\frac{e^{-\pi^{2}\sigma^{2}t^{2}}}{\vartheta_{3}(\frac{\beta}{2}\pi
t,\varphi(\frac{\beta}{2}))}.$

###  3.2. Stability

This section is devoted to the stability analysis of the biorthogonal
expansion of the tensor product $f_{\omega}$ as well as the explicit inversion
formula presented in Theorem 3.6. Let the mixed norm $\|\cdot\|_{\alpha,p}$ be
defined as in equation (6). Using this norm, stability estimates for tensor
products of functions in $V_{\beta}^{1}(\varphi)$ can be derived.

######  Corollary 3.7.

Let $f,h\in V_{\beta}^{1}(\varphi),\omega\in{\mathbb{R}}$, and suppose that
$A(\sigma,\beta,\omega)$ is the lower bound of the Riesz basis
$(T_{\frac{\beta}{2}n}\varphi_{\omega})_{n}$ as given in Theorem 2.4. Then

(21)
$\|f_{\omega}-h_{\omega}\|_{{L^{2}({\mathbb{R}})}}^{2}\leq\frac{1}{A(\sigma,\beta,\omega)}\||\mathcal{G}f|^{2}-|\mathcal{G}h|^{2}\|_{\frac{\beta}{2},2}^{2}$

where
$A(\sigma,\beta,\omega)=\frac{\sigma}{\sqrt{2}}\varphi(\omega)\vartheta_{3}(\frac{\pi}{2},\varphi(\frac{\beta}{2}))$

###### Proof.

By Hölder’s inequality we have $f_{\omega},h_{\omega}\in
V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$. The fact that
$(T_{\frac{\beta}{2}n}\varphi_{\omega})_{n}$ is a Riesz basis for
$V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$ implies that

$A(\sigma,\beta,\omega)\|f_{\omega}-h_{\omega}\|_{{L^{2}({\mathbb{R}})}}^{2}\leq\sum_{n}|\langle
f_{\omega}-h_{\omega},T_{\frac{\beta}{2}n}\varphi_{\omega}\rangle|^{2}.$

In addition, Proposition 3.4 shows that

$\begin{split}|\langle
f_{\omega}-h_{\omega},T_{\frac{\beta}{2}n}\varphi_{\omega}\rangle|&=|{\mathcal{F}}(|\mathcal{G}f(\tfrac{\beta}{2}n,\cdot)|^{2}-|\mathcal{G}h(\tfrac{\beta}{2}n,\cdot)|^{2})(\omega)|\\\
&\leq\||\mathcal{G}f(\tfrac{\beta}{2}n,\cdot)|^{2}-|\mathcal{G}h(\tfrac{\beta}{2}n,\cdot)|^{2}\|_{L^{1}({\mathbb{R}})}.\end{split}$

Combining the previous two inequalities yields the first part of the
statement. To obtain the second assertion, we observe that the 1-periodization
of $\varphi_{\omega}$ with step-size $\frac{\beta}{2}$ is given by
$\Phi_{\beta/2}(t)=\frac{\sigma\beta}{2\sqrt{2}}\varphi(\omega)\vartheta_{3}(\pi
t,\varphi(\frac{\beta}{2})).$ According to Theorem 2.1, the value
$A(\sigma,\beta,\omega)$ is then given as the minimum of the map

$t\mapsto\frac{2\Phi_{\beta/2}(t)}{\beta}$

on $[0,1]$. It was shown by Janssen [27, p. 178] that for every $c\in(0,1)$
the theta function $\vartheta_{3}(\cdot,c)$ attains its minima at
$t\in\frac{\pi}{2}{\mathbb{Z}}$, thereby proving the statement. ∎

By virtue of the RKHS structure it is evident that an analogue version of
Corollary 3.7 can be derived where the $L^{2}$-norm on the left-hand side is
replaced by the $L^{\infty}$-norm. For, if $f,h\in V_{\beta}^{1}(\varphi)$
then $f_{\omega},h_{\omega}\in V^{2}_{\frac{\beta}{2}}(\varphi_{\omega})$ and
$V^{2}_{\frac{\beta}{2}}(\varphi_{\omega})$ is a RKHS. Therefore, the point
evaluation functionals

$f_{\omega}\mapsto f_{\omega}(x),\ \ x\in{\mathbb{R}},$

are continuous linear functionals on
$V^{2}_{\frac{\beta}{2}}(\varphi_{\omega})$ and there exists $K_{x}\in
V^{2}_{\frac{\beta}{2}}(\varphi_{\omega})$ such that $f_{\omega}(x)=\langle
f_{\omega},K_{x}\rangle$ which implies that

$|f_{\omega}(x)-h_{\omega}(x)|\leq\|K_{x}\|_{L^{2}({\mathbb{R}})}\|f_{\omega}-h_{\omega}\|_{L^{2}({\mathbb{R}})}.$

Combining the fact that the generator is a Gaussian with an explicit form of
$K_{x}$ (see, for instance, [4, Theorem 4.1]), we observe that
$x\mapsto\|K_{x}\|_{L^{2}({\mathbb{R}})}$ is bounded on ${\mathbb{R}}$ which
in turn yields the bound

$\|f_{\omega}-h_{\omega}\|_{L^{\infty}({\mathbb{R}})}\leq
c\|f_{\omega}-h_{\omega}\|_{L^{2}({\mathbb{R}})}$

for some constant $c>0$.

Moreover, for a fixed $\omega\in{\mathbb{R}}$, Corollary 3.7 shows that the
tensor product $f_{\omega}$ of functions $f\in V_{\beta}^{1}(\varphi)$ is
stably determined by spectrogram measurements and the stability constant
$\tfrac{1}{A(\sigma,\beta,\omega)}$ in inequality (21) is independent of $f$
and $h$. Consequently, the reconstruction of $f_{\omega}$ from
$|\mathcal{G}f(\tfrac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$ is globally
stable within the signal class $V_{\beta}^{1}(\varphi)$. Since

$A(\sigma,\beta,\omega)=\frac{\sigma}{\sqrt{2}}\varphi(\omega)\vartheta_{3}(\tfrac{\pi}{2},\varphi(\tfrac{\beta}{2}))$

it follows that the stability constant for reconstructing the modulus
$f_{0}=|f|^{2}$ is the best among the constants
$\\{A(\sigma,\beta,\omega):\omega\in{\mathbb{R}}\\}$ and the stability
deteriorates rapidly in $\omega$. Classical examples for instabilities are of
the form

(22) $\begin{split}f_{n,+}&=T_{\beta n}\varphi+T_{-\beta n}\varphi,\\\
f_{n,-}&=T_{\beta n}\varphi-T_{-\beta n}\varphi,\end{split}$

and they show that the stability constant grows like $e^{n^{2}}$ [3]. Thus,
one cannot expect to stably reconstruct arbitrary non-positive functions
without imposing further assumptions. We surpass instabilities arising from
signals of the form (22) in the following way: A closer look on the map
$f\coloneqq f_{n,+}$ shows that on the interval $I=[-\beta n,\beta n]$ it
holds that

$|f_{n,+}(\beta n)|=|f_{n,+}(-\beta n)|\approx 1$

whereas $|f|\approx 0$ on a large part of the interior of $I$. Therefore,
$|f|$ (and also $|\mathcal{G}f|$) is concentrated on two almost disjoint
components which is a classical indicator for instabilities [1, 23, 24]. Such
situations can be excluded by the requirement that $f$ satisfies condition
(P): if $p_{1}<\cdots<p_{J}\in{\mathbb{R}},I\subseteq[p_{1},p_{J}]$ and
$\gamma>0$ with $|f(p_{j})|\geq\gamma$ for all $j$ then the distance of the
areas where $|f|$ is concentrated is determined by the value $r=\max_{1\leq
j\leq J-1}p_{j+1}-p_{j}$. In this setting we expect that the quotient distance
$\min_{\tau\in{\mathbb{T}}}\|f-\tau g\|$ can be controlled by the norm of the
difference of the corresponding spectrograms up to factor which depends on
$e^{r^{2}}$ and $\frac{1}{\gamma}$. This is indeed the case as we shall
elaborate in the following. First, we define a constant $C(\sigma,\beta)$
depending only on the variance of the generator as well as the step-size of
the underlying Gaussian shift-invariant space by

(23)
$C(\sigma,\beta)\coloneqq\sup_{p\in{\mathbb{R}}}\sum_{n\in{\mathbb{Z}}}|T_{\frac{\beta}{2}n}{\mathcal{F}^{-1}}\Lambda(p)|$

where $\Lambda$ is the map which characterizes the dual generator, see
equation (20). We start with local stability estimates around points
$p_{j}\in{\mathbb{R}},1\leq j\leq J,J\in{\mathbb{N}}$ where $f(p_{j})\neq 0$
for all $j$.

######  Lemma 3.8.

Let $f,g\in V_{\beta}^{\infty}(\varphi),r>0,J\in{\mathbb{N}}$ and
$p_{j}\in{\mathbb{R}},1\leq j\leq J,$ such that $f(p_{j}),g(p_{j})\neq 0$ for
every $j$. Define

$\tau_{j}\coloneqq\frac{\overline{g(p_{j})}|f(p_{j})|}{|g(p_{j})|\overline{f(p_{j})}},\
I_{j}\coloneqq[p_{j}-r,p_{j}+r],$
$c_{j}\coloneqq\frac{1}{|g(p_{j})|}\left(e^{\frac{r^{2}}{4\sigma^{2}}}+\frac{\|f\|_{L^{\infty}(I_{j})}}{|f(p_{j})|+|g(p_{j})|}\right).$

Then
$\||f|^{2}-|g|^{2}\|_{L^{\infty}({\mathbb{R}})}\leq\sqrt{2}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}C(\sigma,\beta)$
and for every $j\in\\{1,\dots,J\\}$ it holds that

$\min_{\tau\in{\mathbb{T}}}\|f-\tau
g\|_{L^{\infty}(I_{j})}\leq\|f-\tau_{j}g\|_{L^{\infty}(I_{j})}\leq
c_{j}\sqrt{2}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}C(\sigma,\beta),$

with $C(\sigma,\beta)$ being defined as in equation (23).

###### Proof.

In view of Corollary 3.5, both maps $|f|^{2}$ and $|g|^{2}$ can be expanded in
terms of the dual generator of $\varphi_{0}=\varphi^{2}$. Hence, we have for
every $t\in{\mathbb{R}}$ the estimate

$\begin{split}||f(t)|^{2}-|g(t)|^{2}|&=\left|\sum_{n}\langle
f_{0},T_{\frac{\beta}{2}n}\varphi_{0}\rangle
T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(t)-\sum_{n}\langle
g_{0},T_{\frac{\beta}{2}n}\varphi_{0}\rangle
T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(t)\right|\\\ &\leq\sum_{n}|\langle
f_{0},T_{\frac{\beta}{2}n}\varphi_{0}\rangle-\langle
g_{0},T_{\frac{\beta}{2}n}\varphi_{0}\rangle||T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(t)|\\\
&\leq\sqrt{2}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}\sum_{n}|T_{\frac{\beta}{2}n}{\mathcal{F}^{-1}}\Lambda(p)|\\\
&\leq\sqrt{2}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}C(\sigma,\beta)=:B.\end{split}$

Let $\omega\in{\mathbb{R}}$ with $|\omega|\leq r$. Since
$f(p_{j}),g(p_{j})\neq 0$ the explicit reconstruction formula from tensor
products shows that

$f(p_{j}+\omega)=\frac{1}{\overline{f(p_{j})}}\overline{f_{\omega}(p_{j}+\omega)},\
g(p_{j}+\omega)=\frac{1}{\overline{g(p_{j})}}\overline{g_{\omega}(p_{j}+\omega)}.$

The choice of $\tau_{j}$ implies that

$\begin{split}&|f(p_{j}+\omega)-\tau_{j}g(p_{j}+\omega)|=\left|\frac{1}{|f(p_{j})|}f_{\omega}(p_{j}+\omega)-\frac{1}{|g(p_{j})|}g_{\omega}(p_{j}+\omega)\right|\\\
&\leq\frac{1}{|g(p_{j})|}|f_{\omega}(p_{j}+\omega)-g_{\omega}(p_{j}+\omega)|+\frac{||g(p_{j})|-|f(p_{j})||}{|f(p_{j})g(p_{j})|}|f_{\omega}(p_{j}+\omega)|\\\
&=\frac{1}{|g(p_{j})|}(|f_{\omega}(p_{j}+\omega)-g_{\omega}(p_{j}+\omega)|+||f(p_{j})|-|g(p_{j})|||f(p_{j}+\omega)|)\\\
&\leq\frac{1}{|g(p_{j})|}\left(|f_{\omega}(p_{j}+\omega)-g_{\omega}(p_{j}+\omega)|+\frac{B}{|f(p_{j})|+|g(p_{j})|}\|f\|_{L^{\infty}(I_{j})}\right).\end{split}$

Setting $A\coloneqq|f_{\omega}(p_{j}+\omega)-g_{\omega}(p_{j}+\omega)|$ and
employing the reconstruction formula from Theorem 3.6 and the explicit form of
the dual generator gives

$\begin{split}A&=\left|\sum_{n}\left(\int_{\mathbb{R}}(|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}-|\mathcal{G}g(\tfrac{\beta}{2}n,t)|^{2})e^{-2\pi
i\omega
t}\,dt\right)T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)\right|\\\
&\leq\sum_{n}\||\mathcal{G}f(\tfrac{\beta}{2}n,\cdot)|^{2}-|\mathcal{G}g(\tfrac{\beta}{2}n,\cdot)|^{2}\|_{L^{1}({\mathbb{R}})}|T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)|\\\
&\leq\sqrt{2}e^{\frac{\omega^{2}}{4\sigma^{2}}}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}\sum_{n}|T_{\frac{\beta}{2}n+\frac{\omega}{2}}{\mathcal{F}^{-1}}\Lambda(p+\omega)|\\\
&\leq e^{\frac{r^{2}}{4\sigma^{2}}}B.\end{split}$

The assertion follows from that. ∎

For $j\in{\mathbb{N}}$, let $\tau_{j},I_{j}$ and $c_{j}$ be defined analogue
to Lemma 3.8. The following elementary Lemma will be useful in the proof of
the main stability result of the present section.

######  Lemma 3.9.

Let $f,g\in V_{\beta}^{\infty}(\varphi),r>0$ and $p_{j},p_{m}\in{\mathbb{R}}$
such that

$f(p_{j}),g(p_{j}),f(p_{m}),g(p_{m})\neq 0.$

Suppose that $c_{j},\tau_{j},\tau_{m}$ are defined as in Lemma 3.8. If we
define

(24)
$B\coloneqq\sqrt{2}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}C(\sigma,\beta)$

then we have the implication

$|p_{j}-p_{m}|\leq
r\implies|\tau_{j}-\tau_{m}|\leq\frac{c_{j}B}{|g(p_{m})|}+\frac{B}{|f(p_{m})|(|f(p_{m})+|g(p_{m})|)}.$

###### Proof.

Since $|p_{j}-p_{m}|\leq r$ we have $p_{m}\in I_{j}$. Lemma 3.8 implies that

$|f(p_{m})-\tau_{j}g(p_{m})|\leq c_{j}B.$

Using the definition of $\tau_{j}$ we can re-write the left-hand side of the
previous inequality as

$|f(p_{m})-\tau_{j}g(p_{m})|=\left|\frac{f(p_{m})\overline{f(p_{j})}|g(p_{j})|}{|f(p_{j})g(p_{j})|}-\frac{g(p_{m})\overline{g(p_{j})}|f(p_{j})|}{|f(p_{j})g(p_{j})|}\right|=:|\mu-\nu|.$

Since

$\tau_{j}=\frac{\overline{g(p_{j})}|f(p_{j})|}{|g(p_{j})|\overline{f(p_{j})}},\
\
\tau_{m}=\frac{\overline{g(p_{m})}|f(p_{m})|}{|g(p_{m})|\overline{f(p_{m})}}$

we obtain with Lemma 3.8

$\begin{split}|\tau_{j}-\tau_{m}|&=\left|\frac{1}{|f(p_{m})|}\mu-\frac{1}{|g(p_{m})|}\nu\right|\leq\frac{|\mu-\nu|}{|g(p_{m})|}+\frac{||f(p_{m})|^{2}-|g(p_{m})|^{2}|}{|g(p_{m})|(|f(p_{m})|+|g(p_{m})|)}\\\
&\leq\frac{c_{j}B}{|g(p_{m})|}+\frac{B}{|g(p_{m})|(|f(p_{m})|+|g(p_{m})|)}.\end{split}$

∎

With the help of Lemma 3.9, the local stability result obtained in Lemma 3.8
transfers to stability estimates on larger intervals by imposing condition
(P).

######  Theorem 3.10.

Let $\gamma>0$ and $p_{1}<\cdots<p_{J}\in{\mathbb{R}}$ such that $f\in
V_{\beta}^{\infty}(\varphi)$ satisfies condition (P). If $I=[p_{1}-r,p_{J}+r]$
and $r=\max_{1\leq j\leq J-1}(p_{j+1}-p_{j})$ then for every $g\in
V_{\beta}^{\infty}(\varphi)$ we have

(25) $\begin{split}&\min_{\tau\in{\mathbb{T}}}\|f-\tau g\|_{L^{\infty}(I)}\\\
&\lesssim_{\beta,\sigma}(J-1)e^{\frac{r^{2}}{4\sigma^{2}}}\frac{\max\\{\|f\|_{L^{\infty}(I)}^{2},\|f\|_{L^{\infty}(I)}+\|g\|_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{3}\\}}\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}\end{split}$

where the implicit constant is upper bounded by
$\frac{32\sqrt{2}}{3}C(\sigma,\beta)$.

###### Proof.

Case 1. Suppose first that $|\mathcal{G}g|^{2}$ is in a ball of radius
$(2\sqrt{2}C(\sigma,\beta))^{-1}\gamma^{2}$ around $|\mathcal{G}f|^{2}$ with
respect to the mixed norm $\|\cdot\|_{\frac{\beta}{2},\infty}$, that is,

$\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}\leq\frac{\gamma^{2}}{2\sqrt{2}C(\sigma,\beta)}.$

By Lemma 3.8 we have
$\||f|^{2}-|g|^{2}\|_{L^{\infty}({\mathbb{R}})}\leq\sqrt{2}C(\sigma,\beta)\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}$
and therefore for every $j\in\\{1,\dots,J\\}$ it holds that

$||f(p_{j})|-|g(p_{j})|\leq\frac{||f(p_{j})|^{2}-|g(p_{j})|^{2}|}{|f(p_{j})|}\leq\frac{\gamma}{2}.$

In particular, $|g(p_{j})|\geq\frac{\gamma}{2}$. Define
$I_{j}\coloneqq[p_{j}-r,p_{j}+r],j\in\\{1,\dots,J\\}$. Since
$|p_{j+1}-p_{j}|\leq r$ for all $j$ we have $I=\bigcup_{j=1}^{J}I_{j}.$ Now
let $\tau_{1},\dots,\tau_{J}\in{\mathbb{T}}$ be chosen as in Lemma 3.8. Then

(26)
$\|f-\tau_{1}g\|_{L^{\infty}(I)}=\max\\{\|f-\tau_{1}g\|_{L^{\infty}(I_{j})}:j=1,\dots,J\\}.$

and for a fixed $j\in\\{1,\dots,J\\}$ we have

$\begin{split}\|f-\tau_{1}g\|_{L^{\infty}(I_{j})}&\leq\|f-\tau_{j}g\|_{L^{\infty}(I_{j})}+|\tau_{1}-\tau_{j}|\|f\|_{L^{\infty}(I_{j})}\\\
&\leq\|f-\tau_{j}g\|_{L^{\infty}(I_{j})}+\|f\|_{L^{\infty}(I)}\sum_{i=1}^{j-1}|\tau_{i}-\tau_{i+1}|\\\
&\leq\frac{2B}{\gamma}\left(e^{\frac{r^{2}}{4\sigma^{2}}}+\frac{2\|f\|_{L^{\infty}(I)}}{3\gamma}\right)+\|f\|_{L^{\infty}(I)}\sum_{i=1}^{j-1}|\tau_{i}-\tau_{i+1}|.\end{split}$

By the assumption on the distance between the $p_{j}$’s and the definition of
the $I_{j}$’s we have $p_{j}\in I_{j-1}$ for every $j\in\\{2,\dots,J\\}$.
Therefore, Lemma 3.9 shows that

$\begin{split}\sum_{i=1}^{j-1}|\tau_{i}-\tau_{i+1}|&\leq\sum_{i=1}^{j-1}\left(\frac{c_{i}B}{|g(p_{i+1})|}+\frac{B}{|f(p_{i+1})|(|f(p_{i+1})|+|g(p_{i+1})|)}\right)\\\
&\leq\sum_{i=1}^{j-1}\frac{2c_{i}B}{\gamma}+\frac{2B}{3\gamma^{2}}\\\
&\leq\frac{2(j-1)B}{3\gamma^{2}}+\frac{4(j-1)B}{\gamma^{2}}\left(e^{\frac{r^{2}}{4\sigma^{2}}}+\frac{2\|f\|_{L^{\infty}(I)}}{3\gamma}\right)\end{split}$

where $B$ is defined as in (24). Using standard estimates it follows that,

$\|f-\tau_{1}g\|_{L^{\infty}(I_{j})}\leq\frac{32}{3}(j-1)e^{\frac{r^{2}}{4\sigma^{2}}}\frac{\max\\{\|f\|_{L^{\infty}(I)},\|f\|_{L^{\infty}(I)}^{2}\\}}{\min\\{\gamma,\gamma^{2},\gamma^{3}\\}}C(\sigma,\beta)B$

which implies in combination with equation (26) that

$\|f-\tau_{1}g\|_{L^{\infty}(I)}\leq\frac{32}{3}(J-1)e^{\frac{r^{2}}{4\sigma^{2}}}\frac{\max\\{\|f\|_{L^{\infty}(I)},\|f\|_{L^{\infty}(I)}^{2}\\}}{\min\\{\gamma,\gamma^{2},\gamma^{3}\\}}B.$

Case 2. If

$\||\mathcal{G}f|^{2}-|\mathcal{G}g|^{2}\|_{\frac{\beta}{2},\infty}>\frac{\gamma^{2}}{2\sqrt{2}C(\sigma,\beta)}$

then clearly for every $\tau\in{\mathbb{T}}$ we have the estimate

$\|f-\tau
g\|_{L^{\infty}(I)}\leq\frac{2(\|f\|_{L^{\infty}(I)}+\|g\|_{L^{\infty}(I)})}{\gamma^{2}}B.$

The statement follows from case 1 and case 2. ∎

Additional assumptions on $\sigma$ and $\beta$ yield explicit upper bounds on
the constant $C=C(\sigma,\beta)$. To achieve such bounds we first observe that
according to Section 2.2 the map ${\mathcal{F}^{-1}}\Lambda$ satisfies an
exponential decay. Thus, there are constants
$K=K(\sigma,\beta),\nu=\nu(\sigma,\beta)>0$ such that

(27) $|{\mathcal{F}^{-1}}\Lambda(t)|\leq Ke^{-\nu|t|}.$

In an exemplary way we can derive a result of the following form which will
result in explicit upper bounds on $C(\sigma,\beta)$.

######  Lemma 3.11.

If $\frac{\beta}{4}\leq\sigma\leq\frac{\beta}{2}\leq 1$ then
$\nu\geq\frac{1}{4}$ and $K\leq\frac{205}{\sigma}$.

###### Proof.

See the Appendix C. ∎

A consequence of Lemma 3.11 is an explicit upper bound on the stability
constant $C(\sigma,\beta)$: if
$\frac{\beta}{4}\leq\sigma\leq\frac{\beta}{2}\leq 1$ then

$C(\sigma,\beta)=\sup_{p\in{\mathbb{R}}}\sum_{n\in{\mathbb{Z}}}|{\mathcal{F}^{-1}}\Lambda(p-\tfrac{\beta}{2})|\leq\frac{205}{\sigma}\left(2+\int_{\mathbb{R}}e^{-\frac{\beta}{8}|t|}\right)=\frac{205}{\sigma}\left(2+\frac{16}{\beta}\right).$

######  Remark 3.12 (On the dependence on $\|f\|_{L^{\infty}(I)}$ and
$\|g\|_{L^{\infty}(I)}$ in the stability estimte (25)).

Shift-invariant spaces $V_{\alpha}^{p}(\varphi^{u}),\alpha>0,p\in[1,\infty],$
generated by a Gaussian with standard deviation $u>0$ satisfy the norm
equivalence

$\|h\|_{L^{p}({\mathbb{R}})}\asymp\|a\|_{\ell^{p}({\mathbb{Z}})},\ h\in
V_{\alpha}^{p}(\varphi^{\nu}),$

where $h$ has defining sequence $a=(a_{n})_{n}\in\ell^{p}({\mathbb{Z}})$ [4,
Theorem 3.1]. Moreover, recent sampling results for shift-invariant spaces
with totally positive generator of Gaussian type show that

$\|h\|_{L^{p}({\mathbb{R}})}\asymp\|h(\Omega)\|_{\ell^{p}({\mathbb{Z}})}$

whenever $\Omega\subset{\mathbb{R}}$ is separated with lower Beurling density
$D^{-}(\Omega)>\alpha^{-1}$ [25, Theorem 4.4]. In equation (19) we observed
that if $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$ then $\mathcal{G}f(\cdot,0)\in
V_{\beta}^{\infty}(\varphi^{\sqrt{2}\sigma})$ has defining sequence
$(d_{n})_{n}$ with $d_{n}=\sigma\sqrt{\pi}c_{n}$. Setting
$\Omega=\frac{\beta}{2}{\mathbb{Z}}$ gives
$D^{-}(\Omega)=2\beta^{-1}>\beta^{-1}$ and the norm equivalences above imply

$\|f\|_{L^{\infty}({\mathbb{R}})}\asymp\||\mathcal{G}f|\|_{L^{\infty}({\mathbb{R}}\times\\{0\\})}\asymp\||\mathcal{G}f|\|_{\ell^{\infty}(\frac{\beta}{2}{\mathbb{Z}}\times\\{0\\})}.$

Consequently, one has

$\|f\|_{L^{\infty}(I)}\lesssim_{\sigma,\beta}\||\mathcal{G}f|\|_{\ell^{\infty}(\frac{\beta}{2}{\mathbb{Z}}\times\\{0\\})}$

with a universal constant depending only on $\sigma$ and $\beta$. With this
choice of a sampling set $\Omega$, the right-hand side of the stability
estimate (25) can be made dependent only on
$\gamma,\sigma,\beta,|\mathcal{G}f(\frac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$
and $|\mathcal{G}g(\frac{\beta}{2}{\mathbb{Z}}\times{\mathbb{R}})|$.

##  4\. Algorithmic approximation in $V_{\beta}^{\infty}(\varphi)$

In the final section of the present article we shall combine our previous
results to derive an algorithmic approximation of functions $f\in
V_{\beta}^{\infty}(\varphi)$ from finitely many spectrogram samples
$|\mathcal{G}f(X)|,X\subset{\mathbb{R}}^{2},|X|<\infty$. Assume that the
samples $X$ are given on a finite grid of the form

(28) $X=\tfrac{\beta}{2}\\{-N,\dots,N\\}\times h\\{-H,\dots,H\\}$

where $N,H\in{\mathbb{N}}$ and $h,\beta>0$. We call $\frac{1}{h}$ the sampling
density of $X$ in frequency direction. If
$\eta\in{\mathbb{R}}^{(2N+1)\times(2H+1)}$ denotes a noise matrix then the
given sampling set $\mathfrak{S}$ takes the form

$\begin{split}&\mathfrak{S}=(|\mathcal{G}f(X)|^{2}+\eta_{n,k})_{n,k}\in{\mathbb{R}}^{(2N+1)\times(2H+1)},\\\
&\mathfrak{S}(n,k)=|\mathcal{G}f(\tfrac{\beta}{2}n,hk)|^{2}+\eta_{n,k}.\end{split}$

To quantify the contribution of the noise $\eta$ we use the
$\ell^{\infty}$-operator norm of $\eta$,

$\|\eta\|_{\infty}\coloneqq\sup_{x\neq 0}\frac{\|\eta
x\|_{\infty}}{\|x\|_{\infty}}=\max_{1\leq i\leq
2N+1}\sum_{j=1}^{2H+1}|\eta_{ij}|,$

which is the maximum absolute row sum of $\eta$. Our only assumption on the
noise $\eta$ is that we have control over the norm
$\|\eta\|_{\infty}\leq\delta$ for some noise-level $\delta>0$. Otherwise, the
error is arbitrary and can be adversarial.

Figure 4. The contour plot depicts the spectrogram of a function $f\in
V_{\beta}^{\infty}(\varphi)$ and the white dots visualize the location of the
samples $\mathfrak{S}$. The values $\frac{2}{\beta}$ and $\frac{1}{h}$ are the
densities in time ($x$) resp. frequency ($\omega$) direction.

###  4.1. The numerical approximation routine $\mathcal{R}$

We start by presenting our reconstruction approach in an abstract setting,
leaving the ansatz open for extensions to other signal classes (see Section
4.4). Assume for the time-being that the function $f$ has only the property of
being measurable and bounded. Let $p_{1}<\cdots<p_{J}$ and $\gamma>0$ such
that $f$ satisfies condition (P). For simplicity we assume that
$-p_{1}=p_{J}\eqqcolon s$ and set $I=[-s,s]$. The aim is to recover $f$ on the
interval $I$. Generalizations to other intervals are straightforward and can
be achieved by a simple translation. Motivated by Proposition 3.1 and Theorem
3.6 we define constants $c_{j}$ by

$c_{j}=h\sum_{n}\sum_{k}\mathfrak{S}(n,k)T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}(p_{j}),$

local reconstructive functions $L_{j}$ by

$L_{j}(\omega)=\frac{h}{\sqrt{c_{j}}}\sum_{n}\sum_{k}\mathfrak{S}(n,k)e^{2\pi
i\omega hk}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p_{j}+\omega)$

and phases $\nu_{0},\dots,\nu_{J-1}\in{\mathbb{T}}$ by

$\nu_{0}=1,\ \ \nu_{j}=\frac{L_{j}(p_{j+1}-p_{j})}{|L_{j}(p_{j+1}-p_{j})|}\
(j=1,\dots,J-1).$

Note that $c_{j},L_{j}$ and $\nu_{j}$ depend only on the sampling set
$\mathfrak{S}$. Assuming that $L_{j}$ and $\nu_{j}$ are well-defined, i.e.
$c_{j}>0$ and $L_{j}(p_{j+1}-p_{j})\neq 0$, gives rise to the definition of a
numerical approximation routine.

######  Definition 4.1.

Suppose that $f:{\mathbb{R}}\to{\mathbb{C}}$ is a measurable and bounded map
which satisfies condition (P) with $\gamma>0$ and
$p_{1}<\cdots<p_{J}\in{\mathbb{R}},-p_{1}=p_{J}=s$. Let the grid $X$ be
defined as in (28) and suppose that $L_{j}$ and $\nu_{j}$ are well-defined.
The numerical approximation routine $\mathcal{R}:[-s,s]\to{\mathbb{C}}$ of $f$
is defined as follows: if $t\in[-s,s]$ such that $t\in(p_{j},p_{j+1}]$ with
$t=p_{j}+\omega$ then

$\mathcal{R}(t)=\nu_{1}\cdots\nu_{j-1}L_{j}(\omega).$

For $t=p_{1}=-s$ we define $\mathcal{R}(t)=L_{1}(0)$.

In order to derive approximation results by means of the numerical
approximation routine $\mathcal{R}$, we define for $j=1,\dots,J-1$ the error
term

(29)
$E_{j}(\omega)\coloneqq|f_{\omega}(p_{j}+\omega)-\sqrt{c_{j}}\overline{L_{j}(\omega)}|.$

This error term allows us to state conditions under which the functions
$L_{j}$ and the phases $\nu_{j}$ are well-defined. More importantly, it yields
an upper bound on the quotient distance of $f$ and $\mathcal{R}$.

######  Theorem 4.2.

Let $f:{\mathbb{R}}\to{\mathbb{C}}$ be a measurable and bounded function which
satisfies condition (P) with $\gamma>0$ and
$p_{1}<\cdots<p_{J}\in{\mathbb{R}},-p_{1}=p_{J}=s$. If $I=[-s,s]$,
$0<\varepsilon\leq\min\left\\{\frac{\gamma^{2}}{2\sqrt{8}},\frac{\gamma^{3}}{4\|f\|_{L^{\infty}(I)}}\right\\}$
and

$\max_{1\leq j\leq J-1}\|E_{j}\|_{L^{\infty}[0,p_{j+1}-p_{j}]}\leq\varepsilon$

then $L_{j}$ and $\nu_{j}$ are well-defined for every $j\in\\{1,\dots,J\\}$.
Further, it holds that

$\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}(I)}\leq
32(J-1)\frac{\max\\{1,\|f\|^{2}_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{5}\\}}(\varepsilon+\varepsilon^{2}).$

###### Proof.

Let $I\coloneqq[-s,s]$ and $I_{j}\coloneqq(p_{j},p_{j+1}]$ for
$j=1,\dots,J-1$.

Step 1: Upper bounding
$\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}(I)}$. Assume for
the time-being that the phases $\nu_{j}$ and the constants $c_{j}$ are well-
defined. Let $t\in I$ such that $t\in(p_{j},p_{j+1}]$ with $t=p_{j}+\omega$
and $2\leq j\leq J-1$. Then

(30)
$\begin{split}&\left|f(t)-\frac{f(p_{1})}{|f(p_{1})|}\mathcal{R}(t)\right|\\\
&\leq\left|f(p_{j}+\omega)-\frac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)\right|+\left|\frac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)-\frac{f(p_{1})}{|f(p_{1})|}\nu_{1}\cdots\nu_{j-1}L_{j}(\omega)\right|\\\
&=\left|f(p_{j}+\omega)-\frac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)\right|+\underbrace{\left|\frac{f(p_{j})}{|f(p_{j})|}-\frac{f(p_{1})}{|f(p_{1})|}\nu_{1}\cdots\nu_{j-1}\right|}_{\coloneqq
A}|L_{j}(\omega)|.\end{split}$

The term $A$ can be bounded by

(31)
$\begin{split}A&=\left|\overline{\nu_{j-1}}\frac{f(p_{j})}{|f(p_{j})|}-\frac{f(p_{1})}{|f(p_{1})|}\nu_{1}\cdots\nu_{j-2}\right|\\\
&\leq\left|\overline{\nu_{j-1}}\frac{f(p_{j})}{|f(p_{j})|}-\frac{f(p_{j-1})}{|f(p_{j-1})|}\right|+\left|\frac{f(p_{j-1})}{|f(p_{j-1})|}-\frac{f(p_{1})}{|f(p_{1})|}\nu_{1}\cdots\nu_{j-2}\right|\\\
&\leq\sum_{i=2}^{j}\left|\frac{f(p_{i})}{|f(p_{i})|}-\frac{f(p_{i-1})}{|f(p_{i-1})|}\nu_{i-1}\right|\end{split}$

where the third inequality follows by induction. Each summand in the last term
of the sum above satisfies

(32)
$\begin{split}&\left|\frac{f(p_{i})}{|f(p_{i})|}-\frac{f(p_{i-1})}{|f(p_{i-1})|}\nu_{i-1}\right|\\\
&=\left|\frac{1}{|f(p_{i})|}f(p_{i})-\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}\frac{f(p_{i-1})}{|f(p_{i-1})|}L_{i-1}(p_{i}-p_{i-1})\right|\\\
&\leq|f(p_{i})|\left|\frac{1}{|f(p_{i})|}-\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}\right|\\\
&+\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}\left|f(p_{i})-\frac{f(p_{i-1})}{|f(p_{i-1})|}L_{i-1}(p_{i}-p_{i-1})\right|\\\
&=|f(p_{i})|\left|\frac{|f(p_{i})|-|\frac{f(p_{i-1})}{|f(p_{i-1})|}L_{i-1}(p_{i}-p_{i-1})|}{|f(p_{i})||L_{i-1}(p_{i}-p_{i-1})|}\right|\\\
&+\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}\left|f(p_{i})-\frac{f(p_{i-1})}{|f(p_{i-1})|}L_{i-1}(p_{i}-p_{i-1})\right|\\\
&\leq\frac{2}{|L_{i-1}(p_{i}-p_{i-1})|}\left|f(p_{i})-\frac{f(p_{i-1})}{|f(p_{i-1})|}L_{i-1}(p_{i}-p_{i-1})\right|.\end{split}$

Combining the inequalties (30), (31) and (32) gives

$\begin{split}&\left|f(t)-\frac{f(p_{1})}{|f(p_{1})|}\mathcal{R}(t)\right|\leq\left|f(p_{j}+\omega)-\frac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)\right|\\\
&+2|L_{j}(\omega)|\sum_{i=2}^{j}\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}\left|f(p_{i})-\frac{f(p_{i-1})}{|f(p_{i-1})|}L_{i-1}(p_{i}-p_{i-1})\right|.\end{split}$

Observe that $p_{i}\in I_{i-1}$ and $f(p_{i})=f(p_{i-1}+(p_{i}-p_{i-1}))$.
Therefore, if we set

$Q\coloneqq\max_{1\leq j\leq
J-1}\|f(p_{j}+\cdot)-\tfrac{f(p_{j})}{|f(p_{j})|}L_{j}\|_{L^{\infty}(I_{j})}$

then

$\left|f(t)-\frac{f(p_{1})}{|f(p_{1})|}\mathcal{R}(t)\right|\leq
Q+2Q|L_{j}(\omega)|\sum_{i=2}^{j}\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}.$

Observing that

$|L_{j}(\omega)|\leq\left|f(p_{j}+\omega)-\frac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)\right|+|f(p_{j}+\omega)|\leq
Q+\|f\|_{L^{\infty}(I)},$

gives

(33) $\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}(I)}\leq
Q+2Q\left(\|f\|_{L^{\infty}(I)}+Q\right)\sum_{i=2}^{j}\frac{1}{|L_{i-1}(p_{i}-p_{i-1})|}.$

Step 2. Well-definedness of $c_{j}$. If the map $S_{j}$ is defined by

$S_{j}(\omega)=\sqrt{c_{j}}\overline{L_{j}(\omega)}=h\sum_{n}\sum_{k}\mathfrak{S}(n,k)e^{-2\pi
i\omega hk}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p_{j}+\omega),$

then $E_{j}(\omega)=|f_{\omega}(p_{j}+\omega)-S_{j}(\omega)|.$ Observe that
$c_{j}=S_{j}(0),f_{0}(p_{j})=|f(p_{j})|^{2}$ and

$c_{j}\geq|f(p_{j})|^{2}-||f(p_{j})|^{2}-c_{j}|\geq\gamma^{2}-|f_{0}(p_{j})-S_{j}(0)|=\gamma^{2}-E_{j}(0).$

By assumption we have $E_{j}(0)\leq\max_{1\leq j\leq
J-1}\|E_{j}\|_{L^{\infty}[0,p_{j+1}-p_{j}]}\leq\varepsilon\leq\frac{\gamma^{2}}{2}$
which gives

(34) $c_{j}\geq\frac{\gamma^{2}}{2}.$

In particular, the constants $c_{j}$ are well-defined.

Step 3: Upper bounding $E_{j}(\omega)$. We have shown that the constants
$c_{j}$ are well-defined. Recalling that if $f(p_{j})\neq 0$ then the identity
$\frac{1}{\overline{f(p_{j})}}\overline{f_{\omega}(p_{j}+\omega)}$ holds for
every $\omega\in{\mathbb{R}}$. We can continue with the following estimate:

(35)
$\begin{split}&|f(p_{j}+\omega)-\tfrac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)|=\left|\frac{1}{\overline{f(p_{j})}}\overline{f_{\omega}(p_{j}+\omega)}-\frac{f(p_{j})}{|f(p_{j})|}\frac{1}{\sqrt{c_{j}}}\overline{S_{j}(\omega)}\right|\\\
&=\left|\frac{1}{f(p_{j})}f_{\omega}(p_{j}+\omega)-\frac{|f(p_{j})|}{f(p_{j})}\frac{1}{\sqrt{c_{j}}}S_{j}(\omega)\right|\\\
&\leq\frac{1}{\sqrt{c_{j}}}|f_{\omega}(p_{j}+\omega)-S_{j}(\omega)|+\left|\frac{f(p_{j})}{|f(p_{j})|}\left(\frac{1}{f(p_{j})}-\frac{|f(p_{j})|}{f(p_{j})}\frac{1}{\sqrt{c_{j}}}\right)\right||f_{\omega}(p_{j}+\omega)|\\\
&=\frac{1}{\sqrt{c_{j}}}|f_{\omega}(p_{j}+\omega)-S_{j}(\omega)|+\left|\frac{1}{|f(p_{j})|}-\frac{1}{\sqrt{c_{j}}}\right||f_{\omega}(p_{j}+\omega)|\\\
&=\frac{1}{\sqrt{c_{j}}}|f_{\omega}(p_{j}+\omega)-S_{j}(\omega)|+\frac{|c_{j}-|f(p_{j})|^{2}|}{\sqrt{c_{j}}(\sqrt{c_{j}}+|f(p_{j})|)}|f(p_{j}+\omega)|\\\
&\leq\frac{1}{\sqrt{c_{j}}}|f_{\omega}(p_{j}+\omega)-S_{j}(\omega)|+\frac{\|f\|_{L^{\infty}(I)}}{\sqrt{c_{j}}(\sqrt{c_{j}}+|f(p_{j})|)}|f_{0}(p_{j})-S_{j}(0)|\\\
&=\frac{1}{\sqrt{c_{j}}}E_{j}(\omega)+\frac{\|f\|_{L^{\infty}(I)}}{\sqrt{c_{j}}(\sqrt{c_{j}}+|f(p_{j})|)}E_{j}(0).\end{split}$

Using the bound obtained in equation (34) together with the fact that
$|f(p_{j})|\geq\gamma$ yields

(36)
$|f(p_{j}+\omega)-\tfrac{f(p_{j})}{|f(p_{j})|}L_{j}(\omega)|\leq\frac{\sqrt{2}}{\gamma}E_{j}(\omega)+\frac{\|f\|_{L^{\infty}(I)}}{\gamma^{2}}E_{j}(0).$

Step 4: Well-definedness of the phases $\nu_{j}$. We use the upper bound on
$E_{j}$ to show that the phases $\nu_{j}$ are well-defined. First, observe
that

$|L_{j}(p_{j+1}-p_{j})|\geq|f(p_{j+1})|-|f(p_{j+1})-\tfrac{f(p_{j})}{|f(p_{j})|}L_{j}(p_{j+1}-p_{j})|.$

Since $E_{j}(\omega)\leq\max_{1\leq j\leq
J-1}\|E_{j}\|_{L^{\infty}[0,p_{j+1}-p_{j}]}\leq\varepsilon$ for every
$\omega\in[0,p_{j+1}-p_{j}]$ and since $\varepsilon$ satisfies the upper bound
$\varepsilon\leq\min\left\\{\frac{\gamma^{2}}{2\sqrt{8}},\frac{\gamma^{3}}{4\|f\|_{L^{\infty}(I)}}\right\\}$
it follows it follows from the upper bound obtained in (35) that
$|f(p_{j+1})-\tfrac{f(p_{j})}{|f(p_{j})|}L_{j}(p_{j+1}-p_{j})|\leq\frac{\gamma}{2}.$
In particular, this shows that

(37) $|L_{j}(p_{j+1}-p_{j})|\geq\frac{\gamma}{2}.$

Thus, the phases $\nu_{j}$ are well-defined for all $j$.

Step 5: Combining step 1-4.

If $Q$ is given as above then from inequality (36) we obtain

$Q\leq\frac{\sqrt{2}\max\\{1,\|f\|_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{2}\\}}\underbrace{\max_{j=1,\dots,J}\|E_{j}\|_{L^{\infty}}+E_{j}(0)}_{\coloneqq\Xi}$

Inequality (33) and the lower bound 37 implies that

$\begin{split}&\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}(I)}\leq\frac{\sqrt{2}\max\\{1,\|f\|_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{2}\\}}\Xi\\\
&+\frac{4\sqrt{2}(J-1)\max\\{\|f\|_{L^{\infty}(I)},\|f\|_{L^{\infty}(I)}^{2}\\}}{\gamma\min\\{\gamma,\gamma^{2}\\}}\Xi+\frac{8(J-1)\max\\{1,\|f\|_{L^{\infty}(I)}^{2}\\}}{\gamma\min\\{\gamma^{2},\gamma^{4}\\}}\Xi^{2}\\\
&\leq
8(J-1)\frac{\max\\{1,\|f\|_{L^{\infty}(I)},\|f\|_{L^{\infty}(I)}^{2}\\}}{\min\\{\gamma,\gamma^{2},\gamma^{4},\gamma^{5}\\}}(2\Xi+\Xi^{2})\end{split}$

In particular, the assumption on $\varepsilon$ and the fact that
$\min\\{\gamma,\gamma^{2},\gamma^{4},\gamma^{5}\\}=\min\\{\gamma,\gamma^{5}\\}$
and
$\max\\{1,\|f\|_{L^{\infty}(I)},\|f\|_{L^{\infty}(I)}^{2}\\}=\max\\{1,\|f\|_{L^{\infty}(I)}^{2}\\}$
gives

$\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}(I)}\leq
32(J-1)\frac{\max\\{1,\|f\|_{L^{\infty}(I)}^{2}\\}}{\min\\{\gamma^{1},\gamma^{5}\\}}(\varepsilon+\varepsilon^{2}).$

∎

###  4.2. Application to Gaussian shift-invariant spaces

Recall that the inner products $\langle
f_{\omega},T_{x}\varphi_{\omega}\rangle$ were given in terms of the Fourier
integral

(38) $\langle
f_{\omega},T_{x}\varphi_{\omega}\rangle=\int_{\mathbb{R}}|\mathcal{G}f(x,t)|^{2}e^{-2\pi
i\omega t}\,dt.$

To allow an approximation of functions in $f\in V_{\beta}^{\infty}(\varphi)$
from $|\mathcal{G}f(X)|$ where $X$ is a set of finitely many sampling points,
we discretize the above integral using a suitable quadrature formula. If
$\sigma$ is the standard deviation of the Gaussian $\varphi$ then we define
$\sigma^{\prime}\coloneqq\frac{1}{2\pi\sigma}$. The choice of a quadrature
formula is based on the following factorization formula of the spectrogram.

######  Theorem 4.3.

If $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$ then the spectrogram of $f$ factors as

(39)
$|\mathcal{G}f(x,t)|^{2}=\pi\sigma^{2}\varphi^{\sigma^{\prime}}(t)S_{x}(t)$

where $S_{x}(t)=\sum_{\ell}b_{\ell}(x)e^{\pi i\beta\ell t}$ is a trigonometric
series whose coefficients satisfy the Gaussian bound

$|b_{\ell}(x)|\leq\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}\sqrt{2\pi}\right)e^{-\frac{1}{8}(\frac{\beta\ell}{\sigma})^{2}}.$

In particular, for every $x\in{\mathbb{R}}$ the map
$z\mapsto|\mathcal{G}f(x,z)|^{2}$ extends from ${\mathbb{R}}$ to an entire
function on ${\mathbb{C}}$. The extension is given by the map ${\mathbb{C}}\ni
z\mapsto\pi\sigma^{2}\varphi^{\sigma^{\prime}}(z)S_{x}(z)$.

###### Proof.

See the Appendix D. ∎

Recall that for $h>0$ and $H\in{\mathbb{N}}\cup\\{\infty\\}$ the trapezoidal
rule approximation of a map $W:{\mathbb{R}}\to{\mathbb{C}}$ is defined by

(40) $I_{h}^{H}(W)\coloneqq h\sum_{k=-H}^{H}W(hk).$

Applying this quadrature rule to the Fourier integral (38) gives

(41) $I_{h}^{H}(t\mapsto|\mathcal{G}f(x,t)|^{2}e^{-2\pi i\omega
t})=h\sum_{k=-H}^{H}|\mathcal{G}f(x,hk)|^{2}e^{-2\pi i\omega hk},$

which essentially represents the discrete Fourier transform. We apply a
classical result on the exponentially convergent trapezoidal rule [34, Theorem
5.1].

######  Theorem 4.4 (Trefethen-Weideman).

Let $a>0$ and suppose that $W$ is an analytic map in the strip
$U_{a}=\\{z\in{\mathbb{C}}:|\mathrm{Im}(z)|<a\\}$. Suppose further that
$W(x)\to 0$ uniformly as $|x|\to\infty$ in the strip. If

$M(W)\coloneqq\sup_{t+iy\in U_{a}}\int_{-\infty}^{\infty}|W(t+iy)|\,dt<\infty$

then, for any $h>0$, the trapezoidal rule approximation $I_{h}^{\infty}(W)$ of
$\int_{\mathbb{R}}W$ exists and satisfies

$\left|I_{h}^{\infty}(W)-\int_{\mathbb{R}}W\right|\leq\frac{2M(W)}{e^{2\pi
a/h}-1}.$

The quantity $2M$ in the numerator is optimal.

Truncating the series which corresponds to the biorthogonal expansion of
$f_{\omega}$ and using the approximation (41) of the inner products given in
(38), results in the map

(42) $S(\omega)=h\sum_{n=-N}^{N}\sum_{k=-H}^{H}\mathfrak{S}(n,k)e^{-2\pi
i\omega hk}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega),\ \
N\in{\mathbb{N}},$

which is precisely the function $\sqrt{c_{j}}\overline{L_{j}}$ (with
$p=p_{j}$) appearing in the error term $E_{j}$ defined in equation (29). The
pointwise distance between the map $\omega\mapsto f_{\omega}(p+\omega)$ and
$S$ can be upper bounded as follows.

######  Lemma 4.5.

Assume that $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$. Suppose that
$N=\lceil\frac{2}{\beta}(s+\frac{r}{2})\rceil+m$ for some $m\in{\mathbb{N}}$
and some $r,s>0$. Let $h>0$ and $H\in{\mathbb{N}}$. Then for every
$p\in[-s,s]$ and every $\omega\in[0,r]$ we have the error bound

(43) $\begin{split}&|f_{\omega}(p+\omega)-S(\omega)|\\\ &\leq
4\sqrt{\pi}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}\frac{\sigma}{\nu\beta}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\|c\|_{\infty}^{2}e^{-\frac{\nu\beta}{2}m}\\\
&+2\sqrt{\pi}Ke^{\frac{\omega^{2}}{4\sigma^{2}}+\frac{|\omega|}{\sigma}+1}\sigma\left(2+\frac{4}{\nu\beta}\right)\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\|c\|_{\infty}^{2}\frac{1}{e^{\frac{1}{\sigma
h}}-1}\\\
&+\sqrt{\pi}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}\sigma\left(2+\frac{4}{\nu\beta}\right)\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\|c\|_{\infty}^{2}e^{-2(\pi
Hh\sigma)^{2}}\\\
&+\sqrt{2}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}\left(2+\frac{4}{\nu\beta}\right)h\|\eta\|_{\infty}\end{split}$

where $K=K(\sigma,\beta)$ and $\nu=\nu(\sigma,\beta)$ denote the decay
constants of the dual generator as defined in (27).

###### Proof.

See the Appendix E. ∎

Lemma 4.5 becomes meaningful if we interpret it in a qualitative way: recall
that the constants $K$ and $\nu$ depend only on $\sigma$ and $\beta$. Suppose
that $f$ satisfies condition (P) and that the variance $\sigma^{2}$ and the
step-size $\beta$ are fixed, i.e. both the window function and the underlying
signal space is fixed. Under these assumption, it follows from inequality (43)
and the definition of the error terms $E_{j}$ that

(44) $\max_{1\leq j\leq
J-1}\|E_{j}\|_{L^{\infty}[0,p_{j+1}-p_{j}]}\lesssim_{\sigma,\beta,r}\|c\|_{\infty}^{2}e^{-am}+\|c\|_{\infty}^{2}\frac{1}{e^{\frac{1}{\sigma
h}}-1}+\|c\|_{\infty}^{2}e^{-b(Hh)^{2}}+h\|\eta\|_{\infty}$

where $a$ and $b$ are constants depending only on $\sigma$ and $\beta$. The
constant $r$ is given by

(45) $r\coloneqq\max_{1\leq j\leq J-1}(p_{j+1}-p_{j}).$

Let the universal constant in inequality (44) be denoted by
$\mathcal{D}=\mathcal{D}(\sigma,\beta,r)$. Then the following approximation
result holds.

######  Theorem 4.6.

Assume that $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$ and satisfies condition (P) with
$p_{1}<\cdots<p_{J}\in{\mathbb{R}},-p_{1}=p_{J}=s$ and $\gamma>0$. Let
$r\coloneqq\max_{1\leq j\leq J-1}(p_{j+1}-p_{j})$ and let $\varepsilon$ be
chosen as in Theorem 4.2, i.e.
$0<\varepsilon\leq\min\left\\{\frac{\gamma^{2}}{2\sqrt{8}},\frac{\gamma^{3}}{4\|f\|_{L^{\infty}(I)}}\right\\}.$
Suppose that the sampling density $\frac{1}{h}$ in frequency direction
satisfies

$\frac{1}{h}\geq\sigma\log\left(\frac{4\mathcal{D}\|c\|_{\infty}^{2}(J-1)}{\varepsilon}+1\right)$

and the measurements are given on the grid

$X=\tfrac{\beta}{2}\\{-N,\dots,N\\}\times h\\{-H,\dots,H\\}$

such that the grid size characterizing parameters $N,H$ satisfy

$H\geq\frac{1}{h}\left(\frac{1}{b}\log\left(\frac{4\mathcal{D}\|c\|_{\infty}^{2}(J-1)}{\varepsilon}\right)\right)^{\frac{1}{2}}$

and

$N\geq\lceil\tfrac{2}{\beta}(s+\tfrac{r}{2})\rceil+\frac{1}{a}\log\left(\frac{4\mathcal{D}\|c\|_{\infty}^{2}(J-1)}{\varepsilon}\right).$

Then the following holds: if the noise level does not exceed
$\frac{\varepsilon}{4h(J-1)\mathcal{D}}$, i.e.
$\|\eta\|_{\infty}\leq\frac{\varepsilon}{4h(J-1)\mathcal{D}}$, then

(46) $\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}[-s,s]}\leq
32\frac{\max\\{1,\|f\|^{2}_{L^{\infty}(I)}\\}}{\min\\{\gamma,\gamma^{5}\\}}(\varepsilon+\varepsilon^{2})$

where $\mathcal{R}$ denotes the numerical approximation routine.

###### Proof.

Denote the four summands on the right-hand side of inequality (44) by
$\Xi_{1},\dots,\Xi_{4}$. It follows that if
$\mathcal{D}\Xi_{i}\leq\frac{\varepsilon}{4(J-1)}$ for $i=1,\dots,4$ then

$\max_{j=1,\dots,J-1}\|E_{j}\|_{L^{\infty}[0,p_{j+1}-p_{j}]}\leq\frac{\varepsilon}{J-1}.$

Elementary manipulations show that the condition
$\mathcal{D}\Xi_{i}\leq\frac{\varepsilon}{4(J-1)}$ for $i=1,\dots,4$ is
satisfied by the above assumptions on $h,H,N$ and $\|\eta\|_{\infty}$. The
statement is therefore a consequence of Theorem 4.2. ∎

Based on the previous statement we can study the growth of the number of
samples needed to achieve the bound (46) for an increasing length of the
reconstruction interval $I=[-s,s]$. Consider the noiseless case, $\eta=0$.
Suppose that condition (P) holds on the entire real-line, i.e. there exists a
partition

$P=\cdots<p_{-1}<p_{0}<p_{1}<\cdots,\ |f(p_{j})|\geq\gamma$

so that the maximal distance between two consecutive points $p_{j}$ and
$p_{j+1}$ remains upper bounded by $r$, i.e.
$\sup_{j\in{\mathbb{Z}}}(p_{j+1}-p_{j})\leq r.$ By going to a sub-partition we
can always assume that for an interval $[-s,s]$ there exists $p_{j},p_{k}\in
P$ with $p_{j}\leq-s,p_{k}\geq s$ and $k-j\leq\frac{4s}{r}+\mathcal{O}(1)$.
Therefore, the assumptions on the bounds on $h,H$ and $N$ as stated in Theorem
4.6 can be re-written as

$\frac{1}{h}\geq\sigma\log\left(\frac{\mathcal{D}^{\prime}\|c\|_{\infty}^{2}s}{\varepsilon}+1\right),H\geq\frac{1}{h}\left(\frac{1}{b}\log\left(\frac{\mathcal{D}^{\prime}\|c\|_{\infty}^{2}s}{\varepsilon}\right)\right)^{\frac{1}{2}},$
$N\geq\lceil\tfrac{2}{\beta}(s+\tfrac{r}{2})\rceil+\frac{1}{a}\log\left(\frac{\mathcal{D}^{\prime}\|c\|_{\infty}^{2}s}{\varepsilon}\right).$

where $\mathcal{D}^{\prime}$ is a constant depending only on $\sigma,\beta$
and $r$. A direct consequence is

######  Corollary 4.7.

Under the assumptions above, the following holds: in order to achieve a
reconstruction of $f\in V_{\beta}^{\infty}(\varphi)$ with defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$ on an interval $I=[-s,s]$ of length $2s$ up
an error bound of the form (46) using the numerical approximation routine
$\mathcal{R}$, the number $\mathcal{N}(s)$ of spectrogram samples satisfies
the upper growth estimate

$\mathcal{N}(s)\lesssim_{\sigma,\beta,r}\log\left(\frac{s\|c\|_{\infty}^{2}}{\varepsilon}\right)^{\frac{3}{2}}\left(s+\log\left(\frac{s\|c\|_{\infty}^{2}}{\varepsilon}\right)\right).$

Assumptions on $\sigma$ and $\beta$ turn the qualitative results above into
quantitative results by means of explicit upper bounds on $a,b$ and
$\mathcal{D}$. This can be done in a similar fashion as at the end of Section
3 and exploiting Lemma 3.11.

######  Proposition 4.8.

If $\frac{\beta}{4}\leq\sigma\leq\frac{\beta}{2}\leq 1$ and $r\leq 2\sigma$
then

$\mathcal{D}\leq
40000\left(2+\frac{16}{\beta}\right)\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2},\
\ a\geq\frac{\beta}{8},\ \ b\geq 2\pi^{2}\sigma^{2}.$

###### Proof.

This follows by applying the bounds on $K$ and $\nu$ derived in Lemma 3.11 to
each term on the right-hand side of inequality (43). ∎

###  4.3. Algorithm

In a natural way, the foregoing results lead to a reconstruction algorithm
whenever $f\in V_{\beta}^{\infty}(\varphi)$ satisfies condition (P). This is
an assumption on the signal itself which is unknown if only spectrogram
samples are accessible. However, we have shown that the map $f_{0}=|f|^{2}$
can be recovered in a globally stably way by means of a biorthogonal
expansion. Let the grid $X$ and the sampling set $\mathfrak{S}$ be given as
above and set

$F=F_{N,H}=h\sum_{n=-N}^{N}\sum_{k=-H}^{H}\mathfrak{S}(n,k)T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}.$

If $\eta=0$ then $F_{N,H}\to|f|^{2}$ uniformly on compact intervals. This
motivates the following 4-step approximation procedure.

Input:
$\mathfrak{S}=(|\mathcal{G}f(\tfrac{\beta}{2}n,hk)|^{2}+\eta_{n,k})_{n,k}\in{\mathbb{R}}^{(2N+1)\times(2H+1)}$,
$\tilde{r},\tilde{\gamma},s>0$;

Output: $\mathcal{R}:[-s,s]\to{\mathbb{C}}$

  1. (1)

Set
$F=h\sum_{n}\sum_{k}\mathfrak{S}(n,k)T_{\frac{\beta}{2}n}\widetilde{\varphi_{0}}$

  2. (2)

Find $p_{1}<\cdots<p_{J}\in I=[-s,s],J\geq 2$, such that $F(p_{j})\geq\gamma$,
$p_{j+1}-p_{j}\leq r$ and $p_{j+2}-p_{j}\geq r$ (if $J\geq 3$) for all
$j\in\\{1,\dots,J\\}$

  3. (3)

Define for $j\in\\{1,\dots,J\\}$ local reconstructive functions $L_{j}$ by

$L_{j}(\omega)=F(p_{j})^{-\frac{1}{2}}h\sum_{n=-N}^{N}\sum_{k=-H}^{H}\mathfrak{S}(n,k)e^{2\pi
i\omega hk}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p_{j}+\omega)$

and phases $\nu_{j}$ by

$\nu_{0}=1,\ \ \nu_{j}=\frac{L_{j}(p_{j+1}-p_{j})}{|L_{j}(p_{j+1}-p_{j})|}\
(j=2,\dots,J-1).$

  4. (4)

Set $\mathcal{R}(t)=\nu_{1}\cdots\nu_{j-1}L_{j}(\omega)$ if
$t\in(p_{j},p_{j+1}]$ with $t=p_{j}+\omega$ and $j=1,\dots,J-1$;
$\mathcal{R}(p_{1})=L_{1}(0)$ and $\mathcal{R}(t)=0$ otherwise

Algorithm 1 Reconstruction in $V_{\beta}^{\infty}(\varphi)$

Algorithm 1 approximates function in $V_{\beta}^{\infty}(\varphi)$ in a
provably stable way.

######  Theorem 4.9.

Suppose that $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$ and
$\|f\|_{L^{\infty}({\mathbb{R}})},\|c\|_{\ell^{\infty}({\mathbb{Z}})}\leq\mathcal{L}$.
Let $r,\gamma,s>0$ and

$0<\varepsilon\leq\min\left\\{\frac{\gamma^{2}}{2\sqrt{8}},\frac{\gamma^{3}}{4\mathcal{L}}\right\\}.$

Suppose that the samples are given on the grid $X$ with

$\frac{1}{h}\geq\sigma\log\left(\frac{16\mathcal{D}\mathcal{L}^{2}s}{\varepsilon
r}+1\right),\
H\geq\frac{1}{h}\left(\frac{1}{b}\log\left(\frac{16\mathcal{D}\mathcal{L}^{2}s}{\varepsilon
r}\right)\right)^{\frac{1}{2}},$
$N\geq\lceil\tfrac{2}{\beta}(s+\tfrac{r}{2})\rceil+\frac{1}{a}\log\left(\frac{16\mathcal{D}\mathcal{L}^{2}s}{\varepsilon
r}\right)$

and $\mathcal{D},a,b$ are defined as above. If the noise level satisfies
$\|\eta\|_{\infty}\leq\frac{\varepsilon r}{16h\mathcal{D}s}$ then the
following holds.

  1. (1)

Let $p_{1}<\cdots<p_{J}\in I$ be the points detected in Step 2 of Algorithm 1
with input parameters
$\tilde{r}=r,\tilde{\gamma}=\frac{3}{2}\gamma^{2},\tilde{s}=s$. Then
$p_{1}<\cdots<p_{J}$ satisfy condition (P) with constants $r$ and $\gamma$

  2. (2)

If $p_{1}<\cdots<p_{J}\in I$ are the points detected in Step 2 of Algorithm 1
with input parameters
$\tilde{r}=r,\tilde{\gamma}=\frac{3}{2}\gamma^{2},\tilde{s}=s$ and if
$\mathcal{R}$ is the output function of Algorithm 1 then

$\min_{\tau\in{\mathbb{T}}}\|f-\tau\mathcal{R}\|_{L^{\infty}[p_{1},p_{J}]}\leq
32\frac{\max\\{1,\mathcal{L}^{2}\\}}{\min\\{\gamma,\gamma^{5}\\}}(\varepsilon+\varepsilon^{2})$

###### Proof.

(1) If $p_{1}<\cdots<p_{J}\in I=[-s,s]$ are the points detected in Step 2 of
Algorithm 1 then the condition $p_{j+2}-p_{j}\geq r$ implies that
$\frac{4s}{r}+1\geq J$ and therefore $J-1\leq\frac{4s}{r}$. Let $p\in[-s,s]$,
let $S$ be defined as in equation (42) and let $F$ be the function defined in
Step 2 of Algorithm 1. Then $S(0)=F(p)$. Combining the inequalities (43) and
(44) with the assumptions on $h,H,N$ and arguing in an analogue fashion as in
the proof of Theorem 4.6 yields

$\begin{split}||f(p)|^{2}-F(p)|&=|f_{0}(p)-S(0)|\\\
&\leq\mathcal{D}\left(\|c\|_{\infty}^{2}e^{-am}+\|c\|_{\infty}^{2}\frac{1}{e^{\frac{1}{\sigma
h}}-1}+\|c\|_{\infty}^{2}e^{-b(Hh)^{2}}+h\|\eta\|_{\infty}\right)\\\
&\leq\frac{r\varepsilon}{4s}\leq\varepsilon\leq\frac{1}{2}\gamma^{2}.\end{split}$

Since $p$ was arbitrary, this estimate holds for every $p\in[-s,s]$. Let
$p_{j}\in I$ be one of the detected points. Then
$F(p_{j})\geq\tilde{\gamma}=\frac{3}{2}\gamma^{2}$ and therefore

$|f(p_{j})|^{2}\geq
F(p_{j})-|F(p_{j})-|f(p_{j})|^{2}|\geq\frac{3}{2}\gamma^{2}-\frac{1}{2}\gamma^{2}=\gamma^{2}.$

Since $j\in\\{1,\dots,J\\}$ was arbitrary and $J\geq 2$, we conclude from the
inequality above that the points $p_{1}<\cdots<p_{J}$ satisfy condition (P).

(2) According to Part 1, the points $p_{1}<\cdots<p_{J}$ satisfy condition
(P). The map $\mathcal{R}$ defined in Step 4 of Algorithm 1 is precisely the
numerical approximation routine as defined in Definition 4.1 restricted to
$[p_{1},p_{J}]$. Observing that
$J-1\leq\frac{4s}{r},[p_{1},p_{J}]\subset[-s,s]$ and
$\|f\|_{L^{\infty}({\mathbb{R}})},\|c\|_{\ell^{\infty}({\mathbb{Z}})}\leq\mathcal{L}$
and consulting Theorem 4.6 implies the assertion. ∎

Figure 5. Visualization of step 2 of Algorithm 1: plot of the absolute value
$|f|$ of a function $f\in V_{\beta}^{\infty}(\varphi)$ on the interval
$I=[-40,40]$. The black dots represent points $(p_{j},F(p_{j}))$ with
$p_{j+1}-p_{j}\leq r=2$ and $F(p_{j})\geq\gamma=0.5$.

######  Remark 4.10.

The partitioning step (Step 2) in Algorithm 1 can be executed as follows:
evaluate the function $F$ on a grid

$-s=t_{1}<\cdots t_{L}=s.$

Select all points $t_{i_{1}}<\cdots<t_{i_{M}}$ such that
$F(t_{i_{m}})\geq\gamma$ for all $m=1,\dots,M$. Remove those points
$t_{i_{m}}$ of $t_{i_{1}}<\cdots t_{i_{M}}$ which satisfy

$t_{i_{m+1}}-t_{i_{m-1}}\leq r$

and do this as long as there are no points to remove anymore. Call the
resulting points $u_{i_{1}}<\cdots<u_{i_{K}}$. Let $i_{k}$ be the first index
such that $u_{i_{k+1}}-u_{i_{k}}\leq r$ and $J\in{\mathbb{N}}$ the largest
value such that $u_{i_{k+\ell}}-u_{i_{k+\ell-1}}\leq r$ for all
$\ell=1,\dots,J$. Finally, set

$p_{\ell}=u_{i_{k+\ell-1}},\ \ell=1,\dots,J.$

Figure 6. Reconstruction of a complex-valued function $f\in
V_{\beta}^{\infty}(\varphi)$ with $\beta=1$ and generator $\varphi(t)=e^{-\pi
t^{2}}$ on the interval $[-40,40]$ using Algorithm 1 with $r=1.5,\gamma=1$.
The spectrogram samples are taken on a grid $X\subset{\mathbb{R}}^{2}$ of size
$161\times 151$,
$X=\tfrac{1}{2}\\{-80,\dots,80\\}\times\tfrac{1}{15}\\{-75,\dots,75\\}$. To
each spectrogram sample $|\mathcal{G}f(X)|^{2}$, Gaussian noise with mean zero
and standard deviation 0.001 is added, i.e. the measurement matrix
$\mathfrak{S}$ takes the form
$\mathfrak{S}=|\mathcal{G}f(X)|^{2}+\mathcal{N}(0,\sigma^{2}),\sigma=0.001$.
To visualize the approximation, we multiplied $\mathcal{R}$ with a global
phase (the phase of $f$ at $p_{1}$, where $p_{1}$ arises from step 2 of
Algorithm 1).

######  Remark 4.11.

Suppose for simplicity that $\beta,\gamma,r\approx 1$ and that the noise is
Gaussian of the form $\mathcal{N}(0,\sigma^{2})$. Empirical simulations
highlight that if the samples are taken on a grid which satisfies the
conditions of Theorem 4.9 then Algorithm 1 reconstructs functions in
$V_{\beta}^{\infty}(\varphi)$ with almost no visible error provided that the
noise level satisfies $\sigma\leq 0.01$. If the noise level exceeds $0.01$
then the algorithm usually terminates earlier since no point
$p\in{\mathbb{R}}$ with $|f(p)|\geq\gamma$ could be found.

Figure 7. Reconstruction of a complex-valued linear spline $f$ using Algorithm
1 with $\sigma=\beta=0.1,\gamma=0.2,r=0.3$ and no noise. The samples are taken
on the grid $\frac{\beta}{2}\\{-120,\dots,120\\}\times c\\{-150,\dots,150\\}$.
Since $f$ has support in $I=[-5,5]$ we choose $c=\frac{1}{2|I|}=\frac{1}{20}$.
To visualize the approximation, we multiplied $\mathcal{R}$ with a global
phase (the phase of $f$ at $p_{1}$, where $p_{1}$ arises from step 2 of
Algorithm 1).

###  4.4. Beyond $V_{\beta}^{\infty}(\varphi)$

Compactly supported signals. Algorithm 1 was designed for functions in shift-
invariant spaces with Gaussian generator. One could inquire about the
justification of applying Algorithm 1 to different signal classes such as
compactly supported maps. To give a meaningful answer to this question we
define for $a,h>0$ the map $\mathcal{P}_{\omega}:L^{4}[-a,a]\to
V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$ via

$\mathcal{P}_{\omega}(f)=h\sum_{n\in{\mathbb{Z}}}\sum_{j\in{\mathbb{Z}}}|\mathcal{G}f(\tfrac{\beta}{2}n,hj)|^{2}e^{2\pi
i\omega hj}T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}.$

This is essentially the local reconstructive function defined in Section 4.1
with (noiseless) samples given on the infinite lattice
$X=\frac{\beta}{2}{\mathbb{Z}}\times h{\mathbb{Z}}$.

######  Proposition 4.12.

Let $a,h>0$ such that $ah\leq\frac{1}{4}$. Then for every $f\in L^{4}[-a,a]$
and every $\omega\in{\mathbb{R}}$ the map $\mathcal{P}_{\omega}(f)$ is the
orthogonal projection of $f_{\omega}$ onto
$V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$.

###### Proof.

General frame theory implies that the orthogonal projection
$\mathcal{P}_{\omega}(g)$ of a map $g\in{L^{2}({\mathbb{R}})}$ onto
$V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$ is given by

$\mathcal{P}_{\omega}(g)=\sum_{n}\langle
g,T_{\frac{\beta}{2}n}\varphi_{\omega}\rangle
T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}.$

Since $f\in L^{4}[-a,a]$ we have $f_{\omega}\in L^{2}[-a,a]$. The identity
${\mathcal{F}}|\mathcal{G}f(x,\cdot)|^{2}(\omega)=\langle
f_{\omega},T_{x}\varphi_{\omega}\rangle$ implies that the Fourier transform of
$|\mathcal{G}f(x,\cdot)|^{2}$ vanishes outside of the interval $[-2a,2a]$.
Hence, the map $t\to|\mathcal{G}f(x,t)|^{2}$ is band-limited with bandwidth at
most $4a$. The assumption on $h$ implies that $h\leq\frac{1}{4a}$ and
Shannon’s sampling theorem [26, Theorem 6.13] yields

$|\mathcal{G}f(x,t)|^{2}=\sum_{j}|\mathcal{G}f(x,hj)|^{2}\mathrm{sinc}(\tfrac{1}{h}t-j),\
\ t\in{\mathbb{R}}.$

Setting $x=\frac{\beta}{2}n$ and applying the Fourier transform in the second
argument of the spectrogram results in

${\mathcal{F}}(|\mathcal{G}f(\tfrac{\beta}{2}n,\cdot)|^{2})(\omega)=\langle
f_{\omega},T_{\frac{\beta}{2}n}\varphi_{\omega}\rangle=h\sum_{j}|\mathcal{G}f(\tfrac{\beta}{2}n,hj)|^{2}e^{2\pi
i\omega hj}$

and this proves the statement. ∎

This result shows that if we run Algorithm 1 with a compactly supported
function rather than a function in $V_{\beta}^{\infty}(\varphi)$ then in each
step the algorithm approximates the projection of $f_{\omega}$ onto
$V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$. Heuristically, compactly
supported functions that can be well-approximated by a linear combination of
Gaussians and which satisfy condition (P) can be reconstructed with this
methodology. In Figure 7 we visualize the performance of Algorithm 1 assuming
that $f$ is a continuous function with compact support (but is not
differentiable).

Figure 8. Projection $P_{V}(\text{sinc})$ of a sinc function onto the shift-
invariant space $V=V_{\beta}^{2}(\varphi^{\sigma})$ with $\sigma=1$ and
$\beta=1,\frac{3}{2},2$.

Band-limited signals. Suppose now that $f$ has compact support in the
frequency domain, i.e. $f$ is a band-limited signal belonging to the Paley-
Wiener space

$PW_{a}^{2}({\mathbb{R}})=\\{f\in
L^{2}({\mathbb{R}}):{\mathrm{supp}}(\hat{f})\subseteq[-a/2,a/2]\\},\ a>0.$

Empirically, Algorithm 1 approximates $f\in PW_{a}^{2}({\mathbb{R}})$ from
noisy samples as soon as the standard deviation $\sigma$ of the Gaussian
window $\varphi$ lies below a constant depending on the bandwidth $a$ of $f$.
This follows from two observations. Firstly, $f$ is generated by a sinc
function (Shannon’s sampling theorem) and a sinc can be well-approximated by a
linear combination of equally spaced Gaussians with standard deviation
$\sigma\approx\frac{1}{a}$, see Figure 8 for a visualization. Secondly, if $f$
has bandwidth $a$ then $f_{\omega}$ has bandwidth $2a$ for every
$\omega\in{\mathbb{R}}$. Hence, $PW_{a}^{2}({\mathbb{R}})$ exhibits a similar
invariance of the tensor product operation as in the Gaussian shift-invariant
setting (Proposition 3.3). Since $\varphi_{\omega}$ is (up to a constant) a
Gaussian with standard deviation $\frac{\sigma}{\sqrt{2}}$ for every
$\omega\in{\mathbb{R}}$, we observe that under the assumption
$\sigma\approx\frac{1}{a}$ every $f_{\omega}$ can be well-approximated by
projecting $f_{\omega}$ onto the Gaussian shift-invariant space
$V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$. Clearly, general frame theory
shows that the projection of $f_{\omega}$ onto
$V_{\frac{\beta}{2}}^{2}(\varphi_{\omega})$ can be derived as soon as the
inner products $\langle f_{\omega},T_{x}\varphi_{\omega}\rangle$ are
available. Since

$\langle
f_{\omega},T_{x}\varphi_{\omega}\rangle=\int_{\mathbb{R}}|\mathcal{G}f(x,t)|^{2}e^{-2\pi
i\omega t}\,dt$

(Proposition 3.4), the inner products can be recovered up to a small error
using a suitable quadrature rule. In case of a band-limited signal $f\in
PW_{a}^{2}({\mathbb{R}})$ we further observe that

$|\mathcal{G}f(x,t)|=|{\mathcal{F}}(fT_{x}\varphi)(t)|\leq\left|\int_{\mathbb{R}}\hat{f}(t-s)\hat{\varphi}(s)\,ds\right|$
$\leq
a\|\hat{f}\|_{L^{2}[-\frac{a}{2},\frac{a}{2}]}\|\hat{\varphi}\|_{L^{\infty}[-\frac{a}{2}+t,\frac{a}{2}+t]}$

where we used the convolution theorem for the Fourier transform. Thus, the map
$t\mapsto|\mathcal{G}f(x,t)|$ satisfies a Gaussian decay as in Theorem 4.3.
Figure 9 depicts the output of Algorithm 1 for an input function $f\in
PW_{a}^{2}({\mathbb{R}})$ in a Gaussian noise regime.

Figure 9. Reconstructing a piece of a band-limited signal using Algorithm 1
with $\beta=0.5,r=1,\gamma=0.05$ and a Gaussian window with standard deviation
$\frac{1}{4}$. The spectrogram samples are taken on the grid
$X=0.04\\{50,\dots,50\\}\times\frac{\beta}{2}\\{-120,\dots,120\\}$. To each
spectrogram sample Gaussian noise $\mathcal{N}(0,\sigma^{2})$ is added with
$\sigma=0.0001$. To visualize the approximation, we multiplied $\mathcal{R}$
with a global phase (the phase of $f$ at $p_{1}$, where $p_{1}$ arises from
step 2 of Algorithm 1).

The foregoing discussion highlights that a combination of approximation
properties of Gaussian shift-invariant spaces, numerical integration theory
and the abstract theory presented in Section 4.1 point towards new
approximation results from phaseless samples for function spaces beyond
$V_{\beta}^{\infty}(\varphi)$. We leave this research direction open for
future work.

## Appendix

### A. Proof of Theorem 2.3

###### Proof.

The fact that $\theta$ is an element of $V_{\beta}^{2}(\phi)$ follows from
[10, Lemma 9.3.2]. If $S$ is the frame operator of $(T_{\beta n}\phi)_{n}$
then

${\mathcal{F}}S\theta=\left(\sum_{k\in{\mathbb{Z}}}\langle\hat{\theta},M_{-k\beta}\hat{\phi}\rangle
M_{-k\beta}\right)\hat{\phi}.$

The inner products $\langle\hat{\theta},M_{-k\beta}\hat{\phi}\rangle$ can be
written as

$\begin{split}\langle\hat{\theta},M_{-k\beta}\hat{\phi}\rangle&=\int_{\mathbb{R}}\hat{\theta}(t)\overline{\hat{\phi}(t)}e^{2\pi
ik\beta
t}\,dt=\sum_{n\in{\mathbb{Z}}}\int_{0}^{1/\beta}\hat{\theta}(t+\tfrac{n}{\beta})\overline{\hat{\phi}(t+\tfrac{n}{\beta})}e^{2\pi
ik\beta t}\,dt\\\
&=\int_{0}^{1/\beta}\sum_{n\in{\mathbb{Z}}}\frac{\hat{\phi}(t+\frac{n}{\beta})}{\Psi_{\beta}(t+\frac{n}{\beta})}\overline{\hat{\phi}(t+\tfrac{n}{\beta})}{\bm{1}}_{D\cap[0,\frac{1}{\beta}]}(t)e^{2\pi
ik\beta t}\,dt\\\
&=\int_{0}^{1/\beta}{\bm{1}}_{D\cap[0,\frac{1}{\beta}]}(t)e^{2\pi ik\beta
t}\,dt=\frac{1}{\beta}\widehat{{\bm{1}}_{D\cap[0,\frac{1}{\beta}]}}(k)\end{split}$

where $\widehat{{\bm{1}}_{D\cap[0,\frac{1}{\beta}]}}(k)$ is the $k$-th Fourier
coefficient of ${\bm{1}}_{D\cap[0,\frac{1}{\beta}]}$. By periodicity we have

$\sum_{k}\langle\hat{\theta},M_{-k\beta}\hat{\phi}\rangle
M_{-k\beta}={\bm{1}}_{D}.$

If $\hat{\phi}(t)\neq 0$ then $\Psi_{\beta}(t)\neq 0$ and therefore we have
${\bm{1}}_{D}\hat{\phi}=\hat{\phi}$ which implies that
${\mathcal{F}}S\theta=\frac{1}{\beta}\hat{\phi}$. ∎

### B. Proof of Proposition 2.5

###### Proof.

Suppose that $f\in V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c=(c_{n})_{n}\in\ell^{\infty}({\mathbb{Z}}),f(t)=\sum_{n}c_{n}T_{\beta
n}\varphi(t)$. Let $I\subset{\mathbb{R}}$ be a compact interval such that
$I\subset[-s,s],s>0$. Let $\varepsilon>0$. Define for $M\in{\mathbb{N}}$ the
map $g_{M}$ by $g_{M}\coloneqq\sum_{m=-M}^{M}c_{m}T_{\beta m}\varphi$. Observe
that the dual generator $\tilde{\varphi}$ converges to zero exponentially and
since $c\in\ell^{\infty}({\mathbb{Z}})$ there exist a $C>0$ such that

$\left|\langle g_{M},T_{\beta k}\varphi\rangle\right|\leq C$

for every $M\in{\mathbb{N}}$ and every $k\in{\mathbb{Z}}$. It follows that
there exists an $L=L(s)\in{\mathbb{N}}$ such that

$\left|\sum_{\begin{subarray}{c}k\in{\mathbb{Z}}\\\
k\notin\\{-L,\dots,L\\}\end{subarray}}\langle g_{M},T_{\beta k}\rangle
T_{\beta k}\tilde{\varphi}(t)\right|\leq\varepsilon$

for every $t\in[-s,s]$ and every $M\in{\mathbb{N}}$. Now choose $M$ so that

$\left|\sum_{\begin{subarray}{c}m\in{\mathbb{Z}}\\\
m\notin\\{-M,\dots,M\\}\end{subarray}}c_{m}T_{\beta
m}\varphi(t)\right|\leq\varepsilon$

for every $t\in[-s,s]$. Since $g_{M}\in V_{\beta}^{2}(\varphi)$ we have the
estimate

$\begin{split}\left|f(t)-\sum_{n=-L}^{L}\langle f,T_{\beta n}\varphi\rangle
T_{\beta
n}\tilde{\varphi}(t)\right|&\leq\varepsilon+\left|g_{M}(t)+\sum_{n=-L}^{L}\langle
f,T_{\beta n}\varphi\rangle T_{\beta n}\tilde{\varphi}(t)\right|\\\ &\leq
2\varepsilon+\left|\sum_{n=-L}^{L}\langle g_{M}-f,T_{\beta n}\varphi\rangle
T_{\beta n}\tilde{\varphi}(t)\right|.\end{split}$

By dominated convergence, the right-hand side converges to $2\varepsilon$ as
$M\to\infty$ uniformly in $t\in[-s,s]$. ∎

### C. Proof of Lemma 3.11

###### Proof.

Step 1: Upper bounding $|{\mathcal{F}^{-1}}\Lambda|$. Let
$c=\varphi(\frac{\beta}{2})=e^{-\frac{\beta^{2}}{8\sigma^{2}}}$ and let

$\begin{split}a_{n}&=(-1)^{n}\frac{2}{\xi}\sum_{m=0}^{\infty}(-1)^{m}c^{(m+\frac{1}{2})(2|n|+m+\frac{1}{2})},\\\
\xi&=\xi(c)=\sum_{n\in\mathbb{Z}}(-1)^{n}(2n+1)c^{(n+\frac{1}{2})^{2}}\end{split}$

be the Fourier coefficients of the reciprocal theta function as given in
equation (15) and (16). Then

${\mathcal{F}^{-1}}\Lambda(t)=\sum_{n\in{\mathbb{Z}}}a_{n}T_{\frac{\beta}{2}n}{\mathcal{F}^{-1}}(s\mapsto
e^{-\pi^{2}\sigma^{2}s^{2}})(t)=\frac{1}{\sigma\sqrt{\pi}}\sum_{n\in{\mathbb{Z}}}a_{n}e^{-\frac{(t+\frac{\beta}{2}n)^{2}}{\sigma^{2}}}.$

The modulus of the coefficients $|a_{n}|$ is upper bounded by

$\begin{split}|a_{n}|&\leq\frac{2}{|\xi|}c^{|n|}\sum_{m=0}^{\infty}c^{(m+\frac{1}{2})^{2}}\leq\frac{2}{|\xi|}c^{|n|}\left(c^{\frac{1}{4}}+\int_{0}^{\infty}c^{(s+\frac{1}{2})^{2}}\,ds\right)\\\
&\leq\frac{2}{|\xi|}c^{|n|}\left(c^{\frac{1}{4}}+\int_{0}^{\infty}c^{s^{2}}\,ds\right)=\frac{2}{|\xi|}c^{|n|}\left(c^{\frac{1}{4}}+\frac{\sigma}{\beta}\sqrt{2\pi}\right).\end{split}$

It follows that

$|{\mathcal{F}^{-1}}\Lambda(t)|\leq\frac{2(c^{\frac{1}{4}}+\frac{\sigma}{\beta}\sqrt{2\pi})}{\sqrt{\pi}\sigma|\xi|}\sum_{n\in{\mathbb{Z}}}c^{|n|}e^{-\frac{(t+\frac{\beta}{2}n)^{2}}{\sigma^{2}}}$

where the right-hand side is even in $t$. In addition, the series on the right
of the previous inequality satisfies

$\sum_{n\in{\mathbb{Z}}}c^{|n|}e^{-\frac{(t+\frac{\beta}{2}n)^{2}}{\sigma^{2}}}=\sum_{n\in{\mathbb{Z}}}c^{|n|}e^{-\frac{(|t|-\frac{\beta}{2}n)^{2}}{\sigma^{2}}}\leq\underbrace{\sum_{n=\lceil\frac{1}{\beta}|t|\rceil}^{\infty}c^{|n|}}_{\coloneqq
A(t)}+\underbrace{\sum_{n=-\infty}^{\lfloor\frac{1}{\beta}|t|\rfloor}e^{-\frac{(\frac{\beta}{2}n-|t|)^{2}}{\sigma^{2}}}}_{\coloneqq
B(t)}.$

If $t\neq 0$ then the term $A(t)$ can be upper bounded via

$A(t)\leq\int_{\lceil\frac{1}{2}|t|\rceil-1}^{\infty}c^{s}\,ds=\frac{8\sigma^{2}}{\beta^{2}}e^{\frac{\beta^{2}}{8\sigma^{2}}}e^{-\frac{\beta^{2}}{16\sigma^{2}}|t|}\leq
2e^{2}e^{-\frac{1}{4}|t|}$

where in the rightmost inequality we used the assumption that
$\frac{\beta}{4}\leq\sigma\leq\frac{\beta}{2}\leq 1$. By making use of the
elementary bound $e^{-bt^{2}}\leq e^{\frac{b}{4}}e^{-b|t|}$
($t,b\in{\mathbb{R}}$) and the condition on $\sigma$ and $\beta$ we deduce the
chain of inequalities

$\begin{split}B(t)&\leq\sum_{n=-\infty}^{\lfloor\frac{1}{\beta}|t|\rfloor-1}e^{-\frac{(\frac{\beta}{2}n-|t|)^{2}}{\sigma^{2}}}+e^{-\frac{(\frac{\beta}{2}\lfloor\frac{1}{\beta}|t|\rfloor-|t|)^{2}}{\sigma^{2}}}\leq\int_{-\infty}^{\lfloor\frac{1}{\beta}|t|\rfloor}e^{-\frac{(\frac{\beta}{2}s-|t|)^{2}}{\sigma^{2}}}+e^{-\frac{t^{2}}{4\sigma^{2}}}\\\
&\leq\int_{0}^{\infty}e^{-\frac{(\frac{\beta}{2}s+\frac{1}{2}|t|)^{2}}{\sigma^{2}}}+e^{\frac{1}{16}}e^{-\frac{1}{4}|t|}\leq\int_{0}^{\infty}e^{-\frac{1}{4}t^{2}}e^{-|t|s}e^{-s^{2}}\,ds+e^{\frac{1}{16}}e^{-\frac{1}{4}|t|}\\\
&\leq
e^{\frac{1}{16}}e^{-\frac{1}{4}|t|}\int_{0}^{\infty}e^{-s^{2}}\,ds+e^{\frac{1}{16}}e^{-\frac{1}{4}|t|}=\left(\frac{\sqrt{\pi}}{2}+1\right)e^{\frac{1}{16}}e^{-\frac{1}{4}|t|}.\end{split}$

Consequently, $|{\mathcal{F}^{-1}}\Lambda|$ satisfies the pointwise
exponential bound

$|{\mathcal{F}^{-1}}\Lambda(t)|\leq\underbrace{\frac{2(c^{\frac{1}{4}}+\frac{\sigma}{\beta}\sqrt{2\pi})}{\sqrt{\pi}}\left(2e^{2}+\left(\frac{\sqrt{\pi}}{2}+1\right)e^{\frac{1}{16}}\right)}_{\coloneqq\Xi}\frac{1}{\sigma|\xi|}e^{-\frac{1}{4}|t|}.$

If $\frac{\beta}{4}\leq\sigma\leq\frac{\beta}{2}\leq 1$ then $e^{-2}\leq
c=\varphi(\frac{\beta}{2})\leq e^{-\frac{1}{2}}$ and
$\frac{\sigma}{\beta}\leq\frac{1}{2}$. Evaluating $\Xi$ results in the upper
bound $\Xi\leq 41$.

Step 2: Lower bounding $\xi(c)$. For every $0<c<1$ we have

$\xi(c)=2\left(\sum_{n=0}^{\infty}(4n+1)c^{\left(\frac{4n+1}{2}\right)^{2}}-\sum_{n=1}^{\infty}(4n-1)c^{\left(\frac{4n-1}{2}\right)^{2}}\right).$

Let $c\in J\coloneqq[e^{-2},e^{-\frac{1}{2}}]$ and define
$f:{\mathbb{N}}\times J\to{\mathbb{R}}$ by

$f(n,c)=(4n-1)c^{\left(\frac{4n-1}{2}\right)^{2}}.$

The map $f$ has the property that $n\mapsto f(n,c)$ is decreasing for every
$c\in J$ and $c\mapsto f(n,c)$ is increasing for every $n\in{\mathbb{N}}$.
Thus,

$\sum_{n=3}^{\infty}f(n,c)\leq\sum_{n=3}^{\infty}f(n,e^{-\frac{1}{2}})\leq\int_{2}^{\infty}f(t,e^{-\frac{1}{2}})\,dt=e^{-\frac{49}{8}}.$

It follows that for $c\in J$ we have

(47) $\begin{split}\xi(c)&\geq
2\left(\sum_{n=0}^{2}(4n+1)c^{\left(\frac{4n+1}{2}\right)^{2}}-f(1,c)-f(2,c)-\sum_{n=3}^{\infty}f(n,c)\right)\\\
&\geq
2\left(\sum_{n=0}^{2}(4n+1)c^{\left(\frac{4n+1}{2}\right)^{2}}-f(1,c)-f(2,c)-e^{-\frac{49}{8}}\right)\\\
&=-2e^{-\frac{49}{8}}+2x-6x^{9}+10x^{25}-14x^{49}+18x^{81}\eqqcolon
p(x)\end{split}$

with $x=c^{\frac{1}{4}}$. For every
$x\in[(e^{-2})^{\frac{1}{4}},(e^{-\frac{1}{2}})^{\frac{1}{4}}]$ the polynomial
$p$ satisfies the lower bound $p(x)\geq\frac{1}{5}$. It follows that
$\xi(c)\geq\frac{1}{5}$ for every $c\in J$.

Step 3: Combining Step 1 and Step 2. The upper bound $\Xi\leq 41$ and the
lower bound $\xi(c)\geq\frac{1}{5}$ for $c\in J$ implies that

(48)
$|{\mathcal{F}^{-1}}\Lambda(t)|\leq\frac{205}{\sigma}e^{-\frac{1}{4}|t|}.$

Inequality (48) was derived under the condition that $t\neq 0$. By continuity
it also holds for $t=0$. This concludes the proof of the Lemma. ∎

### D. Proof of Theorem 4.3

###### Proof.

Combining the identity $\mathcal{G}f(x,t)=\sum_{k}c_{k}e^{-2\pi i\beta
kt}\mathcal{G}\varphi(x-\beta k,t)$ with the identity

$\mathcal{G}\varphi(x,t)=\sigma\sqrt{\pi}e^{-\frac{x^{2}}{4\sigma^{2}}}e^{-\pi
ixt}e^{-\pi^{2}\sigma^{2}t^{2}}$

yields

$|\mathcal{G}f(x,t)|^{2}=\sum_{k}\sum_{j}\pi\sigma^{2}c_{k}\overline{c_{j}}e^{2\pi
it(\tfrac{\beta}{2}(j-k))}e^{-2\pi^{2}\sigma^{2}t^{2}}e^{-\frac{(x-\beta
k)^{2}}{4\sigma^{2}}}e^{-\frac{(x-\beta j)^{2}}{4\sigma^{2}}}.$

The relation

$e^{-\frac{(x-\beta k)^{2}}{4\sigma^{2}}}e^{-\frac{(x-\beta
j)^{2}}{4\sigma^{2}}}=e^{-\frac{(x-\frac{\beta}{2}(k+j))^{2}}{2\sigma^{2}}}e^{-\frac{\beta^{2}(k-j)^{2}}{8\sigma^{2}}}$

shows that

$|\mathcal{G}f(x,t)|^{2}=\pi\sigma^{2}\sum_{k}\sum_{j}c_{k}\overline{c_{j}}a(\sigma,\beta,k,j)M_{\frac{\beta}{2}(j-k)}\varphi^{\sigma^{\prime}}(t)T_{\frac{\beta}{2}(k+j)}\varphi^{\sigma}(x)$

where $a(\sigma,\beta,k,j)\coloneqq
e^{-\frac{\beta^{2}(k-j)^{2}}{8\sigma^{2}}}$. The product formula (39) follows
at once if we set

$b_{\ell}(x)=\sum_{j,k\in{\mathbb{Z}},j-k=\ell}c_{k}\overline{c_{j}}e^{-\frac{\beta^{2}\ell^{2}}{8\sigma^{2}}}T_{\frac{\beta}{2}(k+j)}\varphi^{\sigma}(x)$

For every $\ell\in{\mathbb{Z}}$ and every $x\in{\mathbb{R}}$ we have the
estimate

$\begin{split}|b_{\ell}(x)|&\leq\|c\|_{\infty}^{2}e^{-\frac{\beta^{2}\ell^{2}}{8\sigma^{2}}}\sum_{j}T_{\frac{\beta}{2}(2j-\ell)}\varphi^{\sigma}(x)=\|c\|_{\infty}^{2}e^{-\frac{\beta^{2}\ell^{2}}{8\sigma^{2}}}\sum_{j}T_{\beta
j}\varphi^{\sigma}(x+\tfrac{\beta}{2}\ell)\\\
&\leq\|c\|_{\infty}^{2}e^{-\frac{\beta^{2}\ell^{2}}{8\sigma^{2}}}\sum_{j}T_{\beta
j}\varphi^{\sigma}(0)\leq\|c\|_{\infty}^{2}e^{-\frac{\beta^{2}\ell^{2}}{8\sigma^{2}}}\left(1+\frac{1}{\beta}\int_{\mathbb{R}}\varphi^{\sigma}(t)\,dt\right)\\\
&=\|c\|_{\infty}^{2}e^{-\frac{\beta^{2}\ell^{2}}{8\sigma^{2}}}\left(1+\frac{\sigma}{\beta}\sqrt{2\pi}\right)\end{split}$

where we used (similar to the proof of Corollary 3.7) that for real $x$ the
theta function $x\mapsto\vartheta(x,c)$ is maximal at integers
$\pi{\mathbb{Z}}$ [27, p. 178]. In view of this Gaussian bound, the
trigonometric series $S_{x}(z)$ is well-defined for $z\in{\mathbb{C}}$ and
converges uniformly on compact subsets of ${\mathbb{C}}$. Hence,
$z\mapsto|\mathcal{G}f(x,z)|^{2}$ extends from ${\mathbb{R}}$ to an entire
function on ${\mathbb{C}}$. ∎

### E. Proof of Lemma 4.5

###### Proof.

Step 1: Numerical integration over ${\mathbb{R}}$. Suppose that $f\in
V_{\beta}^{\infty}(\varphi)$ has defining sequence
$c\in\ell^{\infty}({\mathbb{Z}})$. Let $S_{x}(t)$ be the trigonometric series
as given in Theorem 4.3 so that

$|\mathcal{G}f(x,t)|^{2}=\pi\sigma^{2}\varphi^{\sigma^{\prime}}(t)S_{x}(t).$

For $t,y,x,\omega\in{\mathbb{R}}$ let $W$ be defined by

$W(t+iy)\coloneqq|\mathcal{G}f(x,t+iy)|^{2}e^{-2\pi i\omega(t+iy)}.$

Further, let $A\coloneqq
S_{x}(t+iy),B\coloneqq\varphi^{\sigma^{\prime}}(t+iy)$ and $C\coloneqq
e^{-2\pi i\omega(t+iy)}$. Then

$W(t+iy)=\pi\sigma^{2}ABC.$

We bound the modulus of $A,B$ and $C$ separately. Using the bound on
$|b_{\ell}(x)|$ as given in Theorem 4.3 we obtain

$\begin{split}|A|&=\left|\sum_{\ell}b_{\ell}(x)e^{\pi
i\beta\ell(t+iy)}\right|\leq\sum_{\ell}|b_{\ell}(x)|e^{-\pi\beta\ell y}\\\
&\leq\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}\sqrt{2\pi}\right)\sum_{\ell}e^{-\frac{1}{8}(\frac{\beta\ell}{\sigma})^{2}}e^{-\pi\beta\ell
y}\\\
&=\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}\sqrt{2\pi}\right)e^{2\sigma^{2}\pi^{2}y^{2}}\sum_{\ell}e^{-\frac{\beta^{2}}{8\sigma^{2}}\left(\ell+\frac{4\sigma^{2}y\pi}{\beta}\right)^{2}}\\\
&\leq\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}\sqrt{2\pi}\right)e^{2\sigma^{2}\pi^{2}y^{2}}\sum_{\ell}e^{-\frac{\beta^{2}}{8\sigma^{2}}\ell^{2}}\\\
&\leq\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}\sqrt{2\pi}\right)e^{2\sigma^{2}\pi^{2}y^{2}}\left(1+\frac{1}{\beta}\int_{\mathbb{R}}e^{-\frac{s^{2}}{8\sigma^{2}}}\,ds\right)\\\
&\leq\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}e^{2\sigma^{2}\pi^{2}y^{2}}\end{split}$

In addition, we have
$|B|=\varphi^{\sigma^{\prime}}(t)e^{\frac{y^{2}}{2(\sigma^{\prime})^{2}}}$ and
$|C|=e^{2\pi\omega y}$. It follows that

$|W(t+iy)|\leq\pi\sigma^{2}\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}e^{2\sigma^{2}\pi^{2}y^{2}}e^{\frac{y^{2}}{2(\sigma^{\prime})^{2}}}e^{2\pi\omega
y}\varphi^{\sigma^{\prime}}(t).$

Consider the strip $U=U_{a}=\\{z\in{\mathbb{C}}:|\mathrm{Im}(z)|<a\\}$ with
$a=\sigma^{\prime}=\frac{1}{2\pi\sigma}$ being the conjugate standard
deviation. It follows from the previous estimates that $W(z)\to 0$ uniformly
as $|z|\to\infty$ in the strip $U$ and by Theorem 4.3 the map $W$ is analytic
in $U$. Integration over the Gaussian $\varphi^{\sigma^{\prime}}$ shows
further that for every $t,y\in{\mathbb{R}}$

$\int_{\mathbb{R}}|W(t+iy)|\,dt\leq\sqrt{\frac{\pi}{2}}\sigma\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}e^{2\sigma^{2}\pi^{2}y^{2}}e^{\frac{y^{2}}{2(\sigma^{\prime})^{2}}}e^{2\pi\omega
y}.$

From this we see that inside the strip $U$ the estimate

$\sup_{t+iy\in
U}\int_{\mathbb{R}}|W(t+iy)|\,dt\leq\sqrt{\frac{\pi}{2}}\sigma\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}e^{\frac{|\omega|}{\sigma}+1}$

holds and the theorem of Trefethen and Weidemann, Theorem 4.4, implies that

$\left|I_{h}^{\infty}(W)-\int_{\mathbb{R}}W\right|\leq\sqrt{2\pi}\sigma\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}e^{\frac{|\omega|}{\sigma}+1}\left(\frac{1}{e^{\frac{1}{\sigma
h}}-1}\right).$

Step 2: Estimating the cut-off error. For the integrand $W$ as defined above
and an $H\in{\mathbb{N}}$ we estimate the cut-off error
$|I_{h}^{\infty}(W)-I_{h}^{H}(W)|$. For every $\omega\in{\mathbb{R}}$ we have

$\begin{split}|I_{h}^{\infty}(W)-I_{h}^{H}(W)|&\leq
2h\pi\sigma^{2}\sum_{\ell}|b_{\ell}(x)|\sum_{k=H+1}^{\infty}\varphi^{\sigma^{\prime}}(hk)\\\
&\leq
2h\pi\sigma^{2}\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\sum_{k=H+1}\varphi^{\sigma^{\prime}}(hk)\\\
&\leq
2\pi\sigma^{2}\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\int_{Hh}^{\infty}e^{-2(\pi\sigma
t)^{2}}\,dt.\end{split}$

Using a classical Gaussian tail bound of the form

$\int_{q}^{\infty}e^{-pt^{2}}\,dt\leq\sqrt{\frac{\pi}{4p}}e^{-pq^{2}},\ \ \
p,q>0$

with $p=2\pi^{2}\sigma^{2}$ and $q=Hh$ results in

$|I_{h}^{\infty}(W)-I_{h}^{H}(W)|\leq\sqrt{\frac{\pi}{2}}\sigma\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}e^{-2(\pi\sigma
Hh)^{2}}.$

and the triangle inequality implies that

$\left|\int_{\mathbb{R}}W-I_{h}^{H}(W)\right|\leq\sqrt{\frac{\pi}{2}}\sigma\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\|c\|_{\infty}^{2}\left(\frac{2e^{\frac{|\omega|}{\sigma}+1}}{e^{\frac{1}{\sigma
h}}-1}+e^{-2(\pi Hh\sigma)^{2}}\right).$

Step 3. Estimating the distance $|f_{\omega}(p+\omega)-S(\omega)|$. Define for
$H,N\in{\mathbb{N}},h>0$ and $\omega\in{\mathbb{R}}$ the values $f(n,\omega)$
and $g(n,\omega)$ via

$f(n,\omega)\coloneqq\int_{\mathbb{R}}|\mathcal{G}f(\tfrac{\beta}{2}n,t)|^{2}e^{-2\pi
i\omega t}\,dt$

and

$g(n,\omega)\coloneqq h\sum_{k=-H}^{H}\mathfrak{S}(n,k)e^{2\pi i\omega hk}.$

Using the biorthogonal expansion of $f_{\omega}$ and invoking the definition
of the sampling set $\mathfrak{S}$ gives the upper bound

$\begin{split}&|f_{\omega}(p+\omega)-S(\omega)|\\\
&\leq\underbrace{\left|\sum_{n\in([-N,N]\cap{\mathbb{Z}})^{c}}f(n,\omega)T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)\right|}_{\coloneqq\varepsilon_{1}}+\underbrace{\left|\sum_{n=-N}^{N}(f(n,\omega)-\overline{g(n,\omega)})T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)\right|}_{\coloneqq\varepsilon_{2}}.\end{split}$

If $K$ and $\nu$ are the decay constants as given above then

$\begin{split}\varepsilon_{1}&\leq\sum_{n\in([-N,N]\cap{\mathbb{Z}})^{c}}|f(n,0)||T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)|\\\
&\leq\sqrt{\frac{\pi}{2}}\sigma\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}\|c\|_{\infty}^{2}\sqrt{2}e^{\frac{\omega^{2}}{4\sigma^{2}}}K\sum_{n\in([-N,N]\cap{\mathbb{Z}})^{c}}e^{-\nu|p+\frac{\omega}{2}-\frac{\beta}{2}n|}.\end{split}$

Since $N=\lceil\frac{2}{\beta}(s+\frac{r}{2})\rceil+m$ for some
$m\in{\mathbb{N}}$, $p\in[-s,s]$ and $|\omega|\leq r$ it follows that for
every $n\in([-N,N]\cap{\mathbb{Z}})^{c}$

$\left|p+\frac{\omega}{2}-\frac{\beta}{2}n\right|\geq\frac{\beta}{2}\left(\lceil\tfrac{2}{\beta}(s+\tfrac{r}{2})\rceil+m\right)-s-\frac{r}{2}\geq\frac{\beta}{2}m$

which implies that

$\sum_{n\in([-N,N]\cap{\mathbb{Z}})^{c}}e^{-\nu|a+\frac{\omega}{2}-\frac{\beta}{2}n|}\leq
2\sum_{n=m+1}^{\infty}e^{-\frac{\nu\beta}{2}n}\leq
2\int_{m}^{\infty}e^{-\frac{\nu\beta}{2}t}\,dt=\frac{4}{\nu\beta}e^{-\frac{\nu\beta}{2}m}.$

Thus,

$\varepsilon_{1}\leq\frac{4\sqrt{\pi}\sigma}{\nu\beta}\|c\|_{\infty}^{2}\left(1+\frac{\sigma}{\beta}2\sqrt{2\pi}\right)^{2}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}e^{-\frac{\nu\beta}{2}m}.$

Now let $\mathcal{E}\coloneqq\left|\int_{\mathbb{R}}W-I_{h}^{H}(W)\right|$ be
the quadrature error as derived in Step 2 above. Then

$\begin{split}\varepsilon_{2}&\leq\mathcal{E}\sum_{n=-N}^{N}|T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)|+\sum_{n=-N}^{N}\left(h\sum_{k=-H}^{H}|\eta_{n,k}|\right)|T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)|\\\
&\leq(\mathcal{E}+h\|\eta\|_{\infty})\sum_{n=-N}^{N}|T_{\frac{\beta}{2}n}\widetilde{\varphi_{\omega}}(p+\omega)|\\\
&\leq(\mathcal{E}+h\|\eta\|_{\infty})\sqrt{2}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}\sum_{n\in{\mathbb{Z}}}e^{-\nu|p+\frac{\omega}{2}-\frac{\beta}{2}n|}\\\
&\leq(\mathcal{E}+h\|\eta\|_{\infty})\sqrt{2}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}\left(2+\int_{\mathbb{R}}e^{-\frac{\nu\beta}{2}|t|}\,dt\right)\\\
&=(\mathcal{E}+h\|\eta\|_{\infty})\sqrt{2}Ke^{\frac{\omega^{2}}{4\sigma^{2}}}\left(2+\frac{4}{\nu\beta}\right)\end{split}$

and this yields the assertion by adding up $\varepsilon_{1}$ and
$\varepsilon_{2}$.

∎

## References

  * [1] Alaifari, R., Daubechies, I., Grohs, P., and Yin, R. Stable phase retrieval in infinite dimensions.  Found. Comput. Math. 19 (2019), 869–900.  doi.org/doi.org/10.1007/s10208-018-9399-7.
  * [2] Alaifari, R., and Grohs, P. Phase retrieval in the general setting of continuous frames for banach spaces.  SIAM J. Math. Anal. 49 (2016).  doi.org/10.1137/16M1071481.
  * [3] Alaifari, R., and Grohs, P. Gabor phase retrieval is severely ill-posed.  Appl. Comput. Harmon. Anal. 50 (2021), 401–419.  doi.org/10.1016/j.acha.2019.09.003.
  * [4] Aldroubi, A., and Gröchenig, K. Nonuniform sampling and reconstruction in shift-invariant spaces.  SIAM Rev. 43, 4 (2001), 585–620.  doi.org/10.1137/S0036144501386986.
  * [5] Bozkurt, B., and Couvreur, L. On the use of phase information for speech recognition.  In 2005 13th European Signal Processing Conference (2005), pp. 1–4.
  * [6] Cahill, J., Casazza, P. G., and Daubechies, I. Phase retrieval in infinite-dimensional Hilbert spaces.  Trans. Amer. Math. Soc. Ser. B 3 (2016), 63–76.  doi.org/10.1090/btran/12.
  * [7] Chen, Y., Cheng, C., Sun, Q., and Wang, H. Phase retrieval of real-valued signals in a shift-invariant space.  Appl. Comput. Harmon. Anal. 49, 1 (2020), 56–73.  doi.org/10.1016/j.acha.2018.11.002.
  * [8] Cheng, C., Jiang, J., and Sun, Q. Phaseless sampling and reconstruction of real-valued signals in shift-invariant spaces.  J. Fourier Anal. Appl. 25, 4 (2019), 1361–1394.  doi.org/10.1007/s00041-018-9639-x.
  * [9] Cheng, C., and Sun, Q. Stable phaseless sampling and reconstruction of real-valued signals with finite rate of innovation.  Acta Appl. Math. 171, 1 (2020), 3.  doi.org/10.1007/s10440-020-00371-5.
  * [10] Christensen, O. An Introduction to Frames and Riesz Bases.  Birkhäuser Basel, 2016.  doi.org/10.1007/978-3-319-25613-9.
  * [11] Christensen, O., and Eldar, Y. Oblique dual frames and shift-invariant spaces.  Appl. Comput. Harmon. Anal. 17, 1 (2004), 48–68.  doi.org/10.1016/j.acha.2003.12.003.
  * [12] Corbett, J. The pauli problem, state reconstruction and quantum-real numbers.  Rep. Math. Phys. 57, 1 (2006), 53–68.  doi.org/10.1016/S0034-4877(06)80008-X.
  * [13] da Silva, J. C., and Menzel, A. Elementary signals in ptychography.  Opt. Express 23, 26 (Dec 2015), 33812–33821.  doi.org/10.1364/OE.23.033812.
  * [14] Dainty, J., and Fienup, J. Phase retrieval and image reconstruction for astronomy.  Image Recovery: Theory Appl 13 (1987).
  * [15] Fannjiang, A., and Strohmer, T. The numerics of phase retrieval.  Acta Numer. 29 (2020), 125–228.  doi.org/10.1017/S0962492920000069.
  * [16] Fannjiang, A., and Zhang, Z. Fixed point analysis of douglas-rachford splitting for ptychography and phase retrieval.  ArXiv abs/1909.08600 (2020).
  * [17] Fienup, J. Phase retrieval algorithms: a comparison.  Applied optics 21 15 (1982), 2758–69.
  * [18] Gerchberg, R. A practical algorithm for the determination of phase from image and diffraction plane pictures.  Optik 35 (1972), 237–246.
  * [19] Gröchenig, K. Phase-Retrieval in Shift-Invariant Spaces with Gaussian Generator.  J. Fourier Anal. Appl. 26, 3 (2020), 52.  doi.org/10.1007/s00041-020-09755-5.
  * [20] Grohs, P., Koppensteiner, S., and Rathmair, M. Phase retrieval: Uniqueness and stability.  SIAM Rev. 62, 2 (2020), 301–350.  doi.org/10.1137/19M1256865.
  * [21] Grohs, P., and Liehr, L. Injectivity of Gabor phase retrieval from lattice measurements.  arXiv:2008.07238 (2020).  arxiv.org/abs/2008.07238.
  * [22] Grohs, P., and Liehr, L. On Foundational Discretization Barriers in STFT Phase Retrieval.  J. Fourier Anal. Appl. 28, 39 (2022).  doi.org/10.1007/s00041-022-09935-5.
  * [23] Grohs, P., and Rathmair, M. Stable Gabor Phase Retrieval and Spectral Clustering.  Comm. Pure Appl. Math. 72, 5 (2019), 981–1043.  doi.org/10.1002/cpa.21799.
  * [24] Grohs, P., and Rathmair, M. Stable Gabor phase retrieval for multivariate functions.  J. Eur. Math. Soc. (JEMS) (2021).  doi.org/10.4171/JEMS/1114.
  * [25] Gröchenig, K., Romero, J. L., and Stöckler, J. Sampling theorems for shift-invariant spaces, Gabor frames, and totally positive functions.  Invent. math. 211 (2018), 1119–1148.  doi.org/10.1007/s00222-017-0760-2.
  * [26] Higgins, J. R. Sampling Theory in Fourier and Signal Analysis: Foundations.  Clarendon Press, 2001.
  * [27] Janssen, A. Some Weyl-Heisenberg frame bound calculations.  Indag. Math. 7, 2 (1996), 165–183.  doi.org/10.1016/0019-3577(96)85088-9.
  * [28] Li, J., and Zhou, T. On relaxed averaged alternating reflections (RAAR) algorithm for phase retrieval with structured illumination.  Inverse Problems 33, 2 (jan 2017), 025012.  doi.org/doi.org/10.1088/1361-6420/aa518e.
  * [29] Luke, D. R. Relaxed averaged alternating reflections for diffraction imaging.  Inverse Problems 21, 1 (nov 2004), 37–50.  doi.org/10.1088/0266-5611/21/1/004.
  * [30] Romero, J. Sign retrieval in shift-invariant spaces with totally positive generator.  J. Fourier Anal. Appl. 27, 2 (2021), 27.  doi.org/10.1007/s00041-020-09804-z.
  * [31] Shechtman, Y., Eldar, Y. C., Cohen, O., Chapman, H. N., Miao, J., and Segev, M. Phase retrieval with application to optical imaging: A contemporary overview.  IEEE Signal Processing Magazine 32, 3 (2015), 87–109.  doi.org/10.1109/MSP.2014.2352673.
  * [32] Shenoy, B. A., Mulleti, S., and Seelamantula, C. S. Exact phase retrieval in principal shift-invariant spaces.  IEEE Trans. Signal Process. 64, 2 (2016), 406–416.  doi.org/10.1109/TSP.2015.2481871.
  * [33] Thakur, G. Reconstruction of bandlimited functions from unsigned samples.  J. Fourier Anal. Appl. 17, 4 (Aug 2011), 720–732.  doi.org/10.1007/s00041-010-9144-3.
  * [34] Trefethen, L. N., and Weideman, J. A. C. The Exponentially Convergent Trapezoidal Rule.  SIAM Rev. 56, 3 (2014), 385–458.  doi.org/10.1137/130932132.
  * [35] Whittaker, E. T., and Watson, G. N. A Course of Modern Analysis, 4 ed.  Cambridge Mathematical Library. Cambridge University Press, 1996.  doi.org/10.1017/CBO9780511608759.