Nathanaël Munier
email: nathanael.munier@ens-rennes.fr

Emmanuel Soubies

Pierre Weiss

The MLE is a reliable source: sharp performance guarantees for localization problems

Single source localization from low-pass filtered measurements is ubiquitous in optics, wireless communications and sound processing. We analyse the performance of the maximum likelihood estimator (MLE) in this context with additive white Gaussian noise. We derive necessary conditions and sufficient conditions on the maximum admissible noise level to reach a given precision with high probability. The two conditions match closely, with a discrepancy related to the conditioning of a noiseless cost function. They tightly surround the Cramér-Rao lower bound for low noise levels. However, they are significantly more precise to describe the performance of the MLE for larger levels. As an outcome, we obtain a new criterion for the design of point spread functions in single molecule microscopy.

B Proof of

Theorem 2.1 19 B.1 Establishing the Cramér-Rao lower-bound . . . . . . . . . . . . . . . . 19 B.2 Necessary and sufficient condition for attainment . . . . . . . . . . .

Introduction

Many measurement devices can be modeled by a convolution with the impulse response h of the system followed by a sampling step at some locations z 1 , . . . , z M ∈ R D . A signal u : R D → R with D ∈ N therefore yields a measurement vector y ∈ R M of the form

y m = (u ⋆ h)(z m ) + ε m , (1)
where ε = (ε 1 , . . . , ε M ) is a perturbation modeling noise on the system. A situation of major interest in applications is that of single source localization. This corresponds to assuming that u reads

u = δ x, (2)
where x ∈ R D is the source location. Assuming that h ∈ C 0 (R D ), the model (1) yields

y m def = h(z m -x) + ε m . (3)
The aim of this paper is to analyze the performance of maximum likelihood estimators to recover x from the sole knowledge of the kernel h and the vector y.

We work under what is possibly the simplest possible setting, by assuming that the noise is white and Gaussian, i.e., ε ∼ N (0, σ 2 Id). In that case, the maximum likelihood estimator reads *

x ∈ argmin

x∈R D ℓ ε (x) with ℓ ε (x) def = 1 2 ∥h(Z -x) -h(Z -x) -ε∥ 2 2 . ( 4
)
The computation of x requires solving a non-convex optimization problem. This can be done, for instance, using nonlinear programming techniques. The experiments led in this paper were conducted using multiple Newton methods initialized with a fine grid. The final location with the minimal value was then used to approximate x. This setting is obviously idealized. More realistic situations could include multiple sources with unknown weights and suffering from different sources of noise. Yet, it is at the heart of many engineering issues and we tackle a really basic, yet seemingly unexplored problem.

Applications Our main motivation is related to single molecule localization microscopy [START_REF] Betzig | Imaging intracellular fluorescent proteins at nanometer resolution[END_REF][START_REF] William | Optical detection and spectroscopy of single molecules in a solid[END_REF]. This technology was awarded the 2014 Nobel prize in chemistry. It made it possible to break the Abbe diffraction limit so as to reach nanometric resolution. It consists in sequentially activating and localizing fluorescent molecules with a sub-pixel accuracy. There, the setting where only a few scattered sources are activated at a time and are well "separated" is of importance in fixed-cell imaging. This motivates the analysis of the considered single-source model. It is worth mentioning that similar issues appear for the localization of sounds (microphone), stars (radiotelescope) or phones (wireless communications). Left: the empirical standard deviation using the MLE (blue stars) coincides with the square root of the Cramér-Rao lowerbound (see [START_REF] Bredies | Inverse problems in spaces of measures[END_REF] for its expression) for low noise regimes. In high noise regimes, we observe a significant discrepancy. Right: realizations of the vector y for different noise levels. The green and red bars correspond to the true location x and the estimated one x respectively. Note that y-axis is different in the four graphs on the right.

The Cramér-Rao lower-bound and its limits It has been the subject of numerous theoretical and applied studies in the past 50 years. In particular, the intrinsic performance limits of localization algorithms have been studied using the celebrated Cramér-Rao lower-bound [START_REF] Calyampudi | Linear statistical inference and its applications[END_REF]. This bound provides a theoretical limit on the best precision achievable in average with respect to the noise realizations. In optics, it is now used massively to characterize the performance of optical systems [START_REF] Bobroff | Position measurement with a resolution and noise-limited instrument[END_REF][START_REF] Thompson | Precise nanometer localization analysis for individual fluorescent probes[END_REF][START_REF] Ober | Localization accuracy in single-molecule microscopy[END_REF][START_REF] Marie D'avigneau | Limits of accuracy for parameter estimation and localization in single-molecule microscopy via sequential monte carlo methods[END_REF] as well as a baseline to estimate the quality of algorithms [START_REF] Sage | Super-resolution fight club: assessment of 2d and 3d single-molecule localization microscopy software[END_REF]. It can also serve as an optimization criterion to design new efficient point spread functions [START_REF] Fournier | On the single point resolution of on-axis digital holography[END_REF][START_REF] Shechtman | Optimal point spread function design for 3d imaging[END_REF].

In order to motivate our study, let us start with a numerical experiment. In Fig. 1, we compare the empirical precision of the maximum likelihood estimator to the Cramér-Rao lower-bound. We observe that both coincide for low noise regimes, and then significantly deviate. This illustrates the fact that the Cramér-Rao bound is somewhat insufficient to explain the performance of the MLE.

Contributions and outline

The main outcomes of our study are a set of necessary and sufficient conditions to reach a given localization accuracy r with a given probability. Fig. 2 illustrates our findings. The heat map in this graph reflects the probability of localizing a Dirac mass with a precision r for a standard deviation σ. A clear phase transition appears: above a certain threshold, the probability of detection becomes overwhelming. The phase transition clearly happens around the Cramér-Rao bound in the low noise (or high precision) regime and then significantly deviates. The upper and lower bounds we obtain in this paper clearly circumscribe the phase transition * .

Our results based on concentration inequalities also explain this transition behavior from a theoretical standpoint.

Our main conclusions are as follows:

(i) In general it is not true that the MLE attains the Cramér-Rao lower-bound, even asymptotically (i.e., σ → 0). However, it becomes true under explicit identifiability hypotheses.

(ii) We provide explicit necessary and sufficient conditions for the global minimizer x to satisfy ∥x -x∥ 2 ≤ r in Section 4. The two conditions match for a specific kernel, showing the tightness of our bounds.

(iii) In addition, these conditions also match the Cramér-Rao bound asymptotically when σ, r → 0. For an arbitrary r, the bounds clearly indicate that Cramér-Rao is not accurate anymore and shed new light on the geometry of the localization problem.

(iv) We believe that this work opens new avenues for the field of PSF engineering. If we can choose the kernel h, it suggests new optimization criteria to obtain the "best" possible performance.

Notation Throughout the paper, x ∈ R D denotes the maximum likelihood estimator and x ∈ R D the true location to be estimated. Assuming that h is of class C 2 , we let ∂ d h denote the d-th partial derivative of the impulse response (PSF) h. Moreover, we let h ′ (x) = (∂ 1 h(x), . . . , ∂ D h(x)) T denote the gradient of h at x ∈ R D . Similarly, we let h ′′ (x) ∈ R D×D denote the Hessian of h at x ∈ R D . For a matrix A ∈ R M ×N , we let λ min (A) (resp. λ max (A)) denote its smallest (resp. largest) singular value, ∥A∥ 2→2 denote its spectral norm and ∥A∥ F = Tr(A * A) denote its Frobenius norm. Given two functions a, b we will write a ≲ b if there exists a constant c > 0 not depending on a and b such that for all x, a(x) ≤ c b(x).

To keep notation concise, we introduce the set of sampling points Z = (z 1 , . . . , z M ) and use the following shorthand notation

h(Z -x) def = (h(z 1 -x), . . . , h(z M -x)) ∈ R M h ′ (Z -x) def = (h ′ (z 1 -x), . . . , h ′ (z M -x)) ∈ R D×M h ′′ (Z -x) def = (h ′′ (z 1 -x), . . . , h ′′ (z M -x)) ∈ R D×D×M . We let L 2 (R D ) denote the set of squared integrable functions. For f, g ∈ L 2 (R D ), we let ⟨f, g⟩ L 2 (R D ) def = f (x)ḡ(x) dx (5)
denote the usual scalar product on L 2 (R D ). For two vectors u, v ∈ C N , we set

⟨u, v⟩ def = 1≤n≤N u n vn . (6)

A brief tour of existing performance bounds

Cramér-Rao lower-bound and variants In our context, applying Theorem 3.1 in [START_REF] Kay | Fundamentals of statistical signal processing: estimation theory[END_REF] yields the following result.

Theorem 2.1 (The Cramér-Rao lower-bound). If ε ∼ N (0, σ 2 Id) and h ∈ C 1 (R D ), then any unbiased estimator x of x satisfies:

E ∥x -x∥ 2 2 ≥ CR σ with CR σ def = σ 2 D 2 ∥h ′ (Z -x)∥ 2 F . ( 7
)
In addition, there exists an estimator achieving the above lower-bound if and only if the dimension D = 1 and h is an affine non-constant function.

Proof. The proof is post-poned to Appendix B.

While the first part of the theorem is well known (e.g. [START_REF] Ober | Localization accuracy in single-molecule microscopy[END_REF]), we found no reference stating the second. It shows that the Cramér-Rao bound fails to describe the performance of localization algorithms in general. Yet, the experiment in Fig. 1 shows a close match with the experimental points in the low noise regime.

