Abstract
We study the problem of recovering a function of the form \(f(x) = \sum _{k\in \mathbb {Z}} c_k e^{-(x-k)^2}\) from its phaseless samples \(|f(\lambda )|\) on some arbitrary countable set \(\Lambda \subseteq \mathbb {R}\). For real-valued functions this is possible up to a sign for every separated set with Beurling density \(D^-(\Lambda ) >2\). This result is sharp. For complex-valued functions we find all possible solutions with the same phaseless samples.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
In many measurements only non-negative amplitudes or intensities are recorded rather than the physical quantity itself. The problem then is to recover the underlying object (signal, image) from these phaseless measurements, in other words, to retrieve the phase from the magnitude. This is the problem of phase-retrieval. Particular problems concern the recovery of a function f from its phaseless Fourier measurements \(|\hat{f}(\xi )|\) or the recovery of a function f from its phaseless (or unsigned) samples \(|f(\lambda )|\). For general information about the phase-retrieval problem we refer to the surveys [13, 18].
The question of phase-retrieval is usually ill-posed or even meaningless, unless one imposes additional assumptions on the function to be reconstructed, such as a particular signal model. In this note we consider the problem of phase-retrieval in the particular class of shift-invariant spaces generated by a Gaussian. The prototype of a shift-invariant space is the Paley-Wiener space of bandlimited functions \(\{ f\in L^2(\mathbb {R}): {{\,\mathrm{supp}\,}}\, \hat{f} \subseteq [-1/2, 1/2]\}\). More general shift-invariant spaces serve as a substitute for bandlimited functions and have received wide attention in approximation theory and sampling theory [5, 11].
Given a generator \(g\in L^2(\mathbb {R})\), \(p\in [1,\infty ]\), and a mesh parameter or step size \(\beta >0\), let
One of the versions of phase-retrieval in shift-invariant spaces is the recovery of a function f (up to a scalar) from its phaseless samples \(|f(\lambda )|\) on some set \(\Lambda \). The question then is whether the additional information that f belongs to the shift-invariant space \(V^p_\beta (g)\) suffices to determine f up to a sign. For the prototype of a shift-invariant space, namely the bandlimited functions, this question was solved [21]. Recently Q. Sun and his collaborators have developed a general theory for phase-retrieval in shift-invariant spaces in a series of articles [7,8,9]. A typical result asserts that the samples of |f| on a sufficiently dense union of shifted lattices suffice to recover real-valued functions in some \(V^2(g)\). These papers also cover some of the numerical aspects of phase-retrieval. The problem of phase-retrieval in shift-invariant spaces from Fourier measurements is studied in [19].
We study the problem of phase-retrieval in the shift-invariant space generated by a Gaussian \(\phi _\gamma (x) = e^{-\gamma x^2}\). Precisely, we will assume that f is a linear combination of shifts of a Gaussian and belongs to the shift-invariant space
We will allow samples from an arbitrary separated set \(\Lambda \subset \mathbb {R}\) and measure the density of \(\Lambda \) with the standard notion of the lower Beurling density defined as
We will first consider real-valued functions and unsigned samples \(|f(\lambda )|\). For this case we prove the following uniqueness theorem.
Assume that \(\Lambda \subseteq \mathbb {R}\) is separated and that \(D^-(\Lambda ) > 2\beta ^{-1}\). Then phase-retrieval is possible on \(\Lambda \) for all real-valued functions in \(V_\beta ^\infty (\phi _\gamma )\). This means that an unknown real-valued \(f\in V^\infty _\beta (\phi _\gamma )\) is uniquely determined up to a global sign factor by its phaseless samples \(\{ |f(\lambda )| : \lambda \in \Lambda \}\).
Theorem 1 says that for real-valued \(f, g \in V^\infty _\beta (\phi _\gamma )\) satisfying \(|f(\lambda ) | = |g(\lambda )|\) for all \(\lambda \in \Lambda \) we have either \(g = f\) or \(g=-f\), thus the only ambiguity is the (global) sign of f. Our proof yields a reconstruction procedure (see Section 2), but it is well-known that the phase-retrieval problem in infinite dimensions is necessarily ill-posed [4, 6, 13].
In the second part we will study complex-valued functions in \(V^\infty _\beta (\phi _\gamma )\). In this case there is no uniqueness, instead we will classify all functions \(g\in V^\infty _\beta (\phi _\gamma )\) that satisfy \(|g(\lambda )| = |f(\lambda )|\) on \(\Lambda \).
Before proceeding, let us discuss some of the fine points of Theorem 1.
- (i)
Remarkably, the uniqueness holds even for bounded coefficients, and not just for square-summable coefficients. We can therefore not rely on the Hilbert space theory for phase-retrieval, but technically we need to rely on the Banach space set-up of Alaifari and Grohs [4].
- (ii)
The density condition is sharp. For uniform density \(D(\Lambda ) < 2\beta ^{-1}\) one can produce essentially different real-valued functions f, g with the same phaseless samples \(|g(\lambda ) | = |f(\lambda )|, \lambda \in \Lambda \). See below.
- (iii)
A similar statement for bandlimited functions was proved by Thakur [21] and revisited in [4]. Both [21] and Theorem 1 support the intuition that the recovery of phase from magnitude requires twice as many samples as the recovery from the samples \(f(\lambda )\). This is well known for finite-dimensional frames, but in infinite dimensions it is more subtle to formulate and prove. To our knowledge Theorem 1 is one of only two models for which phase-retrieval is possible with a sharp density condition. The investigations in [7,8,9] require a much higher sampling rate or deal with conditions under which phase-retrieval is not even possible.
In Section 1 we collect several statements about the shift-invariant space \(V^\infty _\beta (\phi _\gamma )\) and then prove Theorem 1. In Section 2 we study phase-retrieval for complex-valued functions. Our main tool is a factorization of period entire functions whose proof is postponed to Section 3.
1 Phase-Retrieval for Real-Valued Functions
We set up the proof of Theorem 1. To avoid unnecessary parameters, we set \(\beta =1\), without loss of generality. This is possible because \(f(x) = \sum _{k} c_k e^{-\gamma (x-\beta k)^2} = \sum _{k} c_k e^{-\gamma \beta ^2 (x/\beta - k)^2} \). This means that \(f \in V^\infty _\beta (\phi _\gamma )\), if and only if \(f ( \beta \cdot ) \in V^\infty _1 (\phi _{\beta ^2\gamma })\). Thus phase-retrieval on \(\Lambda \) is possible for \(V_1^\infty (\phi _{\beta ^2\gamma })\), if and only if phase-retrieval on \(\beta \Lambda \) is possible for \(V_\beta ^\infty (\phi _{\gamma })\). We note that \(D^-(\beta \Lambda ) = \beta ^{-1}D^-(\Lambda )\). Thus it suffices to prove Theorem 1 for \(\beta =1\).
Our first use of complex variable methods is the following lemma for Fourier series.
Lemma 2
-
(i)
Let d be a sequence with Gaussian decay with decay parameter \(\gamma >0\), i.e., \(d_k = c_k e^{-\gamma k^2}\) for some \(c\in \ell ^\infty (\mathbb {Z})\). Then the Fourier series \(\hat{d}(\xi ) = \sum _{k\in \mathbb {Z}} d_k e^{2\pi i k\xi }\) can be extended to an entire function \(D(z) = \hat{d}(\xi + iy)\) with growth of order 2, precisely, \(|D(\xi +iy)| = {\mathcal {O}}( e^{\pi ^2 y^2 / \gamma }) \).
-
(ii)
Conversely, if D(z) is a periodic entire function \(D(z+k) = D(z)\) for all \(z\in \mathbb {C}\) and \(k\in \mathbb {Z}\) with growth \(|D(\xi +iy)| = {\mathcal {O}}( e^{\pi ^2 y^2 / \gamma })\), then the Fourier series of \(D(\xi )\) has coefficients of Gaussian decay \(d_k = c_k e^{-\gamma k^2}\) for some \(c\in \ell ^\infty (\mathbb {Z})\).
Proof
For completeness we give the elementary proof.
- (i)
Writing \(z= \xi +iy\) and \(d_k = c_k e^{-\gamma k^2}\), we have
$$\begin{aligned} \hat{d}(\xi +iy)&= \sum _{k\in \mathbb {Z}} c_k e^{-\gamma k^2} e^{2\pi i k (\xi +iy)} \\&\le \Vert c\Vert _\infty \, \sum _{k\in \mathbb {Z}} e^{-\gamma k^2} e^{2\pi k |y|} \\&= \Vert c\Vert _\infty \, \Big ( \sum _{k\in \mathbb {Z}} e^{-\gamma (k - \pi |y|/\gamma )^2} \Big ) e^{\pi ^2 y^2 / \gamma } = {\mathcal {O}}( e^{\pi ^2 y^2/\gamma } )\, . \end{aligned}$$Clearly \(\hat{d}\) is entire.
- (ii)
If D is entire and periodic, then
$$\begin{aligned} D(z) = \sum _{k\in \mathbb {Z}} d_k e^{2\pi i k z } = \sum _{k\in \mathbb {Z}} d_k e^{-2\pi ky } e^{2\pi i k \xi } \, . \end{aligned}$$with uniform convergence on compact sets and exponentially decaying coefficients. See, e.g., [20, Theorem 3.10.3]. Consequently the Fourier coefficients of \(\xi \mapsto D(\xi +iy)\) are \(d_k e^{-2\pi k y}\) and satisfy
$$\begin{aligned} |d_k |e^{-2\pi k y} \le \int _{0}^1 |D(\xi +iy)| \, d\xi \le C e^{\pi ^2 y^2 /\gamma } \, , \end{aligned}$$for allk and y, where the last inequality follows from the assumption.
Setting \(y= -\frac{\gamma k}{\pi } \) yields the desired estimate
\(\square \)
The analysis of phase-retrieval in \(V^\infty _1 (\phi _\gamma )\) involves several steps.
Step 1.From \(f\in V^\infty _1(\phi _\gamma )\)to \(|f|^2\). We start with a simple algebraic observation.
Lemma 3
If \(f\in V^\infty _1(\phi _\gamma )\), then \(|f|^2 \in V_{1/2}^\infty (\phi _{2\gamma })\).
Proof
We write \(f(x) = \sum _{k\in \mathbb {Z}} c_k e^{- \gamma (x - k)^2}\) with \(c\in \ell ^\infty (\mathbb {Z})\). Since
we find that
This calculation shows that the function \(|f|^2\) belongs to a different shift-invariant space generated by \(\phi _{2\gamma }\) with step size 1/2. Set
From these definitions we see that
If \(c\in \ell ^\infty (\mathbb {Z})\), then \(\tilde{r} \in \ell ^\infty (\mathbb {Z})\), because
Setting \(C= \max (\sum _{k\in \mathbb {Z}} e^{-2\gamma k^2 } , \sum _{k\in \mathbb {Z}} e^{-\gamma (1-2k)^2/2 })\), we have shown that
As a consequence \(|f|^2 \in V^\infty _{1/2}(\phi _{2\gamma })\), as claimed. \(\square \)
Step 2.A sharp sampling theorem. Our main tool is the following sampling theorem for shift-invariant spaces with Gaussian generator from [12, Theorem. 4.4].
Theorem 4
Let \(\gamma >0\) and \(1\le p\le \infty \) and \(\Lambda \subseteq \mathbb {R}\) be separated. If \(D^-(\Lambda ) > \beta ^{-1}\), then for some constants \(A,B>0\) depending on \(\Lambda \) and p
Conversely, if (10) holds, then \(D^-(\Lambda ) \ge \beta ^{-1}\). This was already proved in [5] and shows that Theorem 4 is optimal.
Applying this theorem to the function \(|f|^2 \in V_{1/2}^\infty (\phi _{2\gamma })\), we obtain the following consequence.
Corollary 5
Let \(\gamma >0\) and \(\Lambda \subseteq \mathbb {R}\) be separated with density \(D^-(\Lambda )>2\). If \(f\in V_1^\infty (\phi _\gamma )\) and thus \(|f(x)|^2 = \sum _{n\in \mathbb {Z}} \widetilde{r_n} e^{-2\gamma (x-n/2)}\in V_{1/2}^\infty (\phi _{2\gamma })\), then there exist constants \(A,B>0\) such that
Thus the coefficients \(\tilde{r}\) of \(|f|^2\) are uniquely and stably determined by the phaseless samples of f on \(\Lambda \).
Note that in (11) we have used the norm equivalence \(\sup _{x\in \mathbb {R}} |f(x)|^2 \asymp \sup _{n\in \mathbb {Z}} |\widetilde{r_n}|\).
Step 3.A functional equation. The sampling inequality (11) allows us to recover the coefficients \(\tilde{r}\) from the phaseless samples \(|f(\lambda )|^2\). Finally we have to recover the coefficients c and d from the coefficients \({\tilde{r}}\) of \(|f|^2\), or equivalently from the \(r_n = \widetilde{r_n} e^{-\gamma n^2/2}\).
Let \(\hat{d}(\xi ) = \sum _{k\in \mathbb {Z}} d_k e^{2\pi i k\xi }\) be the Fourier series of d and \(\hat{r}\) be the Fourier series of r. Then Eq. (7) turns into
Since \(d_k = c_k e^{-\gamma k^2}\) has Gaussian decay, Lemma 2 asserts that its Fourier series can be extended to the entire function
with growth \(|D(\xi +iy) | = {\mathcal {O}}( e^{\pi ^2 y^2/\gamma })\). Likewise \(\overline{\hat{d}(-\xi )}\) extends to the entire function \( D^*(z) = \overline{D(-\bar{z})}= \overline{\hat{d}(-\bar{z})}\), and \(\hat{r}\) extends to \(R(z)= \hat{r}(z)\).
Consequently, we have to find the entire function D that satisfies the identity
In other words, to every solution D of the functional Eq. (13) corresponds a function g such that \(|g(\lambda )| = |f(\lambda )|\) for \(\lambda \in \Lambda \).
Assuming that f is real-valued, we can now prove Theorem 1 quickly.
Proof of Theorem 1
Since f is real-valued by assumption, its coefficients are also real-valued, \(c=\bar{c}\). This entails that \( \overline{D(-\bar{z})} = \overline{\sum _{k\in \mathbb {Z}} d_k e^{-2\pi i k \bar{z}} } = \sum _{k\in \mathbb { Z}} d_k e^{2\pi i k z} = D(z) \) and (13) becomes the identity
The uniqueness of f up to a sign is now immediate: assume that two entire (non-zero) functions \(D_1\) and \(D_2\) satisfy \(D_1^2 = D_2^2 = R\). Then \((D_1-D_2)(D_1+D_2) \equiv 0\). Since the ring of entire functions does not have any zero divisors, we conclude that either \(D_1=D_2\) or \(D_1=-D_2\) on \(\mathbb {C}\). Using formulas (4)–(6) we find that the coefficients c of f, and thus f, are uniquely determined by the phaseless samples \(|f(\lambda )|, \lambda \in \Lambda \), up to a sign. Theorem 1 is therefore proved. \(\square \)
Alternatively, one could prove Theorem 1 by verifying the following criterium for phase-retrieval [4, 6]: \(\Lambda \) permits phase-retrieval, if and only if \(\Lambda \) satisfies the complement property, i.e., if \(S \subseteq \Lambda \), then either \(M_S = \{ f\in V^\infty _\beta (\phi _\gamma ) : f(\lambda ) = 0, \, \forall \lambda \in S\} = \{0\}\) or \(M_{\Lambda \setminus S} = \{0\}\). A direct proof of the complement property can be based on Steps 1 and 2 and is then similar to the argument in [4, Thm. 2.5].
Next we show that the density condition is sharp. Let \(\Lambda = (\lambda _j)_{j\in \mathbb {Z}} \subseteq \mathbb {R}\) be an increasing sequence with uniform density \(D(\Lambda ) <2\). This means that the upper Beurling density \(D^{+}(\Lambda ) := \limsup _{r \rightarrow \infty } \sup _{x \in \mathbb {R}} \frac{\# \Lambda \cap [x-r,x+r] }{2r}\) coincides with the lower Beurling density and \(D(\Lambda ) = D^+(\Lambda ) = D^-(\Lambda ) <2\).
We will produce a counter-example to the complement property. Set \(S = \{ \lambda _{2j}: j\in \mathbb {Z}\}\) and \(S^c = \{ \lambda _{2j+1}: j\in \mathbb {Z}\}\). Then S and \(S^c\) are disjoint and \(D(S) = D(S^c) = \tfrac{1}{2}\, D(\Lambda ) <1\). By the necessary density condition for sampling in shift-invariant spaces, e.g. [5], S and \(S^c\) cannot be sampling sets for \(V^2_1(\phi _\gamma )\), but they are interpolating sets by [12, Thm. 1.3]. These facts imply that both maps \(f\rightarrow \big (f(\lambda )\big )_{\lambda \in S}\) and \(g\rightarrow \big (g(\lambda )\big )_{ \lambda ' \in S^c}\) are onto \(\ell ^2(S)\) with non-trivial kernel. Consequently, there exist non-zero functions \(f,g\in V^2_1(\phi _\gamma )\subseteq V^\infty _1(\phi _\gamma )\) such that \(f(\lambda ) = 0 \) for \(\lambda \in S\) and \(g(\lambda ' ) = 0\) for \(\lambda ' \in S^c\). By taking the real part of f and g, we may further assume that f and g are real-valued. Since for \(\lambda \in \Lambda \) either \(f(\lambda ) =0\) or \(g(\lambda ) = 0\), we obtain
By construction, \(f+g\) and \(f-g\) are linearly independent, and thus sign-retrieval is not unique.
2 Complex-Valued Functions
Theorem 1 states that the unsigned samples \(\{|f(\lambda )|\}\) determine a unique real-valued function \(\pm f \in V^\infty _\beta (\phi _\gamma )\). To treat complex-valued functions in \(V_\beta ^\infty (\phi _\gamma )\), we use a factorization of entire periodic functions that is intermediate between the Hadamard factorization and a Blaschke product.
Lemma 6
Let D be a non-zero entire function of order 2 satisfying the periodicity \(D(z+l)\)\( = D(z)\) for all \(z\in \mathbb {C}\) and \(l\in \mathbb {Z}\). Let \(W_+\) be the zeros of D in \(\{x+iy \ne 0: -1/2 < x \le 1/2, y\ge 0\}\) and \(W_-\) be the zeros of D in \(\{x+iy: -1/2< x \le 1/2, y<0\}\), and \(m\in \mathbb {N}\cup \{0\}\) the multiplicity of \(z=0\). Then D possesses the factorization
for some \(r\in \mathbb {Z}\) and \(C\in \mathbb {C}\). The product converges uniformly on compact sets.
We postpone the proof of this lemma to Sect. 3 and first discuss its application to the phase-retrieval problem.
The factorization (15) serves to find all solutions D to the equation \(D(z) \overline{D(-\bar{z})} = R(z)\) in (13). The spirit of this argument is similar to the analysis in [1, 2, 15, 17, 21].
To avoid spelling out the product in (15), we use the notation
Here \(W= W_+ \cup W_-\) is understood as a sequence \(\{w_j : j\in \mathbb {N}\}\) of zeros, where elements may be repeated according to the (finite) multiplicity of the zero. Since D is of order 2, we know that \(\sum _{j\in \mathbb {N}} |w_j|^{-3} <\infty \). See also (21) below. With this understanding we obtain the following convenient formulas for \(\Pi (W, m, r)\).
- (i)
Let \(Jz = -\bar{z}\) be the reflection of \(z\in \mathbb {C}\) about the imaginary axis and \(D^*(z) = \overline{D(-\bar{z})}\). If \(\phi (z) = \frac{e^{2\pi i z} - e^{2\pi i w}}{1 - e^{2\pi i w} }\), then \(\phi ^*(z)= \overline{\phi (-\bar{z})} = \frac{e^{2\pi i z} - e^{-2\pi i \bar{w}}}{1 - e^{-2\pi i \bar{w}} }\). Consequently
$$\begin{aligned} \Pi (W,m,r)^* = \Pi (JW,m,r) \, . \end{aligned}$$(17) - (ii)
Multiplicativity: Let \(V \, \dot{\cup } \, W\) be the concatenation \(\{v_1, w_1, v_2, w_2, \dots \}\) of two sequences. Note that if the sequences are disjoint as sets, then \(V \, \dot{\cup } \, W = V\cup W\). If \(f=\Pi (V,m,r)\) and \(h=\Pi (W,m',r')\), then
$$\begin{aligned} f h = \Pi (V \, \dot{\cup } \, W,m+m',r+r') \, . \end{aligned}$$(18)
Now let \(D = \Pi (W,m,r)\) be given. Then
This implies that the order of the zero at 0 is even and that the factor \(e^{2\pi i z}\) occurs with an even power. Furthermore, since \(J(iv)=iv\) and \(J(1/2+iv) = -1/2+iv\equiv 1/2+iv\) for \(v\in \mathbb {R}\), the zeros on the lines \(i\mathbb {R}\) and \( 1/2+i\mathbb {R}\) also occur with even multiplicity in R.
Now assume that \(R= \Pi (Z,2m,2r)\) is given so that its zero set is symmetric \(Z=JZ\) and that the zeros on the lines \(i\mathbb {R}\) and \(1/2+i\mathbb {R}\) have even multiplicity.
Let \(S_+ = \{ x+iy: 0<x<1/2\}\) and \(S_0 = i\mathbb {R}\cup (1/2+i\mathbb {R})\). Let \(Z_0 \) be the zeros of R in \(Z\cap S_0\) counted with half their multiplicity. In our notation this means that \(Z_0 \dot{\cup } Z_0 = Z\cap S_0\). Next choose \(V\subseteq Z \cap S_+\) arbitrary and set
Then
and consequently
Thus every choice V of zeros of R in the strip \(S_+\) with the corresponding function \(D_V\) yields a valid factorization of R. Clearly, different zeros sets \(V_1, V_2\) (counting multiplicities) yield \(D_{V_1} \ne D_{V_2}\).
Conversely, every factorization \(DD^* = R\) arises in this way, because we can always write the zero set of D as \(W = (W\cap S_+) \cup (W\cap S_0) \cup (W\cap JS_+)\) and we may choose \(V = W\cap S_+\) to recover W from \(Z= W \cup JW\).
To summarize, we state the following lemma.
Lemma 7
Let \(R=R^* = \Pi (Z,2m,2r)\) be a periodic entire function of order 2 with all zeros on \(i\mathbb {R}\cup 1/2 + i\mathbb {R}\) of even multiplicity. Then every solution of \(DD^*=R\) is given by a unimodular multiple of some \(D_V\), as defined in (19) and (20).
If \(|R(\xi +iy)| = {\mathcal {O}}(e^{2\pi ^2 y^2/\gamma })\), then \(|D_V(\xi +iy)| = {\mathcal {O}}(e^{\pi ^2 y^2/\gamma })\).
Proof
Since \(D_V\) is entire and periodic, its growth is \(|D_V(\pm \xi +iy)| = {\mathcal {O}}(e^{\psi (y)})\). Therefore \(|D_V(\xi +iy) D_V(-\xi +iy)| = {\mathcal {O}}(e^{2\psi (y)}) = {\mathcal {O}}(e^{2\pi ^2 y^2/\gamma })\), whence the growth of \(D_V\) follows. \(\square \)
The analysis of the factorization \(DD^* = R \) is the key tool to find all possible solutions to the phase-retrieval problem for complex-valued functions in \(V_\beta ^\infty (\phi _\gamma )\). In contrast to the uniqueness among real-valued solutions, there are always many substantially different solutions. In principle, these can be found by the following procedure.
Reconstruction procedure. Let \(\Lambda \subseteq \mathbb {R}\) with density \(D^- (\Lambda )>2\). Let \(f\in V_1^\infty (\phi _\gamma )\) be arbitrary and \(\{|f(\lambda )|: \lambda \in \Lambda \}\) be given. To find all functions \(h\in V_1^\infty (\phi _\gamma )\) that recover the phaseless values \(|h(\lambda )| = |f(\lambda )|, \lambda \in \Lambda \) we proceed as follows:
- (i)
Find the coefficient sequence \(\tilde{r} \in \ell ^\infty (\mathbb {Z})\) solving the sampling problem
$$\begin{aligned} |f(\lambda ) |^2 = \sum _{n\in \mathbb {Z}} \widetilde{r_n} e^{-2 \gamma (\lambda - n/2)^2} \qquad \lambda \in \Lambda \, , \end{aligned}$$for some function \(|f|^2 \in V^\infty _{1/2} (\phi _{2\gamma })\).
- (ii)
Let \(Z= \{z_j: j\in \mathbb {N}\}\) be the zero set of \(R(z) = \sum _{n\in \mathbb {Z}} \widetilde{r_n} e^{-\gamma n^2/2}\, e^{2\pi i n z}\) in the vertical strip \(S = \{x+iy\in \mathbb {C}: -1/2 < x \le 1/2\}\). Then \(R^*=R\) by (13) and \(R = \Pi (Z, 2m, 2r )\) for some \(m,r \in \mathbb {N}\) by Lemma 6.
- (iii)
Choose \(V\subseteq Z\cap S_+\) and define \(D_V\) by (20).
- (iv)
Determine the Fourier coefficients of \(D_V(\xi )\):
$$\begin{aligned} d_k = \int _0^1 D_V(\xi ) e^{-2\pi i k \xi } \, d\xi \, . \end{aligned}$$and set \(c_k = d_k e^{\gamma k^2}\) and
$$\begin{aligned} f_V(x) = \alpha \sum c_k e^{-\gamma (x-k)^2} \, \end{aligned}$$for some \(\alpha \in \mathbb {C}, |\alpha | =1\). Since \(|R(\xi +iy)| = {\mathcal {O}}(e^{2\pi ^2 y^2/\gamma })\) by Lemma 2, \(|D_V(\xi +iy)| = {\mathcal {O}}(e^{\pi ^2 y^2/\gamma })\) by Lemma 7. By Lemma 2 the Fourier coefficients of \(D_V\) have Gaussian decay and consequently \(c_k = d_k e^{\gamma k^2}\) is bounded. It follows that \(f\in V^\infty _1 (\phi _\gamma )\). By construction \(|f_V(\lambda )| = |f(\lambda )|\) for all \(\lambda \in \Lambda \). Furthermore, every function \(h\in V^\infty _1(\phi _\gamma )\) satisfying \(|h(\lambda ) | = |f(\lambda )|, \lambda \in \Lambda ,\) must be of the form \(f_V\).
Remark
-
1.
If f is real-valued, then \(D^*=D\), and its zero set is symmetric, \(W=JW\), consequently the zero set \(Z= W\dot{\cup } JW\) contains all zeros of D with double multiplicity. Since every zero has even multiplicity, we can set \(Z\cap S_+ = V \dot{ \cup } V\), where V are the zeros of R in \(S_+\) with half the multiplicity. Equation (19) then yields \(W= V \cup JV \cup Z_0 = JW\). The corresponding function \(D_V\) satisfies \(D_V= D_V^*\), and \(f_V\) is the real-valued solution of the phase-retrieval problem. We note that other choices of V yield complex-valued functions \(f_V\) such that \(|f_V(\lambda ) | = |f(\lambda )|\).
For real-valued f the steps (i) — (iv) constitute a reconstruction procedure of f from its unsigned samples \(|f(\lambda )|,\lambda \in \Lambda \). Whereas Theorem 1 only asserts the uniqueness up to a sign, the factorization of Lemma 6 also implies a (rather theoretical) reconstruction.
-
2.
If \(f\in V_1^\infty (\phi _\gamma )\) is real-valued and even, then \(c_k = \overline{c_k} = c_{-k}\). Consequently, \(\hat{d}(\xi ) = \sum _{k\in \mathbb {Z}} c_k e^{-\gamma k^2} e^{2\pi i k\xi }= \overline{\hat{d}(-\xi )}\) is real-valued, even, and smooth, and \(\hat{r}(\xi ) = \hat{d}(\xi )^2\ge 0\). Thus \(\hat{r} \ge 0\), and the only smooth solutions are \(\hat{d} = \pm \hat{r}^{1/2}\). In this case we can obtain the coefficients \(c_k\) directly as the Fourier coefficients of \(\hat{r}^{1/2}\) via
$$\begin{aligned} c_k e^{-\gamma k^2} = \int _{0}^1 \hat{r}(\xi )^{1/2} \, e^{-2\pi i k\xi } \, d\xi \, . \end{aligned}$$Of course, for the boundedness of these coefficients we still need the analysis that led to Lemma 7.
-
3.
Stability. The procedure in steps (i) — (iv) is only of theoretical interest, because it is well-known that phase-retrieval in infinite dimensions is inherently unstable [3, 4, 6]. This is completely obvious in the reconstruction procedure in the shift-invariant space \(V^\infty _1(\phi _\gamma )\): numerically, the transition from the relevant coefficient sequence c to d, given by \(d_k = c_k e^{-\gamma k^2}\) amounts to the truncation of c to a finite sequence. Once the sequence d has been obtained (steps (iii) and (iv) above), the transition \(c_k = d_k e^{\gamma k^2}\) leads to an amplification of all accumulated errors. Yet, despite the inherent instability, several steps in the above reconstruction of f are stable. The relevant estimate is (11), for the reconstruction of \(\tilde{r}\) from the phaseless samples \(|f(\lambda )|\). For coefficient sequences c with small support the reconstruction promises to be reasonably effective, which is consistent with the arguments in [3] and [14].
3 Proof of the Factorization Lemma
As we do not know a precise citation for the statement, we include a proof of Lemma 6. We need to show that every periodic entire function D of order 2 (more generally, of finite order) can be factored into a product with factors of the form
where w is a zero of D in the vertical strip \(S = \{x+iy\in \mathbb {C}: -1/2 < x \le 1/2\}\). The choice of the signs depends on the sign of \(\mathrm {Im}\, w\). As we will see in part (vi) of the proof, the sign is determined by the asymptotic behavior of \(\cot \pi w\) as \(\mathrm {Im}\, w \rightarrow \pm \infty \).
Proof
(i) Since D is periodic, its zero set is periodic and, by definition of \(W_\pm \) the zero set is \(\bigcup _{w\in W_+ \cup W_-} (w +\mathbb {Z}) \). Since D is entire of order 2, the convergence exponent of its zeros is \(>2\) [20]. This implies that
(ii) Let
be the main part of the right-hand side of (15). We first check the convergence of the product. For this we need to verify that
is finite for every \(R>0\). This expression is simply
Since for \(w\in W_-\), \(e^{-\mathrm {Im}\, w} \ge 1+|\mathrm {Im}\, w|^3/6\) and \(|\mathrm {Re} w| \le 1/2\), the sum in (22) converges by (21). Thus \(\prod _{w\in W_-} \) converges uniformly on compact sets. By a similar argument the product \(\prod _{w\in W_+} \frac{e^{-2\pi i z} - e^{-2\pi i w}}{1- e^{-2\pi i w} } \) converges uniformly on compact sets. Consequently \(\tilde{D}\) is an entire function. Clearly \(\tilde{ D}\) is periodic with period 1, and its zero set in the strip S is precisely \(W_- \cup W_+ \) (\(\cup \{0\}\), if 0 is a zero). By construction, D and \(\tilde{ D}\) possess the same zero set with the same multiplicities.
(iii) Next we use the Hadamard factorization theorem to factorize D with respect to its zeros as follows:
where m is the order of the zero at 0 and p is a quadratic polynomial.
We note right away that the first factor is a power of
by the factorization of the sine-function. See [20], Section 9.2, or [16], Lecture 4.
(iv) For the factors with \(w\ne 0\) we introduce
Then G(z, w) has simple zeros at \(w+\mathbb {Z}\), as does the function \(\sin (\pi (z-w))\). Using the identities,
for \(w\ne 0\), e.g., [10, 20], we identify G(z, w) as
This is easily seen by calculating \(G(z,w) \frac{\sin (-\pi w)}{\sin \pi (z-w)}\) with the factorization of \(\sin \pi z\). The quadratic polynomial in the exponent is obtained by substituting (24) and (25) in (23).
(v) Now consider the ratio of corresponding factors in D and \(\tilde{ D}\) and simplify the expression. We argue only for \(w\in W_+\).
whereas for \(w\in W_-\) we have
Next we take the product over \(w\in W_-\) and assume for now that the product converges. Then we obtain
for some quadratic polynomial \(q_+\). Likewise
for a quadratic polynomial \(q_-\), and \(G(z,0)/ \big (e^{2\pi i z} -1\big )= (2\pi i)^{-1} \exp \Big ( -i\pi z + \pi ^2z^2/6 \Big ) = e^{q_0(z)}\). We therefore obtain that
The left-hand side is an entire function with period 1, whereas the right-hand side is the exponential of a quadratic polynomial. It is now easy to see that \(e^P\) is periodic for a polynomial P , if and only if \(P(z) = 2\pi i r z\) for some \(r\in \mathbb {Z}\). We conclude that \(D(z) = \tilde{D}(z) e^{2\pi i rz}\), and this is precisely (15).
(vi) It remains to be shown that the product in (27) converges. First,
Since \(|e^{i\pi w}| = e^{-\pi \mathrm {Im}w}\) and \(|e^{i\pi w}- e^{-i\pi w}|\ge |e^{-i\pi w}| - |e^{i\pi w}| \ge e^{\pi \mathrm {Im}w} - e^{-\pi \mathrm {Im}w} \ge \tfrac{1}{2} e^{\pi \mathrm {Im}w} \) for \( \mathrm {Im}w\ge 1\), say, we obtain
Since the sum in (29) is over the terms with \(\mathrm {Im}w >0\) with \(|\mathrm {Re} w| \le 1/2\) and \(\sum _{w\in W} |w|^{-3} <\infty \), it is finite. For the terms in \(W_-\) our choice of the signs yields the same conclusion. Finally \(\sum _{w\in W} |\frac{1}{2 \sin ^2 \pi w}|\) is finite by the same reason.\(\square \)
References
Akutowicz, E.J.: On the determination of the phase of a Fourier integral. I. Trans. Am. Math. Soc. 83, 179–192 (1956)
Akutowicz, E.J.: On the determination of the phase of a Fourier integral. II. Proc. Am. Math. Soc. 8, 234–238 (1957)
Alaifari, R., Daubechies, I., Grohs, P., Thakur, G.: Reconstructing real-valued functions from unsigned coefficients with respect to wavelet and other frames. J. Fourier Anal. Appl. 23(6), 1480–1494 (2017)
Alaifari, R., Grohs, P.: Phase retrieval in the general setting of continuous frames for Banach spaces. SIAM J. Math. Anal. 49(3), 1895–1911 (2017)
Aldroubi, A., Gröchenig, K.: Beurling-Landau-type theorems for non-uniform sampling in shift invariant spline spaces. J. Fourier Anal. Appl. 6(1), 93–103 (2000)
Cahill, J., Casazza, P.G., Daubechies, I.: Phase retrieval in infinite-dimensional Hilbert spaces. Trans. Am. Math. Soc. Ser. B 3, 63–76 (2016)
Chen, Y., Cheng, C., Sun, Q., Wang, H.: Phase retrieval of real-valued signals in a shift-invariant space. Appl. Comput. Harmon. Anal. 49(1), 56–73 (2020)
Cheng, C., Jiang, J., Sun, Q.: Phaseless sampling and reconstruction of real-valued signals in shift-invariant spaces. J. Fourier Anal. Appl. 25(4), 1361–1394 (2019)
Cheng, C., Sun, Q.: Stable Phaseless Sampling and Reconstruction of Real-Valued Signals with Finite Rate of Innovations. (2018) Preprint, arXiv:1801.05538
Conway, J.B.: Functions of One Complex Variable, second edn. Springer, New York (1978)
de Boor, C., DeVore, R.A., Ron, A.: The structure of finitely generated shift-invariant spaces in \({L}_2({{\mathbb{R}}}^d)\). J. Funct. Anal. 119(1), 37–78 (1994)
Gröchenig, K., Romero, J., Stöckler, J.: Sampling theorems for shift-invariant spaces, Gabor frames, and totally positive functions. Invent. Math. 211(3), 1119–1148 (2018)
Grohs, P., Koppensteiner, S., Rathmair, M.: Phase retrieval: uniqueness and stability. SIAM Rev. 62(2), 301–350 (2020)
Grohs, P., Rathmair, M.: Stable Gabor phase retrieval and spectral clustering. Commun. Pure Appl. Math. 72(5), 981–1043 (2019)
Jaming, P., Kellay, K., Perez III, R.: Phase retrieval for wide band signals. J. Fourier. Anal. Appl. (2020). https://doi.org/10.1007/s00041-020-09767-1
Levin, B.Y.: Lectures on entire functions. American Mathematical Society, Providence, RI. In collaboration with and with a preface by Yu. Lyubarskii, M. Sodin and V. Tkachenko, Translated from the Russian manuscript by Tkachenko (1996)
McDonald, J.N.: Phase retrieval and magnitude retrieval of entire functions. J. Fourier Anal. Appl. 10(3), 259–267 (2004)
Shechtman, Y., Eldar, Y.C., Cohen, O., Chapman, H.N., Miao, J., Segev, M.: Phase retrieval with application to optical imaging: a contemporary overview. IEEE Signal Process. Mag. 32(3), 87–109 (2015)
Shenoy, B.A., Mulleti, S., Seelamantula, C.S.: Exact phase retrieval in principal shift-invariant spaces. IEEE Trans. Signal Process. 64(2), 406–416 (2016)
Simon, B.: Basic Complex Aanalysis A Comprehensive Course in Analysis, Part 2A. American Mathematical Society, Providence, RI (2015)
Thakur, G.: Reconstruction of bandlimited functions from unsigned samples. J. Fourier Anal. Appl. 17(4), 720–732 (2011)
Acknowledgements
Open access funding provided by University of Vienna. The author would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme “Approximation, sampling and compression in data science” where work on this paper was undertaken. Special thanks go to Felix Voigtländer for his critical reading and his detailed comments that led me to correct and expand Sect. 2.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Hans G. Feichtinger.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
K. G. was supported in part by the Project P31887-N32 of the Austrian Science Fund (FWF).
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Gröchenig, K. Phase-Retrieval in Shift-Invariant Spaces with Gaussian Generator. J Fourier Anal Appl 26, 52 (2020). https://doi.org/10.1007/s00041-020-09755-5
Received:
Published:
DOI: https://doi.org/10.1007/s00041-020-09755-5