Efficient Computation of the Zeros of the Bargmann Transform Under Additive White Noise

The Bargmann transform of a real variable function \(f \in L^2(\mathbb {R})\) is the entire functionOriginally introduced as a link between configuration and phase space in quantum mechanics [7], the Bargmann transform was later recognized as a powerful tool in signal analysis [11] because it encodes the correlations between the signal f and the time–frequency shifts of the Gaussian function \(g(t) = \big (\tfrac{2}{\pi }\big )^{\frac{1}{4}} \,e^{-t^2}\,\):In the jargon of time–frequency analysis, the right-hand side of (1.2) is known as the short-time Fourier transform of f with Gaussian window, and measures the contribution to f(t) of the frequency y near \(t=x\).

In practice, the values of the short-time Fourier transform of a signal f are only available on (a finite subset of) a gridand possibly only approximately so due to numerical errors. The goal of Gabor analysis is to extract useful information about f from such limited measurements. Equivalently, by (1.2), the task is to capture the analytic function F given a limited number of its samples on a grid. This second point of view led to the most conclusive results in Gabor theory, such as the complete description of all grids (1.3) for which the Gabor transform fully retains the original analog signal f [11, 21, 23, 24].

While Gabor signal analysis has traditionally focused on large values of the short-time Fourier transform (1.2), recent work has brought to the foreground the rich information stored in its zeros, especially when the signal is contaminated with noise. Heuristically, the zeros of the Bargmann transform of noise exhibit a rather rigid random pattern with predictable statistics, from which the presence of a deterministic signal can be recognized as a salient local perturbation [13, 14, 16]. Remarkably, the Bargmann transform of white noise has been identified as a certain Gaussian analytic random function [5, 6], and consequently, the well-researched statistics of their zero sets [19, 22] can be leveraged in practice [15, Chapters 13 and 15], [5]. The particular structure observed in the zeros of the Bargmann transform under even a moderate amount of white noise has also been invoked as explanation for the sparsity resulting from certain nonlinear procedures to sharpen spectrograms [16], as the zeros of the Bargmann transform are repellers of the reassignment vector field [15, Chapter 12]. The practical exploitation of such insights requires an effective computational link between finitely given data on the one hand and zeros of Bargmann transforms of analog signals on the other.

Suppose that the values of the Bargmann transform F of a signal f are given on a gridand we wish to compute an approximation of \(\{F=0\}\), the zero set of F, within the squareMore realistically, we only have access to samples of F on those grid points near the computation domain, e.g., onThe inverse of the spacing of the grid, \(1/\delta \), will be called the resolution of the data.

In this article, we introduce a variant of MGN, called adaptive minimal grid neighbors (AMN). The algorithm is based on a comparison similar to (1.8) but incorporates an adaptive decision margin, that depends on the particular realization of F. While AMN has the same mild computational complexity and similar practical effectiveness as MGN, we are able to estimate the accuracy and confidence of the computation with AMN in terms of the grid resolution. In this way, we show that AMN is probably approximately correct for the signal model (1.9), in the sense that it computes the zero set with high probability up to the resolution of the data.

On the one hand, we present what to the best of our knowledge are the first formal guarantees for the approximate computation of zero sets of analytic functions from grid values. In fact, besides its main purpose of computation with specific data, the AMN algorithm offers a computationally attractive and provably correct method to simulate zero sets of the Gaussian entire function (2.10), by running the procedure with simulated inputs. On the other hand, our analysis is a first step toward understanding the performance of MGN.