This phenomenon was explained in [START_REF] Naftali | Necessary conditions for a maximum likelihood estimate to become asymptotically unbiased and attain the cramer-rao lower bound. part i. general approach with an application to time-delay and doppler shift estimation[END_REF][START_REF] Renaux | On the highsnr conditional maximum-likelihood estimator full statistical characterization[END_REF]. There, it was shown that under some technical assumptions, the MLE provides a performance asymptotically similar to the Cramér-Rao lower-bound for σ → 0. Hence, the Cramér-Rao lower-bound is indeed a useful tool for small noise levels, but fails to describe the best possible performance for arbitrary noise levels.

Therefore, various authors proposed improved bounds depending nonlinearly on σ 2 , especially in the context of array processing [START_REF] Edward W Barankin | Locally best unbiased estimates[END_REF][START_REF] Chazan | Improved lower bounds on signal parameter estimation[END_REF][START_REF] Weiss | Fundamental limitations in passive time delay estimation-part i: Narrow-band systems[END_REF]. For instance, we refer the reader to the excellent summary in [START_REF] Weiss | Fundamental limitations in passive time delay estimation-part i: Narrow-band systems[END_REF]Fig.3] for more details.

The theoretical bounds obtained in these works have revealed insufficiently precise for some practical applications. This led researchers to derive more heuristic but tighter approximations of the mean square error. The general idea is to describe the curvature of the log-likelihood beyond the origin to reach a more global description [START_REF] Harry | Detection, estimation, and modulation theory, part I: detection, estimation, and linear modulation theory[END_REF][START_REF] Athley | Threshold region performance of maximum likelihood direction of arrival estimators[END_REF][START_REF] Naftali | Necessary conditions for a maximum likelihood estimate to become asymptotically unbiased and attain the cramer-rao lower bound. part i. general approach with an application to time-delay and doppler shift estimation[END_REF].

In this condensed description of a rich field, we see that existing results either describe the tightest possible performance limits through lower-bounds, or describe more heuristic approximations of the MLE variance. To the best of our knowledge, deriving theoretical upper-bounds remains an open research area that is at the heart of the present work. One of the authors recently conducted a similar study in [START_REF] Debarnot | Blind inverse problems with isolated spikes. Information and Inference[END_REF], for the case of blind inverse problems with unknown weights. However, the proof was suboptimal and did not allow us to reach the Cramér-Rao bound asymptotically when σ → 0, contrary to the present work.

Beurling-LASSO framework To resolve superpositions of Dirac masses, a lot of works have considered the so-called Beurling LASSO (BLASSO) problem [START_REF] Boyer | Adapting to unknown noise level in sparse deconvolution[END_REF][START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Butucea | Off-the-grid learning of sparse mixtures from a continuous dictionary[END_REF][START_REF] Emmanuel | Towards a mathematical theory of superresolution[END_REF][START_REF] Denoyelle | Support recovery for sparse superresolution of positive measures[END_REF][START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF][START_REF] Tang | Near minimax line spectral estimation[END_REF]. In this framework, the sources are defined as sparse measures and sparsity is promoted by penalizing the total variation norm. This framework now possesses a rich theory. These include the study of the asymptotic small noise regime [START_REF] Emmanuel | Towards a mathematical theory of superresolution[END_REF][START_REF] Denoyelle | Support recovery for sparse superresolution of positive measures[END_REF][START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF] where it has been proved that BLASSO produces a solution with exactly the same number of spikes as the target. Beyond this asymptotic noise regime, the authors in [START_REF] Boyer | Adapting to unknown noise level in sparse deconvolution[END_REF][START_REF] Tang | Near minimax line spectral estimation[END_REF] exploited the fine structure of the Gaussian white noise to control the effects of the noise and uncover near minimax rates of prediction. The improvement of [START_REF] Boyer | Adapting to unknown noise level in sparse deconvolution[END_REF] lies in the joint estimation of the signal and the noise level, making the estimator adaptive to unknown noise levels. More recently, the authors in [START_REF] Butucea | Off-the-grid learning of sparse mixtures from a continuous dictionary[END_REF] considered a general parameterized model (continuous dictionaries) with correlated Gaussian noise. In this context, they proved that under a minimal separation condition on the true parameters, rates of prediction similar to those attained by the Lasso (linear regression) are achieved.

The simplified model we consider in this paper (single source with fixed amplitude) can be seen as a special case of these works, in particular of [START_REF] Butucea | Off-the-grid learning of sparse mixtures from a continuous dictionary[END_REF]. Yet, in our setting the source location can be multidimensional. Moreover, the proposed analysis sheds new light on the problem at least in two important ways.

• We provide both upper and lower bounds on the localization error which are shown to match closely and surround the Cramér-Rao lower bound for low noise levels.

In particular, we manage to discard some logarithmic factors asymptotically. • Our bounds highlight geometrical features of the kernel h that should be controlled to limit localization errors.

These results are important from a practical point of view. For example in optics, the current practice for characterizing the performance of optical systems, estimating the quality of algorithms or designing new point spread functions is systematically based on the Cramér-Rao lower-bound. Our results show why and when this methodology might be meaningful and highlight other criteria that must be taken into account jointly.

Preliminary facts

In this section, we derive a few basic, yet partly surprising results.

Existence of minimizers

Before studying the variance of the MLE, it is important to check that it is well defined. In fact, the answer is negative.

Proposition 3.1. For any positive kernel h vanishing at infinity, and for any noise level σ > 0, the probability of non existence of the MLE is non zero.

Proof. Take a positive kernel h vanishing at infinity. In that case, P(y m < 0, ∀1 ≤ m ≤ M ) > 0 for all noise levels σ. If all the coordinates of y are negative, it is easy to see that (4) has no minimizer, since ℓ ϵ (x) > lim x ′ →+∞ ℓ ϵ (x ′ ) for any x ∈ R D .

One way to avoid this problem is to add box constraints on the location x. In that case, the minimizer would exist since we would minimize a continuous function over a compact set. However, in such a scenario, the estimator would then end up on the domain boundary. This simple example highlights a fundamental difficulty in the localization problem: outliers can significantly increase the variance of the MLE.

It will therefore be central to control the probability of x being an outlier. Similar observations have already been formulated in [START_REF] Harry | Detection, estimation, and modulation theory, part I: detection, estimation, and linear modulation theory[END_REF][START_REF] Athley | Threshold region performance of maximum likelihood direction of arrival estimators[END_REF].

Identifiability

A second key issue is the identifiability. To illustrate it, let us consider a problem on the real line, i.e., D = 1. Consider the family of kernels h n (x) def = sin(2πnx) and set z m = m/M . In that case, the negative log-likelihood function ℓ ε is periodical and therefore possesses an infinite number of global minimizers. Even restricted on the interval [0, 1], the function possesses at least n global minimizers, therefore the MLE is not well defined again.

The Cramér-Rao bound in that case yields a somewhat contradictory result. Indeed, the bound (7) behaves as σ 2 n 2 and tends to 0 as n → ∞. By minimizing the Cramér-Rao lower-bound, we would opt for a very oscillatory kernel h, while the problem gets less and less identifiable as n grows.

This simple example highlights the fact that the Cramér-Rao bound only provides a local information. In what follows, we will derive global localization results, requiring more stringent conditions on h.

Main results

In this section, we control the probability P (∥x -x∥ 2 ≤ r) for any given radius r > 0. We define the estimator x as

x ∈ argmin x∈Ω ℓ ε (x) with ℓ ε (x) = 1 2 ∥h(Z -x) -h(Z -x) -ε∥ 2 2 , (8)
where

Ω ⊆ B R def = {x ∈ R D , ∥x -x∥ 2 ≤
R} is included in a ball of radius R centered at x. We prefer minimizing on a compact set Ω rather than R D for the following reasons:

(i) In the actual practice, the minimization is usually performed over a compact domain over which the source is assumed to lie. Such a priori knowledge is easily accessible in many applications.

(ii) It ensures the existence of a minimizer (minimization of a continuous function over a compact set).

(iii) It simplifies the presentation significantly.

We could take R = +∞, recovering problem (4), by adding a decay assumption on h. We prefer skipping this aspect for conciseness.

Technical assumption and geometrical quantities

First of all, let us recall that we work under the assumption h ∈ C 2 (R D ) which implies the existence of the following two quantities.

• Boundedness:

Λ def = sup x,x ′ ∈B R ∥h(Z -x) -h(Z -x ′ )∥, (9)
• Lipschitz continuity:

L def = sup x,x ′ ∈B R ∥h(Z -x) -h(Z -x ′ )∥ ∥x -x ′ ∥ . (10)
Moreover, in what follows, we will let

R L def = Λ L .
Remark 4.1. The Lipschitz continuity over B R implies that Λ ≤ 2LR. Hence under the stated assumptions, we get R L ≤ 2R. However, the radius R could be large, in which case, it can be highly preferable to work with R L than R.

In the appendix, we derive a localization result that holds for arbitrary kernels h (Theorem D.1), but which is quite hard to grasp. To present our main results, we will work under the following additional assumption, which significantly eases the presentation and will allow us to draw parallels with the Cramér-Rao lower bound.

1). Assume that y

= h ⋆ δ x + ε, with h belonging to the Sobolev space W 1,2 (R D ) def = {f ∈ L 2 (R D ) ; f ′ ∈ L 2 (R D )}. Then Assumption 4.1 is equivalent to h being non-periodic (there exists no non-zero v ∈ R D such that h(x + v) = h(x) for all x ∈ R D ).
Proof. The proof is post-poned to Appendix C.

In the discrete case however, the study should be handled on a case by case basis since it depends on a complex interplay between the measurement grid and the PSF h.

Under Assumption 4.1, there exists µ > 0 and a radius R µ > 0 such that

