We consider the problem of reconstructing a function \(f\in L^2({\mathbb R})\) given phase-less samples of its Gabor transform, which is defined by
$$\begin{aligned} {\mathcal {G}}f(x,y) :=2^{\frac{1}{4}} \int _{\mathbb R}f(t) e^{-\pi (t-x)^2} e^{-2\pi i y t}\,\text{ d }t,\quad (x,y)\in {\mathbb R}^2. \end{aligned}$$
More precisely, given sampling positions \(\Omega \subseteq {\mathbb R}^2\) the task is to reconstruct f (up to global phase) from measurements \(\{|{\mathcal {G}}f(\omega )|: \,\omega \in \Omega \}\). This non-linear inverse problem is known to suffer from severe ill-posedness. As for any other phase retrieval problem, constructive recovery is a notoriously delicate affair due to the lack of convexity. One of the fundamental insights in this line of research is that the connectivity of the measurements is both necessary and sufficient for reconstruction of phase information to be theoretically possible. In this article we propose a reconstruction algorithm which is based on solving two convex problems and, as such, amenable to numerical analysis. We show, empirically as well as analytically, that the scheme accurately reconstructs from noisy data within the connected regime. Moreover, to emphasize the practicability of the algorithm we argue that both convex problems can actually be reformulated as semi-definite programs for which efficient solvers are readily available. The approach is based on ideas from complex analysis, Gabor frame theory as well as matrix completion. As a byproduct, we also obtain improved truncation error for Gabor expensions with Gaussian generators.
Notes
Communicated by Rachel Ward.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Phase retrieval problems are an important and common class of problems in the physical sciences with applications ranging from diffraction imaging [38] over audio signal processing [21] to quantum mechanics [34]. In mathematical terms, phase retrieval is concerned with the reconstruction from phaseless linear measurements. More formally, given \(T:X\rightarrow X'\) a linear operator between two complex function spaces X and \(X'\), consider the map
$$ \mathcal {A}:f\mapsto |Tf|^2,\quad f\in X $$
where |Tf| denotes the pointwise modulus of Tf, i.e. \(|Tf|(\omega )=|Tf(\omega )|\). Solving the phase retrieval problem amounts to solving the inverse problem associated with the forward operator \(\mathcal {A}\). Clearly, \(\mathcal {A}f=\mathcal {A}h\) if \(h =cf\) with \(|c|=1\). To remove this obvious source of ambiguity one does not distinguish between functions which coincide up to a multiplicative factor of unit modulus,
$$ f \sim h \quad \Longleftrightarrow \quad \exists c\in {\mathbb C},\,|c|=1:\quad h=cf. $$
In a nutshell, the reconstruction task is to come up with the left inverse \(\mathfrak {L}\) of \(\mathcal {A}\), that is, a map satisfying
$$ \forall f\in X:\quad \mathfrak {L}(|Tf|^2) \sim f. $$
It is important to note that it is by no means clear that the left inverse exists. For many instances of phase retrieval problems it is already difficult to decide the question of uniqueness, i.e., whether \(\mathcal {A}\) is injective on \(X/\!\sim \) or not. Typically, there are three fundamental aspects studied within the scope of phase retrieval: uniqueness, stability and actual reconstruction. In terms of the left inverse, these categories correspond to existence of \(\mathfrak {L}\), continuity of \(\mathfrak {L}\) and construction of \(\mathfrak {L}\), respectively.
Ideally, given a concrete phase retrieval problem one would like to have a good understanding of all three aspects. Uniqueness and stability address the issue of well-posedness. Algorithmic methods to reconstruct are of fundamental importance for practical applications. In addition – as for any other numerical method – performance guarantees and a-priori estimates for the error are highly desirable, as is the capability of the method to deal with noisy input data.
Advertisement
Generally speaking, the algorithmic solution of phase retrieval problems is a notoriously delicate matter. Different variations of algorithms based on alternating projections have been around for decades, such as the methods by Gerchberg-Saxton [19] and by Fienup [18] to name just two. These schemes have the advantage of being uncomplicated to implement. However, the absence of convexity makes them difficult to analyse, which is a major drawback when it comes to establishing convergence guarantees. A rather recent trend is based on the idea of lifting the problem into a higher dimensional space and solving a convex reformulation (or relaxation) there. For a number of algorithms of this type, results have been established which guarantee the accuracy of the method in a sufficiently randomized setting. We mention the ’PhaseLift’ algorithm (Candès, Strohmer and Voroninski [8]) and the ’PhaseCut’ algorithm (Waldspurger, d’Aspremont and Mallat [40]) as two of the earliest contributions into this direction. For a comprehensive discussion of numerical aspects of phase retrieval as well as a detailed overview of the literature we refer to the recent survey [17].
1.1 Aim of This Paper & Related Results
In this paper we consider a particular instance of a phase retrieval problem, namely where the linear operator is the short-time Fourier transform with Gaussian window. Precisely, this means that \(T={\mathcal {G}}\), the Gabor transform defined by
$$ {\mathcal {G}}f(x,y) = 2^{1/4} \int _{\mathbb R}f(t) e^{-\pi (t-x)^2} e^{-2\pi i y t}\,\text{ d }t,\quad f\in L^2({\mathbb R}),\,(x,y)\in \Omega , $$
with \(\Omega \subseteq {\mathbb R}^2\). Evaluations of the Gabor transform correspond to correlation between f and time-frequency shifts of a Gaussian
where \(\varphi :=2^{1/4} e^{-\pi \cdot ^2}\) and \(\pi (\lambda )\) denotes a time-frequency shift, i.e.,
$$ (\pi (\lambda )g)(t) = e^{2\pi i yt} g(t-x). $$
The squared modulus of the Gabor transform is called the (Gabor) spectrogram and denoted by \({\mathcal {S}}f=|{\mathcal {G}}f|^2\). The set \(\Omega \) represents the locations where phaseless information is given. If \(\Omega = {\mathbb R}^2\) (in fact, \(\Omega \) open suffices) it is well known that any \(f\in L^2({\mathbb R})/\sim \) is uniquely determined by \(\{{\mathcal {S}}f(\omega ), \omega \in \Omega \}\). Contrary to that, the uniqueness question for discrete sets \(\Omega \) is already quite subtle. While sampling on a lattice (irrespective of its density!) is not enough [3, 27], the union of three suitable perturbations of a sufficiently dense lattice yields uniqueness [28].
Phase retrieval is inherently unstable in infinite dimensions [1, 6] which aggravates matters even more. In the above setting this means that the left inverse of \(f\mapsto {\mathcal {S}}f\) (presuming that it exists) cannot be a well-behaved smooth function. Sources of instabilities are functions \(f=f_1+f_2\) consisting of two (or more) components: we say that \(f_1\) and \(f_2\) are components if their respective Gabor transforms are essentially supported on disjoint domains (in particular, \({\mathcal {G}}f_1 \overline{{\mathcal {G}}f_2}\approx 0\)). In this case we can flip the sign in front of either component and get similar phaseless observations:
On a positive note, functions of aforementioned type are the only source of instability; that is, if the spectrogram is connected, then phase information is stably determined by the phaseless observation [25, 29]. Moreover the stability is measured in terms of quantity that depends on a ”Cheeger constant” that measures the quality of the connectedness (see Remark 2.5 below).
In terms of reconstruction from phaseless Gabor measurements, to the best of our knowledge there is only one result into this direction at this moment in time. For signals residing in the shift-invariant space generated by a Gaussian, Grohs and Liehr [26] establish an explicit inversion formula and prove that its discretization leads to a stable reconstruction method under suitable connectedness conditions. While we do not remove the connectedness constraint, we would like to stress that the results we present here do not require any hypothesis on the structure of the signal to be reconstructed, which is a major novelty in the field.
Advertisement
Escudero et al. [16] consider the problem of locating the positions of the zeros of the Bargmann transform, which is closely related to our problem as Gabor and Bargmann transform coincide up to normalization (and due to the fact that the Bargmann transform is an entire function, and thus essentially determined by its roots).
Finite-dimensional variants of the STFT phase retrieval problem (also called “Coded Diffraction Pattern” often shortened as CDP measurement model) have also been investigated extensively [2, 4, 15, 20, 30, 35]. However, we are not aware of results that quantitatively relate solutions of those finite dimensional analogues to the solution of a continuous one. A major contribution of this paper is therefore that we establish such quantitative estimates in our case.
As outlined above absence of uniqueness and uniform stability is a real issue for the problem at hand. Furthermore, any practical implementation is restricted to process a finite amount of data (in particular, \(\Omega \) finite) while the problem itself is infinite dimensional. Thus, it is inevitable to compromise on the original objective of actually constructing the left inverse \(\mathfrak {L}\) of
It is therefore the aim of this article to identify a map \(\tilde{\mathfrak {L}}:{\mathbb R}^\Omega \rightarrow L^2({\mathbb R})\) which serves as an approximate left inverse of \(\mathcal {A}\).
1.2 Contribution
In this paper we propose an algorithmic solution to compute an approximate left inverse \(\tilde{\mathfrak {L}}\). More specifically, the algorithm takes spectrogram samples as input, i.e.,
with \(\Omega \subseteq {\mathbb R}^2\) finite, and aims to reconstruct f up to a multiplicative constant of unit modulus. Our method is based on solving two convex programs (CP) both of which can actually be formulated as semidefinite programs (SDP). For the reader who is not so familiar with convex optimization, the prototype of a SDP has the form
with \((A_k)_{k=0}^M\) a family of Hermitian matrices, \(\langle A,B\rangle _F= {{\,\textrm{tr}\,}}(B^H A)\) is the Frobenius inner product and \((b_k)_{k=1}^M\subseteq {\mathbb R}\). We refer to the survey article by Vandenberghe and Boyd [39] on semidefinite programming and highlight the following snippet from the abstract of the aforementioned article to partly explain the popularity of SDP.
”Although semidefinite programs are much more general than linear programs, they are not much harder to solve.”
Further, the case where the constraints are inequalities \(\langle X,A_k\rangle _F \ge b_k\) also fits in this framework. We point out that it often makes sense to soften the constraints by replacing \(\langle X,A_k\rangle _F = b_k\) by \(|\langle X,A_k\rangle _F-b_k|\le \varepsilon \) with \(\varepsilon \) a positive tolerance parameter, for example when the system is over-determined or in the presence of noise. A SDP of the above type can be easily set up and solved using the CVXPY package in Python.
The reconstruction scheme is accompanied by numerical analysis. Our results guarantee that the proposed method is accurate within the stable regime (that is, if the spectrogram exhibits sufficient connectivity) and in the presence of noise, presuming that sufficient data is provided (i.e., \(\Omega \) is rich enough). Thus, our algorithm joins the rank of provably convergent semi-definite programming-based methods for phase retrieval problems such as the famous ’PhaseLift’ and ’PhaseCut’ algorithms. We point out that – in contrast to the aforementioned contributions – our results hold in a purely deterministic context and also provide solutions to a continuous problem rather than to a discrete anaogue (the CDP measurement model).
1.3 Main Ideas
Before providing some explanation of our approach we introduce the number
The square lattice with mesh size \(\mathfrak {a}\) will be denoted by \(\Lambda =\mathfrak {a}{\mathbb Z}^2\). It is important to keep in mind that in practice \(\Lambda \) needs to be finite so as to deal with finite dimensional objects. Later on, \(\Lambda \) will be further intersected with a rectangle of finite length but, in this introductory part this aspect will however be neglected for the sake of simplicity of the argument as will be the potential influence of noise. As indicated below (Fig. 1), the proposed method consists of three sub-steps. The underlying ideas behind the individual pieces will be discussed next.
1.3.1 Reduction to Discrete Phase Recovery Problem
Given \(f\in L^2({\mathbb R})\) we introduce a sequence \(v=(v_\lambda )_{\lambda \in \Lambda } \in {\mathbb C}^\Lambda \) by virtue of
Even though the index set \(\Lambda \subseteq {\mathbb R}^2\) has a two-dimensional appearance we think of it as a one-dimensional vector. As it is well-known from Gabor frame theory, the infinite vector v carries all the relevant information of the function f to be reconstructed [13, 33, 36, 37]. More explicitly, the relationship between v and f can be described in terms of an expansion formula involving the so-called dual window \(\psi \in L^2({\mathbb R})\):
Thus, it suffices to recover the vector v up to a global phase factor.
1.3.2 Lifting
The term ’lifting’ refers to the idea of embedding the vector space \({\mathbb C}^\Lambda \) into the matrix space \({\mathbb C}^{\Lambda \times \Lambda }\). We consider the infinite matrix \(v\otimes \overline{v}\in {\mathbb C}^{\Lambda \times \Lambda }\), which is defined by
as an alternative representation of the vector v. The matrix entry \((v\otimes \overline{v})_{\lambda ,\lambda '}\) contains the information of relative phase change between the locations \(\lambda \) and \(\lambda '\). Note that \(v\otimes \overline{v}\) determines v uniquely up to a multiplicative constant of unit modulus – \({\textrm{span} \,}\{v\}\) is the solitary nontrivial eigenspace of the matrix \(v\otimes \overline{v}\). Thus, this approach neatly fits into the scope of phase retrieval. The lifting trick is well-known within the phase retrieval community and has proven to be quite useful, for instance to turn a given phase retrieval problem (which is non-convex by nature) into a convex problem by considering a relaxation in the matrix space.
1.3.3 Matrix Estimator
We are left with the problem of determining the entries of the matrix \(v\otimes \overline{v}\) given spectrogram data \(({\mathcal {S}}f(\omega ))_{\omega \in \Omega }\). In the best case (that is, if \(\Omega \supseteq \Lambda \)) we can directly observe the diagonal entries of the matrix as
while no off-diagonal entries are provided. To go beyond the diagonal we construct a predictor function V based on holomorphically extending the spectrogram. In Sect. 6.1 we prove that there exist \(L:{\mathbb R}^2\times {\mathbb R}^2\rightarrow {\mathbb C}^2\) and \(Q:{\mathbb R}^2\times {\mathbb R}^2 \rightarrow {\mathbb C}\) such that
where \(F:{\mathbb C}^2\rightarrow {\mathbb C}\) is the unique entire extension of \({\mathcal {S}}f\) (that is, \(F\in \mathcal {O}({\mathbb C}^2)\) and \(F\big |_{{\mathbb R}^2}={\mathcal {S}}f\)). Assuming that F is known, it follows from (1.2) that
correctly predicts the entries of the matrix \(v\otimes \overline{v}\). In practice it is not viable to identify F exactly. To obtain a feasible variant of the idea we will pick a finite-dimensional Ansatz space \(\{F_A,\,A\succeq 0\}\) whose members are parameterized by positive definite matrices of a fixed size. Further, we formulate a semi-definite program over \(\{A\succeq 0\}\), the convex cone of positive definite matrices such that its solution \(A_*\) gives rise to an entire function \(F_{A_*}\) which serves as an approximation for F. The resulting predictor is then
Analyzing the accuracy of the estimator reveals that \(\tilde{V}(\lambda ,\lambda ')\) is a reliable approximation for \((v\otimes \overline{v})_{\lambda ,\lambda '}\) if
with \(r>0\) a suitable threshold parameter, whereas accuracy cannot be guaranteed when \(|\lambda -\lambda '|>r\). Hence, \(\tilde{V}\) can only be used to predict relatively few matrix entries.
1.3.4 Matrix Completion
That matrix completion techniques can be quite useful in the context of solving phase retrieval problems and is well documented [7]. For the problem at hand, to infer the remaining entries of the matrix \(v\otimes \overline{v}\) we exploit the structural knowledge we have on that matrix: \(v\otimes \overline{v}\) has rank one and is positive semi-definite. We attack the matrix completion problem by solving the convex relaxation
Find \(Y\succeq 0\) s.t. \(|Y_{\lambda ,\lambda '}-\tilde{V}(\lambda ,\lambda ')| \le \tau \), for all \((\lambda ,\lambda ')\in \mathcal {P}\),
with \(\tau >0\) a suitable threshold. Quite conveniently, the relaxation can be formulated in terms of a SDP. We pick up a result due to Demanet and Jugnon [14] (and establish a slight modification) to show that the convex relaxation is guaranteed to yield an accurate result provided that the data exhibit sufficient connectivity. The precise quantitative concept to measure connectivity is the spectral gap of the (vertex-weighted) graph Laplacian associated to f (see Definition 2.4).
Fig. 1
Schematic decomposition into the respective substeps in the construction of the approximate left inverse \(\tilde{\mathfrak {L}}\) of \(\mathcal {A}\)
×
1.4 Outline
The remainder of this article is organized as follows. Section 2 contains the precise definition of the reconstruction scheme as well as statements concerning the accuracy of the algorithm, which constitute the main results of this article. In Sect. 3 we present some numerical experiments in order to verify the capabilities of the proposed algorithmic solution empirically. Section 4 forms a collection of required preliminary material. In Sect. 5 we discuss an inexact version of the dual window reconstruction formula (1.1). Section 6 is concerned with a detailed analysis of the estimator \(\tilde{V}\). Finally, Sect. 7 contains the proof of the first main theorem, Theorem 2.8.
2 Algorithm and Results
2.1 The Reconstruction Scheme
This section is concerned with presenting the algorithmic solution of the phase retrieval problem at hand. As the method is quite involved we need to introduce a few objects and quantities first.
Throughout \(\mathfrak {a}=\frac{1}{\sqrt{2}}\). The signal to be reconstructed is represented by \(f\in L^2({\mathbb R})\). \(\Gamma \subseteq \mathfrak {a}{\mathbb Z}^2\) denotes a finite subset of the lattice. Furthermore, we denote the cone of positive definite matrices by \(\mathfrak {A}_+(\Gamma )=\{A\in {\mathbb C}^{\Gamma \times \Gamma }:\, A\succeq 0\}\).
We will write \(\mathcal {O}({\mathbb C}^d)\) for the space of holomorphic functions of d complex variables of the full space \({\mathbb C}^d\) (\(d=2\), for most of the paper). We will not use advanced multivariable complex analysis and only basic knowledge of one complex variable analysis is sufficient for reading this paper.
Definition 2.1
(Ansatz function) Let \(\mathcal {J}=\begin{pmatrix} 0& 1\\ -1& 0 \end{pmatrix}.\). Given \(\lambda ,\mu \in {\mathbb R}^2\), let
where \(C(\lambda ,\mu ):= \exp \left\{ -\frac{\pi }{4} \big |\lambda -\mu \big |^2 +\pi i (\lambda _1\lambda _2-\mu _1\mu _2)\right\} \). To every \(A\in {\mathbb C}^{\Gamma \times \Gamma }\) we associate the entire Ansatz function \(F_A\) defined by
We shall denote the canonical dual window of the Gabor frame \((\pi (\lambda )\varphi )_{\lambda \in \mathfrak {a}{\mathbb Z}^2}\) by \(\psi \). Further, we point out that an explicit formula for \(\psi \) is available, see Eq. (4.9).
With this we are ready to formulate the reconstruction scheme which is handed noisy spectrogram samples \( \sigma _\omega \approx {\mathcal {S}}f(\omega ), \omega \in \Omega \) with \(\Omega \subseteq {\mathbb R}^2\) finite and aims to reconstruct f up to a global phase factor.
Algorithm 1
Reconstruction procedure
×
Remark 2.3
(CPs are SDPs) Both, the CP in step 1 as well as the CP in step 2 can actually be recast into a SDP.
Indeed, to see this for the CP in step 1 we refer to Lemma 6.8, where we explicitly construct for any given point \(z=(x,y)\in {\mathbb R}^2\), a hermitian matrix \(W_z\in \mathfrak {A}_+(\Gamma )\) with the property
Furthermore, we add a single element ’\(\infty \)’ to the index set \(\Gamma \) and denote \(\tilde{\Gamma }=\Gamma \cup \{\infty \}\). With this, we introduce a slack variable \(\mu \in {\mathbb R}\) by considering
For the corresponding statement with regards to the CP in step 2, we refer to Lemma 4.1, where we explicitly construct, given an arbitrary point \(p\in \Lambda \times \Lambda \), a pair of hermitian matrices \(E_p^r\) and \(E_p^i\) with the property that for each \(A\in \mathfrak {A}_+(\Lambda )\),
$$ \langle A, E_p^r\rangle _F = {\text {Re}}(A_p), \quad \text {and} \quad \langle A, E_p^i\rangle _F = {\text {Im}}(A_p). $$
is also a solution of the CP (2.2). Finally, we point out that off-the-shelf solvers (in particular, the CVXPY package which was used to produce the experiments carried out in Sect. 3) deal with these aspects automatically and internally. For example, to solve the CP (2.1) we simply declared \(\max _{\lambda \in \Gamma } A_{\lambda ,\lambda }\) as the objective function to be minimized.
2.2 Reconstruction of Gabor Coefficients
The intermediate objective of the algorithm is concerned with the reconstruction of the coefficients \(\{{\mathcal {G}}f(\lambda ),\lambda \in \Lambda \}\). Before we present the result which guarantees the accuracy of this first component of the method we again have to settle some terminology.
First we attach a graph to the provided spectrogram samples in order to specify the relevant quantity of connectivity.
Definition 2.4
(Signal associated graph and spectral gap) Given a triple consisting of \(f\in L^2({\mathbb R})\), a finite set \(\Lambda \subseteq \mathfrak {a}{\mathbb Z}^2\) and \(r>0\), the signal associated graph \(G=(V,E,\alpha )\) is the vertex weighted graph with vertex set \(V=\Lambda \), edge set E defined by
$$ (u,v)\in E \quad \Leftrightarrow \quad 0<|u-v|<r, $$
and vertex weights \(\alpha _v={\mathcal {S}}f(v)\), \(v\in V\). Let \(0=\lambda _1\le \lambda _2 \le \ldots \) denote the eigenvalues of the Laplacian1 of G. The spectral gap is defined as
$$ \lambda _2(f,\Lambda ,r):= \lambda _2. $$
Remark 2.5
(Spectral gap and connectivity) We recall in Lemma 4.15 that G is connected if and only if there is an actual spectral gap, i.e. if \(\lambda _2\) is strictly positive. This suggests to conceive the spectral gap \(\lambda _2\) as a concept to quantify the connectivity of G: the larger the spectral gap of the Laplacian, the more connected is G.
A formal approval of this intuition has been established by Cheeger [9, pages 195–200] in the context of Riemannian geometry by relating the spectral gap to a geometric invariant coined the Cheeger constant. Subsequently, respective results have also been encountered in the world of graph theory [11].
In the remainder we will stick to index sets \(\Lambda ,\Gamma ,\Omega \) of a rather simple form. Namely, we assume that these sets arise as the intersection between a centered rectangle with a square lattice. Precisely, given numbers \(T,S,R,s>0\) we set
The parameters need to be chosen reasonably for the reconstruction method to succeed. For this purpose we introduce the following technical notion.
Definition 2.6
Let \(f\in L^2({\mathbb R})\). Given parameters \(T,S,R,r,s,\varepsilon ,\varepsilon >0\) let \(\Lambda ,\Gamma ,\Omega \) be defined as in (2.1), (2.2) and (2.3), respectively.
We say that the parameters are well calibrated if all of the following relations hold true:
(Number of required samples) The parameters T, S, r are considered to be fixed numbers. Typically \(r\in [0,2]\), and expressions involving r in (2.4)–(2.7) may just be regarded to be constants. The parameter \(\varepsilon \) plays the role of the desired error margin. From a qualitative perspective (neglecting numerical constants) we get that the required number of samples in the “well-calibrated regime” is roughly (asymptotically for \(\varepsilon \) close to 0)
The first main result states that the proposed method recovers the samples \(({\mathcal {G}}f(\lambda ))_{\lambda \in \Lambda }\) accurately under appropriate assumptions and reads as follows.
Theorem 2.8
Let \(f\in L^2({\mathbb R})\) be such that \(\Vert {\mathcal {S}}f\Vert _{L^\infty }\le 1\).2 Suppose that \(T,S,R,r,s,\varepsilon ,\varepsilon '\) are well calibrated. Let \(\sigma \in {\mathbb R}^{\Omega }\) be such that
We would like to stress that the main contribution of this paper is that our algorithm offers predictable error bounds. According to Theorem 2.8 the accuracy of the prediction is driven by two quantities:
– The noise level \(\varepsilon \). Our analysis unfortunately leads to a rather pessimistic power \(\varepsilon ^{1/4}\), but our numerical simulation below show that the algorithm performs better. It is also likely that, under some signal models, the dependence on noise can be brought down to a more acceptable level.
which depends on the connectivity of the support of \({\mathcal {G}}f\) through the associated graph. The statement is empty if \(\lambda _2(f,\Lambda ,r)=0\), i.e., if the associated graph is not connected. For a generic \(f\in L^2({\mathbb R})\), we have that \({\mathcal {G}}f\) does not vanish on the finite set \(\Lambda \). Thus – provided that \(r\ge \mathfrak {a}\) – in general (for generic f) we have that the graph is indeed connected.
Over all, our estimates are all conservative, both in the dependence on noise level, on connectivity and with respect to the numerical constants appearing here (that we decided to keep explicit rather than O’s). These are the outcomes of the proofs, the fact that many steps were needed, none of which is totally optimal. Though slight improvements would be possible, this would have been at the expense of the length and readability of the paper. As far as we are aware of, for all phase retrieval algorithms that are currently available, either they offer no convergence guaranties or convergence only occurs with high probability and, in all cases, the provable estimates are far too pessimistic and involve large numerical constants (often so bad that their explicit value is not given). However, running those algorithms, the real situation is often much better than what the mathematics is able to predict. Unfortunately, this drawback is also present here.
Remark 2.9
(On the choice of r) The performance of the reconstruction method may crucially depend on the choice of r. Given f, the optimal3 choice is
It is important to note that \(r_*(f)\) can be computed if samples \(({\mathcal {S}}f(\lambda ))_{\lambda \in \Lambda }\) are given: the Laplacian (and therefore also the spectral gap \(\lambda _2(f,\Lambda ,r)\)) depends solely on \(({\mathcal {S}}f(\lambda ))_{\lambda \in \Lambda }\) and moreover as \(r\mapsto \lambda _2(f,\Lambda ,r)\) is piecewise constant, it suffices to check a finite number of candidates r (cf. Figure 2 for the three smallest choices).
Note also that r intervenes in two ways in \(C_{stab}(f,r)\): for small r, the dominating term will be the factor \(\lambda _2(f,\Lambda ,r)^{-1}\) while for large r, the exponential term \(e^{0.84r^2}\) will take over. In practice, we have not found it usefull to go beyond \(r=2\) (Fig. 3).
Fig. 2
Three different choices for the parameter r. For the values \(r=\mathfrak {a}=\frac{1}{\sqrt{2}}\) (left), \(r=1\) (center) and \(r=\sqrt{2}\) (right) the blue vertex in the middle has 4, 8 and 12 neighbors, respectively
Fig. 3
We compare two different functions: one having a spectrogram which is connected (left) and the other one consisting of two connected components (right). The white points indicate the finite lattice \(\Lambda \subseteq \mathfrak {a}{\mathbb Z}^2\). The graph in the center shows the dependence of \(C_{stab}(f,r)\) on the parameter r for each of the functions. These computations suggest that the performance of the algorithm will benefit from choosing the parameter r to be relatively large (\(r=\sqrt{5/2}\)) in the disconnected case, while it is favorable to pick \(r=1\) in the connected case
×
×
Remark 2.10
(Comparison with existing stability results) Next we put the above result into perspective with earlier stability results for the Gabor phase retrieval problem. More specifically, with the outcomes of [25, 29], where it has been shown that on a domain \(\Omega \subseteq {\mathbb R}^2\) on which \(|{\mathcal {G}}f|\) is connected, phase information is stably encoded in the phase-less data \(|{\mathcal {G}}f|\). Even though inequality (2.8) is of discrete type, qualitatively it is very much reminiscent of the aforementioned results: The results in the continuous setting quantify connectivity in terms of the Poincaré constant which is known to coincide with the spectral gap of the associated diffusion operator, a generalization of the Laplacian. We refer to [5, Section 2] for more details. Similarly to this – albeit on a purely discrete level – we employ the spectral gap of the corresponding graph Laplacian. To state the obvious, the substantial advantage of the novel results of this article is that we have a mean to actually recover phase information.
2.3 Reconstruction from Incomplete Gabor Coefficients
Given \(\Lambda \subseteq \mathfrak {a}{\mathbb Z}^2\) we formally define an operator \(\mathcal {R}_\Lambda :{\mathbb C}^\Lambda \rightarrow L^2({\mathbb R})\) by
where \(\psi \) denotes the dual window of the Gabor frame \((\pi (\lambda )\varphi )_{\lambda \in \mathfrak {a}{\mathbb Z}^2}\). If \(\Lambda =\mathfrak {a}{\mathbb Z}^2\) and \(c=({\mathcal {G}}f(\lambda ))_{\lambda \in \Lambda }\) the sum in (2.9) converges unconditionally in \(L^2({\mathbb R})\) and exactly reconstructs f, that is, \(f=\mathcal {R}_\Lambda (c)\), cf. Section 4.3.
In practice, one only has a finite number of possibly noisy samples at one’s disposal. It is the purpose of the next result to control the reconstruction error in this inexact setting. As before, given \(T,S>0\) let us denote
Given the fact that only a limited amount of samples is available (particularly, \(\Lambda \subseteq [-T,T]\times \mathbb {R}\)) one cannot expect that f is to be accurately reconstructed outside the interval \([-T,T]\). Moreover, given that there is no information about large frequencies (\(>S\)) it is to be expected that the reconstruction is accurate only if the function to be reconstructed is relatively smooth.
Before we state the result we introduce two quantities. Given \(f\in L^2({\mathbb R})\) we use
The quantity \(\kappa _S(f)\) may be understood as a measure of smoothness of f: If \(\kappa _S(f)\) is negligibly small, then all Gaussian localizations \(\{f e^{-\pi (\cdot -x)^2}, x\in {\mathbb R}\}\) are close to bandlimited (with bandwidth 2S), and vice versa.
The second main result reads as follows.
Theorem 2.11
Let \(T,S\in \mathfrak {a}{\mathbb N}\), let \(0<\tau <T\). For all \(f\in L^2({\mathbb R})\) and for all \(c\in {\mathbb C}^\Gamma \) it holds that
For the proof of Theorem 2.11 we refer to Sect. 5. There are three different terms contributing to the upper bound on the reconstruction error.
The first term is simply the noise on the provided samples.
Recall that \(\Lambda \subseteq [-T,T]\times [-S,S]\). This means that the reconstruction method only draws on Gabor samples located in the strip \({\mathbb R}\times [-S,S]\) while neglecting information from samples outside the strip. Morally, if there is only little contribution from samples outside the strip (that is, if \(\kappa _S(f)\) is small) then neglecting these samples does not affect the accuracy too much.
The decisive factor in the third term is the exponential \(e^{-\frac{\pi }{2} (T-\tau )}\). Since we want to accurately reconstruct on the interval \((-\tau ,\tau )\) we require that \(T>\tau \); clearly, the reconstruction accuracy will benefit from being fed more information (i.e., increasing T). The estimate shows that the improvement on the corresponding error term is exponential with respect to the offset \(T-\tau \).
2.4 Reconstruction from Spectrogram Samples
The content of the main result is to clarify under which conditions and in which sense \(f_*\), the output of Algorithm 1 is a useful estimate for f.
Theorem 2.12
Let \(T,S\in \mathfrak {a}{\mathbb N}\) and let \(0<\tau <T\). Furthermore, suppose the assumptions of Theorem 2.8. Then it holds that \(f_*\), the output of Algorithm 1 satisfies that
To establish (2.12) take \(v\in {\mathbb R}\) arbitrary. Since \({\mathcal {G}}f(v,\cdot )={\mathcal {F}}\{f e^{-\pi (\cdot -v)^2}\}\) it follows from Plancherel’s formula that
we then get for any \(x\in {\mathbb R}\) (by applying (2.13) to \(v=x+u\)) that
$$\begin{aligned} \int _{\mathbb R}|f(t)|^2 e^{-\pi (t-x)^2}\,\text{ d }t&= 2 \int _{\mathbb R}|f(t)|^2 \left( \int _{\mathbb R}e^{-2\pi (t-x-u)^2-2\pi u^2}\,\text{ d }u \right) \,\text{ d }t\\&= 2 \int _{\mathbb R}\left( \int _{\mathbb R}|f(t)|^2 e^{-2\pi (t-x-u)^2}\,\text{ d }t \right) e^{-2\pi u^2}\,\text{ d }u\\&\le (2S+\kappa _S(f)^2) \cdot 2 \int _{\mathbb R}e^{-2\pi u^2}\,\text{ d }u\\&= \sqrt{2} (2S+\kappa _S(f)^2) \end{aligned}$$
As x was arbitrary, taking square roots implies (2.12), and we are done.
3 Numerical Simulations
First of all, the purpose of the present section is to demonstrate empirically the aptitude of the proposed reconstruction algorithm. Furthermore, we aim to develop some sense for the choice of parameters of the scheme.
We consider the reconstruction of certain random signals. The precise random model is the following: Given \(a>0\) and \(\Xi \subseteq a{\mathbb Z}^2\) finite, we pick a vector \((c_\lambda )_{\lambda \in \Xi } \in {\mathbb C}^\Xi \) at random, with each component chosen independently and according to the uniform distribution on the complex unit disk \(\mathbb {D}\subseteq {\mathbb C}\). The resulting function is then given by
where \((\eta _\lambda )_{\lambda \in \Omega }\) are independently and identically distributed random variables according to uniform distribution on the interval \([-\nu ,\nu ]\). The location of coefficients to be reconstructed is in accordance with the position of generating coefficients (Fig. 4).
Fig. 4
In order to make sure that the reconstructed coefficients \(({\mathcal {G}}f(\lambda )_{\lambda \in \Lambda }\) carry all the relevant information of f in an interval around zero, \(\Xi \) is chosen in such a way that in the vertical direction it does not exceed the zone occupied by \(\Lambda \). This means if \(\Xi =a{\mathbb Z}^2\cap ([-T',T']\times [-S',S'])\) and \(\Lambda = \mathfrak {a}{\mathbb Z}^2\cap ([-T,T]\times [-S,S])\), then \(S\ge S'\)
Fig. 5
The top plot shows \(|{\mathcal {G}}f|\) for a randomly generated f. The white points indicate the set \(\Omega \), i.e., the position of the samples fed into the scheme. The red rectangle indicates the zone in which samples of \({\mathcal {G}}f\) will be reconstructed: all points of \(\mathfrak {a}{\mathbb Z}^2\setminus \Lambda \) are on the red dashed line or outside of the rectangle. The two plots below compare real and imaginary part of f and its reconstruction \(f_*\), respectively. In order to make these two functions comparable f is multiplied by an appropriate constant phase factor first. The table at the bottom summarizes a couple of relevant specifications of the experiment carried out
×
×
The main difference between the two experiments (Fig. 5) is the interval on which f is reconstructed. On the left, reconstruction is fairly accurate on \([-3,3]\), while on the right hand side, we obtain a good approximation for the larger interval \([-4.5, 4.5]\). This comes at the price of having to solve a problem of higher complexity. The bottleneck of the reconstruction scheme lies in identifying \(A_*\), the parametrizing matrix of the (approximate) entire extension of the spectrogram \({\mathcal {S}}f\) (step 1 of Algorithm 1). In this step, one needs to solve a SDP where the variable is a matrix of dimension \(|\Gamma | \times |\Gamma |\). Hence, a moderate enlargement of the set \(\Lambda \) results in substantial extra computational expenses. Comparing the two present examples we register roughly a quadruplication of computation time.
Remark 3.1
(Practicability) The numerical results demonstrate that the reconstruction algorithm performs pretty well in a practically useful parameter range as compared to the range of parameters where the error estimates are theoretically guaranteed (i.e. well calibrated configuration). We have to stress though that the results are very much a product of a trial and error process regarding the selection of suitable parameters. For several instances the algorithm would terminate early as either of the convex problems handed to the solver is found to be infeasible.
We are aware, that from a practical viewpoint there is definitely room for improvement: There is a significant gap between the range of practically viable parameters and the notion of well-configured parameter configurations. A more sophisticated approach on how to choose the parameters involved (other than trial and error) would be of great practical relevance. Moreover, it would be highly desirable to have a variant of the scheme which is robust w.r.t. aforementioned infeasibility issues. For example, a viable pathway could be to incorporate the constraints into the objective function instead of using hard constraints. While this would remove the issue of infeasible programs appearing in the reconstruction procedure right away, it would also require separate numerical analysis tailored to the reformulation of the algorithm. As the focal point of this paper lies on the mathematical analysis of the proposed scheme we do not aim to further expand on this topic.
4 Terminology and Prerequisites
4.1 General Notation
Throughout we will understand \({\mathbb R}^d\) as a subspace of \({\mathbb C}^d\). Given a vector \(p\in {\mathbb C}^d\) its Euclidean length is denoted by |p| and we use the notation \(p^2=p\cdot p = \sum _{k=1}^d p_k^2\). Real and imaginary parts are taken componentwise, i.e.,
If \(\Lambda \) is a finite index set with \(N=|\Lambda |\) its cardinality, we can identify \({\mathbb C}^{\Lambda \times \Lambda }\) with \({\mathbb C}^{N\times N}\), the vector space of \(N\times N\) square matrices. Linear algebra concepts such as matrix products, matrix–vector multiplication, trace, positive (semi)-definiteness, eigenvalues and eigenvectors are well-defined in \({\mathbb C}^{\Lambda \times \Lambda }\) and will be denoted by the common notation. Moreover, we introduce the Frobenius inner product on \({\mathbb C}^{\Lambda \times \Lambda }\) by
Recall that \(\langle X, Y \rangle _F\) is real-valued (resp. non-negative) if X, Y are hermitian (resp. positive definite). Given vectors \(a,b\in {\mathbb C}^\Lambda \), we use tensor notation \(a\otimes b\) to denote the outer vector product, that is,
Let \(k,\ell \in \{1,\ldots ,N\}\). and let \(e_k, e_\ell \) denote the k-th and \(\ell \)-th canonical basis vector in \({\mathbb C}^N\). Then, for every \(X\in {\mathbb C}^{N\times N}\) hermitian,
For \(F\in \mathcal {O}({\mathbb C})\) an entire function we will employ the notation \(F^*\) to denote the function defined by \(F^*(z)= \overline{F(\bar{z})}\). Note that \(F^*\in \mathcal {O}({\mathbb C})\). Given \(G\in \mathcal {O}({\mathbb C}^d)\), we define the maximum modulus function by
will be useful on a number of occasions. All values of this function used here have been computed using the EllipticTheta[3,z,q] function on www.wolframalpha.com, in particular, we will use
We denote \(g(x) = e^{-\frac{\pi }{b} x^2}\) and note that \(\hat{g}(\omega ) = \sqrt{b} e^{-b\pi \omega ^2}\). Applying Poisson summation formula allows us to rewrite
The central object of this paper is the following.
Definition 4.3
(Short-time Fourier transform) The short-time Fourier transform(STFT) of \(f\in L^2({\mathbb R}^d)\) with window function \(g\in L^2({\mathbb R}^d)\) is defined by
the Gaussian, we use the notation \({\mathcal {G}}f = {\mathcal {V}}_\varphi f\) and call \({\mathcal {G}}f\) the Gabor transform. The squared modulus of the Gabor transform is called the spectrogram and will be denoted by \({\mathcal {S}}f\), that is, \({\mathcal {S}}f(x,\omega )=|{\mathcal {G}}f(x,\omega )|^2\).
We devote the remainder of this section to collect a couple of properties and statements involving the STFT and refer to Gröchenig’s textbook [22] for more details.
Note that, from Cauchy-Schwarz, we get \(\Vert {\mathcal {S}}f\Vert _{L^\infty }\le \Vert f\Vert _{L^2}^2\). Given \(\lambda =(a,b)\),
$$ {\mathcal {G}}[\pi (\lambda )f](x,\omega ) =e^{-2\pi i a (\omega -b)} \cdot {\mathcal {G}}f (x-a,\omega -b), $$
in particular, \(|{\mathcal {G}}[\pi (\lambda )f](p)| = |{\mathcal {G}}f(p-\lambda )|\). The Gabor transform of the Gaussian \(\varphi \) is given by
where \(c_k>0\) is chosen in such a way that \(\Vert h_k\Vert _{L^2}=1\). Then, \((h_k)_{k\in {\mathbb N}}\) forms an orthonormal basis of \(L^2({\mathbb R})\). The Bargmann transform maps the Hermite functions to monomials of the corresponding degree, that is,
Equation (4.3) implies that Fourier transform of the spectrogram has Gaussian decay. The following lemma reveals that this is still the case after applying a Gaussian cut-off to the spectrogram.
Lemma 4.4
Let \(f\in L^2({\mathbb R})\), then it holds for all \(\tau \in {\mathbb R}^2\) that
Since we can always consider \(\pi (-\tau )f\) instead of f we may assume w.l.o.g. that \(\tau =0\). First we write f in the Hermite basis \(f=\sum _{k\ge 0}\langle f,h_k\rangle h_k\) so that
It remains to establish a pointwise bound for \({\mathcal {V}}_\gamma \gamma \). Note that it follows from (4.6) (replace z by qz and take roots on both sides) that
This paragraph is concerned with discretization properties of the STFT. We refer to textbooks of Gröchenig [22] and Christensen [10] for a comprehensive account of this topic including the collection of statements below.
A family of vectors \((f_i)_{i\in I}\subseteq \mathcal {H}\) with \(\mathcal {H}\) a Hilbert space is called a frame if there exist constants \(0<A\le B\) such that
The maximal A and the minimal B to satisfy the above condition are called frame constants. Given a frame \((f_i)_{i\in I}\) the frame operator defined by
is well-defined, bounded, invertible, self-adjoint and positive. Moreover, the family \((S^{-1}f_i)_{i\in I}\) forms a frame with frame constants \(B^{-1}, A^{-1}\). The frame \((S^{-1}f_i)_{i\in I}\) is called the dual frame.
We consider function systems of the form \(\Phi =(\pi (\lambda )\varphi )_{\lambda \in \Lambda _{a,b}}\), with \(\varphi \) the Gaussian, \(\varphi (x)=2^{1/4}e^{-\pi x^2}\), \(\Lambda _{a,b}=a{\mathbb Z}\times b{\mathbb Z}\) a lattice, \(a,b>0\) discretization parameters. In this case, \(\Phi \) forms a frame for \(L^2({\mathbb R})\) if and only if \(ab<1\). By the definition of the Gabor transform the frame inequality can be written in the following way
The canonical dual of the frame \(\Phi \) has Gabor structure as well and is given by \((\pi (\lambda )\gamma )_{\lambda \in \Lambda _{a,b}}\) with \(\gamma = S^{-1}\varphi \) and the reconstruction identity
holds true, where the sum converges unconditionally in \(L^2({\mathbb R})\).
For the case of integer redundancy – which means that the parameters of the underlying lattice \(a{\mathbb Z}\times b{\mathbb Z}\) satisfy that \((ab)^{-1} \in \{2,3,4,\ldots \}\) – Janssen computed several Gabor frame related quantities explicitly [32, section 6]. In the sequel, we will only consider the case
which falls in this setting. In principle, other configurations could also be used in our approach. However, the above is somehow the canonical choice in the sense that \(\Lambda _\mathfrak {a}\) is the sparsest possible square lattice within the setting of Janssen’s results.
For the present situation, Janssens’s results imply the following. The lower and upper frame bound of \((\pi (\lambda )\varphi )_{\lambda \in \Lambda }\) are given by
while \(\Vert {\mathcal {G}}\psi \Vert _{L^1({\mathbb R}^2)}\le 1.23\).
Remark 4.7
Recall that \(\Vert {\mathcal {G}}\psi \Vert _{L^1({\mathbb R}^2)}\) is the norm of \(\psi \) in the so-called Feichtinger algebra\(\mathcal {S}_0\) which is also the modulation space\(M_1\). The fact that \(\Vert {\mathcal {G}}\psi \Vert _{L^1({\mathbb R}^2)}<+\infty \) follows from [24, Theorem 1.2]. We here compute an explicit bound.
Proof
Since the operator norm of the inverse of the frame operator \(S^{-1}\) is bounded from above by the reciprocal of the lower frame bound, we get
Next, we deal with the sum in the denominator of \(c_k\). Note that if \((a_n)_{n\in {\mathbb N}}\) is a non-increasing sequence of positive numbers, then \(\sum _{n=0}^\infty (-1)^n a_n \ge a_0- a_1\). Since \(n\mapsto (n+\frac{1}{2})e^{-\pi (n+\frac{1}{2})^2}\) is monotonically decreasing for \(n\ge 0\) we get a lower bound for the denominator in (4.10):
The product of the constants in front of the sum is bounded above by 0.67. Clearly, the sum is even with respect to t. Therefore, we can replace t by |t| and further estimate
where \(p(x) = 2x^2-x= 2 \left( x-\frac{1}{4} \right) ^2 -\frac{1}{8}\). The function \(\sum _{k\in {\mathbb Z}} e^{-\pi p(\cdot -k)}\) coincides up to a translation with
we get \(\Vert {\mathcal {G}}[\pi (\lambda )\varphi ]\Vert _{L^1({\mathbb R}^2)}=\Vert {\mathcal {G}}\varphi \Vert _{L^1({\mathbb R}^2)}=2\). It follows from [32, formulas (6.10) and (6.11)] that
Finally, we will also need two simple lemmas. The first one deals with Bessel-bounds for the systems \(\{\pi (\lambda )\psi \}_{\lambda \in \Lambda }\) and \(\{\pi (\lambda )\varphi \}_{\lambda \in \Lambda }\).
Lemma 4.8
For all \(c=(c_\lambda )_{\lambda \in \Lambda } \in \ell ^2(\Lambda )\) it holds that
which implies that \(B'\le 18.04\). It follows from [10, Proposition 11.5.2] that \(B'\) is an upper frame bound for \((\pi (\lambda )\psi )_{\lambda \in \Lambda }\). Moreover, [10, Theorem 3.2.3] implies that
which finishes the proof of the second inequality.
To prove the first inequality, recall that the upper frame bound for the original frame \((\pi (\lambda )\varphi )_{\lambda \in \Lambda }\) is given by
$$ B= 2 \vartheta _3(0,e^{-\pi })^2 < 1.54^2, $$
so that we can proceed as above.
Finally, we also have:
Lemma 4.9
Let \(s>0\) and let \(g(x):= e^{-2\pi x^2}\). Then it holds that \((T_{s\ell }g)_{\ell \in {\mathbb Z}}\) forms a Bessel sequence with
The famous sampling theorem attributed to Shannon, Whittaker and Kotelnikov asserts that a bandlimited function can be reconstructed given samples on the lattice \(\frac{1}{b}{\mathbb Z}^d\) by virtue of the formula
The series converges rather slowly due to the slow decay of the \({{\,\textrm{sinc}\,}}\), which can be a disadvantage especially for numerical purposes. By oversampling the function one can get an improvement on the convergence.
Lemma 4.10
Let \(b>0\) and \(0<h<1/b\). Moreover, let \(\eta \in L^1({\mathbb R}^d)\) be a non-negative function such that
Suppose that \(\psi \in C({\mathbb R}^d)\) is such that \(\psi (\xi )=1\) for \(\xi \in [-\frac{b}{2},\frac{b}{2}]^d\) and \(\psi (\xi )=0\) for \(\xi \notin [-\frac{1}{2\,h},\frac{1}{2\,h}]^d\), then it further holds that
The statement follows now from \(2ch=\frac{1}{2}(1+hb)\).
We will also need an approximate sampling result for almost bandlimited functions.
Lemma 4.11
Let \(s>0\), let \(F\in L^2({\mathbb R}^2)\) and suppose that there exist \(K,C>0\) such that \( |\widehat{F}(\xi )| \le K e^{-C|\xi |^2}\), \(\xi \in {\mathbb R}^2\). Then it holds that
which is the projection of F onto \(PW_b({\mathbb R}^2)\). Furthermore, let \(h=\frac{1}{2b}=s\) and \( \eta =\chi _{[-\frac{1}{2},\frac{1}{2}]^2} *\chi _{[-\frac{1}{2},\frac{1}{2}]^2}. \) Notice that \(\eta \in C({\mathbb R}^2)\) is non-negative and \(\displaystyle \int _{{\mathbb R}^2} \eta (x)\text{ d }x=1\). We apply Lemma 4.10 to \(F_b\): By taking into account that
$$ c=\frac{1}{4}\left( \frac{1}{h}+b\right) = \frac{3}{4} b \quad \text {and}\quad q = \frac{1}{4}\left( \frac{1}{h}-b\right) = \frac{1}{4} b $$
where \(\rho (x):=\frac{9}{16} \cdot {{\,\textrm{sinc}\,}}^2\left( \frac{x}{4\,s}\right) \cdot {{\,\textrm{sinc}\,}}\left( \frac{3x}{4\,s}\right) .\) We apply the triangle inequality and get
It remains to bound the last term involving \(\rho \). To do this note that the univariate \({{\,\textrm{sinc}\,}}\) satisfies the pointwise bound \(|{{\,\textrm{sinc}\,}}(x)| \le \frac{1.2}{1+|x|}\). As a consequence,
4.5 Controlling Holomorphic Functions in Terms of their Boundary Values
We begin with recalling a classical result from complex analysis.
Theorem 4.12
(Hadamard’s Three Line Theorem) Suppose that f is bounded on the strip \(\{x+iy:\, 0\le y\le b\}\) and holomorphic in the interior. Let \(m_f(t):= \sup _{x\in {\mathbb R}} |f(x+it)|\). Then it holds for all \(t\in [0,b]\) that
When \(d=1\), i.e. F is a function of one complex variable, \(M_F(t)=\max \bigl (m_F(t),m_F(-t)\bigr )\) and Hadamard’s Three Line Theorem is easily seen to be also valid with \(M_F\) replacing \(m_F\). We will require a version of this fact for several complex variables for which we did not find a convenient reference:
Lemma 4.13
Suppose that F(z) is bounded on \(\{x+iy\in {\mathbb C}^d: |{\text {Im}}(y)|\le b\}\) and holomorphic in the interior. It holds for all \(t\in [0,b]\) that
We are going to use this inequality in the following way: the function F we will consider belongs to some class of holomorphic functions for which an upper bound of \(M_F(t)\) is known. Then if \(M_F(0)\) is small, \(M_F(0)\le \varepsilon \), we obtain that \(M_F(t)\le M_F(b)^{\frac{t}{b}}\varepsilon ^{1-\frac{t}{b}}\) which shows propagation of smallness away from \({\mathbb R}^d\).
Proof
The statement is trivial if \(t\in \{0,b\}\) is one of the endpoints. Let us fix \(t\in (0,b)\) and pick an arbitrary \(\zeta \in {\mathbb C}^d\) with the property that \(|{\textrm{Im} \,}(\zeta )|=t\). It suffices to show that
which is bounded on the strip \(\{z:\, 0 \le {\textrm{Im} \,}(z) \le b\}\), holomorphic in the interior and satisfies \(f(it)=F(\zeta )\). Moreover, if \(z=x+i0\) is real-valued we have that \(|f(z)|\le M(0)\) and if \(z=x+ib\) lies on the top boundary of the strip then
As opposed to the standard notion of a weighted graph where the edges are furnished with weights, the case where vertices are weighted seems to be scarcely considered. One exception in the literature is the paper by Chung and Langlands [12]. We follow the introductory part of their paper to get familiar with the concept of vertex-weighted graphs.
We begin with an undirected graph \(G=(V,E)\) which we assume to be finite and have no self-loops. If vertices u, v are neighbors (that is, if \((u,v)\in E\)) we will simply write \(u\sim v\). Let us further assume that to each vertex \(v\in V\) there is an associated weight denoted by \(\alpha _v\ge 0\). The Laplacian of the vertex-weighted graph \(G=(V,E,\alpha )\) will be denoted by \(\mathcal {L}^G\) and is defined by the matrix
To G one then associates an unweighted graph \(G'=(V,E')\) with \(E'\) defined by
$$ (u,v)\in E' \quad \text{ if } \text{ and } \text{ only } \text{ if } \quad (u,v)\in E \quad \text {and}\quad \alpha _u \alpha _v >0. $$
We will say that the vertex weighted-graph \(G=(V,E,\alpha )\) is connected if the unweighted graph \(G'=(V,E')\) is connected in the usual sense.
Lemma 4.15
Let \(G=(V,E,\alpha )\) be a vertex-weighted graph, let \(\mathcal {L}^G\) be its Laplacian, and let \(N=|V|\). Then it holds that \(\mathcal {L}^G\) is positive semi-definite with eigenvalues \(0=\lambda _1\le \lambda _2\le \ldots \le \lambda _N\). Furthermore, it holds that
In particular, G is connected if and only if \(\lambda _2>0\).
Proof
The proof is mainly a reproduction of arguments from [12]. We assume w.l.o.g. that \(V=\{1,\ldots ,N\}\). A function on V is thus a vector \(f\in {\mathbb C}^N\) that we endow with its usual \(\ell ^2\)-norm \(\Vert (f_1,\ldots ,f_N)\Vert ^2=\displaystyle \sum _{j=1}^N|f_j|^2\) and the associated scalar product. Further, define a matrix B on \(V\times E\) by
and it follows that indeed \(BB^*=\mathcal {L}^G\), which implies that \(\mathcal {L}^G\succeq 0\). In particular, \(\mathcal {L}^G\) has an orthonormal basis of eigenvectors and the corresponding eigenvalues are all non-negative, \(0\le \lambda _1\le \lambda _2\le \ldots \le \lambda _N\).
Next consider the vector \(\psi =(\sqrt{\alpha _1},\ldots ,\sqrt{\alpha _N})^T\) and notice that, for \(k\in \{1,\ldots ,N\}\) we have that
So \(\psi \) is an eigenvector for the eigenvalue \(\lambda _1=0\).
To prove the last part, let us assume that all the weights \(\alpha _i\) are strictly positive for now. Let us denote \(W={{\,\textrm{diag}\,}}(\alpha _i)\) and, let L be defined by virtue of
Let us denote the double sum in the last line by S. Since we know that the whole expression is non-negative, and thus in particular real-valued we get that
The general case, where some of the weights are allowed to vanish then follows from a continuity argument.
Let G be connected so that \(\alpha _j\alpha _k>0\) when \(j\sim k\) and assume towards a contradiction that \(\lambda _2=0\). Then it follows that a minimizer g of the above problem satisfies
and must thus be a multiple of \((1,\ldots ,1)^T\). This contradicts the constraint \(\sum _j g_j\alpha _j=0\). Hence connectedness of G implies \(\lambda _2>0\).
On the other hand, if G is disconnected, then there exists a non-trivial component \(\emptyset \subsetneq A \subsetneq V\) and one can construct an admissible g by setting \(g_i=1\) for \(i\in A\) and \(g_j=-b\) for \(j\in V\setminus A\) where b satisfies
which achieves that the ratio vanishes and therefore, that \(\lambda _2=0\).
4.7 Rank One Matrix Completion
Matrix completion is concerned with determining a matrix X given only some of its entries. Clearly, this requires some prior knowledge on the structure of the matrix to be recovered. We consider here the case where \(X\succeq 0\) is positive semi-definite and has rank (at most) one. That is, X is of the form
$$ X = \textbf{x}\otimes \bar{\textbf{x}} = \textbf{x}\textbf{x}^H, $$
with \(\textbf{x}\in {\mathbb C}^d\) the generating vector. Note that \(X(i,i)=|x_i|^2\) so we assume that we know the diagonal of X. Let \(E\subsetneq \{1,\ldots ,d\}^2\setminus D\) (\(D=\{(1,1),\ldots ,(d,d)\}\)) denote the index set of the off-diagonal information on the matrix that is available. The problem we are interested in is the following:
$$\begin{aligned} \hbox {Given }\{X_{k,\ell }, (k,\ell )\in E\cup D\},\hbox { find }X\hbox { (or } \textbf{x}\hbox { up to a phase factor).} \end{aligned}$$
The purpose of this section is to present (a slight modification of) a result due to Demanet and Jugnon [14], which relates the matrix recovery problem to a vertex weighted graph associated with the restriction of X to \(D\cup E\), and reveals that any positive semidefinite matrix \(Y\succeq 0\) with
is already a good approximation for X provided that the respective graph has good connectivity as quantified by its spectral gap.
Theorem 4.16
Let \(V=\{1,\ldots ,d\}\), \(D=\{(1,1),\ldots ,(d,d)\}\) and \(E\subset (V\times V){\setminus } D\) so that (V, E) is an undirected graph with no self loops.
For \(x\in {\mathbb C}^d\setminus \{0\}\), let \(\alpha = (|x_i|^2)_{i=1}^d\), let \((V,E,\alpha )\) be the resulting vertex weighted graph and let \(\lambda _2\) denote the spectral gap of \((V,E,\alpha )\), which we assume to be \(>0\).
Let \(B=\sum _{(k,\ell )\in V^2} |\mathcal {L}^G_{k,\ell }|\), and let \(\varepsilon >0\) such that
Note that the hypothesis of this theorem do not require to know x, only to know \(x_k\overline{x_\ell }\) for \((k,\ell )\in D\cup E\). The theorem states that if we find a matrix \(Y\in {\mathbb C}^{d\times d}\), \(Y\succeq 0\) whose \((k,\ell )\) entries with \((k,\ell )\in D\cup E\) approximate well the data, then the top eigenvector provides a good approximation of x, up to a rescaling factor.
The result as well as its proof is a variation of Theorem 4 in [14]. The modification consists in how we measure certain error terms. While we use \(\ell ^\infty \)-norm in assumption (4.13), the original statement employs \(\ell ^1\)-norm at this point.
Proof
Throughout we denote \(X=xx^*\). We introduce a matrix \(L\in {\mathbb C}^{d\times d}\) by
Let \(\phi _k\in {\mathbb R}\) be such that \(x_k = |x_k|e^{i\phi _k}\), \(k\in V\) and let \(\Delta = {{\,\textrm{diag}\,}}(e^{i\phi _1},\ldots ,e^{i\phi _d}).\) Note that \(\Delta \mathcal {L}^G \Delta ^* = L\), that \(L\succeq 0\) with same eigenvalues as the Laplacian \(\mathcal {L}^G\), which we denote by \(0=\lambda _1<\lambda _2\le \ldots \le \lambda _d\). Let \(v_1,\ldots ,v_d\) be the corresponding orthonormal basis of eigenvectors of L, so that
We define for \(k=1,\ldots ,d\) numbers \( c_k:= \langle Y, v_k\otimes \overline{v_k}\rangle _F \ge 0 \) and notice that, \(\langle Y,L\rangle _F = \sum _{k=1}^d \lambda _k c_k\), and as \((v_k)_{k=1}^n\) is an o.n.b., that
i.e. \(Lx =0\). Since by assumption \(\lambda _2>0\) we conclude that \(x=e^{i\theta }|x| v_1\) for suitable \(\theta \in {\mathbb R}\).
The idea of the proof is now to show that \((c_k)_{k=1}^d\) is ’front-heavy’ in the sense that \(c_1\approx {{\,\textrm{tr}\,}}(Y)\) and \(c_2,\ldots ,c_d\approx 0\), and deduce from this that \(Y\approx X\).
Finally, we translate the above result into the context of our de-lifting task.
Corollary 4.17
Let \(f\in L^2({\mathbb R})\), let \(\Lambda \subseteq \mathfrak {a}{\mathbb Z}^2\) finite and let \(r>0\). Let \(\mathcal {L}\) denote the Laplacian of the signal associated graph, let \(B=\sum _{(u,v)\in \Lambda ^2} |\mathcal {L}_{u,v}|\), and let \(D=\{(v,v),\,v\in \Lambda \}\). Further, suppose the following two assumptions:
5 An Error Estimate for the Reconstruction from Incomplete and Noisy Gabor Coefficients
5.1 The Error Estimate
Recall that given \(T,S>0\) we denote \(\Lambda =([-T,T]\times [-S,S])\cap \mathfrak {a}{\mathbb Z}^2\), and that \(\mathcal {R}_\Lambda :{\mathbb C}^\Lambda \rightarrow L^2({\mathbb R})\) is defined by
which together with Proposition 5.1 implies the result. Let \(K,L\in {\mathbb N}\) be given by \(T=\mathfrak {a}K\) and \(S=\mathfrak {a}L\). Note that by applying Lemma 4.5 with \(r=\frac{\mathfrak {a}}{2}\) we get that, for all \(\lambda \in \Lambda '\),
where \(g_k:= \sum _{\ell \in {\mathbb Z}} {\mathcal {G}}f(\mathfrak {a}k,\mathfrak {a}\ell ) M_{\mathfrak {a}\ell }T_{\mathfrak {a}k}\psi \). Notice that each of the series converges unconditionally since it is a sub-series of an unconditionally convergent one. With this, we can write
where we have used Parseval’s relation for the \(L^2\)-norm of m and the fact that \(\dfrac{\lceil \mathfrak {a} |I|\rceil }{\mathfrak {a}}\le |I|+\dfrac{1}{\mathfrak {a}}=2\tau +\sqrt{2}\).
We will now estimate the \(\ell ^2\)-sum over \(\gamma _\ell \). To that end note that,
By adding up the three error terms (5.2), (5.3) and (5.7) we obtain the result.
6 Determining Relative Phase Changes
Suppose we are given (possibly noisy) samples of the spectrogram, that is \(({\mathcal {S}}f(\lambda ))_{\lambda \in \Omega }\) with \(\Omega \subseteq {\mathbb R}^2\) a set of sampling positions. The objective of the present section is to find a way to evaluate the tensor
If \(u=0\), we again find the spectrogram, that is, \({\mathcal {T}}_0[{\mathcal {G}}f](p) = {\mathcal {S}}f(p)\). However, the relevant case is to go beyond \(u=0\) as this is where the information of relative phase changes between points p and \(p+u\) is stored.
We dedicate Sect. 6.1 to shed some light on why \({\mathcal {E}}\) is defined the way it is and to outline the further strategy. In Sect. 6.2 we analyze certain aspects regarding the continuity of \({\mathcal {E}}\) w.r.t. the argument G. In Sect. 6.3 we discuss implications for the task of estimating relative phase changes.
6.1 Motivation and Strategy
The purpose of this paragraph is to clarify the role of the evaluation operator \({\mathcal {E}}\). First we show that the spectrogram extends to an entire function of two variables.
Then F is the entire extension of the spectrogram of f. That is to say, \(F\in \mathcal {O}({\mathbb C}^2)\) and \(F\big |_{{\mathbb R}^2}={\mathcal {S}}f\).
In the sequel, we will simply write \({\mathcal {S}}f\) instead of F.
Proof
That F is entire is obvious as it is a product of entire functions. From the relation between Gabor and Bargmann transform (4.4), it follows that for all \((x,y)\in {\mathbb R}^2\)
This implies that \(F\big |_{{\mathbb R}^2}={\mathcal {S}}f\), and we are done.
The next result describes how evaluations of the function \({\mathcal {S}}f\) relate to the Gabor transform.
Lemma 6.2
Let \(f\in L^2({\mathbb R})\) and let \({\mathcal {S}}f\) be the holomorphic extension of the spectrogram of f as given in Lemma 6.1. For all \(p,u \in {\mathbb R}^2\) it holds that
Let L and Q be defined as in Definition 2.2. With \(p=\begin{pmatrix} x\\ y \end{pmatrix}, u= \begin{pmatrix} a\\ b \end{pmatrix}\) we introduce \(\zeta := L(p,u) \in {\mathbb C}^2\). Notice that
Recall that the objective is to determine (or estimate) values of \({\mathcal {T}}_u [{\mathcal {G}}f](z)\). Assume for a moment we were given \({\mathcal {S}}f\), the holomorphic extension of the spectrogram, on all of \({\mathbb C}^2\). In this case, one simply has to plug in \({\mathcal {S}}f\) into \({\mathcal {E}}\) according to the preceding result.
In our situation however, the provided information is significantly weaker. First, we do not have direct access to \({\mathcal {S}}f\) outside of \({\mathbb R}^2\). While in theory, it is enough to know \({\mathcal {S}}f\) on \({\mathbb R}^2\) (or any open subset thereof) to determine it on all of \({\mathbb C}^2\), to perform this extension in practice is already a challenging task. To make things worse, we do not have access to \({\mathcal {S}}f\) on all of \({\mathbb R}^2\), but only to samples \(({\mathcal {S}}f(\lambda ))_{\lambda \in \Omega }\) with \(\Omega \subseteq {\mathbb R}^2\) finite. An additional difficulty is that those samples are corrupted by noise, but let us neglect this aspect for the moment.
As it turns out, \({\mathcal {S}}f\) not only extends holomorphically to \({\mathbb C}^2\), but this extension has also moderate growth with respect to the distance of a point \(z\in {\mathbb C}^2\) to \({\mathbb R}^2\). The following example demonstrates the importance of such growth in a one-dimensional setting.
Example 6.3
Let us define a family of entire functions \(F_\varepsilon \in \mathcal {O}({\mathbb C})\), \(\varepsilon >0\) by virtue of
Then, each \(F_\varepsilon \) is \(\varepsilon \)-close to the zero function on \({\mathbb R}\subseteq {\mathbb C}\), that is \( \Vert F_\varepsilon - 0\Vert _{L^\infty ({\mathbb R})}=\varepsilon . \) However, if \(z=a+ib\) with \(b>0\) we have that
which blows up if \(\varepsilon \rightarrow 0\). If we consider \(F_\varepsilon \) to be an estimator for the holomorphic extension of the zero function, we find that while approximation of the given data improves for \(\varepsilon \rightarrow 0\) the performance of the estimator degenerates.
Instead, we may look for \(F\in \mathcal {O}({\mathbb C})\) such that \(M_F\) is finite on [0, 2b]. If F is \(\varepsilon \) close to 0 on \({\mathbb R}\), i.e., \(M_F(0)\le \varepsilon \) it follows from Hadamard’s Three Line Theorem that
This suggests that for F to be a reliable estimator it is the combination of both, i) a good approximation of the zero function on \({\mathbb R}\) and ii) it has moderate growth behaviour as quantified by \(M_F\).
We can now outline the approach we take for the problem at hand. First we are going to construct a set of Ansatz functions \(\mathcal {A}\subset \mathcal {O}({\mathbb C}^2)\) obeying the following conditions
we want \(\mathcal {A}\) to be a convex set as we want to formulate a convex problem. Furthermore, to make such a problem practically feasible, \(\mathcal {A}\) must by parameterized by finite dimensional objects; in our case the cone of positive semi-definite matrices of a certain size will play the role of the parameter space.
we need to make sure that \(\mathcal {A}\) has sufficient expressive capabilities; that is, that it contains at least one function F which meets both requirements. Namely, i) approximating \({\mathcal {S}}f\) well on \(\Omega \subseteq {\mathbb R}^2\) and ii) possessing beneficial growth behaviour of the type discussed above.
we need to set up the convex problem in a way to guarantee that its solution does satisfy both of these requirements.
Once we have identified \(F\in \mathcal {A}\) with moderate growth and which approximates the samples well, say
we want to use \(\mathcal {E}[F](p,u)\) (an object which we can access) to estimate \(\mathcal {E}[{\mathcal {S}}f](p,u) = {\mathcal {T}}_u[{\mathcal {G}}f](p)\) (an object which we want to access but cannot). As \({\mathcal {E}}\) is linear, the resulting estimation error is given by \( |{\mathcal {E}}[{\mathcal {S}}f - F](p,u)|.\) An application of Hadamard’s Three Line Theorem (Lemma 4.13) would then imply that
with C(p, u) also depending on the growth behaviour of \({\mathcal {S}}f - F\). Unfortunately, we have no direct way to make sure that F is close to \({\mathcal {S}}f\) on all of \({\mathbb R}^2\), since we only have access to the values of the latter on a finite subset \(\Omega \in {\mathbb R}^2\). In the subsequent part, Sect. 6.2 we will employ sampling and cut-off arguments in order to establish an approximate version of (6.3). That is, an estimate of the form
with the error term \(\epsilon (\Omega )\) rapidly decaying as \(\Omega \) becomes richer.
6.2 Approximate Continuity of the Functional \({\mathcal {E}}\)
Throughout this section we shall employ the notation \(\gamma (z) = e^{-\frac{\pi }{8} z^2}\), \(z\in {\mathbb C}^2\). Moreover, we introduce the following subspace of entire functions
In other words, \(\mathcal {O}^\infty ({\mathbb C}^d) \) is the set of holomorphic functions that are in \(H^\infty (T_r)\) for every tube \(T_r=\{x+iy\in {\mathbb C}^d:\ |{\text {Im}}(y)|<r\}\). For \(G\in \mathcal {O}^\infty ({\mathbb C}^2)\), we define a Gaussian cut-off at \(\tau \in {\mathbb R}^2\) by
The term “Gaussian cut-off” of course refers to the restriction of \(G_\tau \) to \({\mathbb R}^2\). Note that this restriction is in \(L^1({\mathbb R}^2)\) so that its Fourier transform \(\widehat{G_\tau }\) makes sense. We are interested in functions with controlled smoothness of cut-off \(G_\tau \) and introduce
Let \(\tau =p+\frac{1}{2} u\) and consider \(G_\tau (z)= G(z)\gamma (z-\tau )\).
First we rewrite \({\mathcal {E}}[G](p,u)\) in terms of \(G_\tau \): Let L, Q be defined as in Definition 2.2. Note that \({\text {Re}}Q(p,u) = -\frac{\pi }{2} u^2\) and set
$$ \zeta _*:= L(p,u) = p + \frac{1}{2} \begin{pmatrix} 1 & -i\\ i& 1 \end{pmatrix} u. $$
Next, we apply Hadamard’s Three Line Theorem (Lemma 4.13, to be precise) to \(G_\tau \). To that end, note that \(G_\tau \in \mathcal {O}^\infty ({\mathbb C}^2)\) since \(G\in \mathcal {O}^\infty ({\mathbb C}^2)\). As \(|{\text {Im}}\zeta _*|=\frac{|u|}{2}\), we get that
The basic idea is – since \({\mathcal {S}}f\) is not directly available – to identify a suitable dummy \(F\in \mathcal {O}({\mathbb C}^2)\) in place of \({\mathcal {S}}f\), and use \({\mathcal {E}}[F]\) as an estimator for relative phase changes. This raises several questions. Most importantly, how to actually identify F and how accurate is the resulting estimator? The remainder of this paragraph is aimed at resolving these questions. To do that we first introduce a finite-dimensional cone of Ansatz functions, then formulate an associated convex problem (CP) and finally argue that the solution of this CP gives rise to an accurate estimator.
Throughout, let \(\Gamma \subseteq \mathfrak {a}{\mathbb Z}^2\) denote a finite set. The following lemma clarifies the relation between \(F_A\) and the Gabor transform.
Lemma 6.5
Let \(N=|\Gamma |\) and let \(a=(a_\lambda )_{\lambda \in \Gamma }\in {\mathbb C}^\Gamma \). The following properties hold:
i)
\(\Phi _{\lambda ,\mu }\) is the entire extension of \({\mathcal {G}}[\pi (\lambda )\varphi ]\overline{{\mathcal {G}}[\pi (\mu )\varphi ]}\). That is, for all \(p=(x,\omega )\in {\mathbb R}^2\subseteq {\mathbb C}^2\) it holds that
With \(A=a\otimes \bar{a}\) and \(f=\sum _{\lambda \in \Gamma }a_\lambda \pi (\lambda )\varphi \), we have that \(F_A\) is the entire extension of \({\mathcal {S}}f\). That is, for all \(p=(x,\omega )\in {\mathbb R}^2\subseteq {\mathbb C}^2\) it holds that
$$ F_A(p) = {\mathcal {S}}f(x,\omega ). $$
iii)
Suppose \(A\in \mathfrak {A}_+(\Gamma )\) with eigenvalues \(\alpha _1,\ldots ,\alpha _N\ge 0\) and with corresponding orthonormal basis of eigenvectors \(u_1,\ldots ,u_N\in {\mathbb C}^\Gamma \). Let
Then, \(F_A\) is the entire extension of \(\sum _{k=1}^N \alpha _k {\mathcal {S}}f_k\). That is, for all \(p=(x,\omega )\in {\mathbb R}^2\subseteq {\mathbb C}^2\) it holds that
First note that the first statement implies the second one. For this, one simply writes \({\mathcal {S}}f={\mathcal {G}}f\cdot \overline{{\mathcal {G}}f}\) and uses linearity of \(f\mapsto {\mathcal {G}}f\). The second statement then implies the third one by linearity of \(A\mapsto F_A\) once one writes \(\displaystyle A=\sum _{k=1}^N \alpha _k u_k\otimes \overline{u_k}\). Recalling (4.2), for \(\lambda =(a,b)\) we have that
which coincides with \(\Phi _{\lambda ,\mu }(z)\).
Later on we want to apply Proposition 6.4 to \(G=F_A-{\mathcal {S}}f\). Before that we show how in this case the relevant quantities appearing in the right hand side can be controlled in terms of the parameterizing matrix A.
Lemma 6.6
Let \(A\in \mathfrak {A}_+(\Gamma )\). Moreover, let
Committing a slight abuse of notation we denote the restrictions of \(F_A\), \(\gamma \) and \(\Phi _{\lambda ,\mu }\) to \({\mathbb R}^2\) by the same symbols. For the first statement, we need to show for arbitrary \(\tau \in {\mathbb R}^2\) that
As \({\mathcal {F}}[e^{-\frac{9}{8} \pi \cdot ^2}](\xi ) = \frac{8}{9} e^{-\frac{8\pi }{9} \xi ^2}\), we get that the Fourier transform of the above function is given by
is injective (but not onto!). Thus, substituting \(u=\lambda +\mu \) and \(v=\lambda -\mu \) and \(\xi ' = \mathcal {J}\xi \) allows us to estimate the above sum from above by
where we once more made use of Lemma 4.2. Plugging in \(t=2\sqrt{2} \xi '_\ell \), \(\ell \in \{1,2\}\), we obtain by combining the above estimates that
Recall that a positive definite matrix attains its maximum absolute value in the diagonal: \(\Vert A\Vert _{\max } =\max _{\lambda \in \Gamma } A_{\lambda ,\lambda }\). Finally, as
With this (and recalling that \((\lambda ,\mu )\mapsto (\lambda +\mu ,\lambda -\mu )\) is injective on \(\mathfrak {a}{\mathbb Z}^2 \times \mathfrak {a}{\mathbb Z}^2\)),
where the last inequality is again a consequence of Lemma 4.2. An analogous argument shows that the second sum in (6.8) is upper bounded by the same quantity. Hence,
expressing \(\mathcal {B}f\) in terms of \({\mathcal {G}}f\) with (4.4). But \(\Vert {\mathcal {G}}f\Vert _{L^\infty }^2=\Vert {\mathcal {S}}f\Vert _{L^\infty ({\mathbb R}^2)}\) and
Evaluation of \(F_A\) can be expressed in terms of a matrix inner product. In view of Algorithm 1 this fact is relevant in order to see that the CP in step 1 can be rephrased as a SDP as well as for the practical implementation of step 1.
Lemma 6.8
Let \(\Gamma \subseteq \mathfrak {a}{\mathbb Z}^2\) be finite, let \(p\in {\mathbb R}^2\subseteq {\mathbb C}^2\) and let \(v\in {\mathbb C}^\Gamma \) be defined by
In the following, let \(f\in L^2({\mathbb R})\) and let \(s>0\). Moreover, let \(\Omega \subseteq s{\mathbb Z}^2\) and \(\Gamma \subseteq \mathfrak {a}{\mathbb Z}^2\) be finite sets. Given \(p\in {\mathbb R}^2\), we use the notation \(W_p=v\otimes \bar{v}\) with v defined as in Lemma 6.8.
Definition 6.9
(Associated Convex Problem (ACP)) Given a triple \((f,\Gamma ,\Omega )\) as above, and a tolerance parameter \(\varepsilon >0\) we define the Admissible Set as
Solving the ACP (6.9) amounts to finding among all admissible matrices the one such that the maximum of all diagonal entries is minimal. While the admissibility condition can be simply reformulated in terms of \(F_A\), that is,
Here \(\Omega =s{\mathbb Z}^2\cap \mathcal {R}\) where \(\mathcal {R}\) is a square. The condition \(\varepsilon <e^{-1}\) ensures that \(\mathcal {A}(s,\xi )\) contains no point outside \(\mathcal {R}\)
×
Proof
We want to apply Proposition 6.4 to \(G=F_A-{\mathcal {S}}f\). According to Lemma 4.4 and Lemma 6.7, respectively we have that
Next, we provide sufficient conditions for the set of admissible matrices to be non-empty as well as an upper bound for the objective function of a minimizer.
Proposition 6.11
Let \(f\in L^2({\mathbb R})\), let \(\varepsilon \in (0,1)\), \(s>0\) and let \(\Omega \subseteq s{\mathbb Z}^2\). Moreover let \(\Gamma \subseteq \mathfrak {a}{\mathbb Z}^2\) such that
Let \(\psi \) denote the canonical dual of the Gabor frame \((\pi (\lambda )\varphi )_{\lambda \in \mathfrak {a}{\mathbb Z}^2}\). Moreover, let us define \(a\in {\mathbb C}^\Gamma \) by
i.e. \(A\in Adm_\varepsilon (f,\Gamma ,\Omega )\). It remains to show that there exists \(A\in Adm_{\frac{\varepsilon }{2}}(f,\Gamma ,\Omega )\) which further satisfies the inequality \(\max _{\lambda \in \Gamma }A_{\lambda ,\lambda }\le 1.6\), as by the triangle inequality such a matrix is then feasible for step 1.
By Proposition 6.11 (applied to \(\frac{\varepsilon }{2}\)) we only need to show that
We proceed with the proof of statement b). Let \((\lambda ,\lambda ')\in \mathcal {P}\) be arbitrary but fixed, and denote \(p=\lambda \) and \(u=\lambda '-\lambda \). According to Proposition 6.10 (with \(1.5 \varepsilon \) instead of \(\varepsilon \)), it holds that
where \(B=\sum _{(u,v)\in \Lambda } |\mathcal {L}_{u,v}|\) with \(\mathcal {L}\) the Laplacian of the signal associated graph. By the way the graph is defined, we have that the maximal degree (i.e., the maximal number of neighbors a vertex can have) is bounded from above by
In this paper, we have described the first algorithm that provides an approximate solution of the phase retrieval problem for the (continuous) Gabor transform with error bounds. More precisely, given only finite samples \(\mathcal {S}=\{|{\mathcal {G}}f(\lambda ),\lambda \in \Lambda \}|\) with \(\Lambda =\mathfrak {a}{\mathbb Z}^2\cap \mathcal {R}\), \(\mathcal {R}\) a rectangle, of the Gabor transform of some function \(f\in L^2({\mathbb R})\), our algorithm is able to reconstruct an approximation \(f_*\) of f, even if the samples are corrupted with noise. The main result in this paper is that we are able to prove that \(f_*\) is indeed an approximation of f over a large proportion of \(\mathcal {R}\), without having to impose any structural model on f, unlike previously available results. The error bound depends only on the two key expected quantities: the noise level and the connectivity of the graph of \({\mathcal {G}}f\) which is here measured through a spectral property of a finite graph generated by the data, and can thus be explicitly computed.
This work leads us to raise several questions:
– What is the sharpness of the error bounds. We have decided to give explicit values to all numerical constants and have been slightly conservative in our computations to keep them readable. They are within reasonable order though too big for practical applications. Numerical simulations lead to better errors, is there a way to significantly improve our bounds? A second factor that needs to be improved is the dependence on the noise level \(\varepsilon \). Since the error of size \(\varepsilon \) is on the squared spectrogram one should expect the reconstruction error to be of the order \(\varepsilon ^{1/2}\). In our results however, we have an extra square root as the error dependence is of the order of \(\varepsilon ^{1/4}\). The reason for this lies in the way we apply Hadamard’s Three Line Theorem. In principle, on could adapt the argument and push the power as close to 1/2 as desired. This would however cause the numerical constant to blow up. The way we apply the argument may be understood as a canonical compromise balancing the numerical constant and the power on \(\varepsilon \).
– The focus of this paper is on the proof of the error bounds. The implementation we have made here is mainly to illustrate that the algorithm actually works and that our bounds are pessimistic (which seems to be the case for most algorithms used for phase retrieval). We hope this work will trigger sufficient interest from specialists to lead to improvements in the algorithm and its implementation. In particular, we think that automatic calibration of parameters should avoid to run into feasibility issues.
– Would the addition of a particular signal model significantly improve the error bound ? E.g. does this happen if we impose f to be in some shift-invariant space like in [26, 27]?
We think that having shown that approximate reconstruction (without signal model) and based only on finite samples should trigger new hope in solving continuous phase retrieval problems via discretisations (rather than discrete analogues), despite recent rather negative results in that directions.
Acknowledgements
The authors wish to thank the anonymous referees for their careful reading of the manuscript and their comments. For M.R., this research was funded in whole or in part by the Austrian Science Fund (FWF): 10.55776/J4523. Ce travail a bénéficié d’une aide de l’État attribué à l’Université de Bordeaux en tant qu’Initiative d’excellence, au titre du plan France 2030.
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/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
the assumption that \(\Vert {\mathcal {S}}f\Vert _{L^\infty }\le 1\) is purely there for aesthetic reasons in order to keep bounds and implicit constants as simple as possible