We now introduce a new algorithm to compute zero sets of Bargmann transforms. Suppose again that samples of an analytic function \(F :\mathbb {C} \rightarrow \mathbb {C}\) are given on those points of the grid (1.4) that are near the computation domain (1.5), say, onFor each grid point \(\lambda \) strictly inside the computation domain, \(\lambda \in \Lambda _L= \Lambda \cap \Omega _L\), we use the neighboring sample at \(\lambda + \delta \) to compute the following comparison margin:The margin \(\eta _\lambda \) therefore depends on the particular realization of F. To motivate the definition, note that, when \(\lambda =0\), the maximum in (2.2) is taken over |F(0)| and the absolute value of an incremental approximation of \(\partial F(0)\), where \(\partial F=\frac{1}{2}(\frac{d}{dx} F-i \frac{d}{dy} F)\). The comparison margin thus incorporates the size and oscillation of F at \(z=0\). In general, \(\eta _\lambda \) has a similar interpretation with respect to the covariant derivativeand, indeed, \(\eta _\lambda \) is defined so thatThe differential operator \(\bar{\partial }^* F\) plays a distinguished role in the analysis of vanishing orders of Bargmann transforms [10, 12] because it commutes with the translational symmetries of the space that they generate (the Bargmann–Fock shifts defined in Sect. 3.2).

The first step of the algorithm selects all grid points \(\lambda \in \Lambda _L\) that pass the following comparison test:In contrast to (1.8), the comparison in (2.5) does not involve the immediate grid neighbors of \(\lambda \) but rather those points lying on the square centered at \(\lambda \) with half-side-length \(2\delta \); see Fig. 2.

(In particular, the test only involves grid points \(\mu \in \Lambda _{L+2\delta }\).) Intuitively, the larger distance between \(\lambda \) and \(\mu \) permits neglecting the error in the differential approximation (2.4).

The use of non-immediate neighbors in (2.5) introduces a certain redundancy in the selection of numerical zeros, because the comparison boxes delimited by \(\{\mu : |\lambda -\mu |_\infty = 2\delta \}\) overlap and, as a consequence, one zero of F can trigger multiple positive tests; see Fig. 3. The second step of the algorithm sieves the selected points to enforce a minimal separation of \(5\delta \) between different points. The algorithm is formally specified below.

In Sect. 5, we report on numerical experiments that compare the AMN and MGN algorithms. We also include a modified version of thresholding (ST), that uses a threshold proportional to the grid spacing and incorporates a sieving step as in AMN (while standard thresholding without sieving performs extremely poorly, as seen in Fig. 1).

The performance of AMN, MGN, and ST is first tested indirectly, by using these algorithms to simulate the zero sets of the random functions in the input model (2.9). We then compare theoretically derived statistics of the zeros of (2.9) to empirical statistics obtained from the output of AMN and MGN under various simulated realizations of (2.9).

Second, we perform a consistency experiment that aims at estimating the probability of computing a low-distortion parametrization of the zero set of F, as in Theorem 2.2. Specifically, we simulate a realization of the random input F sampled at high-resolution and use the output of AMN or MGN as a proxy for the ground truth \(\{F=0\}\). We then test the extent to which this set is captured by the output of AMN, MGN, or ST from lower resolution subsets of the same simulated data.

The performance of AMN and MGN is almost identical, although the minimal resolution at which MGN starts to perform well is slightly lower than that for AMN. (This is to be expected, as the constants 2 and 5 used in (2.7) and (2.8) are not adequate for low resolutions, cf. Remark 2.1.) Both AMN and MGN significantly outperform ST. See also Fig. 4 for an illustration.

The favorable performance of AMN is interesting also when the input is just noise, as it gives a fast and provably accurate method to simulate the zeros of the Gaussian entire function (2.10). (The simulations that we present in Sect. 5 use certain heuristic shortcuts to accelerate the simulation of the input (2.10)—see Sect. 5.1; although we do not formally analyze these, they are implicitly validated, as the simulated point process reproduces the expected theoretical statistics.)

All numerical experiments can be reproduced with openly accessible software and our code is available at https://​github.​com/​laescudero/​discretezeros. Our implementation of the Bargmann transform uses [4].

Section 3 introduces the notation and basic technical tools about analytic functions, Bargmann–Fock shifts, and their applications to random functions and their zeros. Theorem 2.2 is proved in Sect. 4, while numerical experiments are presented in detail in Sect. 5. Conclusions and outlook on future directions are discussed in Sect. 6.