ℓ 0 (x) ≥ µ 2 2 ∥x -x∥ 2 2 for x ∈ B Rµ , µ 2 2 R 2 µ for x ∈ B R \ B Rµ . (11)
The quantities Λ, µ, R µ and L are related to simple geometrical properties of h (and thus ℓ 0 ). The strong convexity parameter µ denotes the local curvature of ℓ 0 around x. Hence, by picking a small radius R µ , µ can be associated to the minimal eigenvalue of ℓ ′′ 0 (x). The parameter L can be associated to the maximal curvature of ℓ 0 on R D . They are illustrated in Fig. 3 (left) and their behavior for different 1D kernels h is illustrated in Fig. 4.

A refined analysis of these quantities can be carried out case by case as illustrated in the central part of

h ref def = (1 -|x|) + , M ∈ N, Z = (-M, -M + 1, . . . , M -1, M ) , x = 0. (12) x R µ R L R 0 Λ 2 2 µ 2 R 2 µ 2 r → L 2 r 2 2 r → µ 2 r 2 2
xx 2

Eqs ( 9)-( 10) Eq (11) For this choice of h and Z, the noiseless function ℓ 0 has a simple analytical formula:

0 x R µ R L R 0 Λ 2 2 µ 2 R 2 µ 2 x -x 2 0 with h ref
∀x ∈ [-M, M ] , ℓ ref 0 (x) = x 2 if |x| ≤ 1, 1 -{x} + {x} 2 if 1 ≤ |x| ≤ M. ( 13
)
where {x} def = x -⌊x⌋ is the fractional part of x. To get this result, we exploit the fact that h ref is even and continuous, and so is

ℓ ref 0 . Moreover, h ref is linear on each interval [m, m + 1] with -M ≤ m ≤ M -1,
L ref = µ ref = Λ ref = √ 2, R ref µ = √ 3 2 , R ref L = 1. (14)

The main results

We are now ready to present our main results.

Theorem 4.1 (Sufficient conditions). Assume that ε ∼ N (0, σ 2 Id) and that the Assumption 4.1 is satisfied. Set ρ > 0, a radius 0 < r ≤ R and

I = ⌈log 2 (1 + log 2 (R µ /r))⌉.
Consider the two conditions below, where c > 0 is a universal constant * :

4 µ 2 σL c √ D + ρ 2 + 2 ln(I) ≤ r (Cond 1 ) 2 µ 2 σL c √ D ln 3R R L + ρ 2 + 2 ln(I) ≤ R 2 µ R L . (Cond 2 )
Then under either of the following conditions * The proof of the result heavily relies on bounding the supremum of a Gaussian process. To the best of our knowledge, it is currently out of reach to control the multiplicative constants precisely. For the slowly oscillating cosine associated to the frequency ω 1 , we show that different choices of µ and R µ in Assumption 4.1 are possible with the green and red dashed curves. We can choose a large value of µ with a small radius R µ (see the red dashed lower bound). As an effect, the bounds we obtain in Theorem 4.1 will ensure that a highly accuracte estimate can be obtained for low noise regimes. However, they will suffer from a high probability of false detection with higher noise levels. On the other hand, we can choose a smaller value of µ (see the green dashed lower bound) with a larger radius R µ . As a result, our theorem provides sharper estimates for high noise regimes. The Cramér-Rao lower bound on its side is based on the curvature of ℓ 0 at x only. It therefore accomodates only with small noise levels and leads to an overoptimistic conclusion for the mean squared error of the estimator. The function on the right illustrates a pathological kernel for the Cramér-Rao bound: the bound converges to zero due to the high curvature at the origin, but there is a very high probability of false detection since shifted kernels correlate highly with h. Our theorems allow us to use a more precise lower enveloppe that provides sharp guarantees on the estimator location.

• r ≤ Rµ 2 , R ≥ R L 2 , Cond 1 and Cond 2 . • r ≤ Rµ 2 , R ≤ R L 2 and Cond 1 . • r ≥ Rµ 2 and Cond 2 .
the following inequality holds

P (∥x -x∥ 2 ≤ r) ≥ 1 -exp - ρ 2 2 . ( 15
)
The complete proof is given in Appendix D. We will provide some insights in the next section. For now, let us present a similar result showing that the conditions in Theorem 4.1 are not only sufficient but also nearly necessary.

∥h(Z -x) -h(Z -x ′ )∥ 2 ≥ µ min (∥x -x ′ ∥ 2 , R µ ) ∀x, x ′ ∈ B R . (16)
• We have

P (x / ∈ B r ) ≥ 1 -exp(-ρ 2 1 /2) -Φ(ρ 2 )
, where Φ is the cumulative distribution function of the normal distribution, under the condition

r < √ ln 2 8 µ √ D -1 -ρ 2 L L c √ D + ρ 1 min R µ , σ √ ln 2 4 µ L 2 √ D -1 . (Cond ′ 1 ) • We have P (x / ∈ B r ) ≥ 1 -exp(-ρ 2 1 /2) -exp(-ρ 2 2 /2) under the condition σ ln R R µ > R 2 L L 2 √ DR µ µ + 2σ[ρ 2 R L L + Lrc √ D + ρ 1 ] √ DR µ µ . (Cond ′ 2 )
The complete proof is given in Appendix E.

An informal proof

In this section, we provide the essential ingredients behind Theorems 4.1 and 4.2 since they shed light on the problem's geometry. The starting point of these proofs is the following decomposition

ℓ ε = ℓ 0 -∆ ε + 1 2 ∥ε∥ 2 2 where ∆ ε (x) def = ⟨h(Z -x) -h(Z -x), ε⟩ , ∀x ∈ R D .
The term 1 2 ∥ε∥ 2 2 is constant with respect to x and does not change the location of the minimizer. The term ∆ ε is a centered random Gaussian process with

∆ ε (x) ∼ N (0, 2σ 2 ℓ 0 (x)) (17)
Intuitions behind Theorem 4.1 A sufficient condition for success (x ∈ B r ) is that

0 = ℓ 0 (x) -∆ ε (x) < inf x∈B R \Br ℓ 0 (x) -∆ ε (x), (18)
as illustrated on Fig. 5 (left). Then, given that Left: Success (x ∈ B r ) occurs if there exists x ∈ B r (e.g., x = x) such that ℓ 0 (x) -∆ ε (x) (orange point) is lower than the infimum of ℓ 0 -∆ ε over B R \ B r (orange dashed line). Right: The green curve is an upper-bound of the typical amplitude of ∆ ε . The red curve is a lower-bound of ℓ 0 . An (informal) sufficient condition for x ∈ B r is that the red curve dominates the green one at r. [START_REF] Fanglin | Fourier diffuserscope: single-shot 3d fourier light field microscopy with a diffuser[END_REF] and regularity of h ( 9) and ( 10)),

0 r R 0 x -x 2 0 -∆ε 0 r R µ R L R 0 σLR L 1 2 µ 2 R 2 µ r → σ L r r → µ 2 r 2 2 x -x 2
• ∆ ε (x) ≲ σL min (∥x -x∥ 2 , R L ) with high probability (from
• ℓ 0 (x) ≥ µ 2 2 min(∥x -x∥ 2 2 , R 2
µ ) (from Assumption 4.1), we can simplify [START_REF] Mallat | A wavelet tour of signal processing[END_REF] as

σL min (∥x -x∥ 2 , R L ) ≲ µ 2 2 min(∥x -x∥ 2 2 , R 2 µ ), for all ∥x -x∥ 2 ≥ r.
This is illustrated in Fig. 5 (right) with the quadratic curve being higher than the linear one for all ∥x -x∥ 2 ≥ r. This condition can be decomposed as 2σL/µ 2 < r and 2σL/µ 2 < R 2 µ /R L which correspond in essence to Cond 1 and Cond 2 in Theorem 4.1. The difference lies in additive logarithmic terms which appear, since the probability should not be controlled pointwise, but uniformly in B R \ B r . This uniform control is handled using discretization techniques combined with results on the suprema of random processes [START_REF] Talagrand | Upper and lower bounds for stochastic processes. decomposition theorems[END_REF].

Intuitions behind Theorem 4.2 A sufficient condition for failure (x / ∈ B r ) is that there exists x ′ ∈ B R \ B r with t = ∥x ′ -x∥ 2 such that 0 ≈ r small inf x∈Br ℓ 0 (x) -∆ ε (x) > ℓ 0 (x ′ ) -∆ ε (x ′ ). ( 19
)
This condition is illustrated on Fig. 6 (left). Then, given that

• ∆ ε (x ′ ) ≳ σµ min(t, R µ )
with probability close to 1/2 (from [START_REF] Fanglin | Fourier diffuserscope: single-shot 3d fourier light field microscopy with a diffuser[END_REF] and since ∆ ε is symmetric), ∈ B r ) occurs if there exists x t ∈ B R \ B r (with t = ∥x t -x∥ 2 ) such that ℓ 0 (x t ) -∆ ε (x t ) (orange point) is lower than the infimum of ℓ 0 -∆ ε over B r (orange dashed line). Right: The green curve is a lower-bound of the typical amplitude of ∆ ε . The blue curve is an upperbound of ℓ 0 . An (informal) sufficient condition for x / ∈ B r is that the green curve dominates the blue one at t. we can simplify [START_REF] William | Optical detection and spectroscopy of single molecules in a solid[END_REF] as

• ℓ 0 (x ′ ) ≤ L 2 2 min t 2 , R 2 L (from Assumption 4.1), 0 r t R 0 x -x 2 0 -∆ε 0 r t R L R µ R 0 σµR µ 1 2 L 2 R 2 L r → σ µ r r → L 2 r 2 2 x -x 2
σµ min(t, R µ ) ≳ L 2 2 min t 2 , R 2 L .
This is illustrated on Fig. 6 (right) with the quadratic curve being lower than the linear one at ∥x ′ -x∥ 2 = t. Taking t = 2r, we get the two conditions r < σµ/L 2 and σ > L 2 R 2 L /(2µR µ ) which correspond to Cond ′ 1 and Cond ′ 2 in Theorem 4.2 (for small r, ρ 1 , and ρ 2 ). A more careful analysis involves the additive terms appearing in the theorem.

Interpretations and simplifications

In this section, we aim at explaining the different ingredients from the theorems above.

The key geometric features The proposed analysis emphasizes the role of a few key geometrical quantities:

• The radius R µ of quadratic growth and its associated parameter µ

µ 2 ≥ inf x∈B Rµ λ min (ℓ ′′ 0 (x)). ( 20
)
• The Lipschitz constant of the gradient of ℓ 0 :

L 2 ≤ sup x∈B R λ max (ℓ ′′ 0 (x)). (21)
• The local conditioning of ℓ 0 around x:

κ def = L µ ≥ 1.
• The square root of the quotient between the upper and lower bound of ℓ 0 far from x:

θ def = R L L Rµµ ≥ 1.
The two last theorems can be summarized informally as follows. For sufficiently small r, we can get x ∈ B r with large probability under the following

• Sufficient condition: σ ≲ µ √ D min rκ -1 , R µ θ -1 ln R R L -1/2 (22)
• Necessary condition:

σ ≲ L √ D min rκ 2 , R L θ ln R R µ -1/2 . ( 23
)
Only the left term in the minimum above plays a role in the control of the local error around the true location. The term ln(R) -1/2 comes from the fact that as the radius R increases, the probability of false detection far away from x increases. However, it does so at a very moderate rate.

Tightness

The two conditions differ mostly from the conditioning factors κ and θ.

They become equivalent up to multiplicative factors for the reference kernel h ref .

Indeed, set R = M/2 -1, which amounts to looking for the source only around the sampled points. For this kernel, they both read

σ √ D ≲ min r, ln(M ) .
This proves the tightness of the theorem.

The term D ln(R/R L ) This term is not a proof artefact and needs to be accounted for. To illustrate this, let us consider the simple function h(x) = (1 -L∥x∥ ∞ ) + . We assume for simplicity that L = 1/K for some integer K ∈ N and that the sampling set is the Euclidean grid Z = 1, M 1/D D , where we assume that M 1/D is an integer. The function h is L-Lipschitz continuous, has a support [-K, K] D and satisfies R L ∝ 1 L . By definition, ∆ ε (x) = ⟨h(Zx), ε⟩ -⟨h(Zx), ε⟩. Since h is compactly supported, notice that the random variables ⟨h(Zx), ε⟩ and ⟨h(Zx ′ ), ε⟩ are independent for |xx ′ | ≥ 2K. In addition, for x, x ′ ∈ Z ∩ (2KN) D , they are independent and identically distributed Gaussian random variables.

We can pack O(RL) D balls of radius K in a ball of radius R. To find a lowerbound on the supremum of ∆ ε (x), we can therefore use Sudakov's inequality:

X ∼ N (0, Id N ) ⇒ E max 1≤n≤N X n ≳ 2 ln(N ) 2 . ( 24
)
Applied to our setting this yields:

E sup x∈B R ∆ ε (x) ≥ E max x∈Z∩(2KN) D ∆ ε (x) = E max x∈Z∩(2KN) D ⟨h(Z -x), ε⟩ ≳ D ln(R/R L ).
The term ln(I) The term ln(I) = ln(⌈log 2 (1+log 2 (R µ /r))⌉) is likely an artefact of the proof. It appears when we derive a tail bound (see (D.8)) for the term sup x∈Br ∆ ε (x).

In [START_REF] Boyer | Adapting to unknown noise level in sparse deconvolution[END_REF][START_REF] Butucea | Off-the-grid learning of sparse mixtures from a continuous dictionary[END_REF], the authors propose a different proof strategy based on the Rice theorem, which is more elegant, but restricted to the 1D case. We did not find a way to extend the proof to the multivariate case. In 1D, the results coincide, apart from constants and the logarithmic term ln(I). It can be safely neglected in practice. For instance ln(⌈log 2 (1 + log 2 (10 100000 ))⌉) < 3!

Notable consequences

Theorem 4.1 has a few interesting consequences.

Phase transition An important consequence of Theorem 4.1 is a phase transition behavior. Whenever (Cond 1 ) and (Cond 2 ) are satisfied with a sufficiently high value of ρ (say ρ = 3), it becomes very unlikely to see the global minimizer x escaping from the ball B(x, r). In applications, we would typically set a small value of r (e.g. one tenth of a pixel in single molecule localization) and the theorem tells that whenever the condition is satisfied, the estimator will nearly always succeed.

Relationship to Cramér-Rao The condition (Cond 1 ) is strongly connected to the Cramér-Rao lower-bound. Using assumptions ( 10) and ( 11), we obtain

µ 2 ≤ λ min (ℓ ′′ 0 (x)) ≤ λ max (ℓ ′′ 0 (x)) ≤ L 2 . (25)
Given that

ℓ ′′ 0 (x) = M m=1 h ′ (z m -x) h ′ (z m -x) T , we get µ 2 ≤ λ min (ℓ ′′ 0 (x)) ≤ ∥h ′ (Z -x)∥ 2 F D ≤ λ max (ℓ ′′ 0 (x)) ≤ L 2 (26)
since for any matrix

A ∈ R D×M with D ≤ M ∥A∥ 2 F = D d=1 σ 2 d (A) = D d=1 λ d (AA T ) (27)
where σ d (A) and λ d (A) are respectively the singular values and the eigenvalues of A.

Finally, from (Cond 1 ) we get that asymptotically,

r ≳ √ DσL µ 2 ≳ D • σ ∥h ′ (Z -x)∥ F = CR σ . (28)
This is in line with the asymptotic analysis existing in the literature [START_REF] Naftali | Necessary conditions for a maximum likelihood estimate to become asymptotically unbiased and attain the cramer-rao lower bound. part i. general approach with an application to time-delay and doppler shift estimation[END_REF][START_REF] Renaux | On the highsnr conditional maximum-likelihood estimator full statistical characterization[END_REF].

PSF engineering -How to optimize a kernel? A few authors proposed to optimize the point spread function of optical systems by maximizing ∥h ′ (Zx)∥ F , motivated by the Cramér-Rao bound, see e.g. [START_REF] Shechtman | Optimal point spread function design for 3d imaging[END_REF][START_REF] Fournier | On the single point resolution of on-axis digital holography[END_REF]. The second part of Theorem 2.1, shows that this might not be enough. Our results highlight that other facts must be taken into account.

Let us assume that we wish to obtain a localization precision of order r. Looking only at the sufficient condition, the most important factors are then:

• The quadratic growth parameter µ in B R . A good upper-bound for this term is:

µ(r) def = inf x∈Br ∥h ′ (Z -x)∥ F . ( 29
)
This term is essentially equivalent to the Cramér-Rao bound, except that it needs to be controlled uniformly in B r . • We also need to ensure that ℓ 0 (x) is sufficiently large for all x ∈ B R \ B r . This condition is there to ensure the identifiability of the problem. For example, this condition discards the pathological sine kernel discussed in Section 3.2. This would not be taken into account using the Cramér-Rao bound only. • Finally, taking R too large increases the probability of false positives at the slow rate ln(R). This means that cameras with large field of views can be safely used without increasing the false detection rate significantly.

Notice that the factors mentioned above do not include any support size or decay rate constraints, which are usually added for PSF engineering [START_REF] Shechtman | Optimal point spread function design for 3d imaging[END_REF]. Hence, unlocalized kernels could yield interesting results, in the low density regime, where only scattered sources are present. Such unlocalized PSFs are physically realistic [START_REF] Yanny | Miniscope3d: optimized single-shot miniature 3d fluorescence microscopy[END_REF][START_REF] Fanglin | Fourier diffuserscope: single-shot 3d fourier light field microscopy with a diffuser[END_REF] and our results suggest that they may be of interest in the context of SMLM for instance. To our knowledge, this has not been investigated to date.

Analysis for well sampled bandlimited kernels

In this section, we analyze the theorems in the specific case of well sampled bandlimited kernels. This case is of major importance in optics applications. Let us introduce the Fourier transform defined for all f ∈ L 2 (R D ) by

F(f )(ω) def = 1 (2π) D/2 R D f (x) exp(-i⟨x, ω⟩) dx. ( 30
)
Let us recall the Plancherel formula ∥f ∥

L 2 (R D ) = ∥F(f )∥ L 2 (R D ) .
Definition 4.1 (Paley-Wiener space). For W > 0 we say that