For a complex number \(z=x+iy\), we use the notation \(|z|_\infty = \max \{|x|,|y|\}\), while |z| denotes the usual absolute value. The zero set of F is denoted by \(\{F=0\}\). The differential of the (Lebesgue) area measure on the plane will be denoted for short \(dm\), while the measure of a set E is |E|. With a slight abuse of notation, we also denote the cardinality of a finite set Z by \(|Z|\). Squares on the complex plane are denoted by \(Q_r(z) = \{w \in \mathbb {C}: |z-w|_\infty \le r\}\). For two nonnegative functions f, g, we write \(f \lesssim g\) if there exists an absolute constant C such that \(f(x) \le C g(x)\), for all x. We write \(f \asymp g\) if \(f \lesssim g\) and \(g \lesssim f\).

The Wirtinger derivative of a function \(F:\mathbb {C} \rightarrow \mathbb {C}\) is \(\partial F=\frac{1}{2}(\frac{d}{dx} F-i \frac{d}{dy} F)\). When we need to stress on which variable the derivative is taken we write subindices, e.g., \(\partial _w F(z,w)\).

A Gaussian entire function (see [19, Ch. 2] and [22]) is a random function \(F:\mathbb {C} \rightarrow \mathbb {C}\) that is almost surely entire, and such that for every \(z_1, \ldots , z_n \in \mathbb {C}\), \(\big (F(z_1), \ldots , F(z_n)\big )\) is a circularly symmetric complex normal vector. We will be only concerned with the random function F given in (2.9). We also use the notation (1.4), (1.5), (1.6), possibly for distinct values of L.