f ∈ L 2 (R D ) is W -bandlimited if supp (F(f )) ⊆ [-W, W ] D . We let PW(W ) denote the set of W - bandlimited functions in L 2 (R D ).
A bandlimited function belongs to C ∞ (R D ). Let us recall the following fundamental result. Theorem 4.3 (A variant of Whittaker's theorem [START_REF] Mallat | A wavelet tour of signal processing[END_REF]). Assume that f, g ∈ PW(π). Set a sampling step τ ≤ 1. Then for all x ∈ R D , we have:

⟨f, g⟩ L 2 (R D ) = τ 2π D z∈τ Z D f (z -x)g(z -x). ( 31
)
In particular, taking f = g, we get

∥f ∥ 2 L 2 (R D ) = τ 2π D z∈τ Z D f (z -x) 2 . ( 32
)
Proof. The proof is given in Appendix F for completeness. Now assume that h ∈ PW(π) and that it is sampled on Z = [-R, R] D ∩ τ Z D , where τ < 1 is the grid size (1/τ is the oversampling factor). By Theorem 4.3, we have for all x

∥h(Z -x)∥ 2 2 = z∈Z h 2 (z -x) = 2π τ D ∥h∥ 2 L 2 (R D ) - z∈τ Z D \Z h 2 (z -x) ≈ 2π τ D ∥h∥ 2 L 2 (R D )
for sufficiently large R and decaying h. Similarly, we have for all

x, x ′ ∥h ′ (Z -x)∥ 2 2 ≈ 2π τ D ∥h ′ ∥ 2 L 2 (R D ) ⟨h(Z -x), h(Z -x ′ )⟩ ≈ 2π τ D ⟨h(• -x), h(• -x ′ )⟩ L 2 (R D )
using the fact that h ∈ PW(π) ⇒ h ′ ∈ PW(π). We then get that

ℓ 0 (x) ≈ 2π τ D ∥h∥ 2 L 2 (R D ) -⟨h(• -x), h(• -x)⟩ L 2 (R D ) .
Now let Λ, L, and µ be defined according to equations ( 9) to ( 11), and 4.1 for x → ℓ 0 (x)τ D so that they are independent of τ . Then, the conditions ( 22) and ( 23) read

σ ≲ µ τ D/2 min rκ -1 √ D , R µ θ -1 √ D ln R R L -1/2 (33)
σ ≲ L τ D/2 min rκ 2 , R L θ √ D ln R R µ -1/2 . ( 34
)
where κ, θ, R L , and R µ are independent of τ . Hence, for well sampled bandlimited kernels, we have the following qualitative behaviour:

• The performance does not depend on x (as ∥h ′ (Z -•)∥ 2 is nearly constant).

• Over-sampling with τ < 1 leads to improved performances (from ( 33) and (34)).

Appendices A. Derivatives of ℓ ε

Let us start with a set of identities that will be used continuously throughout the proofs. We have

ℓ ε (x) = 1 2 ∥h(Z -x) -y∥ 2 2 , (A.1) ℓ ′ ε (x) = -h ′ (Z -x)(h(Z -x) -y), (A.2) ℓ ′′ ε (x) = h ′′ (Z -x)(h(Z -x) -y) + h ′ (Z -x)h ′ (Z -x) T . (A.3)
Thus evaluating at x = x gives In our case, we have

ℓ ε (x) = ∥ε∥ 2 2 , (A.4) ℓ ′ ε (x) = M m=1 ε m h ′ (z m -x), (A.5) ℓ ′′ ε (x) = M m=1 h ′ (z m -x) h ′ (z m -x) T -ε m h ′′ (z m -x) .
p(y|x) ∝ exp - ∥y -h(Z -x)∥ 2 2 2σ 2 . (B.2) Hence ∂ ln p(y|x) ∂x d = 1 σ 2 M m=1 (h(z m -x) -y m ) • h ′ d (z m -x), (B.3)
where we use the notation h ′ d = ∂ d h in this proof. This yields for any unbiased estimator x

E |x d -xd | 2 2 ≥ E ∂ ln p(y|x) ∂x d • ∂ ln p(y|x) ∂x d -1 = σ 4 • E M m=1 -ε m h ′ d (z m -x) M m=1 -ε m h ′ d (z m -x) -1 = σ 4 • E M m=1 ε 2 m h ′ d (z m -x) 2 -1 = σ 2 ∥h ′ d (Z -x)∥ 2 2
.

Summing over d yields

E ∥x -x∥ 2 2 ≥ D d=1 σ 2 ∥h ′ d (Z -x)∥ 2 2 ≥ D 2 σ 2 ∥h ′ (Z -x)∥ 2 F , (B.4)
where the last inequality is obtained by the fact that the arithmetic mean is greater than the harmonic one (i.e., 1 for all y, x and some D-dimensional functions g and D × D matrix I. The optimal estimator is then x = g(y) and the covariance matrix is I(x) -1 .

D D d=1 a d ≥ D( D d=1 1
a d ) -1
Corollary B.1 (Necessary conditions for attaining Cramér-Rao). In our case, there exists an unbiased estimator x of x that attains the Cramér-Rao bound if and only if D = 1 and h is an affine non constant function.

Proof. Firstly, assume that such an estimator that attains the Cramér-Rao bound exists. Let's show that h should be affine. In our case, the condition from the general case reads 1

σ 2 J h(x) T • (h(Z -x) -y) = I(x) • (g(y) -x) (B.6)
where we have introduced the following notations

h : R D -→ R M x -→ h(Z -x) def = (h(z m -x)) m
and for a function f : R D -→ R I we have fixed the Jacobian of f to be

Jf (x) def = ∂f i ∂x d i,d = (∇f 1 (x) . . . ∇f I (x)) T ∈ R I×D .
Differentiating the equality with respect to y yields

- 1 σ 2 J h(x) T = I(x) • Jg(y). (B.7)
The left-hand side does not depend on y. Hence, Jg(y) is constant, meaning that

g(y) = A • y + b (B.8)
for some A ∈ R D×M and b ∈ R D . This simplifies equation (B.7) as

J h(x) T = -σ 2 I(x) • A. (B.9)
Now let us rewrite (B.6) by replacing g(y) and J h(x) T :

-I(x) • A • (h(Z -x) -y) = I(x) • (A • y + b -x).
Since from the general case, I(x) -1 is well defined and is the covariance matrix, one has that I(x) is invertible. The previous equality simplifies as

-A • h(Z -x) = b -x. (B.10)
Differentiating this expression with respect to x and injecting (B.9) gives

-σ 2 I(x) • AA T = Id D (B.11)
which implies that I(x) does not depends on x. With (B.9), we finally get that h (and thus h) is affine.

To complete the proof, it remains to show that D = 1 and that h cannot be constant. As h is affine, let us set h : x → ⟨a, x⟩ + β with a ∈ R D and β ∈ R. Then

J h(x) T = [a a • • • a] ∈ R D×M .
(B.12)

We then deduce two facts from the invertibility of I(x). First, from (B.11) AA T is also invertible. Second, from (B.9) there exists c ∈ R D such that

A = c • 1 T ∈ R D×M and AA T = c • 1 T • 1 • c T = M • cc T .
Clearly, these two properties can be satisfied at the same time only if D = 1 and a ̸ = 0. This shows that D = 1 and h is affine non constant. Conversely, any affine non constant function h in the case D = 1 attains Cramér-Rao bound since I(x) = M a 2 and g(y

) = β a + 1 M M m=1 h z m -ym a are appropriate.

C. Proof of Proposition 4.1

Proof. The function ℓ 0 and its derivatives read for any

v ∈ R D ℓ 0 (x) = 1 2 R D (h(z -x) -h(z -x)) 2 dz ℓ ′ 0 (x)v = - R D (h(z -x) -h(z -x)) • ⟨h ′ (z -x), v⟩ dz ℓ ′′ 0 (x)(v, v) = R D ⟨h ′ (z), v⟩ 2 dz.
If x is another minimizer of ℓ 0 , then ℓ 0 (x) = 0 and thus h(z

-x) = h(z -x) for almost every z ∈ R D . This is equivalent to h(z) = h(z + (x -x)) which means that h is (x -x)-periodic.
Let's show that ℓ ′′ 0 (x) ≻ 0 ⇐⇒ h ̸ = 0. We proceed by contraposition

ℓ ′′ 0 (x) = 0 ⇐⇒ ℓ ′′ 0 (x)(v, v) = 0, ∀v ∈ R D ⇐⇒ ⟨h ′ (z), v⟩ = 0, ∀v, z ∈ R D ⇐⇒ h ′ = 0 h∈L 2 (R D ) ⇐⇒ h = 0.
This concludes the discussion in the continuous case. In the discrete case however, the study is more involved as it depends on the measurement grid and the PSF h. It should be handled on a case by case basis. Theorem D.1 (A general result). Let (r i ) 0≤i≤I denote an increasing sequence with r 0 = r and r

I = R. Define Ω i = B ri \ B ri-1 and Ēi def =    cσ √ DΛ ri R L if r i ≤ R L 2 cσ √ DΛ ln 3ri R L otherwise and Λi def = Λ min 1, r i R L . (D.1)
where c is a universal constant. Set ρ > 0. From (9), [START_REF] Chazan | Improved lower bounds on signal parameter estimation[END_REF] and under Assumption 4.1.

We have x ∈ B r with probability larger than 1exp(-ρ 2 /2) under the I conditions

1 ≤ i ≤ I: Ēi + ρ 2 + 2 ln(I)σ Λi ≤ inf x∈Ωi ℓ 0 (x). (C i )
Proof. The proof of this result is quite long and technical.

D.1.1. The general strategy Let B r = {x ∈ R D , ∥x -x∥ 2 ≤ r}. We can decompose ℓ ε as ℓ ε = ℓ 0 -∆ ε + 1 2 ∥ε∥ 2 2 , where ∆ ε (x) def = ⟨h(Z -x) -h(Z -x), ε⟩.
Without loss of generality, we consider here that Ω = B R . We partition the domain Ω, as

Ω = 0≤i≤I Ω i with Ω i = B ri \ B ri-1 for i ≥ 1, (D.2)
with Ω 0 = B r , (r i ) 0≤i≤I an increasing sequence with r 0 = r and r I = R. Now, remark that

[∥x -x∥ 2 ≤ r] ⇔ inf x∈Br ℓ ε (x) < inf x∈B c r ℓ ε (x) ⇔ inf x∈Br ℓ 0 (x) -∆ ε (x) < inf x∈B c r ℓ 0 (x) -∆ ε (x) ⇔ inf x∈Br ℓ 0 (x) -∆ ε (x) < inf x∈Ωi ℓ 0 (x) -∆ ε (x), ∀1 ≤ i ≤ I ⇐   ℓ 0 (x) -∆ ε (x) 0 < inf x∈Ωi ℓ 0 (x) -sup x∈Ωi ∆ ε (x), ∀1 ≤ i ≤ I   (D.3) ⇔ inf x∈Ωi l 0 (x) > sup x∈Ωi ∆ ε (x), ∀1 ≤ i ≤ I .
Here c denote the relative complement with respect to B R . The reason we partition the domain in concentric annuli is for the event at line D.3 and the one before to be close. The interest of D.3 is that we only need to control the supremum of the centered process ∆ ε instead on the non centered process ℓ 0 -∆ ε . The sequence of radii (r i ) 0≤i≤I will be optimized at the end of the proof.

D.1.2. Bounding the suprema

The main technical difficulty is to find probabilistic bounds on the supremum sup x∈Ωi ∆ ε (x). To this end, we will use a combination of Gaussian concentration results and Dudley's type inequality. We refer to the three excellent monographs [START_REF] Talagrand | Upper and lower bounds for stochastic processes. decomposition theorems[END_REF][START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF][START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF] for an in depth treatment of this topic. In our specific case, we obtain the following result.

Lemma D.1 (Expectation and tail bounds for the supremum ). Let

E i def = E sup x∈Ωi ∆ ε (x) .
(D.4)

For t ≥ 0, we have

P sup x∈Ωi ∆ ε (x) ≥ t ≤ exp - (t -E i ) 2 2σ 2 L 2 min(R 2 L , r 2 i ) . (D.5)
with

E i ≤ c • σ • L • √ D •    r i if r i ≤ R L 2 , R L • ln 3ri R L otherwise. (D.6)
Proof. First notice that the random process ∆ ε is Gaussian since ε ∼ N (0, σ 2 Id). It can be written alternatively as σ∆ ϵ with ϵ ∼ N (0, Id). Let D ⊂ R D denote a domain and define the mapping f D : ϵ → sup x∈D σ∆ ϵ (x). Let us define

D h (x 1 , x 2 ) def = h(Z -x 1 ) -h(Z -x 2 )
P sup x∈D ∆ ε (x) ≥ E sup x∈D ∆ ε (x) + u ≤ e -u 2 2σ 2 Λ 2 D . (D.8)
From ( 9) and ( 10), we have

∥D h (x, x)∥ 2 ≤ min(Λ, L ∥x -x∥ 2 ).
Hence for D = Ω i , we obtain

Λ Ωi ≤ min(Λ, Lr i ).
The remaining technical difficulty is to find an upper-bound for E sup x∈Ωi ∆ ε (x) . which is a hard problem in general. In this work, we will use Dudley's inequality together with ( 9) and [START_REF] Chazan | Improved lower bounds on signal parameter estimation[END_REF]. Let us introduce the pseudo-metric d : R D × R D → R defined by

d(x, x ′ ) def = E (∆ ε (x) -∆ ε (x ′ )) 2 = E (⟨h(Z -x) -h(Z -x ′ ), ε⟩) 2 (D.9) = σ 2 ∥h(Z -x) -h(Z -x ′ )∥ 2 2 = σ ∥h(Z -x) -h(Z -x ′ )∥ 2 .
(D.10)

It will be used in conjunction with the following tool. We are ready to present Dudley's inequality (see e.g. [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF]Cor. 13.2]).

Theorem D.2 (Dudley's inequality ). The following inequality holds:

E sup x∈S ∆ ε (x) ≤ c δ 0 ln(N (u, S, d)) du, (D.11)
where c is a universal constant and δ > 0 can be taken as the smallest number such that N (u, S, d) ≥ 1.

Lemma D.2. We have for some universal constant c,

E i ≤ c • σ • L • √ D •    r i if r i ≤ R L 2 , R L • ln 3ri R L otherwise.
(D.12)

Proof. In what follows, c is a universal constant that may change from one line to the other. From ( 9) and ( 10), we have

d(x, x ′ ) ≤ σ • min (L∥x -x ′ ∥ 2 , Λ) (D.13)
and we can upper bound E i as

E i = E sup x∈Ωi ∆ ε (x) ≤ E sup x∈Br i ∆ ε (x) .
Using (D.13) and [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF]Cor. 4.2.13], we obtain

N (u, B ri , d) ≤ 1 if u ≥ σ • min(2Lr i , Λ), 3riσL u D otherwise. (D.14)
Hence, in the case 2Lr i ≤ Λ, we obtain using Theorem D.2:

E i ≤ c 2riσL 0 ln(N (u, B ri , d)) du ≤ c 3riσL 0 ln(N (u, B ri , d)) du ≤ c √ D 3riσL 0 ln 3r i σL u du = c • r i • σ • L • √ D.
In the case 2Lr i > Λ, we get

E i ≤ c σΛ 0 ln(N (u, B ri , d)) du ≤ c √ D σΛ 0 ln 3r i σL u du = cσΛ √ D 1 0 ln 3r i L Λv dv = cσΛ √ D ln 3r i L Λ + √ π 2 3r i L Λ erfc 3r i L Λ ≤ cσΛ √ D ln 3r i L Λ + 1 2 3r i L Λ exp - 3r i L Λ
where we use the inequality erfc(z) < exp(-z 2 )

√ πz for z > 0 to get the last inequality.

Finally, since 1 2 √ ze -z ≤ ln(z) for z ≥ 3/2, the condition 2r i > R L implies the simplification: Then, the probability of the event x ∈ B r can be bounded above as follows:

E sup x∈Br i ∆ ε (x) ≤ c • σ • Λ • √ D • ln 3r i R L . ( D
P (x ∈ B r ) ≥ P   1≤i≤I sup x∈Ωi ∆ ε (x) -θ i < 0   ≥ 1 -P   1≤i≤I sup x∈Ωi ∆ ε (x) -θ i ≥ 0   ≥ 1 - I i=1 P sup x∈Ωi ∆ ε (x) -θ i ≥ 0 ≥ 1 - I i=1 exp - (θ i -E i ) 2 2σ 2 L 2 min(R L , r i ) 2 .
Set ρ ≥ 0 and ρ ′ = ρ 2 + 2 ln(I). Under the conditions

E i + ρ ′ σL min(R L , r i ) ≤ θ i , (D.17)
we get that the probability of success is higher than 1exp(-ρ 2 /2).

(x) ≥ min µ 2 r 2 i-1 2 , µ 2 R 2 µ 2 .
Let us assume that R > R L 2 . Without loss of generality, we can also assume that R µ ≤ R L 2 , since the inequalities in [START_REF] Marie D'avigneau | Limits of accuracy for parameter estimation and localization in single-molecule microscopy via sequential monte carlo methods[END_REF] are still valid when replacing B Rµ by B R ′ with R ′ ≤ R µ . In this setting, the success condition (C I ) reads

cσ √ DΛ ln 3R R L + σ ρ 2 + 2 ln(I)Λ ≤ µ 2 R 2 µ 2 . (D.19)
Now, let us set r I-1 = R µ . For 1 ≤ i ≤ I -1, the conditions (C i ) read:

σr i L c √ D + ρ 2 + 2 ln(I) ≤ µ 2 r 2 i-1 2 . (D.20)
This can be rewritten as:

2 µ 2 σL c √ D + ρ 2 + 2 ln(I) ≤ r 2 i-1 r i . (D.21)
Now, by setting r i = 2 2 i -1 r, we get

r 2 i-1 ri = r 2
for all i. In addition 2 2 i -1 r ≥ R µ for i ≥ ⌈log 2 (log 2 (2R µ /r))⌉. Hence, we can set I = ⌈log 2 (1 + log 2 (R µ /r))⌉. This value is larger than 2 for r < Rµ 2 . Hence, under this condition, we get x ∈ B r given that

4 µ 2 σL c √ D + ρ 2 + 2 ln(I) ≤ r 2 µ 2 σΛ c √ D ln 3R R L + ρ 2 + 2 ln(I) ≤ R 2 µ .
In the case r ≥ Rµ 2 , we can set I = 1, Ω 1 = B Rµ and only the second condition is sufficient for success:

2 µ 2 σΛ c √ D ln 3R R L + ρ ≤ R 2 µ .
The case R ≤ R L 2 can be treated as previously, but only Cond 1 matters, since the other one is automatically verified.

E. Proof of Theorem 4.2

Proof. First notice that inf

x∈Br ℓ 0 (x) -∆ ε (x) ≥ inf x∈Br ℓ 0 (x) -sup x∈Br ∆ ε (x) ≥ -sup x∈Br ∆ ε (x).
Using Lemma (D.1), we obtain

E r def = E sup x∈Br ∆ ε (x) ≤ crσL √ D,
where c is a universal constant and for ρ 1 > 0

P sup x∈Br ∆ ε (x) ≥ E r + ρ 1 σLr ≤ exp(-ρ 2 1 /2).
Define the event

E 1 def = inf x∈Br ℓ 0 (x) -∆ ε (x) ≥ -σLr c √ D + ρ 1 .
The previous inequalities imply that

P (E 1 ) ≥ 1 -exp(-ρ 2 1 /2).
Proof of the part related to (Cond ′ 1 ) Now, set t ∈ (r, R µ ] and take an arbitrary point with ∥x -x∥ 2 = t. Let's consider the following inequalities

inf x∈St ℓ ε (x) = inf x∈St ℓ 0 (x) -∆ ε (x) ≤ ℓ 0 (x) -∆ ε (x) ≤ sup x∈St ℓ 0 (x) + inf x∈St -∆ ε (x) (E.1)
where

x def = argmin x∈St -∆(x). It only remains to impose the two following inequalities

sup x∈St ℓ 0 (x) + inf x∈St -∆ ε (x) < -σLr c √ D + ρ 1 ≤ inf x∈Br ℓ ε (x) (E.2)
in order to get the result x / ∈ B r . Indeed, this inequality provides the relevant relation inf St ℓ ε < inf Br ℓ ε . The second inequality is controlled by the event E 1 , whereas we will control the first inequality with the event

E 2 def = inf x∈St -∆ ε (x) < -σLr c √ D + ρ 1 -sup x∈St ℓ 0 (x) . (E.3)
Since the law of the random variable ∆ ε is even, the event E ′ 2 defined as

E ′ 2 def = sup x∈St ∆ ε (x) > σLr c √ D + ρ 1 + sup x∈St ℓ 0 (x) (E.4)
has the same probability than E 2 .

Applying the same reasoning as the one for Lemma D.1 to the random variable sup x∈St ∆ ε (x), implies that

P sup x∈St ∆ ε (x) > E sup x∈St ∆ ε (x) -u ≥ 1 -exp - u 2 2σ 2 (Lt) 2 (E.5) for any u > 0. Setting u = E sup x∈St ∆ ε (x) -sup x∈St ℓ 0 (x) -σLr c √ D + ρ 1 , this allows us to get P (E 2 ) = P (E ′ 2 ) ≥ 1 -e -ρ 2 2 /2 (E.6)
under the condition ρ 2 ≤ u σLt which rewrites as

ρ 2 σLt ≤ E sup x∈St ∆ ε (x) -sup x∈St ℓ 0 (x) -σLr c √ D + ρ 1 . (E.7)
The next step is to find a lower bound for the expectation E sup x∈St ∆ ε (x) given in (E. [START_REF] Calyampudi | Linear statistical inference and its applications[END_REF]. This is accomplished thanks to the following lemmas: Lemma E.1. For D ≥ 2, let B 1 , B 2 be two intersecting balls of R D of respective radius 0 ≤ r 1 ≤ r 2 . Denoting S 1 , S 2 their associated spheres, we define two sphere caps as

C 1 = S 1 ∩ B 2 and C 2 = S 2 ∩ B 1 . (E.8)
Then the sphere cap C 1 has a greater surface area than C 2 , i.e.

λ D-1 (C 1 ) ≥ λ D-1 (C 2 ). (E.9)
Proof. Denote ϕ 1 (resp. ϕ 2 ) the polar angle of the sphere cap C 1 (resp. C 2 ). A simple formula to compute the surface area of a sphere cap can be found in [START_REF] Li | Concise formulas for the area and volume of a hyperspherical cap[END_REF] for example. Denoting A D (r) (resp. A cap D (r, ϕ)) the surface area of a sphere in R D of radius r (resp. of a sphere cap in R D of radius r and polar angle ϕ), one has the following formulae

A D (r) = 2π D-1 2 Γ( D-1 2 )
r D-1 , (E.10)

A cap D (r, ϕ) = ϕ 0 A D-1 (r sin θ)rdθ = r sin ϕ 0 1 1 -s 2 r 2 A D-1 (s)ds. (E.11)
The last equality is obtained thanks to the change of variables s = r sin θ. Because the two balls are intersecting each other, the radius a of the base is common to the two sphere caps. Indeed, one has

r 1 sin ϕ 1 = a = r 2 sin ϕ 2 . (E.12)
Finally, since r 1 ≤ r 2 , for any s < a, the inequality

1 1-s 2 r 2 2 ≤ 1 1-s 2 r 2 1
allows to find the relation Plugging the definition of α allows to conclude that (Cond ′ 1 ) is a necessary condition.

A cap D (r 2 , ϕ 2 ) ≤ A cap D (r 1 , ϕ 1 ) (E.
Proof of the part related to (Cond ′ 2 ) Here, we assume that R > R µ and that the growth condition is globalized:

∥h(Z -x) -h(Z -x ′ )∥ 2 ≥ µ min (∥x -x ′ ∥ 2 , R µ ) ∀x, x ′ ∈ B R .
Hence, we get using [START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF]Cor. 4.2. Taking u = R µ σµ, we get

E sup x∈B R ∆ ε (x) ≥ √ D 2 R µ σµ ln R R µ . (E.29)
Applying the same reasoning as the one for Lemma D.1 to the random variable sup x∈B R ∆ ε (x), implies that

P E sup x∈B R ∆ ε (x) -sup x∈B R ∆ ε (x) ≥ t ≤ exp - t 2 2σ 2 Λ 2 .
(E.30)

Define the event

E 2 def = sup x∈B R ∆ ε (x) ≥ √ D 2 R µ σµ ln R R µ -ρ 2 σΛ .
Combining the previous results, we obtain

P (E 2 ) ≥ 1 -exp(-ρ 2 2 /2).
The event E 1 ∩ E 2 happens with probability larger than 1exp(-ρ 2 1 /2)exp(-ρ 2 2 /2). In addition, this event together with the condition Combining the two results yields

f W = n∈Z D ⟨f W , s W (• -n/W )⟩ L 2 (R D ) s W (• -n/W ) = 1 (2πW ) D/2 n∈Z D f W (n/W )s W (• -n/W ),
which is nothing but Shannon-Whittaker theorem. Using again the fact that (s W (•n/W )) n∈Z D is an orthonormal basis yields:

⟨f W , g W ⟩ L 2 (R D ) = 1 (2πW ) D n∈Z D f W (n/W )g W (n/W ) (F.2)
for f W , g W ∈ PW(πW ).

We have PW(π) ⊂ PW(π/τ ). Hence, we can apply the previous identity with W = 1 τ . This yields

⟨f, g⟩ L 2 (R D ) = τ D (2π) D n∈Z D f (τ n)g(τ n).
(F.

3

)
The result is still valid by shifting f and g by x, resulting in the claimed result.

Figure 1 :

 1 Figure1: A 1D localization experiment. Left: the empirical standard deviation using the MLE (blue stars) coincides with the square root of the Cramér-Rao lowerbound (see[START_REF] Bredies | Inverse problems in spaces of measures[END_REF] for its expression) for low noise regimes. In high noise regimes, we observe a significant discrepancy. Right: realizations of the vector y for different noise levels. The green and red bars correspond to the true location x and the estimated one x respectively. Note that y-axis is different in the four graphs on the right.

Figure 2 :

 2 Figure 2: Phase transitions for single source localization with the MLE. Left: the heat map indicates the empirical probability of the event E r = [∥x -x∥ 2 ≤ r]. We observe a phase transition phenomenon: for a given r and a sufficiently low σ, the probability of success is overwhelming. Above a certain threshold (i.e., when σ ≥ σ 0 ), it decays rapidly to a low probability. The transition occurs close to the square root of the Cramér-Rao lower-bound (red line corresponding to r = CR(σ)) in the low noise regime. The dotted black curve corresponds to an empirical probability of 0.5 (the level line 0.5 of the phase transition diagram). The blue (resp. white) dashed curve corresponds to our theoretical upper (resp. lower) bound on this 0.5 level line. They closely circumscribe the phase transition and predict the behavior for large noise levels as well. Right: The convolution kernels h and the sampling points corresponding to the experiments on the left. From top to bottom: Gaussian kernel, the reference kernel of Example 4.1, and a (sub-sampled) cardinal sine kernel.

Assumption 4 . 1 .

 41 x is the unique global minimizer of the noiseless function ℓ 0 and ℓ ′′ 0 (x) ≻ 0. Assumption 4.1 is quite weak. To illustrate it, we can consider a simplified model without sampling, leading to the following result.

Proposition 4 . 1 (

 41 Generality of Assumption 4.

Figure 4 .

 4 In this example, different choices of values of µ and R µ are available depending on the sought for precision guarantees.

Example 4 . 1 (

 41 Reference kernel). We define a simple kernel h ref for which our geometrical quantities are trivial. It will help us later for interpreting our results. It corresponds to the hat function in the second row of Fig.2. Set D = 1 and

Figure 3 :

 3 Figure 3: Left: Illustration of quantities Λ, L, µ and R µ . The noiseless cost function ℓ 0 is sandwiched between two quadratic functions near x and between two constants far away from the origin. Right: The specific case h ref where µ = L.

  thus ℓ ref 0 is quadratic on each of these intervals. The remaining computation is the interpolation from known values of ℓ ref 0 at points (t/2) 2M t=-2M . The graph of ℓ ref 0 is depicted in Fig. 3 (right). Some elementary calculations yield:

  h = exp(-(•) 2 /(2σ 2 )) h = cos(ω1•) • bump h = cos(ω2•) • bump

Figure 4 :

 4 Figure4: Different kernels h (top) and the corresponding functions ℓ 0 (bottom) for x = 0. Left: a Gaussian with standard deviation 0.5. Middle and right: cosines with two different frequencies multiplied by a bump function. For the slowly oscillating cosine associated to the frequency ω 1 , we show that different choices of µ and R µ in Assumption 4.1 are possible with the green and red dashed curves. We can choose a large value of µ with a small radius R µ (see the red dashed lower bound). As an effect, the bounds we obtain in Theorem 4.1 will ensure that a highly accuracte estimate can be obtained for low noise regimes. However, they will suffer from a high probability of false detection with higher noise levels. On the other hand, we can choose a smaller value of µ (see the green dashed lower bound) with a larger radius R µ . As a result, our theorem provides sharper estimates for high noise regimes. The Cramér-Rao lower bound on its side is based on the curvature of ℓ 0 at x only. It therefore accomodates only with small noise levels and leads to an overoptimistic conclusion for the mean squared error of the estimator. The function on the right illustrates a pathological kernel for the Cramér-Rao bound: the bound converges to zero due to the high curvature at the origin, but there is a very high probability of false detection since shifted kernels correlate highly with h. Our theorems allow us to use a more precise lower enveloppe that provides sharp guarantees on the estimator location.

Theorem 4 . 2 (

 42 Necessary conditions). Under the same assumptions as in Theorem 4.1, R > R µ and

Figure 5 :

 5 Figure 5: Intuition behind Theorem 4.1.Left: Success (x ∈ B r ) occurs if there exists x ∈ B r (e.g., x = x) such that ℓ 0 (x) -∆ ε (x) (orange point) is lower than the infimum of ℓ 0 -∆ ε over B R \ B r (orange dashed line). Right: The green curve is an upper-bound of the typical amplitude of ∆ ε . The red curve is a lower-bound of ℓ 0 . An (informal) sufficient condition for x ∈ B r is that the red curve dominates the green one at r.

Figure 6 :

 6 Figure 6: Intuition behind Theorem 4.2. Left: Failure (x / ∈ B r ) occurs if there existsx t ∈ B R \ B r (with t = ∥x t -x∥ 2 ) such that ℓ 0 (x t ) -∆ ε (x t ) (orange point) islower than the infimum of ℓ 0 -∆ ε over B r (orange dashed line). Right: The green curve is a lower-bound of the typical amplitude of ∆ ε . The blue curve is an upperbound of ℓ 0 . An (informal) sufficient condition for x / ∈ B r is that the green curve dominates the blue one at t.

1 B. 1 .

 11 Establishing the Cramér-Rao lower-bound By [16, (3.20)], we know that the covariance matrix of any unbiased estimator x satisfies cov(x) ≽ I -1 (x) with [I(x)] d,d ′ def = E ∂ ln p(y|x) ∂x d • ∂ ln p(y|x) ∂x d ′ . (B.1)

D. Proof of Theorem 4. 1 D. 1 .

 11 An intermediary resultFor r ≥ 0, let B r def = {x ∈ R D , ∥x -x∥ 2 ≤ r}.

  and Λ D def = sup x∈D ∥D h (x, x)∥ 2 .(D.7)We have forδ ∈ R M f D (ϵ + δ) = σ sup x∈D ⟨D h (x, x), ϵ + δ⟩ ≤ σ sup x∈D ⟨D h (x, x), ϵ⟩ + σΛ D ∥δ∥ 2 , f D (ϵ + δ) = σ sup x∈D ⟨D h (x, x), ϵ + δ⟩ ≥ σ sup x∈D ⟨D h (x, x), ϵ⟩ -σΛ D ∥δ∥ 2 .Hence |f D (ϵ + δ)f D (ϵ)| ≤ σΛ D ∥δ∥ 2 and we can conclude that f D is Lipschitz continuous with constant σΛ D . Using [5, Theorem 5.6], we therefore get that, for any u > 0 and D ⊂ R D ,

Definition D. 1 (

 1 Covering number). The covering number N (δ, S, d) is defined as the minimal number of balls of radius δ in the pseudo-metric d needed to cover S.

. 15 )D. 1 . 3 .

 1513 Concluding the proof of Theorem D.1 Let θ i def = inf x∈Ωi ℓ 0 (x). Now, assume that θ i ≥ E i , ∀1 ≤ i ≤ I. (D.16)

D. 2 .

 2 Concluding the proof of Theorem 4.1 Proof. From Theorem D.1, the inequality (15) is valid if Ēi + ρ 2 + 2 ln(I)σ Λi ≤ inf x∈Ωi ℓ 0 (x) ∀1 ≤ i ≤ I.

  13]:N (u, B R , d) ≥ Rµσ u D for u ≤ R µ σµ.Using Sudakov's inequality[START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF] Thm 7.4.1] or[START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF] Thm 13.4], we obtain:

+ ρ 2 1 (

 21 σΛ < -σLr c √ D + ρ 1 implies that x / ∈ B r . F. Proof of Theorem 4.3 The equality (31) is a consequence of standard results in sampling theory. Set W > 0 and let s W denote the function which Fourier transform equals to F(s) = 2πW ) D/2 1 [-πW,πW ] D . A direct calculation shows that it corresponds to a scaled and tensorized cardinal sine. It is well known that the family (s W (•n/W )) n∈Z D is an orthonormal basis of PW(πW ) (see e.g. [18, Thm. 3.5] in 1D, and use the fact that the tensor product of an orthogonal basis is still an orthogonal basis). In addition, we have the identity for any f W ∈ PW(πW ) (obtained by direct calculation again) ⟨f W , s W (•n/W )⟩ L 2 (R D ) = f W (n/W ) • (2πW ) -D/2 . (F.1)

  ).B.2. Necessary and sufficient condition for attainmentNow, let us prove that the Cramér-Rao bound can be attained only in dimension D = 1 and for affine kernels h. To this end, we recall the second part of[START_REF] Kay | Fundamentals of statistical signal processing: estimation theory[END_REF] Thm. 3.2], adapted to our setting.Proposition B.1. An unbiased estimator x of x that attains the Cramér-Rao bound exists if and only if ∇

x ln p(y|x) = I(x) • (g(y)x), (B.5)

  Example of two sphere caps C 1 and C 2 . The representation gives their intersection on a plane passing through the centers of the spheres.Proof of Lemma E.2. From Assumption[START_REF] Kay | Fundamentals of statistical signal processing: estimation theory[END_REF], the problem is reduced to the Euclidean metric asN (u, S t , d) ≥ N u µσ , S t , d eucli . (E.15)From definition of the covering number, let's take balls B 1 , . . . , B N of radius ũ def = u µσ < t covering the sphere S t with N = N (ũ, S t , d eucli ). The result will come by considering the surface area of the caps C n def = S t ∩ B n . Indeed, since the balls B 1 , . . . , B N cover S t we have S t ⊆ N n=1 C n . Then, taking the Lebesgues measure leads to λ D-1 (S t ) ≤ We set ϕ n the polar angle of the sphere cap C n . With the notations introduced in the proof of Lemma E.1, we can reformulate the previous inequality as A D (t) ≤ Moreover, we get the following bounds from Lemma E.1A cap D (t, ϕ n ) ≤ A cap D (ũ, ψ n ) ≤ A D (ũ) (E.18)where ψ n is the polar angle of the counter-part sphere cap B t ∩ S n . This implies thatA D (t) ≤ N • A D (ũ). (E.19)This equation combined with the area formula (E.10) concludes sinceN (ũ, S t , d eucli ) ≥Going back to the necessary condition (E.7), using Sudakov's inequality[START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF] Thm 7.4.1] or[START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF] Thm 13.4], one gets thanks to lemma E.2We fix the value of α (and thus also the value of t) such that Moreover we check that the condition α ≥ 1 is well verified since it is equivalent to the statement (for small ρ 2 ) By adding the condition t = αr ≤ R µ , we finally get

	E sup x∈St	∆ ε (x) ≥	√	D -1 2	sup v∈[0,tµσ]	v ln	tµσ v	.	(E.21)
	Taking v = t 2 µσ, we get
	E sup x∈St	∆ ε (x) ≥	√	ln 2 4	tµσ	√	D -1.	(E.22)
	Injecting this inequality in (E.7), we have ρ 2 σLt ≤ √ ln 2 4 tµσ √ D -1 -Denoting t = αr with α ≥ 1, this simplifies as L 2 2 σ √ ln 2 4 α µ L √ D -1 -ρ 2 α -c t 2 -σLr c √ √ D + ρ 1 Figure E1: N ρ 2 α + c √ D + ρ 1 = √ ln 2 8 α µ L √ D -1. D + ρ 1 . ≥ Lα 2 2 r.	(E.23) (E.24) (E.25)
		c √	n=1 D + ρ 1 + ρ 2 ≥ √ λ D-1 (C n ). ln 2 8 µ L √ D -1	(E.16) (E.26)
	N n=1 which is true since c > 1 and µ ≤ L. Thanks to this setting, the necessary condition A cap D (t, ϕ n ). (E.17) (E.24) becomes σ √ ln 2 8 µ √ D -1 ≥ L 2 α 2 r. (E.27)
	r ≤	1 α	min R µ , σ	√	ln 2 4	µ L 2	√	D -1 .	(E.28)
										13)
	which concludes the proof. has Lemma E.2. For any 0 < u ≤ tµσ, noting d the pseudo-metric defined in (D.9), one N (u, S t , d) ≥ u . (E.14) tµσ D-1 A D (t) A D (ũ) = D-1 t ũ . (E.20)

Acknowledgments

This work was supported by the ANR Micro-Blind (grant ANR-21-CE48-0008), the University Research School EUR-MINT (State support managed by the National Research Agency for Future Investments program bearing the reference ANR-18-EURE-0023) and by the ANR LabEx CIMI (grant ANR-11-LABX-0040) within the French State Programme "Investissements d'Avenir". P. Weiss acknowledges the support of AI Interdisciplinary Institute ANITI funding, through the French "Investing for the Future-PIA3" program under the Grant Agreement ANR-19-PI3A-0004. The authors thank Yaw Tze Bong and Yann Delaporte for a preliminary study of this problem during a summer internship. They are grateful to the anonymous reviewers who really helped improving the overall presentation and guided us to relevant references.