The analysis of the AMN algorithm is more transparent when formulated in terms of the Bargmann–Fock shifts. For a function \(F:\mathbb {C} \rightarrow \mathbb {C}\), we letThe amplitude of an entire function F is defined as the weighted magnitudeand satisfiesThe comparison margin of the AMN algorithm (2.6) can be expressed in terms of Bargmann–Fock shifts asand leads to the approximation (2.4) because(Here and throughout we write \(F'_\lambda (0)\) for \(\partial [F_\lambda ](0)\).) Similarly, in terms of amplitudes, the test (2.7) readsWith respect to the input model (2.9) we note that, if \(F^0\) is the (zero mean) Gaussian entire function with correlation kernel (2.10), then the Bargmann–Fock shifts \(F^0 \mapsto F^0_w\) preserve the stochastics of \(F^0\), as they leave its covariance kernel invariant. As a consequence, for any \(w \in \mathbb {C}\), \(F^0_w(0), \big [F^{0}_{w}\big ]'(0)\) are independent standard complex normal random variables (with zero mean and variance 1). Indeed, by the mentioned invariance it suffices to consider \(w=0\), and, in this case, \(F^0_w(0), \big [F^{0}_{w}\big ]'(0)\) are the coefficients \(\xi _0\) and \(\xi _1\) in (2.12).

The following weighted version of the minimum principle is at the core of the success of MGN and AMN.

In what follows, we derive basic facts about the input model (2.9), and always assume that (2.10) and (2.11) hold.

The following is a strengthened version of [19, Lemma 2.4.4].

It is easy to see that, almost surely, the random function (2.9) has no multiple zeros. In the analysis of the AMN algorithm, we will also need to control the occurrence of zeros that are multiple up to a certain numerical precision, in the sense that F and its derivative are simultaneously small. The following lemma is a first step in that direction, as it controls the probability of finding a grid point that is an almost multiple zero.

The following proposition is not used in the proof of Theorem 2.2, but rather as a benchmark in the numerical experiments (Sect. 5).

Let L, \(\sigma \), \(\delta \), and F satisfy the assumptions of the theorem, and denote by \(\mathrm {Z}_1\) the set produced by the AMN algorithm after the selection step. Recall that \(L \ge 1\). By choosing a sufficiently large constant in (2.14), we can assume that \(\delta \le 1/5\); otherwise, the success probability would be trivial. For the same reason, we can assume that

We let \(\gamma = 8 \sigma \) and wish to apply Lemma 3.2 with \(t=\gamma \sqrt{\log (1/\delta )}\). By (4.1),Hence, \(t \ge A\) and we can apply Lemma 3.2 to conclude thatfor all \(w \in \Omega _{L+1}\) and \(|z| \le 10\), except for an event of probability at most \(C L^2 \exp \big [ -(t-{\mathrm {A}})^2/(8\sigma ^2)\big ]\), where C is an absolute constant. Since \((t-{\mathrm {A}})^2 \ge \frac{t^2}{2}-{\mathrm {A}}^2\), we further haveSecond, we select a large absolute constant \(\kappa >1\) to be specified later, and use Lemma 3.3 withto conclude that, for each grid point \(\lambda \in \Lambda _{L+2\delta }\),except for an event with probability at most \(\lesssim L^2 \log ^2(1/\delta ) \delta ^4\).

Overall we have excluded events with total probabilityIn what follows, we show that under the complementary events the conclusions of Theorem 2.2 hold.

We claim that, by taking \(\kappa \) sufficiently large, the set \(\{F=0\} \cap \Omega _{L+2\delta }\) satisfies:Suppose that \(\zeta , \zeta ' \in \{F=0\} \cap \Omega _{L+2\delta }\) are such that \(0<|\zeta -\zeta '|_\infty \le 7 \delta \). Since \(L/\delta \in \mathbb {N}\), we can select a lattice point \(\lambda \in \Lambda _{L+2\delta }\) such that \(0 < |\lambda -\zeta | \le \delta \). We now use repeatedly (4.2) and (4.3).

First, we use (4.2) with \(w=\zeta \) and \(z=\zeta '-\zeta \), and note that \(F_\zeta (\zeta '-\zeta )=0\) and \(F_{\zeta }(0)=0\) while \(|\zeta -\zeta '| \le \sqrt{2} |\zeta -\zeta '|_{\infty } \le 7 \sqrt{2} \delta \le 10\) to obtain:Since \(\zeta \not = \zeta '\), we conclude:Second, we similarly apply (4.3) with \(w=\zeta \) and \(z=\lambda -\zeta \), to obtainCombining the last equation with (4.6) yieldsThird, we apply (4.2) with \(w=\lambda \) and \(z=\zeta -\lambda \) to obtainNote that \(|F_\lambda (0)| = \left| F_\zeta (\lambda -\zeta ) \right| \cdot e^{-\frac{1}{2} |\lambda -\zeta |^2}\). Hence, combining (4.7) and (4.8) we obtain:Since \(0<|\lambda -\zeta | \le \delta \) and \(|\zeta -\zeta '|_{\infty }\le 7\delta \), we conclude thatAssuming as we may that \(\kappa > 11\), this contradicts (4.4). Thus, (4.5) must indeed hold.

For each \(\lambda \in \Lambda _L\), we use the notationand observe that, by (4.2),Combining this with (4.3), we conclude that for \(|z|_{\infty } \le 2\delta \) and \(\lambda \in \Lambda _L\),

We show that(Recall that \(\mathrm {Z}_1\) is the set produced after the selection step, while the cube \(Q_\delta (0)\) is defined in Sect. 3.1.)

Let \(\zeta \in \Omega _L\) be a zero of F. Since \(L/\delta \in \mathbb {N}\), we can find \(\lambda \in \Lambda _L\) such that \(|\zeta -\lambda |_\infty \le \delta /2\). We show that \(\lambda \in \mathrm {Z}_1\).

Let us first prove thatSuppose to the contrary that \(|\tau _\lambda | < \kappa \gamma \sqrt{\log (1/\delta )} \cdot \delta \). We will show that this contradicts (4.4). Assuming as we may that \(\kappa \ge 1\), by (4.9),while, by (4.2),provided \(\kappa \ge \frac{1+\sqrt{2}}{2-\sqrt{2}}\). This indeed contradicts (4.4). We conclude that (4.13) holds.

Second, we show that \(\lambda \in \mathrm {Z}_1\) by showing that the test (2.7) is satisfied. By (4.10), and since \(|\zeta -\lambda |_\infty \le \delta /2\), we haveChoosing \(\kappa \ge \frac{8}{3-2\sqrt{2}}\), (4.14) and (4.13) further implyHence,Let \(\mu \in \Lambda \) be an arbitrary lattice point with \(|\mu -\lambda |_{\infty }=2\delta \). By (4.11),Together with (4.14), this impliesFinally, we use (4.13) to analyze the obtained comparison margin against (4.16):where we fixed the value of \(\kappa \) so that \(\frac{3-2\sqrt{2}}{4} \kappa - 15 \ge 0\). Therefore, the point \(\lambda \) passes the selection test (2.7) (as formulated in (3.5)), i.e., \(\lambda \in \mathrm {Z}_1\), as claimed.

We show thatLet \(\lambda \in \mathrm {Z}_1\) be a computed zero, and let us find a zero z of F with \(|\lambda -z|_\infty \le 2 \delta \). In terms of the Fock shift \(F_\lambda \), the success of the test (2.7) reads,see (3.5). For an arbitrary \(z \in \mathbb {C}\) with \(|z|_\infty = 2 \delta \), we can find a lattice point \(\mu \in \Lambda \) with \(|\mu |_\infty = 2\delta \) such that \(|z-\mu |=|z-\mu |_\infty \le \delta /2\). Hence, by (4.11),By (4.4) and (4.9), either \(|\tau _\lambda |\delta \ge \kappa \gamma \sqrt{\log (1/\delta )} \cdot \delta ^2\) or \(|F_\lambda (0)| \ge \kappa \gamma \sqrt{\log (1/\delta )} \cdot \delta ^2 \ge |\tau _\lambda |\delta \). Choosing \(\kappa \ge 88\) ensures in the first case thatand in the second caseCombining this with (4.18), we conclude thatBy Lemma 3.1, there exists \(w_\lambda \in \mathbb {C}\) with \(|w_\lambda | \le 2 \delta \) such that \(F_\lambda (w_\lambda )=0\). This means that \(z_\lambda :=w_\lambda +\lambda \) is a zero of F that satisfies \(|z_\lambda -\lambda |_\infty \le 2 \delta \), as desired.

We now look into the sieving step of the AMN algorithm and analyze the final output set \(\mathrm {Z}\).

Given \(\zeta \in \{F=0\} \cap \Omega _L\), we claim that there exists \(\lambda \in \mathrm {Z}\) such that \(|\zeta - \lambda |_\infty \le 2 \delta \). Suppose to the contrary thatBy (4.12), there exists \(\mu \in \mathrm {Z}_1\) such that \(|\zeta -\mu |_\infty \le \delta /2\). By (4.20), \(\mathrm {Z}\subsetneq \mathrm {Z}\cup \{\mu \}\). We claim that \(\mathrm {Z}\cup \{\mu \}\) is \(5\delta \)-separated. For this, it suffices to check thatIf \(\lambda \in \mathrm {Z}\), by (4.17), there exist \(\zeta ' \in \{F=0\}\) such that \(|\zeta '-\lambda |_\infty \le 2 \delta \). If \(\zeta '=\zeta \), then \(|\zeta -\lambda |_\infty \le 2 \delta \), contradicting (4.20). Thus, \(\zeta \not = \zeta '\), while, \(\zeta ' \in \mathrm {Z}+Q_{2\delta } \subset \Omega _{L+2\delta }\). Hence, we use (4.5) to conclude thatThus, the set is \(5\delta \)-separated:contradicting the maximality of \(\mathrm {Z}\). It follows that a point \(\lambda \in \mathrm {Z}\) such that \(|\zeta - \lambda |_\infty \le 2 \delta \) must exist. We choose any such point, and define \(\Phi (\zeta ) = \lambda \).

By construction, the map \(\Phi \) satisfies (2.15). We now show the remaining properties. To show that \(\Phi \) is injective, assume that \(\Phi (\zeta )=\Phi (\zeta ')\). Then, by (2.15),Hence, by (4.5), we must have \(\zeta =\zeta '\).

Finally, assume that \(\lambda \in \mathrm {Z}\cap \Omega _{L-2\delta }\) and use (4.17) to select a zero \(\zeta \in \{F=0\}\) such that \(|\zeta -\lambda |_\infty \le 2 \delta \). Then \(\zeta \in \Omega _L\), and, by (2.15),As \(\lambda , \Phi (\zeta ) \in \mathrm {Z}\) and \(\mathrm {Z}\) is \(5\delta \)-separated (see (2.8)), we conclude that \(\lambda =\Phi (\zeta )\), as claimed.

This concludes the proof of Theorem 2.2. \(\square \)

We first discuss how to simulate samples from the input model (2.9). To make simulations tractable, we introduce a fast method to draw samples of the Gaussian entire function \(F^0\) given by (2.10) on the finite grid (1.6). The method is based on the relation between the Bargmann transform and the short-time Fourier transform (1.2) and amounts to discretizing the underlying signal f.

We fix \(L>0\), \(T>0\), and \(\delta > 0\). For convenience, we further let \(\sigma = 1\) and assume that \(T\delta ^{-1}\) is an integer. Recall that we also assumed that \(L\delta ^{-1}\) is an integer.

To model a discretization of \(\mathcal {N}\), we take i.i.d. noise samples in the interval \([-T-L, T+L] \subseteq \mathbb {R}\) spaced by a distance \(\delta \). More specifically, we consider a random vector \(w=(w_{-(T+L)\delta ^{-1}}, \ldots , w_{(T+L)\delta ^{-1}})\), where the elements \(w_{s} \sim \mathcal {N}_\mathbb {C}(0, \delta )\) are independent, i.e., \(\mathbb {E}[w_s \overline{w_{s}}]=\delta \), and \(\mathbb {E}[w_s \overline{w_{s'}}]=0\) for \(s \not = s'\). Here, \(w_{s}\) can be interpreted as an integration of \(\mathcal {N}\) over the interval \([\delta s, \delta (s+1)]\).

Let \(f^1:\mathbb {R} \rightarrow \mathbb {C}\), \(\varphi = g|_{[-T,T]}\) the restriction of \(g(t) = (\tfrac{2}{\pi })^{\frac{1}{4}} \,e^{-t^2}\) to the compact support \([-T, T]\) and definefor \(k,j \in \{-L\delta ^{-1}, \dots , L\delta ^{-1}\}\). The mean of \(\widehat{H}\) is given byand approximates the integralwith \(x= \delta k\) and \(y= \delta j\). Furthermore, the covariance of \(\widehat{H}\) isFor small \(\delta \) and sufficiently large T, this is an approximation of the integralwith \(x= \delta k\), \(y= \delta j\), \(u= \delta k'\), and \(v= \delta j'\). Therefore, if we take T large enough so that we can ignore the numerical error introduced by the truncation of the normalized Gaussian window g, we obtain in (5.1) a random Gaussian vector whose covariance structure approximates the right-hand side of (5.2) on the grid \(\Lambda _L\), provided that \(\delta \) is small.

To obtain a vector whose covariance structure approximates (2.10), we proceed as follows. By conjugating z in (5.1) and multiplying by the deterministic factor \(e^{-i x y}\), we obtain an approximate sampling of (2.9) with weight \(e^{-\frac{1}{2} |z|^{2}}\):for \(z=\delta k + i \delta j\). We carry out all computations with the weighted function (5.3), as the unweighted version can lead to floating point arithmetic problems. Note that, for a grid point \(\lambda \), the comparison margin (2.6) can be expressed in terms of \(e^{-\frac{1}{2}|\, \cdot \,|^{2}} F(\,\cdot \,)\) as

As a first test, we simulate random inputs from the model (2.9), as specified in Sect. 5.1, apply the above-described three different algorithms, and test whether this process faithfully simulates the zero sets of the random function (2.9). To this end, we estimate first or second order statistics on the computed zero sets by averaging over several realizations of (2.9), and compare them to the corresponding expected values concerning the zero sets of (2.9).

Having tested the statistical properties of the computed zero sets under the input model (2.9), we now look into the accuracy of the computation for an individual realization F. We aim to test the existence of a map as in Theorem 2.2, that assigns true zeros to computed ones with small distortion and almost bijectively. As a proxy for the (unavailable) ground truth \(\{F=0\}\), we will use the output of AMN from data at very high resolution (computations with MGN yield indistinguishable results). We thus conduct a consistency experiment, where the zero set of the same realization of F is computed from samples on grids of different resolution, and the existence of a map as in Theorem 2.2 between both outputs is put to test.

Suppose that samples of a function F are simulated on a high-resolution grid \(\Lambda _L\) with spacing \(\delta =\delta _{\text {Hi}}\) and restricted to the low-resolution grid \(\Lambda _L\) with spacing \(\delta =\delta _{\text {Lo}}\) by subsampling. We compute \(\widetilde{Z}_{}^{\delta _{\text {Hi}}}\subseteq \Omega _{L-1}\) from the high-resolution data using AMN, and \(\widehat{Z}_{}^{\delta _{\text {Lo}}}\subseteq \Omega _{L-1}\) from the low-resolution data, using one of the algorithms described in Sect. 5.2.2.

Second we construct a set \(U \subseteq \widetilde{Z}_{}^{\delta _{\text {Hi}}}\) and a map \(\phi :U \rightarrow \widehat{Z}_{r}^{\delta _{\text {Lo}}}\) with the following greedy procedure:

The resulting function \(\phi \) is injective and satisfiesWe say that the computation of \(\widehat{Z}_{r}^{\delta _{\text {Lo}}}\) was certified to be accurate ifIn this case, the map \(\phi \) satisfies properties analogous to the ones in Theorem 2.2. Conceivably, other such maps may exist even if the one constructed in the greedy fashion fails to satisfy (5.14). We define the following computation certificate:The experiment to estimate failure probabilities as a function of the grid resolutions is fully specified as follows. We consider the input model (2.9) with \(\sigma =1\). We choose \(F^1\) from Table 2 and rescale it so that \({\mathrm {A}}= \sup _{\zeta \in \mathbb {C}} e^{-\frac{1}{2} |\zeta |^2}|F^1(\zeta )| \) holds for the signal intensities \({\mathrm {A}}=1\) and 100. We fix \(L>0\) and \(\delta _{\text {Hi}}>0\) and let \(\widehat{F}_{1}^{\delta _{\text {Hi}}}, \ldots , \widehat{F}_{R}^{\delta _{\text {Hi}}}\) be R independent realizations of samples of (2.9) on a grid \(\Lambda _L\) with resolution \(\delta =\delta _{\text {Hi}}\), simulated as in Sect. 5.1. These are then subsampled j times with (5.8) yielding \(F_{r}^{\delta _{k}} = \mathcal {S}^{(k)}(F_{r}^{\delta _{\text {Hi}}})\), \(1 \le k \le j\).

We use AMN with input \(F_{r}^{\delta _{\text {Hi}}}\) to obtain a set \(\widetilde{Z}_{r}^{\delta _{\text {Hi}}}\). Further, for each \(1 \le k \le j\), we use each of the algorithms \(M = \text {AMN, MGN, or ST}\) with input \(F_{r}^{\delta _k}\) to obtain sets \(\widehat{Z}_{r,M}^{\delta ^k}\). Finally, we compute all the certificates \(\mathcal {M}(\widetilde{Z}_{r}^{\delta _{\text {Hi}}}, \widehat{Z}_{r,M}^{\delta _k})\) and average them over all realizations to obtain the following estimated upper bound for the failure probability of the method M with grid spacing \(\delta =\delta _k\):We present in Table 3 values obtained for \(p(\delta _k,M)\) for a resolution starting as high as \(\delta _{\text {Hi}}=2^{-9}\), with a truncation of the window g at \(T=6\), in the target domain \(\Omega _{L-1}\) for \(L=7\), and \(R=1000\) realizations of a zero-mean \(F\). We also present the results for \(F^1\) as in Table 2, rescaled to achieve a signal intensity \({\mathrm {A}}=1\) or \({\mathrm {A}}=100\). We see that both AMN and MGN deliver very low failure probabilities (with MGN slightly outperforming AMN at lower resolutions). In contrast, ST delivers large failure probabilities even at high resolution.