Ayoub Belhadji

Rémi Gribonval

Revisiting RIP guarantees for sketching operators on mixture models

In the context of sketching for compressive mixture modeling, we revisit existing proofs of the Restricted Isometry Property of sketching operators with respect to certain mixtures models. After examining the shortcomings of existing guarantees, we propose an alternative analysis that circumvents the need to assume importance sampling when drawing random Fourier features to build random sketching operators. Our analysis is based on new deterministic bounds on the restricted isometry constant that depend solely on the set of frequencies used to define the sketching operator; then we leverage these bounds to establish concentration inequalities for random sketching operators that lead to the desired RIP guarantees. Our analysis also opens the door to theoretical guarantees for structured sketching with frequencies associated to fast random linear operators.

Introduction

Building up linear operators that preserve the distances between two sets is at heart of many problems in the field of inverse problems. The fetch for such linear operators gave birth to a rich literature at the intersection of signal processing and machine learning [Ach01, BM01, Sar06, AC06, MM09, MM12, [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF][START_REF] Foucart | An invitation to compressive sensing[END_REF]. Recently, a new family of inverse problems emerged in the contexte of compressive learning, also called sketched learning [START_REF] Keriven | Sketching for largescale learning of mixture models[END_REF][START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF][START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. These inverse problems are tailored to be used in the field of mixture modeling. In a nutshell, sketched learning is a paradigm aiming to scale up these learning tasks by conducting the learning task on a low dimensional vector, also called a sketch, that contains a "gist" of the initial dataset and that is suited for a specific learning task: sketching is the procedure that outputs the sketch for a given dataset. In practice, sketching boils down to embed a probability distribution π typically on X = R d into C m by considering a sketching operator A such that1

Aπ := X Φ(x)dπ(x) ∈ C m (1)
where Φ is a C m -valued function defined on X called the feature map. As shown in [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF], building up the linear operator A is indirectly constrained by the targeted learning task (e.g.: k-means clustering, or Gaussian Mixture Modeling). This constraint can be expressed using the Maximum Mean Discrepancy (MMD) [GBR + 12] defined as follows: considering a positive definite kernel 2 [BTA11] κ :

X × X → R, the MMD with respect to κ between two probability distributions π and π on X is defined using the norm • κ on the reproducing kernel Hilbert space (RKHS) H associated to κ by

π -π κ := sup f ∈H, f κ≤1 X f (x)dπ(x) - X f (x)dπ (x) . (2)
Equiped with the MMD, the general theory of [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF] suggests to look for sketching operators that satisfy

∀π, π ∈ G, (1 -δ) π -π 2 κ ≤ Aπ -Aπ 2 2 ≤ (1 + δ) π -π 2 κ , (3)
where G is a particular set of probability measures on X and δ ∈ [0, 1). When the kernel κ is shift-invariant, it is possible to build up a sketching operator satisfying (3) by considering random Fourier features [ZM15, [START_REF] Keriven | Sketching for largescale learning of mixture models[END_REF][START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. Initially, random Fourier features were introduced to scale up kernel methods [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF]. This family of approximations is suitable for a shift-invariant kernel κ for which Bochner's theorem [START_REF] Wendland | Scattered data approximation[END_REF][START_REF] Rudin | Fourier analysis on groups[END_REF] holds:

∀x, y ∈ X = R d , κ(x, y) = R d e 2πιω(x-y) κ(ω)dω, (4)
with κ a non-negative function. Although the framework of [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF] holds for more general kernels, the focus of this paper is indeed on shift-invariant kernels, for which we have κ(x, x) = κ(0, 0) = R d κ(ω)dω for every x ∈ X = R d . Moreover, we often simplify the analysis by assuming a normalized kernel, i.e., κ(0, 0) = 1. The results are easily extended to the non-normalized case. With the normalization assumption, the function κ satisfies R d κ(ω)dω = 1 and can be interpreted as a probability density function on the frequency vector ω ∈ R d . Based on the identity (4), the random Fourier feature map is constructed as follows: let ω 1 , . . . , ω m ∈ R d to be i.i.d. random variables with probability density κ(ω) with respect to the Lebesgue measure on R d , and define the random feature map

Φ(x) := 1 √ m (φ ωi (x)) i∈[m] ∈ C m , (5)
where here φ ω (x) = e 2πıω x ∈ C for each ω ∈ R d , and for any integer n ∈ N we denote [n] := {1, . . . , n}. With this design, the (random) empirical kernel κ Φ (x, y) := Φ(x), Φ(y) (where for any u, v ∈ C m u, v := u v, with v the complex conjugate of v) satisfies for every pair of vector x, y ∈ R d

Eκ Φ (x, y) = κ(x, y).

The study of the approximation κ Φ (x, y) ≈ κ(x, y) is a well established area of research. Indeed, since the publication of [START_REF] Rahimi | Random features for large-scale kernel machines[END_REF], many works followed tackling various aspects of this class of approximations. In particular, sharp uniform error bounds on compact sets for RFF were derived in [START_REF] Sutherland | On the error of random fourier features[END_REF][START_REF] Sriperumbudur | Optimal rates for random fourier features[END_REF], and connexions with kernelbased quadrature were established in [START_REF] Bach | On the equivalence between kernel quadrature rules and random feature expansions[END_REF]. Moreover, the quest to various designs of the frequencies were proposed: frequencies based on quasi-Monte Carlo sequences [START_REF] Yang | Quasi-monte carlo feature maps for shift-invariant kernels[END_REF], frequencies based on structured matrices [LSS13, CS16, CRS + 18]. We refer the reader to [START_REF] Liu | Random features for kernel approximation: A survey on algorithms, theory, and beyond[END_REF] for an exhaustive review on this topic.

As it was shown in [SGF + 10], the identity (6) somehow extends to pairs of probability distributions π, π on X

E π -π 2 κΦ = π -π 2 κ . (7)
This formula was crucial in the study of characteristic kernels carried in [SGF + 10].

The study of the fluctuations of ππ 2 κΦ around its expected value ππ 2 κ was carried in [START_REF] Zhao | Fastmmd: Ensemble of circular discrepancy for efficient two-sample test[END_REF] and [START_REF] Sutherland | On the error of random fourier features[END_REF]. Nevertheless, these results do not imply (3): the established guarantees have an additive form | ππ 2 κΦππ 2 κ | ≤ t for a given pair (π, π ) of probability distributions, while (3) have a multiplicative form and holds uniformly on G × G. A study of conditions under which (3) holds was undertaken in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] with a focus on the case where G = G k is a set of mixtures with k components that depend on parameters that belong to R d . In this context, it was shown that (3) holds with high probability provided that:

1. the sketch dimension, m, is large enough: a sufficient sketch size was proved to satisfy m = O(k 2 d) (up to logarithmic factors); and 2. a variant of the RFF (5) is used, with an appropriate importance sampling scheme.

The dependency of this provably good sketch size in k and d does not match the empirical simulations carried out (without importance sampling) in [START_REF] Keriven | Compressive k-means[END_REF], which suggest that (3) can hold with high probability for some m = O(kd) (again, possibly up to logarithmic factors).

To bridge the gap between theory and practice, one would ideally like to both get rid of the importance sampling assumption, which does not seem needed in practice, and to achieve guarantees for sketch sizes with a better dependency in k. In this work, we revisit the analysis of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] with two main contributions:

• we prove that m = O(k 2 d) remains a provably good size even without importance sampling;

• we explain why the high level structure of the proof technique of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF], as well as the structure of our new approach, prevents them from achieving better dependencies in k of provably good sketch sizes.

As we shall see later, our analysis is based on tools inspired from the literature of sparse recovery with incoherent dictionaries ; see Chapter 5 in [START_REF] Foucart | An invitation to compressive sensing[END_REF]. This quadratic dependency on number k of mixture components, which plays the role of a sparsity level, is thus not surprising. Whether the "right" dependency in k of provably good sketch sizes remain an open question. These contributions are obtained by introducing several technical ingredients. First, we provide deterministic sufficient conditions on the sketching operator A so that the Restricted Isometry Property (RIP) (3) holds for mixture models using weighted Fourier features under some conditions. This is achieved thanks to a parametrization of the so-called normalized secant set of the set G k with respect to the MMD. This parametrization uses the notion of dipoles defined and used in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. We extend the use of these tools and show how the proof of (3) boils down to the study of suprema of functions defined on R d . The benefit of this approach is to reduce the study from the normalized secant set, which is a set of signed measures with a geometry that is hard to grasp, to the much easier study of a few explicit functions defined on subsets of R d . Second, we leverage these deterministic sufficient conditions to establish the RIP when the sketching operator is random. This result is instantiated to carry out the proof of (3) in the case of a sketching operator built using i.i.d. frequencies. To constrast our result, which does not require the use of importance sampling with the analysis given in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF], we establish that the high level structure of the latter requires importance sampling. The technique we propose is thus both more general and much closer to practice. Moreover, we establish lower bounds showing the impossibility to achieve sharper estimates of provably good sketch sizes sufficient for a sketching operator based on Fourier feature maps: these impossibility results hold both for our analysis and existing one [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. Finally, we discuss the few steps that remain open to exploit our analysis to prove the RIP even when the frequencies are not necessarily independent, e.g. in the context of structured random Fourier features [LSS13, CS16, CRS + 18].

This article is structured as follows. In Section 2 we recall some notions and results from [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF][START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] that are relevant to our study, as well as their main limitations which motivate this work. In Section 3 we present our results. We conclude and discuss some perspectives in Section 4.

Main tools

We recall some results and definitions relevant to position our contributions.

Sketching operator

The (random) feature maps that we will consider will bear special relations with the considered kernel κ, this will soon be discussed. For the moment we observe that • for any bounded vector-valued function Φ : X → C m , one can define a sketching operator

A : P(X ) → C m π → X Φ(x)dπ(x), (8)
with P(X ) the set of probability distributions on X . Jordan decomposition [START_REF] Halmos | Measure theory[END_REF] allows to extend A to the set M(X ) of finite signed measures, see [GBKT21a, Appendix A.2.].

• for any bounded kernel, one can define for every probability distributions π, π ∈ P(X ) π, π κ := E X∼π E Y ∼π κ(X, Y ).

and extend this "inner product", as well as the definition (2) of the MMD, to all finite signed measures in M(X ). Thanks to a polarization identity, ν, ν κ = 1 4

ν + ν 2 κνν 2 κ , these can be manipulated as usual inner products and norms3 . We will write f, π := E X∼π f (X), with implicit integrability assumption of function f with respect to the probability distribution π. This is extended by a Jordan decomposition to f, π with ν ∈ M(X ). It should always be clear whether the bracket notation ., . stands for this shorthand or for the classical Hermitian inner product between vectors in C m .

Separated mixture model, normalized secant set, and dipoles

We focus our analysis on mixture modeling with a location-based family [GBKT21b, Definition 6.1]: given a base probability distribution π 0 on R d (for example π 0 may be the Dirac at zero, or a centered Gaussian) and a family Θ ⊆ R d of translation parameters, we consider (π θ ) θ∈Θ where π θ is the distribution of X + θ where X ∼ π 0 and observe that the map I : θ → I(θ) = π θ is injective. Given a translation invariant metric ρ on Θ ⊆ R d (for example, ρ(θ, θ ) may be the Euclidean distance between θ and θ , or θθ with any norm • on R d ), we denote T := (Θ, ρ, I) and consider the set of 2-separated k-mixtures [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] defined as

G k = k i=1 u i π θi ; u i ≥ 0, i∈[k] u i = 1, θ i ∈ Θ, ∀i = i ∈ [k], ρ(θ i , θ i ) ≥ 2 . ( 10
)
More general separated mixture models of the form (10) can be defined [GBKT21b, Section 5.2] with T := (Θ, ρ, I) for any metric space (Θ, ρ) and injective map I : Θ → P(X ), in which case we also denote π θ := I(θ). The study of (3) for general separated mixture models motivates the introduction of the normalized secant set S k defined as follows

S k := ν -ν ν -ν κ ; ν, ν ∈ G k , ν -ν κ > 0 . (11) Indeed, (3) is equivalent to sup ν∈S k Aν 2 2 -1 ≤ δ.
In the following, for every set T ⊂ { ν ν κ : ν ∈ M(X ), ν κ > 0} of normalized finite signed measures and every sketching operator A we denote

δ(T|A) := sup ν∈T Aν 2 2 -1 . (12)
As we shall see, the elements of the normalized secant set may be approximated as a mixture of elementary measures called normalized dipoles. Definition 1 (Dipoles [GBKT21b, Definitions 5.3, 5.6] ). A finite signed measure

ι ∈ M(X ) is a dipole w.r.t. T = (Θ, ρ, I) if ι = α 1 π θ1 -α 2 π θ2 , where θ 1 , θ 2 ∈ Θ, ρ(θ 1 , θ 2 ) ≥ 1 and α 1 , α 2 ≥ 0. Two dipoles ι, ι , are 1-separated if ι = α 1 π θ1 - α 2 π θ2 , ι = α 1 π θ 1 -α 2 π θ 2 ,
where ρ(θ i , θ j ) ≥ 1 for i, j ∈ {1, 2}. The set of normalized dipoles (with respect to kernel κ) is denoted

D = D(T ) := ι = ι/ ι κ , ι is a dipole such that ι κ > 0 , (13)
and D 2 = ⊆ D × D denotes the set of pairs of 1-separated normalized dipoles. Dipoles offer a convenient parametrization of the (un-normalized) secant set. Lemma 1 ([GBKT21b, Lemma 5.4]). Let π, π ∈ G k . There exist ≤ 2k nonzero dipoles (ι l ) l∈[ ] that are pairwise 1-separated and satisfy

π -π = i=1 ι i . (14)
In other words, every element of the (unnormalized) secant set ππ is the sum of at most 2k dipoles. The decomposition (14) is convenient when calculating the squared MMD norm π -

π 2 κ = i=1 ι i 2 κ + i =i ι i , ι i κ .
In particular, under some additional assumptions on the kernel that we now discuss, the cross scalar products ι i , ι i κ are close to 0 so that π -π 2 κ can be approximated by i=1 ι i 2 κ .

Kernel coherence

To conduct our analysis, we require further assumptions on the compatibility of the positive definite kernel κ with the parameterized family of distributions T := (Θ, ρ, I).

Definition 2. Given a family T := (Θ, ρ, I), a kernel κ is said to be 1. non-degenerate with respect to T if π θ κ > 0 for every θ ∈ Θ. This allows to define the T -normalized kernel κ as

∀θ, θ ∈ Θ, κ(θ, θ ) := π θ , π θ κ π θ κ π θ κ . ( 15
)
2. locally characteristic with respect to T [GBKT21b, Definition 5.5] if it is nondegenerate with respect to T and |κ(θ, θ )| < 1 for every θ, θ ∈ Θ such that 0 < ρ(θ, θ ) ≤ 1. This ensures that π θαπ θ κ > 0 for every α ∈ R whenever 0 < ρ(θ, θ ) ≤ 1.

Definition 3 (Coherence [GBKT21b, Definition 5.7]). Given an integer ≥ 1 thecoherence of κ with respect to T = (Θ, ρ, I), denoted c = c (κ) is the smallest c ≥ 0 such that, for any pairwise 1-separated dipoles

(ι i ) i∈[ ] such that i=1 ι i 2 κ > 0, we have 1 -c ≤ i=1 ι i 2 κ i=1 ι i 2 κ ≤ 1 + c. ( 16
)
The kernel κ has mutual coherence µ with respect to T if it is locally characteristic wrt T and (

µ = µ(D 2 = |κ) := sup (ι,ι )∈D 2 = | ι, ι κ | (17)
) 18
As shown in [GBKT21b, Lemma 5.8], if the kernel κ has mutual coherence µ with respect to T then κ has -coherence bounded by c := µ( -1). This is reminiscent (and indeed inspired by) classical results on incoherent dictionaries in sparse recovery, see e.g. [START_REF] Foucart | An invitation to compressive sensing[END_REF]Chapter 5]. In particular, if κ has mutual coherence bounded by µ < 1/(2k -1) then the quasi-Pythagorean property (16) holds for = 2k with

c = c 2k ≤ (2k -1)µ < 1. ( 19
)
This implies that the normalized secant set S k is made of "nice" mixtures of separated dipoles.

Proposition 1 ([GBKT21b, Lemma B.1]). Let k ≥ 1 be an integer, and denote by c = c 2k the 2k-coherence of the kernel κ with respect to T . Under the assumption that c < 1, we have

S k ⊂ 2k i=1 α i ι i : (1+c) -1 ≤ 2k i=1 α 2 i ≤ (1-c) -1 , α i ≥ 0, (ι i , ι j ) ∈ D 2 = , 1 ≤ i = j ≤ 2k . (20)
In other words, the normalized secant set S k is made of mixtures of 2k normalized dipoles with weights of controlled 2 norm. This decomposition comes in handy when looking for an upper bound of high order moments as we will study soon for measure concentration arguments.

Location-based families and shift-invariant kernels

In most of this paper we focus on shift-invariant kernels, generally assumed to be normalized (κ(0, 0) = 1). As often we use the abuse of notation κ(x, y) = κ(xy). When the family (π θ ) θ∈Θ used to define the mixture model (10) is location-based, we have [GBKT21b, Proposition 6.2]

∀θ ∈ Θ, π θ κ = π 0 κ , (21)
hence κ is non-degenerate with respect to T if, and only if, π 0 κ > 0. Moreover, the T -normalized kernel κ itself is also shift-invariant. We also abuse notations and denote κ(θ

-θ ) = κ(θ, θ ) = 1 π0 2 κ κ(π θ , π θ ).
The low-coherence property is satisfied by classical shift-invariant kernels and location-based families T [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF].

Example 1 (Mixtures of Diracs and the Gaussian kernel [GBKT21b, Definition 6.9]). In this case, π 0 is the Dirac distribution at 0, ρ = . 2 / where > 0, and κ is the Gaussian kernel:

κ(x, x ) := exp - x -x 2 2 2s 2 , ( 22
)
with s > 0 a scale parameter. The normalized kernel writes [GBKT21b, Section 6.3.1]

κ(θ -θ ) = exp - θ -θ 2 2 2s 2 . ( 23
)
By [GBKT21b, Theorem 5.16, Lemma 6.10, Theorem 6.11], κ is locally characteristic and its mutual coherence with respect to T is smaller than or equal to 12/(16(2k -1)) as soon as

≥ s/s k with s * k := (4 log(ek)) -1 . ( 24
)
Example 2 (Mixtures of Gaussians and the Gaussian kernel [GBKT21b, Definition 6.9]). In this case, we consider the Mahalanobis norm . Σ , defined by x Σ := x, Σ -1 x = Σ -1/2 x 2 for x ∈ R d , where Σ ∈ R d is a positive definite matrix, ρ = . Σ / where > 0, and π 0 = N (0, Σ). Finally κ is the Gaussian kernel:

κ(x, x ) := exp - x -x 2 Σ 2s 2 , ( 25
)
with s > 0 a scale parameter. The normalized kernel writes [GBKT21b, Section 6.3.1]

κ(θ -θ ) = exp - θ -θ 2 Σ 2(2 + s 2 ) . ( 26
)
By [GBKT21b, Theorem 5.16, Lemma 6.10, Theorem 6.11], κ is locally characteristic and its mutual coherence with respect to T is smaller than or equal to 12/(16(2k -1)) as soon as

≥ √ s 2 + 2 s k with s * k := (4 log(ek)) -1 . ( 27
)

Random Fourier features

The analysis in [START_REF] Keriven | Sketching for largescale learning of mixture models[END_REF][START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] is conducted using a variant of the random Fourier feature map described in the introduction, using importance sampling. It also uses the more general notion of a κ-compatible random sketching operator.

Definition 5. Consider a kernel κ on X × X and a random feature map Φ defined as in (5) from a parametric family {φ ω : X → C} ω∈Ω and random parameters (ω 1 , . . . , ω m ), i.i.d. or not. The feature map (and by extension the resulting sketching operator A) is said to be κ-compatible if the expected value (with respect to the draw of frequencies) of the hermitian inner-product Φ(x), Φ(y) is exactly κ(x, y), cf (6).

Definition 6. Given a weight function w : R d → (0, +∞), a sketching operator A is a w-weighted Fourier feature (w-FF) sketching operator if it is built from a feature map Φ as in (5) with some frequency vectors ω 1 , . . . , ω m and individual components defined as

φ ω = φ w ω : x → e 2πıω x /w(ω). ( 28
)
If the frequency components are jointly drawn (i.i.d. or not) from some probability distribution then A is called a w-weighted random Fourier feature (w-RFF) sketching operator.

We will often drop the the dependency of φ ω in w for brevity of notation, and call A a WFF (or RFF) sketching operator when there is no need to specify the corresponding w.

Definition 7. Consider a normalized shift-invariant kernel κ on X = R d . A weight function w : R d → (0, ∞) is said to be κ-compatible if R d w 2 (ω)κ(ω)dω = 1. ( 29
) Example 3. Given a normalized shift-invariant kernel κ on X = R d , if w is κ- compatible then Λ(ω) := w 2 (ω)κ(ω) ( 30
)
defines a probability density function. For frequency vectors drawn (i.i.d. or not) with common marginal probability density function Λ and any x, y we have

E ω∼Λ φ w ω (x)φ w ω (y) = w -2 (ω)e 2πıω (x-y) Λ(ω)dω = e 2πıω (x-y) κ(ω)dω = κ(x -y), (31)
hence the random feature map Φ is κ-compatible (Definition 5)

E ω1,...,ωm Φ(x), Φ(y) = 1 m m j=1 E ω1,...,ωm φ w ωj (x)φ w ωj (y) = 1 m m j=1 E ωj ∼Λ φ w ωj (x)φ w ωj (y) = κ(x, y), moreover, ∀ν, ν ∈ S k , E ω∼Λ φ w ω , ν φ w ω , ν = ν, ν κ . ( 32
)
Specializing this to ν = ν yields E ω∼Λ | φ w ω , ν | 2 = ν 2 κ .
With possibly distinct marginal densities ω j ∼ Λ j , we similarly get that the expectation of Φ(x), Φ(y) is w -2 (ω)e 2πıω (x-y) 1 m ( m j=1 Λ j (ω))dω hence the same conclusion holds if, and only if, the "average marginal density" satisfies almost everywhere

1 m ( m j=1 Λ j (ω)) = w 2 (ω)κ(ω). ( 33
)
It can also occur that the frequencies ω 1 , . . . , ω m are not independent, for example using structured random features [LSS13, CS16, CRS + 18]. Assuming here for simplicity that m is a multiple of d, the construction of such frequencies is such that the matrix Ω ∈ R d×m with columns ω j , 1 ≤ j ≤ m is defined as the concatenation of m/d i.i.d. random matrices

B i ∈ R d×d , 1 ≤ i ≤ m/d. This is advantageous when each B i is structured in such a way that the product Bz for z ∈ R d costs O(d log(d)) instead of O(d 2
), e.g. when d is a power of two and B = D 1 HD 2 HD 3 H with H the matrix associated to the (fast) Hadamard transform, and D , 1 ≤ ≤ 3 appropriate random diagonal matrices. When d is not a power of 2 and/or m is not a multiple of d the construction can be adapted using padding techniques. We refer the reader to [Cha20, Chapter 5], where an overview of such techniques is summarized. It can also be proved that under appropriate conditions the resulting random feature map Φ is still κ-compatible (Definition 5), see e.g. [LSS13, Lemma 7] and [Cha20, Lemma 5.6] for results when κ is a Gaussian kernel.

Existing results and their limitations

To establish a bound of the type (3) with a general mixture model, or equivalently to bound the constant δ(S k |A) of (12) the strategy deployed in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] exploits covering numbers, pointwise concentration, and a deterministic bound on a certain Lipschitz constant. Indeed, if a family

(ν i ) i∈[N ] of elements of the secant set S k satisfies ∀ν ∈ S k , ∃i ∈ [N ], Aν 2 2 -Aν i 2 2 ≤ τ 2 , (34)
then sup

ν∈S k Aν 2 2 -1 ≤ sup i∈[N ] Aν i 2 2 -1 + τ 2 . ( 35
)
hence proving that δ({ν 1 , . . . , ν N }|A) ≤ τ /2 holds is sufficient to deduce that δ(S k |A) ≤ τ . Moreover, assuming there is v > 0 such that for every sketch size m ≥ 1 the corresponding RFF sketching operator A satisfies a punctual concentration estimate of the form sup

ν∈S k P Aν 2 2 -1 > τ 2 ≤ 2 exp - m v , (36)
a union bound allows to deduce that δ({ν 1 , . . . , ν N }|A) ≤ τ /2 holds with probability at least 1 -2N • exp(-m/v) on the draw of A. These arguments show that, for any 0 < η < 1, if the sketch size satisfies m ≥ v log 2N /η then δ(S k |A) ≤ τ with probility at least 1η.

The smallest size of a family satisfying (34) is a covering number of X = S k with the pseudo-metric d(ν, ν ) := | Aν 2 2 -Aν 2 2 | (see e.g. [START_REF] Cucker | On the mathematical foundations of learning[END_REF] for the wellknown definition of coverings in a pseudo-metric space (X, d), and covering numbers, denoted N (X, d, ) at scale > 0). However, in the case of random sketching, this pseudo-metric depends on the random feature map Φ (or equivalently on the random sketching operator A). To circumvent this difficulty the approach of [ For RFF sketching with location-based families, we will see that getting a finite M highly constrains the function w (cf (28)). A primary objective of this paper is to relax this constraint.

For the concentration estimate (36), the approach of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] is generic for general mixture models and general sketching operators defined with a feature map as in (5) using a parameterized family φ ω where ω ∼ Λ are i.i.d. parameters. It combines a Bernstein inequality with an assumption on higher order moments on normalized dipoles. Indeed, a consequence of Proposition 1 is that if the 2k-coherence of κ is bounded by c then4 ∀q ≥ 2, sup

ν∈S k E ω∼Λ | φ ω , ν | 2q ≤ 2k 1 -c 2q sup ι∈D E ω∼Λ | φ ω , ι | 2q , (38)
i.e., controlling the moments on normalized dipoles is enough to control them on the normalized secant. Assuming a κ-compatible random feature map, this was shown to imply a concentration of the squared norm of the sketch Aν 2 2 around its expected value [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]Theorem 5.11].

The following is the specialization of [GBKT21b, Theorem 5.11] to the case of a κ-compatible RFF sketching operator with i.i.d. frequencies ω j ∼ Λ, 1 ≤ j ≤ m. Consider w a κ-compatible weight function, Λ = w 2 κ, and assume that there

β 1 > 0 and β 2 ≥ 1 such that ∀q ≥ 2, sup ι∈D E ω∼Λ | φ w ω , ι | 2q ≤ q! 2 β 1 β q-1 2 . ( 39
)
Then for every m ≥ 1 the RFF sketching operator A built with i.i.d. random frequencies ω j ∼ Λ is κ-compatible and ∀τ > 0, sup

ν∈S k P Aν 2 2 -1 > τ ≤ 2 exp - m v , ( 40
)
where v = v(k, τ ) := 2v k (1 + τ /3)/τ 2 , with v k = 16ekβ 2 log 2 (4ekβ 1 ).
The quantity v(k, τ ) > 0 is reminiscent of a variance and depends on k, τ (as displayed by the notation) but also more implicitly on sup ι∈D E ω∼Λ | φ w ω , ι | 2q , q ≥ 2 via the constants β 1 , β 2 . As will shortly see, the dependence in k is something we pay when estimating the sketch size, and it is natural to wonder whether this is due to the analysis or intrinsic. A side contribution of this paper is to show that this is somehow inevitable for this type of result.

The above arguments from [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] lead to the following result.

Theorem 2. Consider T κ, w, Λ, β 1 > 0, β 2 ≥ 1 as in Theorem 1. Assume that (39) holds, and that the constant M defined in (37) is finite. Then, with v(k, •) as in Theorem 1, we have

∀τ > 0, P δ(S k |A) > τ ≤ 2N S k , . F , τ 2M exp - m v(k, τ /2) . (41)
In particular, under the assumptions of Theorem 2, the property δ(S k |A) ≤ τ holds with probability at least 1η where 0 < η < 1 as soon as the sketch size satisfies

m ≥ v(k, τ /2) log 2N S k , . F , τ 2M /η . (42)
However, this estimate on a sufficient sketch size is only relevant when the constant M defined in (37) is finite and N (S k , . F , τ /(2M )) < +∞. By [GBKT21b, Theorem 5.12, Theorem 5.15, Lemma 6.4, Lemma 6.7], this is the case when κ is strongly locally characteristic with respect to T (a property satisfied in Examples 1 and 2, cf [GBKT21b, Theorem 6.11] ) under the assumption that sup

ω∈R d | φ w ω , π 0 | • max(1, ω , ω 2 ) < +∞ (43)
with . the dual norm of . defined by u := sup v ≤1 u v. Then, by [GBKT21b, Theorem 5.12, Lemma 6.7], we have for fixed > 0, log N (S k , . F , ) = O(kd) up to logarithmic factors in k, d, 1/ , so that a sufficient sketch size to have the desired result with high probability can be shown to satisfy m = O(k 2 d) up to logarithmic factors5 in k, d, M/τ . Condition (43) constrains the choice of weight function w for models such as mixtures of Diracs. Indeed, for this family of mixtures | φ w ω , π 0 | = 1/w(ω) so that (43) implies w(ω) max(1, ω , ω 2 ) (which imposes constraints on the behavior of w both around ω → 0 and ω → +∞). This is the main reason why the analysis in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] is limited to random Fourier features with importance sampling, while plain sampling seems enough in practical experiments. The main contribution of this paper is to establish results valid without assuming (43).

In summary, besides a (strongly locally characteristic) kernel with bounded 2kcoherence and a κ-compatible weight function w, existing results are built on the following assumptions:

1. moment conditions (39) on Λ = w 2 κ, to establish punctual concentration; 2. growth conditions (43) on w, to control the Lipschitz constant M from (37) and the associated covering numbers;

3. i.i.d. frequencies ω j ∼ Λ, 1 ≤ j ≤ m.
Under these assumptions, a sketch size of the order of k 2 d (up to logarithmic factors) is proved to be sufficient. As experiments conducted in [START_REF] Keriven | Compressive k-means[END_REF] suggested that the same result should hold with a smaller sufficient sketch size m = O(kd), this raises the question whether the theoretical bound of Theorem 2 can be refined. An approach which would provide an easy fix would be if we could simply remove a k factor in the punctual concentration estimate of Theorem 1 via a more subtle analysis. This would indeed naturally insert in the analysis of either [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] or of this work to yield the desired order of magnitude of m. A second contribution of this work is to show that such a uniform improvement of concentration estimates is simply not possible.

Main results

This work aims to overcome some shortcomings of the theoretical analysis given in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. First, we show in Section 3.1 that some of the growth conditions (43) are necessary to exploit the analysis given in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. Then, in Section 3.3 we give our main contribution: we provide an alternative analysis that allows to completely relax the growth conditions (43) on w. This yields results (still with a sketch size m of the order of k 2 d) for a much less constrained family of importance sampling schemes, including plain sampling w ≡ 1. This is primarily achieved by circumventing the deterministic control of the Lipschitz constant M from (37): instead, we provide a stochastic control of a "typical" Lipschitz constant, thanks to a reduction of the stochastic control of δ(S k |A) to a stochastic control of its equivalent on dipoles, δ(D|A), and of the coherence of the sketching operator, µ(D 2 = |A). This yields a substantial streamlining of the analysis which is then further reduced to the equivalent quantities for so-called normalized monopoles and balanced normalized dipoles. This is achieved thanks to deterministic bounds on δ(S k |A) established in Section 3.2. Finally, we show in Section 3.4 that both the analysis given in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] and the one given in this work cannot be fixed by a simple improvement of concentration estimates to to close the gap between sufficient sketch sizes endowed with theoretical guarantees, which scale essentially as O(k 2 d), and practically observed sketch sizes, which scale as O(kd) [START_REF] Keriven | Compressive k-means[END_REF].

On the necessity of conditions (43)

As mentioned in Section 2.6, the analysis of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] assumes that condition (43) holds to obtain that M := sup ν∈S k ν F and the covering numbers N (S k , . F , ) are finite. Here we establish a partial converse. The following Proposition is proved in Appendix A.3. Proposition 2. Consider a normalized shift-invariant kernel κ. Consider a locationbased family T = (Θ, , I) with base distribution π 0 where Θ contains a neighborhood of zero and (θ, θ ) := θθ for some arbitrary norm • on R d . Assume that κ, as defined in (15), is C 2 at zero, and assume that ∇ 2 κ(0) ∈ R d×d , the Hessian matric of κ at 0, is non-zero. Then, for weighted Fourier features, we have for every integer k ≥ 1, and separated k-mixture model G k from (10)

sup ν∈S k ν F ≥ sup ω∈R d | φ w ω , π 0 | π 0 κ max 1, 2π ∇ 2 κ(0) op ω . A direct consequence of Proposition 2 is that if sup ν∈S k ν F < +∞ then sup ω∈R d | φ w ω , π 0 | max (1, ω ) < +∞
which is reminiscent of (43) and plays the role of a partial converse.

In the setting of mixtures of Diracs defined in Example 1, we have | φ w ω , π 0 | = 1/w(ω) (cf (28)) and κ is C 2 at 0 with ∇ 2 κ(0) = 0, thus we can apply Proposition 2, and we get that there exists a constant C > 0 such that

∀ω ∈ R d , w(ω) ≥ C max (1, ω ) .
Thus, the proof technique of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF], which is summarized in Theorem 2, indeed requires the weight functions w(ω) to grow with ω to provide non-trivial results. It is in particular inapplicable to the "flat" weight function w(ω) = 1. In contrast, this weight function is covered by our Corollary 2. It is an interesting challenge left to future work to determine if (43) is in fact fully necessary to have both sup ν∈Sκ ν F < +∞ and N (S k , . F , ) < ∞ for some > 0.

Sharp deterministic bounds on δ(S k |A)

In light of Proposition 2, we propose an alternative analysis to control δ(S k |A) that does not require condition (43). This subsection focuses on the deterministic part of this analysis: first, we upper bound δ(S k |A) (which is defined as a supremum over the normalized secant set) using quantities defined on simpler sets made of dipoles (Proposition 3); then the latter are themselves controlled in terms of even simpler, quantities defined in terms of monopoles and balanced dipoles (Proposition 4); finally all considered quantities are explicitly written as suprema of empirical averages over frequency vectors ω j (Proposition 5). This will be used in the next subsection to control all quantities in the context of a random sketching operator A. As we will see, the main price to pay for this alternative analysis is that (unlike in Theorem 2, and more generally in results of the same flavor inspired by compressive sensing) δ(S k |A) is no longer proved to be arbitrarily small with high probability when the sketch size m is large enough, but only arbitrarily close to a quantity (smaller than one) depending on the 2k-coherence of the kernel κ.

From the normalized secant set to normalized monopoles and balanced dipoles

As a first step we bound the targeted quantity, which is defined as a supremum on the normalized secant set, in terms of two suprema defined on simpler sets of normalized dipoles.

Proposition 3 (From the secant set to normalized dipoles). Consider a kernel κ, a family T , and an integer k ≥ 1 such that κ has its 2k-coherence with respect to T bounded by 0 ≤ c < 1. Consider a sketching operator A defined via (1) with any feature map Φ(•) such that Aπ θ is well-defined for every probability distribution in the family T . We have

δ(S k |A) ≤ 1 1 -c c + δ(D|A) + (2k -1)µ(D 2 = |A) . ( 44
)
The proof, which is given in Appendix A.4, is essentially an adaptation of a bound of the restricted isometry constant for incoherent dictionaries in sparse recovery, see e.g. [START_REF] Foucart | An invitation to compressive sensing[END_REF]Chapter 5]. The minor technicality is to take into account deviations to the normalization of dictionary columns, which is captured by the term δ(D|A).

The upper bound (44) reduces the study of δ(S k |A) to that of δ(D|A) and µ(D 2 = |A). Note that this bound is only relevant if we can ensure that δ(S k |A) < 1 when δ(D|A) and µ(D 2 = |A) are sufficiently small, i.e., if c/(1c) < 1, which is possible to achieve in practice by a proper selection of the parameters of the kernel (see Example 2).

We now push the analysis further to scrutinize δ(D|A) and µ(D 2 = |A). As these two quantities are defined as suprema of a function defined on D and D 2 = respectively, which are abstract sets of measures for which the topology is hard to grasp intuitively, we show that both δ(D|A) and µ(D 2 = |A) boil down to suprema of functions defined on subsets of R d .

From now on we specialize to a location-based family T and a shift-invariant kernel κ that is locally characteristic with respect to T . In this setting we have the following

property of normalized dipoles [GBKT21b, Lemma C.1] D = ν ν κ , ν = π 0 -1 κ s(π θ -απ θ ); s ∈ {-1, 1}, 0 ≤ α ≤ 1, 0 < (θ, θ ) ≤ 1 , (45)
where since κ is locally characteristic we have ν κ > 0. In other words, for such κ and T , a normalized dipole is characterized by a sign s ∈ {-1, 1}, the two nodes θ, θ ∈ Θ that satisfies 0 < (θ, θ ) ≤ 1 and a parameter α ∈ [0, 1] that characterizes how balanced is the normalized dipole. This suggests the following definitions.

Definition 8. Given a location-based family T and a shift-invariant kernel κ that is locally characteristic with respect to T , the set of normalized monopoles is defined by

M = ν ν κ , ν = π 0 -1 κ sπ θ ; s ∈ {-1, 1}, θ ∈ Θ . (46)
The set of balanced normalized dipoles is defined by

D = ν ν κ , ν = π 0 -1 κ s(π θ -π θ ); s ∈ {-1, 1}, 0 < (θ, θ ) ≤ 1 . ( 47
)
In a nutshell, normalized dipoles correspond to α = 0, while normalized balanced dipoles correspond to α = 1. Moreover, with a slight abuse of notation we define shorthands to denote the sets of all elements (ι, ι ) ∈ D 2 = (i.e., of pairs of separated normalized dipoles) where each elements is resticted to be either a monopole or a balanced dipole:

M 2 = := M 2 ∩ D 2 = , M × D = := (M × D) ∩ D 2 = , D2 = := D2 ∩ D 2 = . (48)
Now, we are ready to state the following result which is proved in Appendix A.5.

Proposition 4 (From normalized dipoles to normalized monopoles and balanced dipoles). Consider T = (Θ, ρ, I) a location-based family with base distribution π 0 where ρ(•, •) = • -• for some norm • , and κ a normalized shift-invariant kernel that is locally characteristic with respect to T . Considering the sets of (normalized) monopoles and dipoles associated to T , and A a WFF sketching operator (cf Definition 6) with arbitrary frequencies ω 1 , . . . , ω m , we have

δ(D|A) = max δ(M|A), δ( D|A) . ( 49
)
If in addition κ ≥ 0 we also have

1 ≤ µ(D 2 = |A) max(µ(M 2 = |A), µ( D2 = |A), µ(M × D = |A)) ≤ 3. ( 50
)
The lower bound holds regardless of the assumption κ ≥ 0.

Inspecting the proof shows that δ(D|A) ≥ max δ(M|A), δ( D|A) is valid for any sketching operator such that Aπ θ is well defined for any distribution in the family T . Similarly the lower bound in (50) holds under this relaxed assumption. It remains open whether the converse bounds extend (possibly with weaker constants) beyond the case of WFF operators and location-based families. It also remains open whether the upper bound in (50) (or a qualitatively equivalent but larger bound) still holds without the assumption that κ ≥ 0. This is left to future work, as this assumption is satisfied by all concrete kernels we will work with.

Expression using the supremum of certain empirical processes

The main overall consequence of Proposition 3 and Proposition 4 is that under the appropriate assumptions we have • , and assume that κ is locally characteristic with respect to T . Let Ω ∈ R d×m be a matrix with arbitrary columns ω 1 , . . . , ω m and A = A Ω be a WFF sketching operator (cf Definition 6) with frequencies ω 1 , . . . , ω m . With φ ω defined as in (28), define for

δ(S k |A) ≤ 1 1 -c c+max δ(M|A), δ( D|A) +(6k-3) max µ(M 2 = |A), µ( D2 = |A), µ(M× D = |A)) (51
ω ∈ R d , x, x ∈ R d such that κ(x) < 1 and y ∈ R d ψ(ω) := | π 0 , φ ω | 2 π 0 2 κ (52) f d (x|ω) := 2 sin 2 ω, x /2 1 -κ(x) (53)
f mm (y|ω) := cos ω, y (54)
f md (x, y|ω) := 2 sin ω, x /2 sin ω, y + x/2 2(1 -κ(x)) (55) f dd (x 1 , x 2 , y|ω) := 4 sin ω, x 1 /2 sin ω, x 2 /2 cos ω, y + x 2 /2 -x 1 /2 2(1 -κ(x 1 )) 2(1 -κ(x 2 )) . (56)
Denote Ω ∈ R d×m the matrix with columns

ω j , 1 ≤ j ≤ m and Ψ m (Ω) := 1 m m j=1 ψ(ω j )
and for ∈ {m, d, mm, md, dd}

Ψ (•|Ω) := 1 m m j=1 ψ(ω j )f (•|ω j ). ( 57
) Denote Θ -Θ := {x -x : (x, x ) ∈ Θ 2 }.
With the sets of (normalized) monopoles and dipoles associated to T as defined in (46), ( 47) and (48), we have

δ(M|A) = 1 -Ψ m (Ω) , (58)
with

Θ d := x ∈ Θ -Θ, 0 < x ≤ 1 , we have δ( D|A) = sup x∈Θ d 1 -Ψ d (x|Ω) , (59)
with

Θ mm := y ∈ Θ -Θ, 1 ≤ y , we have µ(M 2 = |A) = sup y∈Θmm Ψ mm (y|Ω) , (60)
there exists a set

Θ md ⊂ Θ d × Θ mm , s.t. µ(M × D = |A) = sup (x,y)∈Θ md Ψ md (x, y|Ω) , (61)
there exists a set

Θ dd ⊂ Θ d × Θ d × Θ mm , s.t. µ( D2 = |A) = sup (x1,x2,y)∈Θ dd Ψ dd (x 1 , x 2 , y|Ω) . (62)
NB: Since κ is locally characteristic, κ(x) < 1 for x ∈ Θ d hence all of the above functions are well defined.

Lipschitz property and covering numbers

The study of the suprema of functions Ψ (z|Ω) (as defined in (57)) for random i.i.d. frequencies ω j is classical and fits within the general theory of empirical processes. It typically relies on establishing pointwise concentration inequalities for Ψ (z|Ω) and showing that with high probability on the draw of frequencies Ω the function Ψ (•|Ω) is Lipschitz with respect to a metric ∆ on Θ such that the covering numbers of Θ with respect to ∆ are well controlled.

The following result establishing a Lipschitz bound is proved in Appendix A.7.

Theorem 3 (Lipschitz bound). Let T := (Θ, ρ, I) be a location-based family with base distribution

π 0 on R d , with Θ ⊆ R d a bounded subset, ρ(•, •) := • -• where • is some norm on R d .
Let κ be a non-degenerate normalized shift-invariant kernel on R d . Assume that there is some norm • a on R d and a function κ : [0, +∞) → R such that, with R := sup x∈Θ d x a , the normalized kernel κ(x) defined in (15) satisfies for every

x ∈ R d such that x a ≤ R κ(x) = κ( x a ) . (63)
Assume that the following function is of class

C 1 on (0, R) α : r > 0 → α(r) := r 1 -κ(r) (64)
and that

C κ := sup 0<r≤R max(1, α 2 (r), |α (r)| 2 ) < ∞. ( 65
)
Consider ψ(•) defined as in (52) with φ ω defined as in (28), Ω ∈ R d×m with arbitrary columns ω 1 , . . . , ω m , and Ψ (•|Ω), Θ defined as in Proposition 5 for ∈ {d, mm, md, dd}. Then, we have for each ∈ {d, mm, md, dd}

∀z, z ∈ Θ , |Ψ (z|Ω) -Ψ (z |Ω)| ≤ 6Ψ 0 (Ω) • C κ • ∆ (z, z ), ( 66
)
where

Ψ 0 (Ω) := 1 m m j=1 ψ(ω j )f 0 (ω j ), f 0 (ω) := 3 i=1 ω i a, . (67)
and the metrics ∆ on the domains Θ , ∈ {d, mm, md, dd} are defined as

∆ d (x, x ) := | x a -x a | + x x a - x x a a , (68)
∆ mm (y, y

) := y -y a , (69)
∆ md ((x, y), (x , y

)) := ∆ d (x, x ) + ∆ mm (y, y ), (70)
∆ dd ((x 1 , x 2 , y), (x 1 , x 2 , y )) := ∆ d (x 1 , x 1 ) + ∆ d (x 2 , x 2 ) + ∆ mm (y, y ), (71)
Covering numbers are controlled using the following result established in Appendix A.7.4.

Proposition 6 (Covering numbers). Define D := diam a (Θ) = sup x∈Θ-Θ x a . For every τ > 0, and for each ∈ {d, mm, md, dd}, we have

N (τ ) := N (Θ , ∆ , τ ) ≤ 1 + 64(D + 1)/τ 3d+2 . ( 72
)

Results for random sketching

In this section, we leverage Section 3.2 to establish RIP results for random sketching.

We first establish a generic result before exploiting it for specific examples and showing that it allows to improve upon and to extend existing work from the literature.

Theorem 4. Consider T = (Θ, ρ, I), κ ≥ 0 and • a satisfying the assumptions of Theorem 3, and C κ as in (65). Assume that κ has its mutual coherence with respect to T bounded by 0 < µ < 1/10. Let k ≥ 1 be an integer such that 1 ≤ k < 1 10µ , and denote c := (2k -1)µ. Let w be a κ-compatible weight function (cf Definition 7). Consider an integer m ≥ 1 and Ω ∈ R d×m a random matrix (possibly with non i.i.d. columns ω 1 , . . . , ω m ), such that the average marginal density of the ω j 's satisfies (33). Denote Ψ (•|Ω), Θ as in Proposition 5 for ∈ {d, mm, md, dd}, and Ψ 0 (Ω) as in Theorem 3.

Given any M > 0, 0 < τ < 1 -5c, v > 0, if the following inequalities hold

P Ψ 0 (Ω) > M ≤ 2 exp - m v , (73)
P |Ψ m (Ω) -EΨ m (Ω)| > τ 4 ≤ 2 exp - m v , (74)
∀z ∈ Θ d , P |Ψ d (z|Ω) -EΨ d (z|Ω)| > τ 8 ≤ 2 exp - m v , (75)
∀ ∈ {mm, md, dd}, ∀z ∈ Θ , P |Ψ (z|Ω) -EΨ (z|Ω)| > τ 16k ≤ 2 exp - m v , (76)
then the w-FF sketching operator A (cf Definition 6) with frequencies ω 1 , . . . , ω m satisfies

P δ(S k |A) > 4c + τ 1 -c ≤ 12 • exp - m v 1 + C/τ ) 3d+2 , (77)
where

C := 6144C κ M • k(1 + diam a (Θ)). ( 78
)
Under the assumption of the theorem, a consequence is that for any 0 < η < 1

m ≥ v(3d + 2) log(1 + C/τ ) + log(10/η) =⇒ P δ(S k |A) > 4c + τ 1 -c ≤ η. ( 79
)
hence estimating the order of magnitude of v, C and τ satisfying the assumptions of the theorem is key to estimate a sufficient sketch size. The proof of Theorem 4 is given in Appendix A.8. Our next result establishes the concentration inequalities ( 74)-( 75)-( 76) under a sub-exponentiality assumption on functions associated to the random frequencies ω j , 1 ≤ j ≤ m.

Definition 9. A real-valued random variable is sub-exp(ν, β), where ν, β ≥ 0, if Ee λ(X-EX) ≤ e λ 2 ν 2 2 , ∀|λ| ≤ 1 β . ( 80
)
The case β = 0 corresponds to a sub-Gaussian variable.

If X is sub-exp(ν, β) then by the standard Cramér-Chernoff method

6 ∀t > 0, P X -EX > t ≤ 2 max e -t 2 2ν 2 , e -t β ≤ 2 exp - t 2 2ν 2 + βt . ( 81
)
We establish the inequalities ( 74)-( 75)-( 76) by showing that Ψ m (Ω) and Ψ (z|Ω), ∈ {d, mm, md, dd}, z ∈ Θ , are sub-exponential with controlled expectations. =A wellknown property of sub-exp random variables is that if

X 1 , . . . , X m are independent sub-exp(ν, β) then 1 m m j=1 X j is sub-exp(ν/ √ m, β/m).
Thus, when the frequencies

ω j ∼ Λ, 1 ≤ j ≤ m are i.i.d. random variables, in order to prove that Ψ m (Ω) is sub- exp(ν/ √ m, β/m
), it is enough to prove that the random variables ψ(ω j ), 1 ≤ j ≤ m, are sub-exp(ν, β). Similarly, for ∈ {d, mm, md, dd} and z ∈ Θ , in order to prove that Ψ (z|Ω) is sub-exp(ν/ √ m, β/m) it is enough to prove that the random variables ψ(ω) and ψ(ω)f (z|ω), ω ∼ Λ, are sub-exp(ν, β). For this purpose, the following lemma (proved in Appendix A.9.1) will be crucial.

Lemma 2. Under the assumptions of Theorem 5 (see below), for each ∈ {d, mm, md} and z ∈ Θ , there exists

x 0 ∈ R d satisfying x 0 a = 1 such that |f (z|ω)| ≤ ( C κ | ω, x 0 |) p , ∀ω ∈ R d , with p d = 2, p mm = 0, p md = 1. (82)
Moreover, for each z ∈ Θ dd , there are

x i ∈ R d such that x i a = 1, i = 1, 2 and |f dd (z|ω)| ≤ C κ 4 ω, x 1 2 + ω, x 2 2 , ∀ω ∈ R d .
Using Lemma 2, we obtain that the random variables ψ(ω)f (z|ω) are (almost surely) bounded by random variables of the form ψ(ω)( √ C κ | ω, x |) p , with x ∈ R d and p ∈ {0, 1, 2}, allowing to leverage the following lemma proved in Appendix A.9.2. Lemma 3. Consider real-valued random variables X, Y where Y is sub-exp(ν, β) and |X| ≤ Y almost surely. Then X is sub-exp(ν , β), where

ν := 2ν 2 + 16(E(Y )) 2 . ( 83
)
The following theorem considers a slightly generalized case with block-i.i.d. variables, covering structured random features.

Theorem 5. Consider T := (Θ, ρ, I) a location-based family with base distribution π 0 on R d , with Θ ⊆ R d a bounded subset, ρ(•, •) := • -• where • is some norm on R d . Let κ ≥ 0 be a non-degenerate normalized shift-invariant kernel on R d , and assume that there is some norm • a on R d and a function κ : [0, +∞) → R such that, with R := sup x∈Θ d x a , the normalized kernel κ(x) defined in (15) satisfies κ(x) = κ( x a ) for every x ∈ R d such that x a ≤ R. Assume that the function α defined in (64) is of class C 1 on (0, R) and the constant C κ defined in (65) is finite. Moreover, assume that κ has its mutual coherence with respect to T bounded by µ where 0 < µ < 1 10 . Let 1 ≤ k < 1 10µ and define c := (2k -1)µ. Let w be a κ-compatible weight function and m be an integer multiple of b ∈ N * , and consider A a w-FF sketching operator (Definition 6) associated to the frequencies

(ω 1 , . . . , ω m ) that are block-i.i.d. corresponding to m/b i.i.d. d × b random matrices B i , 1 ≤ i ≤ m/b such that (33) holds. Let τ ∈ (0, 1 -5c)
, and assume that 1. there exists ν, B > 0 and β ≥ 0 such that for each x ∈ R d satisfying x a = 1, the following random variables are sub-exp(ν,

β) with |E(Z p )| ≤ B Z p := 1 b b j=1 ψ(ω j )( C κ | ω j , x |) p , p ∈ {0, 1, 2}. ( 84
)
2. there exists M > 0 such that

P Ψ 0 (Ω) > M ≤ 2 exp - m v . ( 85
) v := 256k 2 b(2ν 2 + βτ ) τ 2 , where ν := √ 2 ν 2 + 8B 2 . ( 86
)
Then A satisfies

P δ(S k |A) > 4c + τ 1 -c ≤ 12 • exp - m v 1 + C/τ ) 3d+2 , (87)
where

C := 6144C κ M • k(1 + diam a (Θ)). ( 88
)
When B ψ := sup ω∈R d ψ(ω) < +∞, (87) also holds with v from (86) by replaced with

v := 256k 2 b(2B 2 ψ ν 2 + B ψ βτ ) τ 2 (89)
if we assume (85) with v instead of v and replace Item 1 by the same assumption on the random variables

Z p := 1 b b j=1 ( C κ | ω j , x |) p , p ∈ {0, 1, 2}, ( 90
)
Theorem 5 is obtained by applying Theorem 4, see Appendix A.9.3. Next we give two examples: for mixtures of Gaussians, Item 2 is established using sub-exponentiality; for mixtures of Diracs, Item 2 requires a bit more work.

The case of a mixture of Gaussians. We consider the kernel κ and the overall setting of Example 2, and a w-RFF sketching operator A with "flat" κ-compatible weight function w ≡ 1 and i.i.d. frequencies ω ∼ N (0, Σ -1 /s 2 ). In this setting, the function ψ defined in (52) satisfies

7 ∀ω ∈ R d , ψ(ω) = | π 0 , φ ω | 2 π 0 2 κ = e -ω T Σω (1 + 2s -2 ) -d 2 . ( 91
)
Given the definition (67) of f 0 (•), we deduce that ψ(ω) and ψ(ω)f 0 (ω) are bounded, so that Hoeffding's inequality yields Item 2 for an explicit M independent of m and for any v > 0, while the variant of Item 1 with Z p follows from the sub-exponentiality of

| ω, x | 2 , s ∈ {0, 1, 2}, since ω ∼ N (0, Σ -1 /s 2 )
. Details are given in Appendix A.9.4, including sub-exponentiality constants and a proof that T and κ satisfy the assumptions of Theorem 5. When all is said and done, we obtain the following result.

Corollary 1. Consider Θ ⊆ R d , an integer k ≥ 1, a scale s > 0, and

≥ 2 + s 2 (4 log(5ek)). ( 92
)
With T , κ, Σ as in Example 2 and A the w-RFF sketching operator with "flat" κcompatible weight function w ≡ 1 and m i.i.d. frequencies ω j ∼ Λ := N (0, Σ -1 /s 2 ), the mutual coherence of κ with respect to T is bounded by µ where 0 < µ < 1 10k . Moreover, for each 0 < τ < 1 -5c, where c := (2k -1)µ, we have

P δ(S k |A) > 4c + τ 1 -c ≤ 12 exp - m v 1 + C/τ ) 3d+2 , (93)
where v = v k (τ ) with v k (τ ) := 512k 2 (C 0 /τ ) 2 + 1 3 (C 0 /τ ) , with C 0 ≤ 7 √ 3 2 s -2 (1 + 2s -2 ) d/2 , ( 94
)
C ≤ 43000 2 (1 + 2s -2 ) d/2 • k(1 + diam a (Θ)). ( 95
)
In contrast to [GBKT21b, Theorem 6.11], the RIP constant here is not guaranteed to be (with high probability) arbitrarily close to zero, but only smaller than the quantity (4c + τ )/(1c), which can be made arbitrarily close to 4c/(1c) < 1 (since c = (2k -1)µ < (2k -1)/10k < 1/5). The assumption (92) relating the separation parameter and the scale parameter s is essential to guarantee that 10kµ < 1. This technical condition is important since our bounds are only valid under the assumption that 5c = 5(2k -1)µ < 1. In particular, we deduce that the probability that the event δ

(S k |A) ≤ (4c + τ )/(1 -c) holds is larger than 1 -η, with η ∈]0, 1], whenever m ≥ (3d + 2)v k (τ ) log 1 + C/τ + log(12/η).
In other words, a sufficient sketch size m scales as O(dv k (τ ) log(C/τ )). Typically, we seek to determine the dependency of the sketch size in terms of the sparsity k and the dimension d. Considering a near minimum separation parameter according to (92), a fixed diameter, and 1 ≤ log k = O(d), let us highlight two regimes:

1. the regime

√ d s = O(poly(d)): then (1 + 2s -2 ) d/2 = O(1) so that C 0 = O(log k), v k (τ ) = O((τ -1 k log k) 2
) and log(C) = O(log(kd)) and the the sufficient sketch size scales as O((τ -1 k log k) 2 log kd). 2. the regime where s is of the order of one: then (1 + 2s -2 ) d/2 = O(e cd/2 ), with c = log(1 + 2s -2 ) so that v k (τ ) = O((τ -1 k log k) 2 de cd ) and log(C) = O(d) so that the sufficient sketch size scales as O((τ -1 k log k) 2 d 2 e cd );

In both regimes, we obtain similar results as in [GBKT21b, Table 1]. There exists an intermediate regime,

c 1 d 1/4 ≤ s 2 ≤ c 2 √ d,
for large d, where we expect that Theorem 5 can be leveraged to obtain better sketch size estimates, that would not be achievable with the techniques of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. A closer inspection of our proof techniques indeed suggests that better dependencies can be obtained by relying on Item 1 of Theorem 5 (with Z p ) rather than on its variant with Z p . Concretely, this means obtaining better sub-exponentiality constants for the random variables ψ(ω)| ω, x | p .

As an example, for p = 0, the proof given in Appendix A.9.4 only relies on the crude uniform deterministic bound ψ(ω) ≤ B ψ := sup ω∈R d ψ(ω) = (1 + 2s -2 ) d/2 , hence it cannot yield a better result than Hoeffding's bound [START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF]

∀ > 0, P ψ(ω) -Eψ(ω) > ≤ exp - 2 2 B 2 ψ .
It is well known that exploiting the variance of ψ(ω), V ψ := Vψ(ω) can lead to better results using Bernstein's concentration inequality [BLM13a, Theorem 2.10]

∀ > 0, P ψ(ω) -Eψ(ω) > ≤ exp - 2 2(V ψ + B ψ ) .
In the setting of Corollary 1, since ω ∼ Λ is Gaussian, we can compute explicitly

E ω∼Λ ψ(ω) = 1 and V ψ := Vψ(ω) ≤ E ω∼Λ ψ 2 (ω) = (1 + 4s -4 (1 + 4s -2 ) -1 ) d/2 . Thus log(V ψ ) = d log(1 + 4s -4 (1 + 4s -2 ) -1 )/2, while log(B ψ ) = d log(1 + 2s -2 )/2, hence in the regime c 1 d 1/4 ≤ s 2 ≤ c 2 √ d we have V ψ = O(1) while B ψ ≥ e c3 √ d
. Empirical experiments further suggest that even this Bernstein bound remains crude, and even essentially vacuous (on the order of one): this is illustrated on Figure 1, as well the behavior of the following conjectured upper bound

P ψ(ω) -Eψ(ω) > ≤ exp - 2 2(V ψ + V ψ ) . (Conjecture)
which remains to be proved for a range of 0 < < max to be determined. Proving this conjecture and similar ones for ω, x p ψ(ω), p = 1, 2 would lead to definite improvements to the bounds derived in Corollary 1 and consecrate the advantage of the analysis developed in this work over the analysis given in [START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF], justifying the supplementary assumption on the RIP constant (to be larger than 4c/(1c)) that our analysis requires. This is however left to future work.

The case of a mixture of Diracs We now consider the setting of Example 1, and a w-RFF sketching operator A corresponding to the "flat" κ-compatible weight function w ≡ 1 and i.i.d. frequencies ω ∼ N (0, s -2 I d ). In this setting, the function ψ defined in (52) satisfies This is a setting where the analysis adopted in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] cannot be applied, since the condition (43) does not hold. Indeed, by (96) and by the fact that π 0 κ = 1 we have sup

8 ∀ω ∈ R d , ψ(ω) = | π 0 , φ ω | 2 π 0 2 κ = 1. ( 96
P(ψ(ω) -Eψ(ω) ≥ ) e - 2 2(V ψ +B ψ ) e - 2 2(V ψ + √ V ψ )
P(ψ(ω) -Eψ(ω) ≥ ) e - 2 2(V ψ +B ψ ) e - 2 2(V ψ + √ V ψ )
ω∈R d | φ w ω , π 0 | • max(1, ω , ω 2 ) = +∞.
Reasoning as in the case of a mixture of Gaussians allows to establish the variant of Item 1 with Z p required in Theorem 5. However, in this setting, ψ(ω)f 0 (ω) is no longer sub-exponential hence establishing Item 2 in Theorem 5 requires more work and a choice of M > 0 that depends at most polynomially on the sketch size m. As detailed in Appendix A.9.4, we get the following result as a corollary of Theorem 5.

Corollary 2. Consider Θ ⊆ R d , an integer k ≥ 1, a scale s > 0, and

≥ s(4 log(5ek)). ( 97
)
With T , κ, Σ as in Example 1 and A the w-RFF sketching operator with "flat" κcompatible weight function w ≡ 1 and m i.i.d. frequencies

ω j ∼ Λ := N (0, s -2 I d ),
where I d is the identity matrix of dimension d, the mutual coherence of κ with respect to T is bounded by µ where 0 < µ < 1 10k . Moreover, for each 0 < τ < 1 -5c, where c := (2k -1)µ, we have

P δ(S k |A) > 4c + τ 1 -c ≤ 12 exp - m v 1 + C(τ, m)/τ ) 3d+2 , (98)
where

v = v k (τ ) := 512k 2 (C 0 /τ ) 2 + 1 3 (C 0 /τ ) , with C 0 ≤ 7s -2 max(1, √ 3 2 ), (99)
C(τ, m) := 6144(1 + 2s -1 ) 3 max(1, √ 3 2 )(2d 3/2 + √ mτ 3/2 ) • k(1 + diam a (Θ)). ( 100
)
As in the case of Gaussian mixtures, and in contrast to [GBKT21b, Theorem 6.11], the RIP constant is not guaranteed to be (with high probability) arbitrarily close to zero: it can only be made arbitrarily close to 4c/(1c) < 1. This is the price we pay for being able to handle plain importance sampling with w ≡ 1. Observe that

1 + C(τ, m)/τ ≤ √ m(1 + C(τ, 1)/τ ) ≤ m(1 + C(τ, 1)/τ ) hence the r.h.s. of (98) is upper bounded by 12 exp - m v 1 -(3d + 2)v log(m) m + (3d + 2) log 1 + C(τ, 1)/τ . ( 101
)
We deduce that for η ∈ (0, 1], and for the w -RF F sketching operator described in Corollary 2, the probability that the event δ(S k |A) ≤ (4c + τ )/(1c) holds is larger than 1η, as soon as

m log m (3d + 2)v log 1 + C(τ, 1)/τ + log(12/η) = Ω(k 2 d).
In other words, a sufficient sketch size is O(k 2 d): our analysis allows to obtain the same dependencies on k and d as the analysis developed in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] but without assuming the conditions (43) that imposes constraints on the importance sampling weight w. It would be tempting to think that a judicious choice of the weight function w would allow to further improve the dependency on k of the sketch size from O(k 2 d) to O(kd). Unfortunately, as we shall see in Section 3.4, our analysis does not allow us to make such an improvement. The investigation of the role of the weight function is deferred for future work. Finally, observe that the constant log(1 + C(τ, 1)/τ ) depends logarithmically on D ( the diameter of Θ), on s -1 , and on d log k. Note that the logarithmic dependency on D is well known in the Fourier features literature [START_REF] Sriperumbudur | Optimal rates for random fourier features[END_REF], while the dependency on s -1 has empirical implications: the parameter s should be choosen small enough so that the mutual coherence of κ with respect to T is bounded by µ, yet not too small. Interestingly, this phenomenon was documented in several empirical investigations [START_REF] Keriven | Compressive k-means[END_REF][START_REF] Chatalic | Efficient and privacy-preserving compressive learning[END_REF].

Towards bounds for structured random sketching

A benefit of the theoretical analysis presented in this work is to pave the way to theoretical guarantees on the RIP of sketching operators based on structured features. Indeed, as evoked in Section 2.5, there are now many constructions of structured random Fourier features where m is a multiple of d and the frequencies ω 1 , . . . , ω m are block-i.i.d. with blocks of size b = d: the matrix Ω ∈ R d×m with columns ω j , 1 ≤ j ≤ m is the concatenation of i.i.d. random matrices

B i ∈ R d×d , 1 ≤ i ≤ m/d.
Such constructions can be designed to lead to (non independent but) identically distributed Gaussian frequencies ω j ∼ N (0, σ 2 I d ), so that the average marginal density satisfies (33) with a Gaussian kernel and the simplest κ-compatible weight function w ≡ 1, see e.g. [START_REF] Chatalic | Efficient and privacy-preserving compressive learning[END_REF]Chapter 5]. This allows to reuse the proof techniques used to establish Corollary 1-Corollary 2, showing as an intermediate step that each

X j := ψ(ω j )( √ C κ | ω j , x |) p (resp. X j := ( √ C κ | ω j , x |) p , when B ψ < +∞), with ar- bitrary x ∈ R p satisifying x a = 1 and p ∈ {0, 1, 2}, is sub-exp(ν, β) with |EX| ≤ B.
If the variables X j were independent, we would deduce that their blockwiseempirical average Z p defined in (84) (resp. Z p from (90)), which satisfies

|EZ p | ≤ B, is sub-exp(ν/ √ d, β/d).
Even though the X i 's are not independent, we can still prove that Z p (resp. Z p ) satisfy the first assumption (Item 1) of Theorem 5. Indeed, by Lemma 9, the random variable

d × Z p = d j=1 ψ(ω j )( √ C κ | ω j , x |)
p is subexp(dν, dβ), since it is a sum of d random variables that are sub-exp(ν, β), thus Z p (and similarly Z p ) is sub-exp(ν, β).

In the case of mixtures of Gaussians, the variables ψ(ω j )f 0 (ω j ) are bounded and the very same reasoning as in the proof of Corollary 1, yields that (85) holds true for the same constant M and any v > 0. Gathering all of the above shows that for Gaussian mixture models, sketching with the considered structured random Fourier features satisfies the RIP: (93) holds with v = dv k (τ ), where v k (τ ) given in (94). The price we pay for such a quick analysis is an additional d factor in the sufficient sketch size m.

While this result does not assume the independence of the random variables X j , it comes with a cost: settling for the use of Lemma 9 worsens the 'variance' term (86) by a factor d compared to the fully i.i.d. setting. Thus, a refined analysis of the expectation and of the sub-exponentiality constants of the random variables Z p is required in order to prove competitive bounds on sketch sizes for structured sketching. Ideally, we may hope to prove that Z p and Z p are sub-exp(ν, β) with ν = O(1/ √ d) and β = O(1/d) hold for some families of structured random matrices. Note however that this would require to slightly sharpen the bound obtained in Theorem 5. Indeed, the main bottleneck in the sketch size would be the constant ν defined in (86) that involves the term B which is a constant that does not depend on d. Improving Theorem 5 would either require to refine Lemma 3 in order to circumvent the presence of this constant in ν , or to more directly rely on Theorem 4 and in establishing autonomous concentration bounds. This is left to future work. Finally, to handle the case of mixtures of Diracs, one would need to revisit Proposition 11 to control the behavior of Ψ 0 (Ω) in the structured setting.

Lower bounds

To conclude, we provide several lower bounds that complete the picture established in this section.

First, we show that condition (43), which is known to be sufficient to control the covering numbers appearing in Theorem 2, is indeed close to necessary for these covering numbers to be well-defined and finite. This shows that existing theory (such as [GBKT21b, Theorem 5.13]) is simply too restrictive to provide guarantees for perhaps the most natural setting where there is "no" importance sampling, i.e., w ≡ 1, which is in contrast covered by our new results.

Second, we investigate the gap between sufficient sketch sizes endowed with theoretical guarantees, which scale as O(k 2 d), and practically observed sketch sizes, which scale as O(kd). We demonstrate that a proof route which could seem natural to bridge this gap is in fact a dead-end, leaving possible improvements to further work.

Lower bounds on variance terms

The empirical investigations in [START_REF] Keriven | Compressive k-means[END_REF] showed that a practically sufficient sketch size scales as O(dk) compared to the theoretically sufficient sketch size O(dk 2 ) obtained by the analysis given in [GCK + 20] and the analysis given in this work. This suggest that there is still room for improvement on the theoretical bounds of sketching. We investigate below theoretical approaches that may seem natural ways to improve the proof techniques respectively introduced in [GCK + 20] and in this work. Our main conclusion is that these approaches cannot lead to the desired explanation of the empirical findings of [START_REF] Keriven | Compressive k-means[END_REF].

Limits of the proof technique of [GCK + 20] After a careful examination of the proof given in [GCK

+ 20], it may be tempting to improve the concentration inequality (40) and target one of the form ∀τ > 0, sup

ν∈S k P Aν 2 2 -1 > τ 2 ≤ 2 exp - m v 0 (τ ) ,
with v 0 (τ ) independent of k (under appropriate incoherence assumptions on κ, that depend of k). This would indeed easily provide the desired result by combining the technical ingredients as in the proof of Theorem 2, however under standard assumptions 9 on the growth of v 0 (τ ) when τ → ∞, it is a classical exercice 10 to show that this implies bounded moments E Aν 2q 2 , for q ≥ 2, depending only on v 0 (τ ) and m, in particular this would also imply the existence of a constant C > 0, independent of k, such that

∀ν ∈ S k , V Aν 2 2 ≤ C m .
where V(•) denotes the variance of a scalar random variable. However, as we now show, under typical assumptions on the 2k-coherence of the kernel, this variance grows linearly with k.

We begin with a technical lemma proved in Appendix A.1.

Lemma 4. Consider a normalized shift-invariant kernel κ and π 0 ∈ P(R d ). If w : R d → (0, +∞) is κ-compatible and satisfies

φ 1 ω , π 0 4 w -2 (ω)κ(ω)dω < +∞, (102)
then the following shift-invariant kernel is well-defined

κ w (θ, θ ) := R d φ 1 ω , π 0 4 w -2 (ω)κ(ω)e 2πiω (θ-θ ) dω, θ, θ ∈ R d ( 103
)
and satisfies κ w (0, 0) ≥ π 0 4 κ . The following weight function is κ-compatible and satisfies (102)

w 0 (ω) := π 0 -1 κ • | φ 1 ω , π 0 |. ( 104
)
Moreover κ w0 (0, 0) = π 0 4 κ and more generally

κ w0 (θ, θ ) = π 0 2 κ π θ , π θ κ , θ, θ ∈ R d . ( 105
)
9 A subgaussian tail or a sub-exponential tail. 10 See Theorem 2.3 in [START_REF] Boucheron | Concentration Inequalities: A Nonasymptotic Theory of Independence[END_REF] and Lemma 1 in [START_REF] Bousquet | Sharper bounds for uniformly stable algorithms[END_REF].

In the special case of a Dirac base distribution π 0 , (104) simply defines a "flat" weight function w 0 ≡ 1 since π 0 2 κ = π 0 , π 0 κ = κ(0, 0) = 1 = | φ 1 ω , π 0 |. Theorem 6. Consider a normalized shift-invariant kernel κ. Consider a locationbased family T with base distribution π 0 , an integer k ≥ 1, and the separated kmixture model G k from (10) where (θ, θ ) := θθ for some arbitrary norm

• on R d . Consider a vector θ * ∈ R d such that θ * ≥ 1, and observe that the following two k-mixtures are 1-separated with respect to , i.e.,

ν k,1 , ν k,2 ∈ G k , so that ν k := (ν k,1 -ν k,2 )/ ν k,1 -ν k,2 κ ∈ S k : ν k,1 = k i=1 1 k π (2i-2)θ * , ν k,2 = k i=1 1 k π (2i-1)θ * . ( 106
)
1. If the 2k-coherence of κ with respect to T is bounded by 0 ≤ c < 1 then for any κ-compatible weight function w that satisfies (102), the w-RFF sketching operator A with m i.i.d frequencies ω j ∼ Λ := w 2 κ satisfies

V Aν k 2 ≥ 1 m C w k -1 , (107)
where

C w := κ w (0, 0) π 0 4 κ • 4/3 -2c w (1 + c) 2 with c w := 2k sup θ,θ : θ-θ ≥1 |κ w (θ, θ )| κ w (0, 0) . ( 108
)
2. If the mutual coherence of κ is bounded by c/2k we have c w0 ≤ c with w 0 as in (104).

The proof of Theorem 6 is given in Appendix A.2. For a kernel with mutual coherence bounded by c/2k with c ≤ 1/2, we obtain

4/3-2cw 0 (1+c) 2
≥ (4/3 -1)/(3/2) 2 = 4/27 ≥ 1/7. Since κ w0 (0, 0)/ π 0 4 κ = 1 (by Lemma 4) we get C w0 ≥ 1/7. Finally, since the mutual coherence of κ is bounded by c/2k, its 2k-coherence is bounded by c (cf (19)), and (107) implies that the w 0 -RFF sketching operator A with m i.i.d frequencies ω j ∼ Λ 0 := w 2 0 κ satisfies

V Aν k 2 ≥ k/7 -1 m . (109)
In the special case of a mixture of Diracs, since w 0 ≡ 1, it is not difficult to check that κ w0 = κ. For a non-negative kernel κ ≥ 0, the fact that κ w0 ≥ 0 allows to improve an intermediate bound (in Equation (118) in the proof), leading to the same result where 4/3 -2c w0 is replaced with 4/3c w0 in the definition of C w0 . This shows that (109) is then valid even with a mutual coherence bounded by c/2k with c < 1.

Under the assumptions of Theorem 6, with w = w 0 , we have V Aν k 2 = Ω(k/m). This implies that with this weight function, and even with the usual incoherence assumption, the term v(k, τ ) in (40) cannot be bounded from above by a universal constant that is independent of k. This result highlights the difference between classical compressed sensing and sketching. Indeed, if we consider a random Gaussian matrix A ∈ R m×d with i.i.d. entries N (0, 1/m), it is well known that for every normalized vector x ∈ R d (such that x 2 = 1) the variance of Ax 2 2 does not depend on the sparsity k of the vector x; see e.g. [FR13, Lemma 9.8].

Figure 2 illustrates this claim: we compare the variance of Ax k 2 2 where x k ∈ R d is a normalized vector of sparsity k to the variance of Aν k 2 2 where A and ν k are defined in Theorem 6, with π 0 the Dirac distribution, w = w 0 ≡ 1, and the 2k-coherence of κ is smaller than 1/2. We observe that the variance of Ax k 2 2 is practically flat as a function of k, while the variance of Aν k 2 2 is linear in k. This observation shows that the study of the RIP in the set of mixtures of Diracs G k is not a mere extension of the existing RIP literature in Euclidean spaces. Limits of the proof technique proposed in this paper. Now, a careful examination of the analysis leading to Corollary 1 and Corollary 2 suggests that the unwanted O(k 2 d) instead of O(kd) behaviour of the sufficient sketch size results from the requirement of concentration inequality (76) in Theorem 4. In particular, in order to improve the theoretical guarantees of sketching using i.i.d. random frequencies, it would be tempting to seek a weight function w such that the random variable

ψ (z|ω) := ψ(ω)f (z|ω) is sub-exp(ν /, b ) with ν = O(1/ √ k)
, for each ∈ {mm, md, dd} and z ∈ Θ . The reader can check that such an approach would indeed allow to establish guarantees with a sketch size O(kd). However, this would also imply that for ∈ {mm, md, dd} and z ∈ Θ , the variance of ψ (z|ω) would satisfy Vψ (z|ω) = O(1/k). Now, when κ has mutual coherence bounded by µ < 1/(2k -1) (this is a natural assumption in our context), the expectation of this variable satisfies Eψ (z|ω) = O(1/k), hence we would obtain that

E[ψ 2 (z|ω)] = O(1/k). (110)
The following result shows that (110) cannot hold in the specific setting of mixture of Diracs.

Proposition 7. Consider T to be a location-based family with the dirac in 0 as a base distribution, and consider κ to be a normalized shift-invariant kernel such that κ ≥ 0. Consider φ ω as defined in (28), then for any κ-compatible weight function w and for ω ∼ Λ := w 2 κ, we have

∀y ∈ Θ mm , E[ψ 2 mm (y|ω)] ≥ 1 4 . (111)
This lower bound holds irrespective of how small the mutual coherence of κ may be.

Proof. Let y ∈ Θ mm . Since π 0 2 κ = κ(0, 0) = 1 and | π 0 , φ ω | = 1/w(ω), by ( 52)-(54) we have

ψ mm (y|ω) := ψ(ω)f mm (y|ω) = | π 0 , φ ω | 2 π 0 2 κ cos( ω, y ) = cos( ω, y ) w 2 (ω) . ( 112
)
As w is κ-compatible, we have R d w 2 (ω)κ(ω)dω = 1, thus by Cauchy-Schwarz inequality we get

E ω∼Λ [ψ 2 mm (y|ω)] = R d cos 2 ( ω, y ) w 4 (ω) w 2 (ω)κ(ω)dω = R d w 2 (ω)κ(ω)dω R d cos 2 ( ω, y ) w 2 (ω) κ(ω)dω ≥ R d | cos( ω, y )|κ(ω)dω 2 ≥ R d cos 2 ( ω, y )κ(ω)dω 2 .
Finally, observe that cos( ω, y ) 2 = (1 + cos(2 ω, y ))/2, so that we have, using that κ ≥ 0,

E ω∼Λ [ψ 2 mm (y|ω)] ≥ 1 2 R d κ(ω)dω+ R d cos(2 ω, y )κ(ω)dω 2 = 1 2 (1+κ(2y, 0)) 2 ≥ 1 4 .
w 1 (ω) = 1, w 2 (ω) = (1 + ω ) -1 , w 3 (ω) = ( ω 4 + 1)( ω 6 + 1) -1 .
Proposition 7 shows that improving the dependency of the sketch size on m cannot simply rely on improved concentration bounds: obtaining sharper bounds on sketch sizes that reflect the empirical findings of [START_REF] Keriven | Compressive k-means[END_REF] seems to require a substantially subtler analysis which is beyond the scope of this paper. crucial in the field of compressive learning: it measures how the sketching operator preserves the MMD distance between measures belonging to a model set of measures. In particular, the sketching operators proposed in [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] are suited for models of mixtures and are based on Fourier features. Nevertheless, the proposed theoretical analysis makes some additional assumptions that are summarized by the conditions (43). After investigating the partial necessity of the conditions (43) in the analysis of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF], we proposed an alternative analysis based on deterministic bounds of δ(S k |A), then we showed how to leverage these deterministic bounds to establish the Restricted Isometry Property for stochastic sketching operators restricted to sets of mixtures based on location based measures. In particular, we showed that our revisited analysis allows to deal with realistic settings not covered by [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF].

Beyond these contributions, this work opens the door to further developments on the theoretical study of sketching operators used in the context of compressive learning. For instance, in the context of structured sketching introduced in [CGK18], the frequencies are rather block-i.i.d. samples but not i.i.d. samples (cf the end of Section 2.5). Theorem 4 remains valid in this context: indeed this result can be used without assuming that the frequencies ω 1 , . . . , ω m are i.i.d.. The main hindrance remaining on this direction is to check that the punctual concentration expressed by conditions (74), ( 75), (76) hold even when using block-i.i.d. frequencies. For this purpose, the existing results on the literature may help [LSS13, CS16, CRW17, MKBO18]. Another setting where our results may be useful is the study of deterministic sketching operators. Indeed, as shown in Section 3, the core of our analysis is based on deterministic bounds of δ(S k |A) presented in Section 3.2, and recent years have witnessed an increased interest into the theoretical study of deterministic Fourier feature maps [START_REF] Dao | Gaussian quadrature for kernel features[END_REF][START_REF] Yang | Quasi-monte carlo feature maps for shift-invariant kernels[END_REF]. Investigating whether deterministic sketching operators still satisfy the same guarantees as the stochastic ones is thus both a natural and challenging question.

As shown in Section 3.4, neither the analysis of [START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF] nor our analysis unfortunately achieves to explain the empirical findings of [START_REF] Keriven | Compressive k-means[END_REF], and there remains a gap between sufficient sketch sizes endowed with theoretical guarantees, which scale as O(k 2 d), and practically observed sketch sizes, which scale as O(kd). On the one hand, the quadratic theoretical dependency on the 'sparsity' k is not surprising given the known limits of sparse recovery guarantees exploiting dictionary coherence [ [START_REF] Foucart | An invitation to compressive sensing[END_REF]Chapter 5]. Yet, the literature on compressive sensing manages to establish bounds essentially linear in the sparsity using random matrix techniques that do rely on mutual coherence [FR13, Chapter 9]. The proofs in this field exploit a fine study of the eigenvalues of random matrices, which was until now somehow overlooked in the community of compressive learning. Thus, an interesting direction of research is the study of the eigenvalues of the random matrices that appear in this context. Recent developments on the study of ridge kernel regression for random Fourier features may help [AKM + 17, LTOS19]. In particular, in this line of research, the authors investigated the impact of the frequency distribution in the quality of the approximations based on random Fourier features. The techniques developed in these works may be helpful to understand the impact of the frequency distribution in the design of sketching operators. In the same vein, alternative frequency distributions, that define other kernels than the Gaussian kernel, have manifested better empirical performance when used in sketching-based learning tasks such as mixture learning; see Section 4.2 in [START_REF] Chatalic | Efficient and privacy-preserving compressive learning[END_REF] for an example. This motivates to scrutinize the impact of the kernel on the design of the sketching operator.

Acknowledgement This project was supported by the AllegroAssai ANR project ANR-19-CHIA-0009. The authors would like to thank Titouan Vayer for his constructive feedback on an early version of this work and for sketching an early version of Lemma 7. Rémi Gribonval would like to thank Felix Krahmer for interesting discussions at the Oberwolfach Workshop 2148.

A Proofs

A.1 Proof of Lemma 4 By (102), the integral in (103) converges hence the kernel κ w is well-defined and shift-invariant. Consider arbitrary θ, θ ∈ R d and denote π θ , π θ deduced from π 0 as in a location-based family. Recall that by definition, π θ is the distribution of X + θ where X ∼ π 0 , and π θ is the distribution of X + θ . By (31), standard computations with the MMD 11 yield

π θ , π θ κ = R d φ 1 ω , π 0 2 κ(ω)e 2πıω (θ-θ ) dω. ( 113
)
Specializing (113) to θ = θ = 0 we get by Cauchy-Schwarz' inequality, since w is κ-compatible

π 0 4 κ = R d φ 1 ω , π 0 2 κ(ω)dω 2 = R d φ 1 ω , π 0 2 w -1 (ω) κ(ω)w(ω) κ(ω)dω 2 ≤ R d φ 1 ω , π 0 4 w -2 (ω)κ(ω)dω 2 • R d w 2 (ω)κ(ω)dω 2 (103)&(29) := κ w (0, 0) .
The equality case of Cauchy-Schwarz is when w(ω) ∝ φ 1 ω , π 0 2 w -1 (ω), i.e., w(ω) ∝ w 0 (ω) with w 0 defined in (104). We have

w 2 0 (ω)κ(ω)dω (104) = π 0 -2 κ • | φ 1 ω , π 0 | 2 κ(ω)dω (113) = π 0 -2 κ • π 0 , π 0 κ = 1 ,
hence w 0 is the only equality-case of Cauchy-Schwarz which is κ-compatible. The fact that w 0 (ω) satisfies (102) follows from w 0 ∝ φ 1 ω , π 0 2 w -1 0 (ω). Finally we write

κ w0 (θ, θ ) (103)
:= R d φ 1 ω , π 0 4 w -2 0 (ω)κ(ω)e 2πıω (θ-θ ) dω (104) = π 0 2 κ • R d φ 1 ω , π 0 2 κ(ω)e 2πıω (θ-θ ) dω (113) = π 0 2 κ • π θ , π θ κ .

A.2 Proof of Theorem 6

The proof relies on the following result which gives a closed formula of the variance of interest.

Proposition 8. Consider a normalized shift-invariant kernel κ, a κ-compatible positive weight function w satisfying (102), Λ = w 2 κ and A a κ-compatible random w-FF sketching operator as in Example 3 with m i.i.d. frequencies. Consider a location-based family T with base distribution π 0 . Given any location parameters θ 1 , . . . , θ 2k ∈ Θ and weights u 1 , . . . , u 2k ∈ R, we have

V A i∈[2k] u i π θi 2 = 1 m (u ⊗2 ) K w (θ)u ⊗2 - 2k i=1 u i π θi 4 κ , (114)
11 See [MFS + 17, Section 2.1] and [GBKT21b, proof of Proposition 6.2].

where u ⊗2 ∈ R (2k) 2 is the tensor product with itself of the vector u ∈ R 2k containing the u i , and

K w (θ) = [κ w (θ i1 -θ i2 , θ i4 -θ i3 )] (i1,i2),(i3,i4)∈[2k] 2 ∈ R (2k) 2 ×(2k) 2 (115)
with [2k] := {1, 2, . . . , 2k} and κ w is the shift-invariant kernel defined in (103).

Proof of Proposition 8. As A

2k i=1 u i π θi 2 = 1 m j∈[m] φ w ωj , 2k i=1 u i π θi 2 is the average of m i.i.d. variables, we have V A 2k i=1 u i π θi 2 = 1 m V φ w ω , 2k i=1 u i π θi 2 so we now characterize V| φ w ω , 2k i=1 u i π θi | 2 = E ω∼Λ φ w ω , 2k i=1 u i π θi 4 -E ω∼Λ φ w ω , 2k i=1 u i π θi 2 2 = E ω∼Λ φ w ω , 2k i=1 u i π θi 4 - 2k i=1 u i π θi 4 κ
where we used (32) since w is κ-compatible and Λ = w 2 κ (see Example 3). Given the expression (28) of φ ω := φ w ω = φ 1 ω /w(ω) and since {π θ } θ∈Θ is location-based,

φ ω , π θ = E X∼π θ φ ω (X) = E X ∼π0 φ ω (X +θ) = e 2πıω θ E X ∼π0 φ ω (X ) = e 2πıω θ φ ω , π 0 , so that we can develop φ ω , 2k i=1 u i π θi 4 = 2k i1=1 2k i2=1 2k i3=1 2k i4=1 u i1 u i2 u i3 u i4 φ ω , π θi 1 φ ω , π θi 2 φ ω , π θi 3 φ ω , π θi 4 = 2k i1=1 2k i2=1 2k i3=1 2k i4=1 u i1 u i2 u i3 u i4 | φ ω , π 0 | 4 e 2πı ω (θi 1 -θi 2 +θi 3 -θi 4 ) .
Moreover, given the expression (30) of the pdf Λ(ω) we have for every

i 1 , i 2 , i 3 , i 4 ∈ [2k] E ω∼Λ | φ ω , π 0 | 4 e 2πı ω(θi 1 -θi 2 +θi 3 -θi 4 ) = R d | φ ω , π 0 | 4 e 2πı ω (θi 1 -θi 2 +θi 3 -θi 4 ) w 2 (ω)κ(ω)dω = R d | φ 1 ω , π 0 | 4 w -4 (ω)e 2πı ω (θi 1 -θi 2 +θi 3 -θi 4 ) w 2 (ω)κ(ω)dω = κ w (θ i1 -θ i2 , θ i4 -θ i3 ),
where κ w is defined in (103). As a result, we have

E φ ω , 2k i=1 u i π θi 4 = 2k i1=1 2k i2=1 2k i3=1 2k i4=1 u i1 u i2 u i3 u i4 κ w (θ i1 -θ i2 , θ i4 -θ i3 ) = (u ⊗2 ) K w (θ)u ⊗2
where, according to the notations of the proposition u ⊗2 ∈ R (2k) 2 is the vector with entries u ⊗2 (i1,i2) = u i1 u i2 for each pair (i

1 , i 2 ) ∈ [2k] × [2k]
, and K w (θ) is the square matrix of size (2k) 2 × (2k) 2 defined in (115). Putting the pieces together yields (114) as claimed.

By Proposition 8 with ν

k := µ k,1 -µ k,2 = 2k i=1 u i π θi , where u i := (-1) i-1 k , θ i := (i -1)θ * , V Aν k 2 = V A(µ k,1 -µ k,2 ) 2 µ k,1 -µ k,2 4 κ = 1 m (u ⊗2 ) K w (θ)u ⊗2 µ k,1 -µ k,2 4 κ -1 . ( 116
)
We now bound µ k,1µ k,2 4 κ and (u ⊗2 ) K w (θ)u ⊗2 to get the first part of the Theorem.

Bounding

µ k,1 -µ k,2 4
κ . Since κ is shift-invariant and T is a location-based family we have π θi

2 κ = π 0 2 κ for each i ∈ [2k]. Since (θ i , θ j ) = θ i -θ j = |i -j| • θ * ≥ 1 for 1 ≤ i = j ≤ 2k, the 2k (unnormalized) monopoles {u i π θi } 2k i=1
are pairwise 1-separated dipoles with respect to ρ. As κ has its 2k-coherence with respect to T bounded by c (cf Definition 3-( 16)), it follows that

2 k (1-c) π 0 2 κ = (1-c) 2k i=1 u i π θi 2 κ ≤ µ 1,k -µ 2,k 2 κ ≤ (1+c) 2k i=1 u i π θi 2 κ = 2 k (1+c) π 0 2 κ ,
where we used that u 2 i = 1/k 2 for every i. Therefore

4 π 0 4 κ (1 -c) 2 k 2 ≤ µ 1,k -µ 2,k 4 κ ≤ 4 π 0 4 κ (1 + c) 2 k 2 . ( 117
)
Bounding (u ⊗2 ) K w (θ)u ⊗2 . Since u i1 u i2 = (-1) i1+i2 /k 2 for each i 1 , i 2 ∈ [2k], we write (u ⊗2 ) K w (θ)u ⊗2 = 1 k 4 i1,i2,i3,i4∈[2k] (-1) i1+i2+i3+i4 K w (θ) i1,i2,i3,i4
.

Consider the sets

I = := {(i 1 , i 2 , i 3 , i 4 ) ∈ [2k] 4 , i 1 -i 2 = i 3 -i 4 }, I + := {(i 1 , i 2 , i 3 , i 4 ) ∈ [2k] 4 , (-1) i1+i2+i3+i4 = 1}, I -:= {(i 1 , i 2 , i 3 , i 4 ) ∈ [2k] 4 , (-1) i1+i2+i3+i4 = -1},
and observe that I = ⊂ I + , I + ∪ I -= [2k] 4 and that the definition (115) implies

(-1) i1+i2+i3+i4 K w (θ) i1,i2,i3,i4 ≥      κ w (0, 0), ∀(i 1 , i 2 , i 3 , i 4 ) ∈ I = -|κ w (θ i1 -θ i2 , θ i4 -θ i3 )| ∀(i 1 , i 2 , i 3 , i 4 ) ∈ I - -|κ w (θ i1 -θ i2 , θ i4 -θ i3 )| ∀(i 1 , i 2 , i 3 , i 4 ) ∈ I + \I = . ( 118
)
Further observe that since

i 1 -i 2 -i 3 + i 4 ≡ i 1 + i 2 + i 3 + i 4 [2], if (i 1 , i 2 , i 3 , i 4 ) ∈ I -∪ (I + \I = ), then either i 1 -i 2 -i 3 + i 4 ≡ 1[2] or i 1 -i 2 -i 3 + i 4 = 0. In both cases, we have |i 1 -i 2 -i 3 + i 4 | ≥ 1, hence θ i1 -θ i2 -θ i3 + θ i4 = (i 1 -i 2 -i 3 + i 4 )θ * ≥ 1, and |κ w (θ i1 -θ i2 , θ i3 -θ i4 )| ≤ sup θ,θ : θ-θ ≥1 |κ w (θ, θ )| ≤ c w 2k κ w (0, 0),
where we used definition (108). Observe moreover that since

I -= {(i 1 , i 2 , i 3 , i 4 ); (i 1 , i 2 , i 3 ) ∈ [2k] 3 , i 4 ∈ [2k], i 4 ≡ 1 -(i 1 + i 2 + i 3 )[2]} we have I -= (2k) 3 × k = 8k 4 . Similarly, (I + \I = ) = I + -I = = 8k 4 -I = .
Finally, as we will show below I = ≥ 16k 3 /3 (the proof is postponed at the end of the section) we obtain

(i1,i2,i3,i4)∈[2k] (-1) i1+i2+i3+i4 K w (θ) i1,i2,i3,i4 ≥ I = -(I + \I = ) • c w 2k -I -• c w 2k • κ w (0, 0) = I = 1 + c w 2k -8c w k 3 • κ w (0, 0) ≥ (16/3 -8c w )k 3 • κ w (0, 0). Thus, (u ⊗2 ) K w (θ)u ⊗2 ≥ 8 k 2
3c w • κ w (0, 0) and combining with ( 116) and ( 117)

yields V Aν k 2 ≥ 1 m (C w k -1) with C w k = 8 k (2/3 -c w )κ w (0, 0) k 2 4 π 0 4 κ (1 + c) 2 , i.e., C w = 2(2/3 -c w ) κw(0,0) π0 4 κ (1+c) 2 as defined in (108).
To conclude the proof of (107) we now establish the claimed lower bound on I = . Since I = is the disjoint union of

I = := {(i 1 , i 2 , i 3 , i 4 ) ∈ [2k] 4 , i 1 -i 2 = i 3 -i 4 = },
∈ {-(2k -1), . . . , 0, . . . , 2k -1}, and

I = = I - = = (2k -) 2 for 0 ≤ ≤ 2k -1, hence I = = I 0 = + 2 2k-1 =1 I = = (2k) 2 + 2k-1 =1 2(2k -) 2 = 2 2k-1 =0 (2k -) 2 -(2k) 2 = 2 2k =1 ( ) 2 -4k 2 = 1 3 2k(2k + 1)(4k + 1) - 12 3 k 2 ≥ 16 3 k 3 . ( 119
)
where we used the well known fact that n =1 ( ) 2 = n(n + 1)(2n + 1)/6 for every integer n.

We proceed to the second claim. For θ, θ such that θθ ≥ 1, ι = π θ and ι = π θ are (non-normalized) 1-separated dipoles with respect to . The mutual coherence assumption and Lemma 4 yield

κ w0 (θ, θ ) π 0 2 κ = π θ , π θ κ ≤ c 2k π θ κ π θ κ = c 2k π 0 2 κ = c 2k π 0 , π 0 κ = c 2k κ w0 (0, 0) π 0 2 κ . (120)
This shows that c w0 defined in (108) satisfies c w0 ≤ c.

A.3 Proof of Proposition 2

For any mixture model, kernel, and feature family, the set of normalized dipoles D is included in the normalized secant set hence sup

ν∈S k ν F = sup ω∈R d sup ν∈S k | φ w ω , ν | ≥ sup ω∈R d sup ν∈D | φ w ω , ν |.
For x ∈ Θ s.t. 0 < x ≤ 1, define ιx := π xπ 0 . Since Θ contains a neighborhood of zero, π 0 / π 0 κ , ιx / ιx κ ∈ D as soon as x is small enough hence there is 0

< δ ≤ 1 such that sup ν∈S k ν F ≥ sup ω∈R d max | φ w ω , π 0 | π 0 κ , sup 0< x ≤δ | φ w ω , π x -π 0 | π x -π 0 κ . Since φ w ω , π x = e 2πı ω,x φ w ω , π 0 and π x -π 0 2 κ = 2 π 0 2 κ (1 -κ(x)) we have sup 0< x ≤δ | φ w ω , π x -π 0 | π x -π 0 κ = | φ w ω , π 0 | • sup 0< x ≤δ |e 2πı ω,x -1| π 0 κ 2(1 -κ(x)) .
Now, since κ achieved its maximum at zero where it is C 2 , we have for every x = 0

lim t→0 1 -κ(tx) t 2 x 2 = -x T ∇ 2 κ(0)x 2 x 2 .
By assumption, ∇ 2 κ(0) = 0 and we get

C := sup 0< x ≤δ lim t→0 1 -κ(tx) t 2 x 2 = ∇ 2 κ(0) op 2 > 0.
We obtain sup

0< x ≤δ |e 2πı ω,x -1| 1 -κ(x) ≥ sup 0< x ≤δ lim t→0 |e 2πıt ω,x -1| 1 -κ(tx) = sup 0< x ≤δ lim t→0 |2πıt ω, x | 1 -κ(tx) = sup 0< x ≤δ | 2πω, x/ x | lim t→0 1-κ(tx) t 2 x 2 ≥ 1 C sup 0< x ≤δ | 2πω, x/ x | = 2π C ω . Therefore sup ν∈S k ν F ≥ sup ω∈R d | φ w ω , π 0 | π 0 κ max 1, π √ 2 C ω .
To conclude we use that π √ 2/C = 2π/ ∇ 2 κ(0) op .

A.4 Proof of Proposition 3

Let ν ∈ S k . By Proposition 1, there exist 2k normalized dipoles ι 1 , . . . , ι 2k ∈ D, with (ι i , ι j ) ∈ D 2 = when i = j, and coefficients α 1 , . . . , α 2k ≥ 0 such that (1

+ c) -1 ≤ i∈[2k] α 2 i ≤ (1 -c) -1 that satisfy ν = i∈[2k] α i ι i . We notice that i =j∈[2k] α i α j = ( i∈[2k] α i ) 2 - i∈[2k] α 2 i ≤ ( √ 2k α 2 ) 2 -α 2 2 ≤ 2k -1 1 -c .
Since Aπ θ is well defined for probability distributions in the family T , the action of A is well defined on k-mixtures, hence on elements of the normalized secant set. We have

Aν 2 2 - i∈[2k] α 2 i = i,j∈[2k] α i α j Aι i , Aι j - i∈[2k] α 2 i = i∈[2k] α 2 i ( Aι i 2 2 -1) + i =j∈[2k] α i α j Aι i , Aι j ,
we obtain

Aν 2 2 -1 = i∈[2k] α 2 i -1 + i∈[2k] α 2 i ( Aι i 2 2 -1) + i =j∈[2k] α i α j Aι i , Aι j .
For i = j, since Aι j , Aι i is the complex conjugate of Aι i , Aι j , we have Aι i , Aι j + Aι j , Aι i = Re Aι i , Aι j +Re Aι j , Aι i hence

i =j∈[2k] α i α j Aι i , Aι j = i =j∈[2k] α i α j Re Aι i , Aι j .
As a result

Aν 2 2 -1 ≤ 1 - i∈[2k] α 2 i + i∈[2k] α 2 i ( Aι i 2 2 -1) + i =j∈[2k] α i α j Re Aι i , Aι j ≤ 1 - i∈[2k] α 2 i + i∈[2k] α 2 i sup ι∈D Aι 2 2 -1 + i =j∈[2k] α i α j sup (ι,ι )∈D 2 = Re Aι, Aι . Now, since (1 + c) -1 ≤ i∈[2k] α 2 i ≤ (1 -c) -1 we have 1 -i∈[2k] α 2 i ≤ c/(1 -c), hence Aν 2 2 -1 ≤ 1 1 -c c + sup ι∈D Aι 2 2 -1 + (2k -1) sup (ι,ι )∈D 2 =
Re Aι, Aι .

Since this holds for every ν ∈ S k , this establishes (44) using the definitions of δ(•|A) (see ( 12)) and of µ(D 2 = |A) (see ( 18)).

A.5 Proof of Proposition 4

To prove Proposition 4 we rely on a generic formula expressing Aι 2 2 for ι ∈ D that depends on a scalar α ∈ [0, 1], which reflects how balanced the normalized dipole ι is, and on a vector x, which reflects the relative position between the supports of the two monopoles that form ι. We also exploit an expression of Re Aι, Aι for (ι, ι ) ∈ D 2 = that depends on two scalars α, α reflecting how balanced ι and ι are respectively, and on two relative-position vectors x, x . The proof of the following proposition is deferred to Appendix A.5.1. Proposition 9. Consider T = (Θ, ρ, I) a location-based family with base distribution π 0 where ρ(•, •) = • -• for some norm • , and κ a normalized shift-invariant kernel that is locally characteristic with respect to T . Consider A a WFF sketching operator (Definition 6) with frequencies ω 1 , . . . , ω m , Θ d and ψ(ω) as defined in (59) and (52), and κ as defined in (15).

• For any normalized dipole ι ∈ D, there exists α ∈ [0, 1] and a vector x ∈ Θ d such that

Aι 2 2 = 1 m m j=1 ψ(ω j ) (1 -α) 2 + 2α(1 -cos ω j , x ) (1 -α) 2 + 2α(1 -κ(x)) . ( 121
)
The case of a normalized monopole ι ∈ M corresponds to α = 0 (and arbitrary x), while the case of a balanced normalized dipole corresponds to α = 1. Viceversa, for any α ∈ [0, 1] and x ∈ Θ d there is ι ∈ D such that this equality holds.

• For (ι, ι ) ∈ D 2 = , there exist s, s ∈ {-1, 1}, α, α ∈ [0, 1], θ 1 , θ 2 , θ 1 , θ 2 ∈ Θ that satisfy ∀i, j ∈ {1, 2}, (θ i , θ j ) ≥ 1, 0 < (θ 1 , θ 1 ) ≤ 1, 0 < (θ 2 , θ 2 ) ≤ 1, ( 122
)
such that Re Aι, Aι = ss a -α b -αc + αα d (1 -α) 2 + 2α(1 -κ(x)) (1 -α ) 2 + 2α (1 -κ(x )) , (123
) where x := θ 1θ 2 ∈ Θ d and x := θ 1θ 2 ∈ Θ d , and a, b, c and d are defined as follows

a = 1 π 0 2 κ Re Aπ θ1 , Aπ θ 1 , b = 1 π 0 2 κ Re Aπ θ1 , Aπ θ 2 , c = 1 π 0 2 κ Re Aπ θ2 , Aπ θ 1 , d = 1 π 0 2 κ Re Aπ θ2 , Aπ θ 2 . ( 124
)
The case where ι is a monopole (resp. a balanced dipole) corresponds to α = 0 (resp. α = 1) and similarly for ι and α .

Proof of (49). Since normalized monopoles and balanced normalized dipoles are special cases of normalized dipoles, we have M ⊂ D and D ⊂ D hence by the definition (12) of δ(D|A) as a supremum we trivially have δ(D|A) ≥ max δ(M|A), δ( D|A) .

To establish (49) we show the converse inequality. First observe that for any normalized monopole ι M ∈ M we have Aι M

Aι 2 2 = 1 m m j=1 ψ(ω j ) (1 -α) 2 + 2α(1 -cos ω j , x ) (1 -α) 2 + 2α(1 -κ(x)) .
Define a balanced normalized dipole as ι D := π0-πx π0-πx κ ∈ D. Proposition 9 again yields

Aι D 2 2 = 1 m m j=1 ψ(ω j ) 1 -cos ω j , x 1 -κ(x)
so that, with simple algebraic manipulations, we have

Aι 2 2 = (1 -α) 2 1 m m j=1 ψ(ω j ) + 2α 1 m m j=1 ψ(ω j )(1 -cos ω j , x ) (1 -α) 2 + 2α(1 -κ(x)) = (1 -α) 2 Aι M 2 2 + 2α(1 -κ(x)) Aι D 2 2 (1 -α) 2 + 2α(1 -κ(x)) . We deduce that min Aι M 2 2 , Aι D 2 2 ≤ Aι 2 2 ≤ max Aι M 2 2 , Aι D 2 2 . Moreover, since ι D ∈ D, we have max(1 -Aι D 2 2 , Aι D 2 2 -1) = |1 -Aι D 2 2 | ≤ δ( D|A) hence 1 -Aι 2 2 ≤ 1 -min Aι M 2 2 , Aι D 2 2 = max 1 -Aι M 2 2 , 1 -Aι D 2 2 ≤ max δ(M|A), δ( D|A) , Aι 2 2 -1 ≤ max Aι M 2 2 -1, Aι D 2 2 -1 ≤ max δ(M|A), δ( D|A) ,
This shows that |1-Aι 2 2 | ≤ max δ(M|A), δ( D|A) and establishes (49) as claimed.

Proof of (50). Recall that the families defined in (48

) satisfy M 2 = , M × D = , D2 = ⊂ D 2 = .
Hence, by the definition (18) of µ(•|A) as a supremum we trivially have

µ(D 2 = |A) ≥ max µ(M 2 = |A), µ(M × D = |A), µ( D2 = |A
) . This yields the lower bound in (50). To establish the upper bound we will use a result which proof is postponed to Section A.5.2.

Proposition 10. Let a, b, c, d ∈ R and e, f ∈ [0, 1) and consider the function

g defined on [0, 1] × [0, 1] by h(u, v) = a -bu -cv + duv √ 1 + u 2 -2eu 1 + v 2 -2f v . (125)
We have

sup (u,v)∈[0,1] 2 h(u, v) ≤ 3 max |a|, |b|, |c|, |d|, |b -a| √ 1 -e , |d -c| √ 1 -e , |d -b| √ 1 -f , |c -a| √ 1 -f , |a -b -c + d| √ 1 -e √ 1 -f .
Consider an arbitrary 1-separated pair of normalized dipoles, (ι, ι ) ∈ D 2 = , and denote s, s ∈ {-1, 1}, α, α ∈ [0, 1], θ 1 , θ 2 , θ 1 , θ 2 ∈ Θ, x, a, b, c, d the parameters satisfying (122)-( 123)-(124) as given by Proposition 9. As x, x ∈ Θ d we have 0 < (x, 0) ≤ 1 and 0 < (x , 0) ≤ 1, and since κ is locally characteristic12 with respect to T and as κ ≥ 0 implies κ ≥ 0 (cf (9) and (15)) , this yields e := κ(x ), f := κ(x) ∈ [0, 1) so that the expression (123) reads as h(α , α) with h as in (125). Since α, α ∈ [0, 1] and e, f ∈ [0, 1), by Proposition 10 applied to the absolute value of the expression (123) we get

Re Aι, Aι ≤ 3 max |a|, |b|, |c|, |d|, |b -a| √ 1 -e , |c -d| √ 1 -e , |b -d| √ 1 -f , |a -c| √ 1 -f , |b -a -c + d| √ 1 -e √ 1 -f .
Now, observe that (124) in Proposition 9 implies that every t ∈ {a, b, c, d} can be written as t = Re Aν, Aν where (ν, ν

) ∈ M 2 = , hence max(|a|, |b|, |c|, |d|) ≤ sup (ξ,ξ )∈M 2 = Re Aξ, Aξ = µ(M 2 = |A).
Similarly, observe that (124) implies also that |b -a|/ √ 1e = |Re Aν, Aν | where

ν := π θ1 π θ1 κ ∈ M; ν := π θ 1 -π θ 2 π θ 1 -π θ 2 κ ∈ D,
and by (122

) we have (ν, ν ) ∈ M × D = hence |b -a| √ 1 -e ≤ sup (xi,ξ )∈M× D = Re Aξ, Aξ =: µ(M × D = |A).
By symmetry, the same argument is valid for

|c -d|/ √ 1 -e, |b -d|/ √ 1 -f and |a -c|/ √ 1 -f . Therefore max |b -a| √ 1 -e , |c -d| √ 1 -e , |b -d| √ 1 -f , |a -c| √ 1 -f ≤ µ(M × D = |A).
Finally, with ν := (π θ1π θ2 )/ π θ1π θ2 κ and ν : 122)) and as a result

= (π θ 1 -π θ 2 )/ π θ 1 -π θ 2 κ , we have (ν, ν ) ∈ D2 = (by (
|b -a -c + d| √ 1 -e √ 1 -f = Re Aν, Aν ≤ sup (ξ,ξ )∈ D2 = Re Aξ, Aξ =: µ( D2 = |A).
Combining all of the above yields

Re Aι, Aι ≤ 3 max µ(M 2 = |A), µ(M × D = |A), µ( D2 = |A) .
As this holds for every (ι, ι ) ∈ D 2 = this establishes (50).

A.5.1 Proof of Proposition 9

Consider a normalized dipole ι ∈ D. Since ρ is a norm we can apply [GBKT21b, Lemma C.1] hence there exists a dipole ι such that ι = ι ι κ , with ι = s π0 κ (π θ1απ θ2 ), where s ∈ {-1, 1}, α ∈ [0, 1] and

x := θ 1 -θ 2 ∈ Θ -Θ satisfies 0 < x ≤ 1.
Since κ is locally characteristic we have ι κ > 0 hence the ratio ι/ ι κ indeed makes sense. The case of a normalized monopole ι ∈ M corresponds to α = 0 and an arbitrary x, while the case of a balanced dipole corresponds to α = 1. Moreover, since κ is translation invariant and T is a location-based family by (21) we have π θ1 κ = π θ2 κ = π 0 κ , and

π θ1 , π θ2 κ = κ(θ 1 , θ 2 ) • π θ1 κ π θ2 κ = κ(x) • π 0 2 κ
where we recall that the T -normalized kernel κ is defined in (15). Therefore

ι 2 κ = (1 -α) 2 + 2α(1 -κ(x)), Aι 2 2 = 1 m m j=1 ψ(ω j ) (1 -α) 2 + 2α(1 -cos ω j , x ) .
Since Aι 2 2 = Aι 2 2 / ι 2 κ , taking the quotient yields (121) as claimed. Vice-versa for α ∈ [0, 1] and x ∈ Θ d , there are θ 1 , θ 2 ∈ Θ 2 such that 0 < θ 1θ 2 ≤ 1 and setting ι = (π θ1απ θ2 )/ π θ1απ θ2 κ yields a normalized dipole satisfying the desired expression.

Similarly, for any 1-separated pair of normalized dipoles (ι, ι

) ∈ D 2 = we write ι = ι ι κ , ι = ι ι κ , with ι = s π 0 κ (π θ1 -απ θ2 ), ι = s π 0 κ (π θ 1 -α π θ 2 ),
where s, s ∈ {-1, 1}, α, α ∈ [0, 1] and x := θ 1 -θ 2 ∈ Θ-Θ and x := θ 1 -θ 2 ∈ Θ-Θ satisfy 0 < x ≤ 1 and 0 < x ≤ 1. The 1-separation assumption means that for every i, j ∈ {1, 2} we have

θ i -θ j ≥ 1. Since π θ1 κ = π θ2 κ = π θ 1 κ = π θ 2 κ = π 0 κ and π θ1 , π θ2 κ = π 0 2 κ κ(x), and π θ 1 , π θ 2 κ = π 0 2 κ κ(x ) we obtain ι 2 κ = (1 -α) 2 + 2α(1 -κ(x)), ι 2 κ = (1 -α ) 2 + 2α (1 -κ(x )) Re Aι, Aι = ss π 0 2 κ Re A(π θ1 -απ θ2 ), A(π θ 1 -απ θ 2 ) = ss (a -α b -αc + αα d) ,
with a, b, c, d as in (124). Since Re Aι, Aι = Re Aι, Aι /( ι κ ι κ ) we obtain (123). The special cases of monopoles and balanced dipoles, are proved similarly as above and left to the reader.

A.5.2 Proof of Proposition 10

We will use a technical Lemma which proof is postponed to the end of the section.

Lemma 5. Consider α, β ∈ R, γ ∈ [0, 1) and the function φ α,β,γ defined on [0, 1] by

φ α,β,γ (t) = α -βt 1 + t 2 -2γt . ( 126
)
We have

∀t ∈ [0, 1], |φ α,β,γ (t)| ≤ √ 3 max |α|, |β|, |β -α| 2(1 -γ) . (127) Consider (u
, v) ∈ [0, 1] 2 , f ∈ [0, 1), and define g := 1 √ 1+v 2 -2f v . We have h(u, v) = ga -gbu -gcv + gduv √ 1 + u 2 -2eu = (ga -gcv) -(gb -gdv)u √ 1 + u 2 -2eu = φ ga-gcv,gb-gdv,e (u)
|ga -gcv| = |a -cv| 1 + v 2 -2f v = |φ a,c,f (v)| ≤ √ 3 max |a|, |c|, |c -a| √ 1 -f , |gb -gdv| = |b -dv| 1 + v 2 -2f v = |φ b,d,f (v)| ≤ √ 3 max |b|, |d|, |d -b| √ 1 -f , |gb -gdv -ga + gcv| = |gb -ga + (gc -gd)v| = |b -a -(d -c)v| 1 + v 2 -2f v = |φ b-a,d-c,f (v)| ≤ √ 3 max |b -a|, |d -c|, |(d -c) -(b -a)| √ 1 -f .
Combining the above inequalities we obtain

|h(u, v)| ≤ 3 max |a|, |b|, |c|, |d|, |b -a| √ 1 -e , |d -c| √ 1 -e , |d -b| √ 1 -f , |c -a| √ 1 -f , |a -b -c + d| √ 1 -e √ 1 -f .
Proof of Lemma 5. Equivalently, we bound c := sup t∈[0,1] g(t) where g(t) := |φ α,β,γ (t)| 2 = P (t)/Q(t), P (t) := (βt-α) 2 , and

Q(t) := 1+t 2 -2γt. The bound c ≤ 3 max(α 2 , β 2 , (β- α) 2 /(1 -γ)
) is trivial if α = β = 0, so we now assume (α, β) = 0. We have g(0) = α 2 and g(1) = (βα) 2 /(2(1γ)) so the bound is also trivial if the maximum is achieved at a boundary point, so to conclude we now assume that c is achieved at an interior point t ∈ (0, 1), which must satisfy g (t) = 0. Since g = (P Q -P Q )/Q 2 the fact that g (t) = 0 reads as

0 = P (t)Q(t) -P (t)Q (t) = 2β(βt -α)(1 + t 2 -2γt) -(βt -α) 2 2(t -γ) = 2(βt -α) β(1 + t 2 -2γt) -(βt -α)(t -γ) = 2(βt -α) β + Z Z βt 2 -2βγt -Z Z βt 2 + αt + βγt -αγ = 2(βt -α) (α -βγ)t -(αγ -β) .
Since we assume (α, β) = (0, 0), we have

P (t)/Q(t) = g(t) ≥ max(g(0), g(1)) = max(α 2 , (β -α) 2 /(2(1 -γ))) > 0, hence P (t) = 0, i.e. βt -α = 0, thus the location of the maximum satisfies (α -βγ)t = αγ -β.
This implies that α = βγ (otherwise we would have both α = βγ and αγ = β, hence β = αγ = (βγ)γ = βγ 2 , and similarly α = αγ 2 ; since 0 ≤ γ < 1 this would contradict the fact that (α, β) = (0, 0)). Moreover, since

P (t)Q(t) -P (t)Q (t) = 0 we have g(t) = P (t)/Q(t) = P (t)/Q (t) = 2β(βt -α)/(2(t -γ))
. Since g(t) > 0 this shows that β = 0, and we conclude that

g(t) = β(βt -α) t -γ = β (α -βγ)(βt -α) (α -βγ)(t -γ) = β (αγ -β)β -(α -βγ)α (αγ -β) -(α -βγ)γ = β 2αβγ -α 2 -β 2 β(γ 2 -1) = α 2 + β 2 -2αβγ 1 -γ 2 = (α -β) 2 + 2αβ(1 -γ) (1 + γ)(1 -γ) ≤ (α -β) 2 1 -γ + 2|αβ| ≤ (α -β) 2 1 -γ + 2 max α 2 , β 2 ≤ 3 max α 2 , β 2 , (α -β) 2 1 -γ .
A.6 Proof of Proposition 5

Equalities (58), (59), (60), ( 61) and (62) are straightforward applications of the following lemma.

Lemma 6. Under the assumptions and notations of Proposition 5, there exist sets

Θ md ⊂ Θ d × Θ mm and Θ dd ⊂ Θ d × Θ d × Θ mm such that, 1. For every ι ∈ M, we have 1 -Aι 2 2 = 1 -Ψ m (Ω), for every Ω and A = A Ω . 2. For every ι ∈ D, there is x ∈ Θ d such that 1 -Aι 2 2 = 1 -Ψ d (x|Ω)
for every Ω and A = A Ω ; and vice-versa.

For

(ι, ι ) ∈ M 2 = , there are s ∈ {-1, 1}, y ∈ Θ mm s.t.
Re Aι, Aι = sΨ mm (y|Ω) for every Ω and A = A Ω , and vice-versa. 4. For (ι, ι ) ∈ M × D = there are s ∈ {-1, 1}, (x, y) ∈ Θ md s.t. Re Aι, Aι = sΨ md (x, y|Ω) for every Ω and A = A Ω , and vice-versa.

5. For (ι, ι ) ∈ D2 = there are s ∈ {-1, 1}, (x, x , y) ∈ Θ dd s.t. Re Aι, Aι = sΨ dd (x, x , y|Ω), for every Ω and A = A Ω , and vice-versa.

Proof of item 1: Proposition 9 yields Aι

2 2 = 1 m m j=1 ψ(ω j ) for every ι ∈ M.
Proof of item 2: Proposition 9 yields that for every ι ∈ D there is

x ∈ Θ d such that 1 -Aι 2 2 = 1 -1 m m j=1 ψ(ω j ) 1-cos ωj ,x 1-κ(x) = 1 -1 m m j=1 ψ(ω j )f d (x|ω j )
, and vice-versa, where we used that for t ∈ R we have 1cos t = 2 sin 2 (t/2).

The remaining items use the second part of Proposition 9 which gives a generic formula for Re Aι, Aι : when (ι, ι

) ∈ D 2 = there are s, s ∈ {-1, 1}, α, α ∈ [0, 1], θ 1 , θ 2 , θ 1 , θ 2 ∈ Θ satisfying (122)-(123) with x := θ 1 -θ 2 ∈ Θ d , x := θ 1 -θ 2 ∈ Θ d ,
and a, b, c and d are defined by (124). We will also use that given that A is a (κ, w)-FF sketching operator (cf Definition 6) and π θ is obtained by translation of π 0 we have Re Aπ θi , Aπ

θ j = 1 m m j=1 | π 0 , φ ωj | 2 cos ω j , θ i -θ j , and that y := θ 1 -θ 1 satisfies y ∈ Θ -Θ and y = θ 1 -θ 1 ≥ 1 by (122), thus y ∈ Θ mm . Proof of item 3 When (ι, ι ) ∈ M 2 = , we have α = α = 0 hence (123)-(124) yield Re Aι, Aι = ss a = ss π 0 2 κ 1 m m j=1 | π 0 , φ ωj | 2 cos ω j , θ 1 -θ 1 = ss m m j=1
ψ(ω j ) cos ω j , y .

Vice-versa for such s, s , y it is easy to exhibit (ι, ι ) ∈ M 2 = satisfying the same expression.

Proof of item 4 When (ι, ι ) ∈ M × D = , α = 0 and α = 1, which similarly yields

Re Aι, Aι = ss a -b 2(1 -κ(x )) = ss m m j=1 ψ(ω j ) cos ω j , θ 1 -θ 1 -cos ω j , θ 1 -θ 2 2(1 -κ(x )) .
Now, using the identity cos(u)cos(v) = -2 sin((uv)/2) sin((u + v)/2), we get cos ω j , θ 1θ 1cos ω j , θ 1θ 2 = cos ω j , ycos ω j , y + x = 2 sin ω j , x /2 sin ω j , y + x /2 .

Thus

Re Aι, Aι = ss Ψ md ((x , y)|Ω),

where x = θ 1θ 2 and y = θ 1θ 1 satisfy x ∈ Θ d and y ∈ Θ mm . We define Θ md as the set of all couples (x , y) ∈ Θ d ×Θ mm that satisfy (129) for some (ι, ι ) ∈ (M× D) = and s, s ∈ {-1, 1}.

Proof of item 5 When (ι, ι ) ∈ D2 = , α = 1 and α = 1, hence (123)-(124) similarly yield

Re Aι, Aι = ss a -b -c + d 2(1 -κ(x)) 2(1 -κ(x )) = ss m m j=1 ψ(ω j ) cos ω j , θ 1 -θ 1 -cos ω j , θ 1 -θ 2 -cos ω j , θ 2 -θ 1 + cos ω j , θ 2 -θ 2 2(1 -κ(x)) 2(1 -κ(x )) .
Since cos(u)-cos(v) = -2 sin( u-v 2 ) sin( u+v 2 ) and sin(u)-sin(v) = 2 sin( u-v 2 ) cos( u+v 2 ), and denoting y := θ 1θ 1 , x := θ 1θ 2 , and x := θ 1θ 2 , we get x, x ∈ Θ d , y ∈ Θ mm and cos ω j , θ 1θ 1cos ω j , θ 1θ 2cos ω j , θ 2θ 1 + cos ω j , θ 2θ 2 = cos ω j , ycos ω j , y + xcos ω j , yx + cos ω j , yx + x = 2 sin ω j , x /2 sin ω j , y + x /2 -2 sin ω j , x /2 sin ω j , yx + x /2 = 2 sin ω j , x /2 sin ω j , y + x /2sin ω j , yx + x /2 = 4 sin ω j , x/2 sin ω j , x /2 cos ω j , y + x /2x/2 .

Thus

Re Aι, Aι = ss Ψ dd ((x, x , y)|Ω).

We define Θ dd as the set of all triplets (x, x , y) ∈ Θ d × Θ d × Θ mm that satisfy (130) for some (ι, ι ) ∈ D2 = and s, s ∈ {-1, 1}.

A.7 Proof of Theorem 3

Consider ∈ {d, md, mm, dd} and z, z ∈ Θ , and denote

∆ ,Ω (z, z ) := |Ψ (z|Ω) -Ψ (z |Ω)| .
The result will follow if we exhibit z 1 , . . . , z T , 2 ≤ T ≤ 6 such that

z 1 = z, z T = z such that max 1≤t≤T -1 ∆ (z t , z t+1 ) ≤ ∆ (z, z ) (131)
and if we can find smooth functions u ∈ [0, 1] → f ,t (u|ω) such that for every ω ∈ R d and every t

f ,t (0|ω) = f (z t |ω), f ,t (1|ω) = f (z t+1 |ω) , (132)
sup 0<u<1 |f ,t (u|ω)| ≤ G(ω)∆ (z t , z t+1 ) ( 133
)
where

G(ω) := C κ 3 i=1 ω i a, . (134)
Indeed, this will imply by the triangle inequality, the mean value theorem, and (67) that

∆ ,Ω (z, z ) = ∆ ,Ω (z 1 , z T ) ≤ T -1 t=1 ∆ ,Ω (z t , z t+1 ) = T -1 t=1 1 m m j=1 ψ m (ω j )[f ,t (1|ω j ) -f ,t (0|ω j )] ≤ T -1 t=1 1 m m j=1 ψ m (ω j ) |[f ,t (1|ω j ) -f ,t (0|ω j )]| ≤ 1 m T -1 t=1 m j=1 ψ m (ω j ) sup 0<u<1 |f ,t (u|ω j )| ≤ 1 m T -1 t=1 m j=1 ψ m (ω j )G(ω j )∆ (z t , z t+1 ) =   1 m m j=1 ψ m (ω j )G(ω j )   • T -1 t=1 ∆ (z t , z t+1 ) ≤   1 m m j=1 ψ m (ω j )G(ω j )   • 6∆ (z, z ) = 6Ψ 0 (Ω) • C κ • ∆ (z, z ).
The case = md. For any x, y, ω, by (55), ( 63), (64), since 2 sin v sin w = cos(vw)cos(v + w)

f md (x, y|ω) = √ 2 sin ω, x /2 sin ω, y + x/2 1 -κ( x a ) = √ 2α( x a ) sin ω, x /2 sin ω, y + x/2 x a = 1 √ 2 α( x a ) cos( ω, y ) -cos( ω, y + ω, x ) x a .
Since z 1 = (x, y) = (x, ȳ(0)), z 2 = (x, y ) = (x, ȳ(1)) = (r(0) • n, y ), z 3 = (x, y ) = (r(1) • n, y ) = (r • n(0), y ), z 4 = (x , y ) = (r • n(1), y ), Property (132) holds with

f md,1 (u|ω) := √ 2α(r) sin r ω, n /2 sin ω, ȳ(u) + x/2 r , (138)
f md,2 (u|ω) := √ 2α(r(u)) sin r(u) ω, n /2 sin ω, y + r(u) • n/2 r(u) , (139)
f md,3 (u|ω) := 1 √ 2 α(r ) cos( ω, y ) -cos( ω, y + r ω, n(u) ) r . ( 140
)
The case = dd. For any x 1 , x 2 , y, ω, (56) yields using ( 63)-( 64)

f dd ((x 1 , x 2 , y)|ω) = 2 sin ω, x 1 /2 sin ω, x 2 /2 cos ω, y + x 2 /2 -x 1 /2 1 -κ( x 1 a ) 1 -κ( x 2 a ) = 2α( x 1 a )α( x 2 a ) sin ω, x 1 /2 sin ω, x 2 /2 cos ω, y + x 2 /2 -x 1 /2 x 1 a x 2 a
Reasoning as above establishes Property (132) holds with z 1 = (x 1 , x 2 , y), z 2 = (x 1 , x 2 , y ), z 3 = (x 1 , x 2 , y ), z 4 = (x 1 , x 2 , y ), z 5 = (x 1 , x2 , y ), z 6 = (x 1 , x 2 , y ), ȳ(u) := y + u(yy), where xi , r i , r i , ri (u), n i , n i , ni (u), i ∈ {1, 2} were defined in the same way as in the case = d, and f dd,1 (u|ω) := 2α(r 1 )α(r 2 ) sin r 1 ω, n 1 /2 sin r 2 ω, n 2 /2 cos ω, ȳ(u) + r 2 n 2 /2r 1 n 1 /2 r 1 r 2 (141)

f dd,2 (u|ω) := 2α(r 1 (u))α(r 2 ) sin r1 (u) ω, n 1 /2 sin r 2 ω, n 2 /2 cos ω, y + r 2 n 2 /2 -r1 (u) • n 1 /2 r1 (u)r 2 (142) f dd,3 (u|ω) := 2α(r 1 )α(r 2 ) sin r 1 ω, n1 (u) /2 sin r 2 ω, n 2 /2 cos ω, y + r 2 n 2 /2 -r 1 • n1 (u)/2 r 1 r 2 (143) f dd,4 (u|ω) := 2α(r 1 )α(r 2 (u)) sin r 1 ω, n 1 /2 sin r2 (u) ω, n 2 /2 cos ω, y + r2 (u)n 2 /2 -r 1 n 1 /2 r 1 r2 (u) (144)
f dd,5 (u|ω) := 2α(r 1 )α(r 2 ) sin r 1 ω, n 1 /2 sin r 2 ω, n2 (u) /2 cos ω, y + r 2 n2 (u)/2r 1 n 1 /2 r 1 r 2 (145)

A.7.3 Proof of the bound (133)

To continue we gather a few observations. First, since sinc(t) := sin(t)/t = 1 0 cos(xt)dx for every t = 0 (and sinc(0) = 1) we have sinc (t) =

∀v ∈ R d , |α(t) sin(t ω, v /2)/t| = |α(t) ω,v 2 sinc(t ω, v /2)| ≤ √ C κ 2 ω a, v a .
(146) Recalling that ȳ(u) := y + u(yy), n(u) := n + u(nn), r(u) := r + u(rr), and ω ∈ R d we now bound the following auxiliary functions and their derivatives, with arbitrary φ ∈ R g 0,φ (u) := cos( ω, ȳ(u) + φ) , g 1 (u) := α(r(u))

sin(r(u) ω, n /2) r(u) , g 2 (u) := α(r ) sin(r ω, n(u) /2) r .

Since 0 < r ≤ R we have

|g 0,φ (u)| = | sin( ω, ȳ(u) + φ) • ω, y -y | ≤ | ω, y -y | ≤ ω a, • y -y a , |g 2 (u)| = |α(r ) cos(r ω, n(u) /2) • ω,n -n 2 | ≤ √ C κ ω a, 2 • n -n a .
As g 1 (u) = α(r(u)) ω,n 2 sinc(r(u) ω, n /2), n a = 1, and r(u) ≤ max(r, r ) ≤ R we get

|g 1 (u)| = α (r(u)) sinc(r(u) ω, n /2) + α(r(u)) ω, •n 2 sinc (r(u) ω, n /2) • ω, n 2 • (r -r) ≤ √ C κ ω a, 2 • (1 + ω a, /2) • |r -r|
Since n(u) a ≤ max( n a , n a ) = 1 we also get using ( 146)

max(|g 1 (u)|, |g 2 (u)|) ≤ √ C κ 2 ω a, max( n a , n(u) a ) = √ C κ 2 ω a, .
We are now equipped to proceed.

The case = d. Expressions (135)-(136) yield f d,1 (u|ω) = 2g 2 1 (u), f d,2 (u|ω) = 2g 2 2 (u). By (68) and the choice of z 1 = x, z 2 = x, z 3 = x we have ∆ d (z 1 , z 2 ) = |r -r|, ∆ d (z 2 , z 3 ) = nn a and we obtain the bound (133) since

|f d,1 (u)| = |4g 1 (u)g 1 (u)| ≤ C κ ( ω 2 a, + ω 3 a, /2) • |r -r| ≤ G(ω) • ∆ d (z 1 , z 2 ) , |f d,2 (u)| = |4g 2 (u)g 2 (u)| ≤ C κ ω 2 a, • n -n a ≤ G(ω) • ∆ d (z 2 , z 3 ) .
The case = mm. By the expression (137) we have f mm,1 = g 0 . The bound (133) follows from

|f mm,1 (u)| = |g 0,0 (u)| ≤ ω j a, y -y a (65)&(69) ≤ G(ω)∆ mm (z 1 , z 2 ).
The case = md. By the identity cos(θπ/2) = sin(θ) we have f md,1 (u)

(138) = √
2g 1 (0)g 0,φ (u) with φ := ω, x /2π/2, and by (139) f md,2 (u) = √ 2g 1 (u) sin(ψ(u)) with ψ(u) := ω, y + r(u)n/2 , and ψ (u) = ω, n (rr)/2. Combining with (140) we obtain the bound (133) since

|f md,1 (u)| = | √ 2g 1 (0)g 0,φ (u)| ≤ √ C κ √ 2 ω j 2 a, y -y a Cκ≥1&(70) ≤ G(ω)∆ md (z 1 , z 2 ) , |f md,2 (u)| = √ 2|g 1 (u) sin(ψ(u)) + g 1 (u) cos(ψ(u)) ω, n (r -r)/2| ≤ √ 2 √ C κ ω a, 2 (1 + ω a, /2)|r -r| + √ C κ ω a, 2 ω a, |r -r|/2 ≤ C κ ω a, √ 2 (1 + ω a, ) • |r -r| ≤ G(ω)∆ md (z 2 , z 3 ) , |f md,3 (u)| = 1 √ 2 |α(r ) sin( ω, y + r ω, n(u) ) • ω, n -n | ≤ √ C κ ω a, √ 2 • n -n a ≤ G(ω)∆ md (z 2 , z 3 ) .
The case = dd Denote g i,j , i, j = 1, 2 the functions defined as g i with r j , r j , etc. instead of r, r etc. By (141) we have f dd,1 (u) = 2g 1,1 (0)g 1,2 (0)g 0,φ (u) with φ := r 2 n 2 /2-r 1 n 1 /2, and by (142

), f dd,2 (u) = 2g 1,1 (u)g 1,2 (0) cos(ψ(u)) with ψ 2 (u) := ω, y + r 2 n 2 /2 -r1 (u) ω, n 1 /2, ψ 2 (u) = -ω, n 1 (r 1 -r 1 )/2 hence |f dd,1 (u)| = |2g 1,1 (0)g 1,2 (0)g 0,φ (u)| ≤ C κ 2 ω 3 a, • y -y a ≤ G(ω)∆ dd (z 1 , z 2 ) , |f dd,2 (u)| = |2g 1,2 (0)| • |g 1,1 (u) cos(ψ(u)) + g 1,1 (u) sin(ψ(u)) ω, n 1 (r 1 -r 1 )/2| ≤ C κ ω a, √ C κ ω a, 2 (1 + ω a, /2)|r 1 -r 1 | + √ C κ ω a, 2 ω a, |r 1 -r 1 |/2 ≤ C κ 2 ω 2 a, (1 + 3 ω a, /4) |r 1 -r 1 | ≤ G(ω)∆ dd (z 2 , z 3 ) .
Similarly by (144) f dd,4 (u) = 2g 1,1 (1)g 1,2 (u) cos(ψ 4 (u)) with ψ 4 (u) := ω, y -r 1 n 1 /2 + r2 (u) ω, n 2 /2 and the same reasoning yields the same bound. This establishes the bound (133) for t = 1, 2, 4. By (143) and the identity 2 sin v cos w = sin(v + w) + sin(vw) we write

f dd,3 (u) = g 1,2 (0) α(r 1 ) r 1 2 sin r 1 ω, n1 (u) /2 cos ω, y + r 2 n 2 /2 -r 1 • n1 (u)/2 = g 1,2 (0) α(r 1 ) r 1 sin( ω, y + r 2 n 2 /2 ) + sin(r 1 ω, n1 (u) -ω, y + r 2 n 2 /2 ψ3(u)
)

|f dd,3 (u)| = |g 1,2 (0) α(r 1 ) r 1 cos(ψ 3 (u))ψ 3 (u)| ≤ √ C κ ω a, 2 √ C κ r 1 |ψ 3 (u)| = C κ ω a, 2 | ω, n 1 -n 1 | ≤ C κ ω 2 a, 2 • n 1 -n 1 a ≤ G(ω)∆ dd (z 3 , z 4 ).
The same reasoning works from (145) for t = 5. This establishes the bound (133) for t = 3, 5.

A.7.4 Proof of Proposition 6

We denote by B a (resp. = rnr i s j a + ns j a ≤ rnr i n a + r i nr i s j a + ns j a ≤ |rr i | n a + (r i + 1) ns j a ≤ τ /2 + (R d + 1)τ /(2(R d + 1)) ≤ τ.

An upper bound of N mm (τ ). By definition of R mm we have Θ mm ⊂ R mm • B a . By [GBKT21b, Lemma A.1] [Wai19, Lemma 5.7] and (69) we have

N mm (τ ) := N (Θ mm , • a , τ ) ≤ N R mm • B a , . a , τ /2 = N B a , . a , τ /(2R mm ) ≤ 1 + 4R mm /τ d ≤ 1 + 4D/τ d .
An upper bound of N md (τ ). By (61), we have Θ md ⊂ Θ d × Θ mm . Thus by [GBKT21b, Lemma A.1], we have

N md (τ ) = N (Θ md , ∆ md , τ ) ≤ N (Θ d × Θ mm , ∆ md , τ /2).
Now, given the definition (70) of ∆ md we have

N md (τ ) ≤ N (Θ d × Θ mm , ∆ md , τ /2) ≤ N (Θ d , ∆ d ,
N dd (τ ) ≤ N (Θ d × Θ d × Θ mm , ∆ dd , τ /2) (71) ≤ N (Θ d , ∆ d , τ /8) 2 N (Θ mm , ∆ mm , τ /4) = N d (τ /8)N d (τ /8)N mm (τ /4) ≤ 1 + 64(D + 1)/τ 2(d+1) 1 + 16D/τ d ≤ 1 + 64(D + 1)/τ 3d+2 .
To conclude, observe that the last bound dominates all the previous ones.

A.8 Proof of Theorem 4

Since the average marginal density of the ω j 's satisfies (33), we have

EΨ m (Ω) = 1 (149) EΨ d (z|Ω) = 1, ∀z ∈ Θ d (150) |EΨ (z|Ω)| ≤ µ ∀ ∈ {mm, md, dd}, ∀z ∈ Θ . (151)
The proof of (151) (( 149) and ( 150) are obtained similarly) is postponed to the end of this section. By (151) we have 75),(76) yield

|Ψ (z|Ω)| ≤ |Ψ (z|Ω) -EΨ (z|Ω)| + µ, ∀ ∈ {mm, md, dd}, ∀z ∈ Θ hence (74),(
P |Ψ m (Ω) -1| > τ 4 ≤ 2 exp - m v , (152) ∀z
∈ Θ d , P |Ψ d (z|Ω) -1| > τ 8 ≤ 2 exp - m v , (153)
∀ ∈ {mm, md, dd}, ∀z ∈ Θ , P |Ψ (z|Ω)| > µ + τ 16k ≤ 2 exp - m v . (154)
Now, observe that the mutual incoherence assumption implies that κ is locally characteristic with respect to T and that its 2k-coherence is bounded by c = (2k -1)µ. Since κ ≥ 0, all assumptions of Propositions 3 to 5 and Theorem 3 thus hold. For each ∈ {d, mm, md, dd} consider a covering (z i ) i∈[N (τ )] of Θ with respect to ∆ at scale

τ := τ 96M k • C κ . ( 155
) By Theorem 3, if Ψ 0 (Ω) ≤ M , (156)
max i∈∈[N d (τ )] |Ψ d (z d i |Ω) -1| ≤ τ /8 (157) max ∈{mm,md,dd} max i∈∈[N (τ )] |Ψ (z i |Ω)| ≤ µ + τ 16k (158)
then by (66), for each ∈ {mm, md, dd} and z ∈ Θ there is

i ∈ [N (τ )] such that |Ψ (z|Ω)| ≤ |Ψ (z i |Ω)| + |Ψ (z|Ω) -Ψ (z i |Ω)| ≤ µ + τ 16k + 6M • C κ • ∆ (z, z i ) ≤τ ≤ µ + τ 16k + τ 16k ≤ µ + τ 8k ,
and similarly for each z ∈ Θ d there is

i ∈ [N d (τ )] such that |Ψ d (z|Ω) -1| ≤ |Ψ (z d i |Ω) -1| + |Ψ d (z|Ω) -Ψ (z d i |Ω)| ≤ τ 8 + τ 8 ≤ τ 4 .
Thus, when (156)-( 157 If in addition we have

|Ψ m (Ω) -1| ≤ τ 4 (159)
then by Proposition 5 and the bound (51), which follows from Propositions 3 and 4, we obtain max δ(M|A), δ( D|A) ≤ τ /4,

(2k -1) max µ(M 2 = |A), µ( D2 = |A), µ(M × D = |A)) ≤ (2k -1)µ + τ /4 = c + τ /4, δ(S k |A) ≤ 1 1 -c c + τ 4 + 3(c + τ 4 ) = 4c + τ 1 -c .
Observe that, since 0 < τ < 1 -5c, we have 4c + τ < 1c hence (4c + τ )/(1c) < 1.

To conclude, we bound the probability p that one of the inequalities ( 156)-( 157)-( 158)-(159) fails to hold. Using (155), denoting D := diam a (Θ), we have 1 + 64(D + 1)/τ = 1 + 6144M k(D + 1)C κ /τ = 1 + C/τ . By a union bound combining (73)-( 152)-( 153)-( 154) and by Proposition 6 we obtain

p ≤ 2 exp - m v • 2 + ∈{d,mm,md,dd} N (τ ) ≤ 2 exp - m v • 2 + 4 1 + 64(D + 1)/τ 3d+2 ≤ 12 exp - m v • 1 + C/τ 3d+2 .
Proof of (151). Let ∈ {mm, md, dd} and let z ∈ Θ . First, by Lemma 6, there exists (ι, ι ) ∈ D 2 = and ξ ∈ {-1, 1} such that Ψ (z|Ω) = ξ Aι, Aι for any choice of Ω (and of the corresponding sketching operator A = A Ω ). In the following, we show that E Ω Aι, Aι = ι, ι κ , so that, by the definition (17) of the mutual coherence with respect to T , we get

|E Ω Ψ (z|Ω)| = | ι, ι κ | ≤ µ. Remember that Aι, Aι = m j=1 φ ωj , ι φ ωj , ι /m, so that E Ω Aι, Aι = 1 m m j=1 E Ω φ ωj , ι φ ωj , ι = 1 m m j=1 R d Λ j (ω) φ ω , ι φ ω , ι dω = R d 1 m m j=1 Λ j (ω) φ ω , ι φ ω , ι dω (33) = R d w(ω) 2 κ(ω) φ ω , ι φ ω , ι dω = ι, ι κ .
A.9 Proof of Theorem 5 and its corollaries

In this section, we prove Theorem 5, Corollary 1 and Corollary 2. We start by establishing Lemma 2, and a few lemmas to deal with sub-exponential random variables.

A.9.1 Proof of Lemma 2

The case = d. With x = z ∈ Θ d , x := x/ x a we have x a = 1. As | sin t| ≤ |t| for all t

|f d (z|ω)| (53) = 2 sin 2 ( ω, x )/2 1 -κ( x a ) (64) = 2α 2 ( x a ) sin 2 ( ω, x /2) x 2 a (65) ≤ 1 2 C κ ω, x 2 ≤ C κ | ω, x | 2 .
This establishes (82) with p = p d = 2.

The case = mm. Denote y = z ∈ Θ mm . We have |f mm (z|ω)|

= | cos( ω, y )| ≤ 1. This establishes (82) with p = p mm = 0. The case = md. With (x, y) = z ∈ Θ md and x := x/ x a we have x a = 1 and

|f md (z|ω)| (55) = 2 sin ω, x/2 sin ω, y + x/2 2(1 -κ(x)) (64) ≤ √ 2α( x a ) sin ω, x/2 x a (65) ≤ √ 2 C κ ω, x 2 x a ≤ C κ | ω, x |. (160)
This establishes (82) with p = p md = 1.

The case = dd. With (x 1 , x 2 , y) = z ∈ Θ dd and x i = x i / x i a we have x i a = 1 and

|f dd (z|ω)| (56) = 4 sin ω, x 1 /2 sin ω, x 2 /2 cos ω, y + x 2 /2 -x 1 /2 2(1 -κ(x 1 )) 2(1 -κ(x 2 )) (64) ≤ 2α( x 1 a )α( x 2 a ) sin ω, x 1 /2 sin ω, x 2 /2 x 1 a x 2 a (65) ≤ C κ 2 ω, x 1 / x 1 a ω, x 2 / x 2 a = C κ 2 ω, x 1 ω, x 2 ≤ C κ 4 ω, x 1 2 + ω, x 2 2 .
A.9.2 Some properties of sub-exponential random variables

λ(X-EX) = +∞ q=0 λ q q! E(X -EX) q ≤ 1+ +∞ q=2 |λ| q q! E|X -EX| q ≤ 1+ +∞ q=2 |λ| q q! E(Y +EY ) q .
Using the binomial formula this yields

Ee λ(X-EX) ≤ 1 + +∞ q=2 |λ| q q! q j=0 q j E(Y -EY ) j E q-j = 1 + ∞ j=0 |λ| j j! E(Y -EY ) j • q≥max(j,2)
|λ| q-j j! q! q j E q-j .

Observe that E(Y -EY ) 0 = 1, E(Y -EY ) 1 = 0, and q≥max(j,2)

|λ| q-j j! q! q j E q-j = q≥max(j,2)

|λ| q-j (q -j)! E q-j = k≥0 (|λ|E) k k! = e |λ|E , j ≥ 2 k≥1 (|λ|E) k k! = e |λ|E -1 -|λ|E, j = 0.
Since Y is sub-exp(ν, β), when |λ| ≤ 1/β we obtain (using again that E(Y -EY ) j = 0 for j = 1)

Ee λ(X-EX) ≤ 1 + (e |λ|E -1 -|λ|E) + ∞ j=2 |λ| j j! E(Y -EY ) j e |λ|E = 1 + ∞ j=2 |λ| j j! E(Y -EY ) j e |λ|E -|λ|E = Ee |λ|(Y -EY ) e |λ|E -|λ|E ≤ e ν 2 λ 2 /2+|λ|E -|λ|E.
To conclude we use a technical lemma which proof is postponed to Appendix A.9.6.

Lemma 7. For α > 0, we have

∀t ≥ 0, e αt 2 /2+t -t ≤ e (α+2)t 2 . ( 161
)
Applying the lemma with α = (ν/E) 2 , t = |λ|E, we obtain

|λ| ≤ 1/β =⇒ Ee λ(X-EX) ≤ e ν 2 λ 2 2 +|λ|E -|λ|E = e αt 2 2 +t -t ≤ e (α+2)t 2 = e 2(ν 2 +2E 2 )λ 2 2 . (162) This shows that X is sub-exp(ν , β) with (ν ) 2 = 2(ν 2 + 2E 2 ) = 2ν 2 + 16(EY ) 2 .
Lemma 8. If X ∼ N (0, 1) then X 2 is sub-exp(2, 4) and |X| is sub-exp(4, 4).

Proof. Since Y := X 2 follows the chi-squared distribution of one degree of freedom, by [START_REF] Forbes | Statistical distributions[END_REF] we have

Ee λY = 1 √ 1 -2λ , ∀|λ| < 1 2 . ( 163
)
In particular, since EY = 1, then

Ee λ(Y -EY ) = Ee λ(Y -1) = e -λ √ 1 -2λ ≤ e 2 2 λ 2 2 , ∀|λ| ≤ 1 4 .
This is the definition of a sub-exp(2, 4) random variable. Now, considering Z := |X|, since |t| ≤ t 2 + 1/4 for each t ∈ R, we have

Z = |X| ≤ 1 4 + X 2 . a.s.
Since X 2 is sub-exp(2, 4), X 2 +1/4 is also sub-exp(2, 4). As E(X 2 +1/4) = 5/4 ≤ √ 2, by Lemma 3, X is sub-exp(ν, 4), with ν 2 := 2 × 2 2 + 4(5/4) 2 ≤ 16, hence Z is subexp(4, 4). Lemma 9. Consider X i , i = 1, 2 two real-valued random variables (possibly non independent), assumed to be respectively sub-exp(ν i , β i ). Then X 1 +Y 2 is sub-exp(ν, β) where ν := ν 1 + ν 2 , and β := max

β 1 (ν 1 + ν 2 ) ν 1 , β 2 (ν 1 + ν 2 ) ν 2 . ( 164
)
Proof. Let p = (ν 1 + ν 2 )/ν 1 and q = (ν 1 + ν 2 )/ν 2 , so that 1/p + 1/q = 1. By Hölder's inequality and Definition 9,

if |λ| ≤ min( 1 pb1 , 1 qb2 ) = min ν1 b1(ν1+ν2) , ν2 b2(ν1+ν2) then Ee λ(X1+X2) ≤ (Ee λpX1 ) 1/p (Ee λqX2 ) 1/q ≤ e λ 2 p 2 ν 2 1 2p e λ 2 q 2 ν 2 2 2q ≤ e λ 2 (pν 2 1 +qν 2 2 ) 2 = e λ 2 (ν 1 +ν 2 ) 2 2 .
A.9.3 Proof of Theorem 5

The proof of Theorem 5 leverages Theorem 4. Before exploiting this theorem we check that the basic required assumptions are met: i) T = (Θ, ρ, I), κ ≥ 0 and • a are satisfying the assumptions required in Theorem 3, ii) κ is assumed to have its mutual coherence with respect to T bounded by 0 < µ < 1/10, and k satisfies 1 ≤ k < 1 10µ , iii) w is a κ-compatible weight function and the average marginal density of the ω j 's satisfies (33), iv) the assumption (73) holds. Now, we move to check the more technical assumptions: (74),( 75),(76) with v defined in (86). For this purpose, we prove that Ψ m (Ω) is sub-exp(ν / m/b, β /(m/b)) and for ∈ {d, mm, md, dd}, and for z ∈ Θ , Ψ (z|Ω) is sub-exp(ν m/b, β /(m/b)), where we recall that b is the block size, and ν , β will be specified in due time to derive (74),( 75),(76) using (81).

First, consider ∈ {d, mm, md, dd} and z ∈ Θ , and observe that

Ψ (z|Ω) = 1 m/b m/b j=1 1 b b i=1 ψ(ω (j-1)b+i )f (z|ω (j-1)b+i ) =:Xj ,
where by assumption the random variables X j are independent and identically distributed. A well-known property of sub-exp random variables is that if X 1 , . . . , X n are independent sub-exp(ν, β) then 1 n n j=1 X j is sub-exp(ν/ √ n, β/n). Thus, in order to prove that Ψ (z|Ω) is sub-exp(ν / m/b, β /(m/b)), it is enough to prove that the random variable

X := 1 b b i=1 ψ(ω i )f (z|ω i )
is sub-exp(ν , β ). For this purpose, we make use of Lemmas 2 and 3. Consider arbitrary x t ∈ R d , t ∈ {0, 1, 2}, s.t. x t a = 1, and denote Z t,p :=

1 b b i=1 ψ(ω i )( √ C κ | ω i , x t |) p , t, p ∈ {0, 1, 2}. By assumption, each Z t,p is sub- exp(ν, β) with |E(Z t,p )| ≤ B. We distinguish two cases
• if ∈ {d, mm, md}, since ψ(.) ≥ 0, the first claim of Lemma 2 implies that |X| ≤ Z 0,p for some choice of x 0 , hence by Lemma 3 X is sub-exp(ν , β), where

ν := 2ν 2 + 16B 2 . ( 165
(Ω) is sub-exp(ν / m/b, β /(m/b)), it is enough to prove that X := 1 b b i=1 ψ(ω i ) is sub-exp(ν , β
). Since ψ(ω) = Z 0,0 for any choice of x 0 , this is indeed true with ν as in (165) and β = β. Now, we use (81) applied to Ψ m (Ω) with t = τ 4 , and to Ψ d (z|Ω) with t = τ 8 , and to Ψ (z|Ω) with t = τ 16k for ∈ {d, mm, md, dd} and z ∈ Θ , to get that the left hand side of (74),(75),( 76) is bounded from above by max

t∈{ τ 4 , τ 8 , τ 16k } 2 exp - (m/b)t 2 2ν 2 + βt = 2 exp - (m/b) τ 16k 2 2ν 2 + β τ 16k = 2 exp - mτ 2 256bk 2 (2ν 2 + β τ 16k
where we used that t → t 2 /(2(ν ) 2 + βt) is an increasing function. We conclude by observing that, with v as defined in (86), we have

256bk 2 (2ν 2 + β τ 16k ) ≤ 256bk 2 (2ν 2 + βτ ) = τ 2 v,
To prove the variant of the theorem, we first reason as above to show that the modified assumptions imply that for arbitrary ψ(ω i )f (z|ω i ) satisfies |X| ≤ Y for an appropriate choice of x 1 , x 2 . The same reasoning as above yields that X is sub-exp(B ψ ν , B ψ β) with ν as in (165). We conclude similarly once we observe that 256bk 2 (2B 2 ψ ν 2 + B ψ βτ ) = τ 2 v .

x t ∈ R d , t ∈ {0, 1, 2}, s.t. x t a = 1 the random variable Y p := 1 b b i=1 B ψ ( √ C κ | ω, x 0 |) p is sub-exp(B ψ ν, B ψ β) with |EY p | ≤ B ψ β, and similarly for Y := 1 b b i=1 B ψ C κ ( ω, x 1 2 + ω, x 2
A.9.4 Proofs of Corollary 1 and Corollary 2

Corollary 1 and Corollary 2 are direct consequences of Theorem 5. To see why, we check that the assumptions of these theorems are met in these settings.

Checking that the assumptions on T and κ hold, and controlling C κ , µ.

C κ ≤ max 1, 4 √ 3R, 4 √ 3σ 2 ≤ max 1, √ 3 2 , √ 3σ
2 . Now we proceed separately for the two settings.

• For Gaussian mixtures, as √ 2 + s 2 ≤ (4 log(ek)) -1 , we get σ = 2(2 + s 2 ) ≤ , and by [GBKT21b, Theorem 5.16, Lemma 6.10] κ is locally characteristic with mutual coherence with respect to T bounded by µ ≤ 12/(16(10k -1)).

• For mixtures of Diracs, since s ≤ (4 log(5ek)) -1 , we get σ := √ 2s ≤ and the bound on the coherence holds by [GBKT21b, Theorem 5.16, Lemma 6.10].

In both cases, we get µ ≤ 12/(16(10k -1))m ≤ 1/(10k) and σ ≤ . The latter implies

C κ ≤ max 1, √ 3 2 , √ 3σ 2 = max(1, √ 3 2 ). ( 166
)
Since B ψ := sup ω∈R d ψ(ω) is finite in both settings, we may use the variant of Theorem 5. Indeed, by (91) (resp. by ( 96)) B ψ = (1 + 2s -2 ) d/2 for Gaussian mixtures (resp. B ψ = 1 for mixtures of Diracs). Now, we check that the assumptions expressed in Item 1 (in its variant involving Z p ) and Item 2 of Theorem 5 hold in both settings. (167) This is done in the following. To handle both settings in a common framework, define Σ = I d for the setting of a mixture of Diracs, so that in both cases we have . a = . Σ . Thus, a vector x ∈ R d satisfies x a = x Σ = 1 if, and only if, Σ -1/2 x 2 = 1. Since ω ∼ N (0, s -2 Σ -1 ) we have sΣ 1/2 ω ∼ N (0, I d ) hence s ω, x = s Σ 1/2 ω, Σ -1/2 x ∼ N (0, 1), so that (E| ω, x |) 2 ≤ E| ω, x | 2 = 1/s 2 , hence using also that | ω, x | 0 ≡ 1 we obtain max We move now to check that Item 2 holds in both settings.

Identifying M such that Item 2 in Theorem 5 holds for Gaussian mixtures with any v > 0. We show that

|ψ(ω)f 0 (ω)| ≤ M := 4B ψ , ∀ω, (168)
hence (85) holds for any v > 0. In particular, (85) holds for v = v k (τ ), with v k (τ ) defined in (94). Indeed, for every t ≥ 0 we have t 2 ≤ (t + t 3 )/2 (since t(t -1) 2 ≥ 0), hence given the definition (67) of f 0 and since • a, = • Σ -1 we have f 0 (ω) ≤ 3 2 ( ω Σ -1 + ω 3 Σ -1 ) for every ω, so that |ψ(ω)f 0 (ω)|

= B ψ e -ω T Σω/2 f 0 (ω) ≤ 3 2 B ψ e -ω 2 Σ -1 /2 ( ω Σ -1 + ω where ϕ 1 (t) := te -t 2 /2 , and ϕ 2 (t) := t 3 e -t 2 /2 , and it is easy to prove that sup t∈R ϕ 1 (t) = ϕ 1 (1) = e -1/2 ≤ 1, and sup t∈R ϕ 2 (t) = ϕ 2 ( √ 3) = 3 √ 3e -3/2 ≈ 1.16 ≤ 5/3 ≈ 1.66. In other words, (85) holds with M = M (τ 3/2 m 1/2 ) and v = v k (τ ). Wrapping up the proof.

To complete the proof of Corollary 1 and Corollary 2 we use Theorem 5 and the last step is to give explicit upper bounds of the constants C and v respectively defined in (88) and (89).

We start with v , and we show that it is upper bounded by v k (τ ) defined in (94) (resp. in (99)). By (167), ν = β = 4B hence, by (86 (x-1) 3 +(1-2x) 2 = x 3 +x 2 -x = x(x 2 +x-1) = x[x+(1+ √ 5)/2][x+(1-√ 5)/2] ≤ 0 hence (1 -2x) 2 ≤ (1x) 3 , and since 1 -2x > 0 it follows that 1 -2x ≤ (1x) 3/2 . Thus, we obtain

) ν = √ 2 √ ν 2 + 8B 2 = √ 48B 2 ≤ √ 49B 2 = 7B
|α 1 (t)| =
1e -t 2 (1 + t 2 ) √ 1e -t 2 3 ≤ 1 -2e -t 2 √ 1e -t 2 3 = 1 -2x (1x) 3/2 ≤ 1, Now, when 0 < t ≤ 1, since [v(t)] -3/2 = (α 1 (t)/t) 3 , using that |α 1 (t)| ≤ (1e -1 ) -1/2 max(1, t) = (1e -1 ) -1/2 and (1e -1 ) -3/2 ≈ 1.99 ≤ 2 we get |α 1 (t)| ≤ (1e -1 ) -3/2 1e -t 2 (1 + t 2 ) t 3 ≤ 2 1e -t 2 (1 + t 2 ) t 3 .

It is enough to show that g(t) := (1e -t 2 (1 + t 2 ))/t 3 ≤ 1/2, ∀t ∈ (0, 1]. We have g (t) = t -4 (-3 + e -t 2 (3 + 3t 2 + 2t 4 )) hence sign(g (t)) = -sign(e t 2 -(1 + t 2 + 2 3 t 4 )). Thus there is a neighborhood of zero in which g is increasing, since sign(g (t)) = -sign(1 + t 2 + 1 2 t 4 + O(t 6 ) -(1 + t 2 + 2 3 t 4 )) = -sign(-1 6 t 4 + O(t 6 )) = +1 for t small enough. Since g is continuously differentiable, its supremum on (0, 1] is thus either equal to g(1) = 1 -2/e ≈ 0.264 < 1/2 or to g(t * ), for some local maximum 0 < t * ≤ 1 which must satisfy g (t * ) = 0. To conclude without further characterizing the existence or value of such a root, we establish that any such root must satisfy g(t * ) ≤ 1/2. Indeed using that g (t * ) = 0 if, and only if e t Proof. First, to prove (171) when ω 1 , . . . , ω m are i.i.d. samples from N (0, 1 s 2 I d ), it is enough to deal with the case s = 1. Next, for s = 1, denoting Ω ∈ R dm the concatenation of ω 1 , . . . , ω m ∈ R d , the vector Ω has independent standard normal random entries when ω 1 , . . . , ω m are i.i.d. samples from N (0, I d ), and for any 2 ≤ p < ∞ the function f p : R dm → R defined by f p (Ω) := ( m j=1 ω j p 2 ) 1/p is (as we will soon show) 1-Lipschitz with respect to the Euclidean norm in R dm . Therefore, we may use the Tsirelson-Ibragimov-Sudakov inequality [START_REF] Tsirelson | Norms of gaussian sample functions[END_REF], a.k.a. concentration of a random variable that writes as a Lipschitz function of a Gaussian vector [BLM13a, 59 Theorem 5.6], to obtain P(f p (Ω) -Ef p (Ω) ≥ t) ≤ exp(-t 2 /2), for each t ≥ 0, or equivalently ∀t ≥ 0, P f p (Ω) (for s = 1) as claimed. Now, observe that for t ≥ 0 we have t 3t -(t 2 -1) = (t 2 -1)(t -1) = (t -1) 2 (t + 1) ≥ 0 hence t 3 + 1 ≥ t 2 + t and t + t 2 + t 3 ≤ 1 + 2t 3 . Thus 3 i=1 ω j i 2 ≤ 1 + 2 ω j 3 2 , and we deduce (172) from (171). To complete the proof, we show that f p is 1-Lipschitz with respect to . 2 . Denoting v Ω := ( ω j 2 ) j∈[m] ∈ R m , observe that f p (Ω) = v Ω p . Thus, for Ω, Ω ∈ R dm , since p ≥ 2, we have

f p (Ω) -f p (Ω ) = v Ω p -v Ω p ≤ v Ω -v Ω p ≤ v Ω -v Ω 2 . Finally, v Ω -v Ω 2 2 = m j=1 ( ω j 2 -ω j 2 ) 2 ≤ m j=1 ω j -ω j 2 2 = Ω -Ω 2 2 .
A.9.6 Proof of Lemma 7

Denote c := 2(α + 2) and ϕ(t) := e -(c-α)t 2 /2+tte -ct 2 /2 . Since ϕ(0) = 1, it is enough to prove that ϕ is non-increasing on R + . Since ϕ is C 1 , we study the sign of ϕ (t) = -(cα)t + 1 + (ct 2 -1)e -αt 2 /2-t e -(c-α)t 2 /2+t which is the sign of ψ(t) := 1 -(cα)t + (ct 2 -1)e -αt 2 /2-t . To show that ψ(t) ≤ 0 for each t ∈ R + we study its sign on the intervals (0, 1 c-α ) and ( 1 c-α , +∞). As a preliminary we record that since α > 0, we have √ c/(cα) = 2(2 + α)/(α + 4) ≤ 1/2. (173)

  By analogy with the kernel coherence we define the coherence of a sketching operator: Definition 4 (Operator Coherence). For any sketching operator A and any set T ⊆ D 2 = µ(T|A) := sup (ι,ι )∈T |Re Aι, Aι |.

Theorem 1 (

 1 [GBKT21b, Theorem 5.11]). Let T := (Θ, ρ, I) be a location-based family with base distribution π 0 on R d , with Θ ⊆ R d a bounded subset, ρ(•, •) := •-• where • is some norm on R d . Consider a normalized shift-invariant kernel κ with an integer k ≥ 1 such that κ has its 2k-coherence with respect to the location-based family T bounded by 0 ≤ c ≤ 3/4

  )As we now show, the advantage behind this dissection is that the study of the quantities δ( D|A), µ(M 2 = |A), µ(M × D|A), µ( D2 = |A) boils down to the study of suprema of the absolute value of auxiliary functions defined as empirical means. We prove in Appendix A.6 the following result. Proposition 5. Consider κ a normalized shift-invariant kernel, T = (Θ, ρ, I) a location-based family with base distribution π 0 where ρ(•, •) = • -• for some norm

Figure 1 :

 1 Figure 1: (top) Histogram of ψ(ω) when ω ∼ N (0, s -2 I d ); (bottom) Empirical graph of P(ψ(ω)-Eψ(ω) ≥ ) and two candidate analytic bounds for s = 3 and d = 5 (left), d = 100 (right).

Figure 2 :

 2 Figure 2: The term m × V Ax k 2 (left) compared to the term m × V Aν k 2 (right).

Figure 3 :

 3 Figure 3: An illustration of the lower bound of Proposition 7 (left) for three choices of w (right):w 1 (ω) = 1, w 2 (ω) = (1 + ω ) -1 , w 3 (ω) = ( ω 4 + 1)( ω 6 + 1) -1 .

  ω j ). Since is a norm, this is a direct consequence of Proposition 9 and shows that δ(M|A) = |1 -Aι M 2 2 | independently of the choice of the monopole ι M . Now, consider an arbitrary normalized dipole ι ∈ D. If ι is either a normalized monopole or a balanced dipole, we trivially have |1-Aι 2 2 | ≤ max(δ(M|A), δ( D|A)). Otherwise, by Proposition 9 again, there exists α ∈ (0, 1) such that

  v)| = |φ ga-gcv,gb-gdv,e (u)| ≤ √ 3 max |ga -gcv|, |gb -gdv|, |gbgdvga + gcv| √ 1e . Now, we can use Lemma 5 again to get

10

  -x sin(xt)dx hence max(| sinc(t)|, | sinc (t)|) ≤ 1. Now, by definition of the dual norm • a, , for every ω, v ∈ R d we have | ω, v | ≤ ω a, v a . Thus, by definition (65) of C κ for every 0 < t ≤ R we have

  S a ) the unit ball (resp. unit sphere) with respect to . a , R d := sup x∈Θ d x a , and R mm := sup x∈Θmm x a . Observe that max(R d , R mm ) = sup x a = diam a (Θ) =: D.An upper bound of N d (τ ). Denote I := (0, R d ] ⊆ R. We will soon show thatN d (τ ) := N (Θ d , ∆ d , τ ) ≤ N (I, | • |, τ /2) × N S a , • a , τ 2(R d +1) . (147) By [GBKT21b, Lemma A.1], since S a ⊂ B a , we have N S a , • a , τ 2(R d +1) ≤ N B a , . a , τ 4(R d +1) . Moreover, by [Wai19, Lemma 5.7] the inequality N B a , . a , τ (4(R d +1) ≤ 1+8(R d +1)/τ d is valid for every τ > 0. Finally, since N (I, |•|, τ /2) ≤ 1+2R d /τ ≤ 1 + 8(R d + 1)/τ we obtain N d (τ ) ≤ 1 + 8(R d + 1)/τ d+1 ≤ 1 + 8(D + 1)/τ d+1 .We now establish (147). DenoteN 1 := N (I, | • |, τ /2), N 2 := N (S a , • a , τ /(2(R d + 1))),and consider (r i ) i∈[N1] a covering of I with respect to | • | at scale τ /2 and (s i ) i∈[N2] a covering of S a with respect to • a at scale τ /(2(R d + 1)). We show that the family (ri • s j ) (i,j)∈[N1]×[N2]is a covering of Θ d with respect to the metric ∆ d at scale τ . For this, consider an arbitrary x ∈ Θ d (recall the definition (59)) and define r := x a and n := x/r. By definition of R d and I we have r ∈ I, and n a ∈ S a , hence there arei ∈ [N 1 ], j ∈ [N 2 ] such that |rr i | ≤ τ /2 and ns j a ≤ τ /(2(R d + 1)). To reach the conclusion we show that ∆ d (x, r i s j ) ≤ τ . Indeed ∆ d (x, r i s j ) = ∆ d (rn, r i s j ) (68)

  )-(158) hold we have sup z∈Θ d |Ψ d (z|Ω) -1| ≤ τ 4 and max ∈{mm,md,dd} sup z∈Θ |Ψ (z|Ω)| ≤ µ + τ 8k .

Proof of Lemma 3 .

 3 Denote E := 2EY . If E = 0 then Y = X = 0 almost surely, hence X (and Y ) are both sub-exp(ν , β ) for any choice of ν , β ≥ 0 so the result is trivial. Assume now that E > 0. Since |X -EX| ≤ |X| + |EX| ≤ Y + EY almost surely, we get Ee

  2 )/4. Then, using the definition of B ψ we obtain that: for = m, X := 1 b b i=1 ψ(ω i ) satisfies |X| ≤ Y 0 ; for ∈ {d, mm, md} and z ∈ Θ , X := 1 b b i=1 ψ(ω i )f (z|ω i ) satisfies |X| ≤ Y p for an appropriate choice of x 0 , p ∈ {0, 1, 2}; for = dd and z ∈ Θ , X := 1 b b i=1

  First, observe that, in the setting of Gaussian (resp. Dirac) mixtures of Example 2 (resp. of Example 1), the kernel satisfies κ ≥ 0, and (63) holds with . a = . Σ (resp. with • a = • 2 ) and κ(r) = e -r 2 /σ 2 with σ := 2(2 + s 2 ) (resp. with σ := √ 2s). In both settings we have = • a / , and by the definition of Θ d (see (59), with • := • a / ), we have R := sup x∈Θ d x a ≤ . Thus, by Lemma 10, the constant C κ from (65) satisfies

  Checking the variant of Item 1 in Theorem 5 We show the existence of ν, β, B > 0 such that the random variables Z p defined in (90) are sub-exp(ν, β) with |E(Z p )| ≤ B. Since the frequencies ω 1 , . . . , ω m are i.i.d., we consider a block size b = 1 and Z p = ( √ C κ | ω, x |) p with ω ∼ Λ. We will indeed prove that for each x ∈ R d s.t. x a = 1, the random variables | √ C κ ω, x | p , p ∈ {0, 1, 2} are sub-exp(ν, β) with |EZ p | ≤ B, where B := max(1, C κ s -2 ), and ν = β = 4B.

  p∈{0,1,2} E| C κ ω, x | p ≤ max(1, C κ s -1 , C κ s -2 ) = B.By Lemma 8, s| ω, x | is sub-exp(4, 4) ands 2 ω, x 2 is sub-exp(2, 4), hence | √ C κ ω, x | is sub-exp(4 √ C κ /s, 4 √ C κ /s), and C κ ω, x 2 is sub-exp(2C κ /s 2 , 4C κ /s 2 ). Observe that max(4 √ C κ /s, 2C κ /s 2 ) ≤ 4B and max(4 √ C κ /s, 4C κ /s 2 ) ≤ 4B to conclude that | √ C κ ω, x | and C κ ω, x 2 are indeed both sub-exp(ν, b) with ν = b = 4B.The same holds for p = 0 since | √ C κ ω, x | 0 ≡ 1. NB: in the setting of Gaussian mixtures, for x ∈ R d such that x Σ = 1, ψ(ω) and ψ(ω)| ω, x | and ψ(ω) ω, x 2 are bounded and we may alternatively have used Hoeffding's inequality[START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] instead of Theorem 5. We chose to use the latter as it allows to encompass both settings under the same reasoning.

π

  Identifying M such that Item 2 holds for mixtures of Diracs withv = v k (τ ). Since ψ(ω) = 1 (cf (96)) we have Ψ 0 (Ω) = 1 m m j=1 f 0 (ω j ), with f 0 (ω) defined in (67). Since • a = • 2 we have • a, = • 2 hence f 0 (ω) = 3 t=1 ω t 2 . As ω ∼ N (0, s -2 I d ), Proposition 11 yields ∀t ≥ 0, P Ψ 0 (Ω) > M (t) ≤ exp -(mt) d 3/2 + t . We define C 0 := 7B ψ B(169)and recall that C 0 ≥ 7 since B ψ ≥ 1 and B ≥ 1. Therefore, for 0 < τ ≤ 1, and v k (τ ) as defined in (99), we haveP Ψ 0 (Ω) > M (τ 3/2 m 1/2 ) ≤ exp -mτ 2 ≤ 2 exp(-m/v k (τ )),since 2/τ ≤ 2/τ 2 ≤ 2(C 0 /τ ) 2 ≤ v k (τ ).

  . Hence, B 2 ψ ν 2 ≤ (7B ψ B) 2 = C 2 0 and B ψ β = 4B ψ B = 4 7 C 0 where C 0 is defined in (169). Since the block size is b = 1, by (89) we obtain v = 256k 2 b(2B 2 ψ ν 2 + B ψ βτ ) τ 2 ≤ 512k 2 (C 0 /τ )

  2) 2 = 0.4 < 1/2. Proposition 11. Consider s > 0, and let ω 1 , . . . , ω m be i.i.d. samples from N (0, 1 s 2 I d ). Then ∀τ ≥ 0, 3/2 8/π + τ ≤ exp -3/2 8/π + τ ≤ exp -

  τ /4)N (Θ mm , ∆ mm , τ /4). (148) Indeed, with (x i ) i∈[N d (τ /4)] a covering of Θ d with respect to ∆ d at scale τ /4 and (y j ) j∈[Nmm(τ /4)] a covering of Θ mm with respect to ∆ mm at scale τ /4 it is straightforward to show using (70) that (x i , y j ) (i,j)∈[N d (τ /4)]×[Nmm(τ /4)] covers Θ d × Θ mm with respect to ∆ md at scale τ /2. Combined with the above estimates we get An upper bound of N dd (τ ) By (62), we have Θ dd ⊂ Θ d × Θ d × Θ mm , thus a similar argument yields

	N md (τ ) ≤ N d (τ /4)N mm (τ /4) ≤ 1 + 32(D + 1)/τ	d+1 1 + 16D/τ	d .

)

  • if = dd by the second claim of Lemma 2 we similarly get the existence ofx t ∈ R d satisfying x t a = 1, t = 1, 2, such that |X| ≤ Z with Z := (Z 1,2 + Z 2,2 )/4. By Lemma 9, Z 1,2 + Z 2,2 is sub-exp(2ν, 2β), and |E(Z 1,2 + Z 2,2 )| ≤ 2B, hence Z := (Z 1,2 + Z 2,2 )/4 is also sub-exp(ν, β) with |E(Z )| ≤ B.By Lemma 3 we also get that X is sub-exp(ν , β) with ν as in (165).

	Now, consider = m. Similarly, to prove that Ψ m

  Σ -1 ) ≤ 4B ψ since ϕ(t) := (t + t 3 )e -t 2 /2 satisfies ϕ(t) ≤ 8/3 for t ∈ R. Indeed, we have

	3 Σ -1 )
	≤ B ψ ϕ( ω sup 3 2 t∈R t∈R t∈R ϕ(t) ≤ sup ϕ 1 (t) + sup ϕ 2 (t),

  Ef p (Ω) + τ p ≤ expt 2 /2 .By convexity we have(a + b) p = 2 p (a/2 + b/2) p ≤ 2 p-1 (a p + b p ) for every a, b ∈ R + , hence ∀t ≥ 0, P f p (Ω) p ≥ 2 p-1 Ef p (Ω) p + t p ≤ expt 2 /2 .We now show that Ef p (Ω) p ≤ md p/2 E|g| p . The convexity of t → t p/2 (p ≥ 2) onR + yields | p = d p/2 E|g| pwhere ω ∼ N (0, I d ), g ∼ N (0, 1). B convexity of t → t p and Jensen's inequality, it follows that Ef p (Ω)

	E ω p 2 = d p/2 E	1 d	d i=1	ω 2 i	p/2	≤ d p/2 E	1 d	d i=1	|ω i

p ≥ p ≤ E f p (Ω) p = m j=1 E ω j p 2 = mE ω p 2 ≤ md p/2 E|g| p .

As a result

∀t ≥ 0, P( f p (Ω) p ≥ 2 p-1 (md p/2 E|g| p + t p )) ≤ exp(-t 2 /2), or equivalently P 1 m m j=1 ω j p ≥ 2 p-1 d p/2 E|g| p +τ ≤ exp(-(mτ ) 2/p /2) for each τ ≥ 0. Since E|g| 3 = 8/π [FEHP11,

Chapter 11], considering p = 3 yields (171)

Integrability is treated informally in this introduction and will be more formally discussed in Section

2.1.2 In the rest of this paper when we write kernel we implicitly assume a positive definite kernel.

Note that M(X ) equipped with . κ is not necessarily a Hilbert space, since M(X ) is not necessarily complete with respect to . κ. See [SZ21, Theorem 3.1] for details.

See before Eq. (109) in the proof of Theorem

5.11 in [GBKT21b, Section B.1]

If the sup in (43) is not only finite but at most polynomial in k, d then log M/τ is also logarithmic in k, d.

See e.g. [BLM13a, Section 2.2] and the proof of Theorem 2.8.1. in[START_REF] Vershynin | High-dimensional probability: An introduction with applications in data science[END_REF].

See [GBKT21b, Section 6.3.1].

See again [GBKT21b, Section 6.3.1].

ConclusionIn this work we revisited the theoretical analysis of the Restricted Isometry Property for sketching operators proposed in[START_REF] Gribonval | Compressive statistical learning with random feature moments[END_REF][START_REF] Gribonval | Statistical learning guarantees for compressive clustering and compressive mixture modeling[END_REF]. This property is

See Definition 2.

A.7.1 Construction of z t , 1 ≤ t ≤ T First we focus on the construction of z 1 , . . . , z T satifying the inequality (131):

• When = d, we have z = x and z = x where x, x ∈ Θ d (cf (59)). Observe that r := x a , r := x a satisfy r, r > 0, and that n := x/r, n := x /r satisfy n a = n a = 1. We set z 1 = x, z 2 = x, z 3 = x where x := x a • (x/ x a ) satisfies x a = x a . Given the definition (68) we have ∆ (z 1 , z 2 ) = |rr | = | x ax a | ≤ ∆ (x, x ) = ∆ (z, z ) and similarly ∆ (z 2 , z 3 ) = nn a ≤ ∆ (z, z ) as claimed.

• When = mm, z = y, z = y , where y, y ∈ Θ mm and we simply set z 1 = z, z 2 = z .

• When = md, z = (x, y) and z = (x , y ) where x, x ∈ Θ d , y, y ∈ Θ mm . Setting x as above we define z 1 = z = (x, y), z 2 = (x, y ), z 3 = (x, y ) and z 4 = (x , y ). It is not difficult to check that the inequality (131) holds given the definition (70) of ∆ md .

• Finally, when = dd, z = (x 1 , x 2 , y) and z = (x 1 , x 2 , y ) where

To complete the proof of Theorem 3 we now exhibit f ,t satisfying (132)-( 133) by treating each case = d, = mm, = md, = dd and pair (z t , z t+1 ). First we build the functions and show that they satisfy (132). Then observing their common structure we establish the bound (133).

A.7.2 Construction of f ,t satisfying (132)

The case = d. For u ∈ (0, 1), we define r(u) := r + u(rr) and n(u) := n + u(nn), which satisfies n(u) a = (1u)n + un a ≤ (1u) n a + u n a = 1, and we set

Property (132) follows from ( 53) and (63) since

The case = mm. For u ∈ (0, 1), we define ȳ(u) := y + u(yy) and

Property (132) follows by (54) since z 1 = y = ȳ(0) and z 2 = y = ȳ(1).

This matches the expressions of v k (τ ) used in (94) and (99). Soon we will also prove that C 0 satisfies the bounds expressed in (94) and (99).

As for C, observe that by definition (88

, so that we only need to give an upper bound of 6144M C κ to get the expressions that appear in (95) and (100).

To conclude we bound C 0 and 6144M C κ . First, by (166), we have

2 ), and by (167) B = max(1, C κ s -2 ). We study separately the two settings:

• For mixtures of Gaussians, by (92) we have ≥ max(s, 1) hence

, we get by (169

• For mixtures of Diracs, by (97

2 ) as claimed in (99). Finally observe that c := 8/π ≈ 1.6 so that cd 3/2 + t ≥ 1 for every t > 0 hence

2 )(2d 3/2 + √ mτ 3/2 ) as claimed in (100).

A.9.5 Some helpful results

Lemma 10. Consider σ > 0 and for r ≥ 0 define α σ (r

3 max(σ, R), and sup

Proof. First we show that α σ (r) = σα 1 (r/σ) ≤ (1e -1 ) -1/2 max(σ, r) when r ≥ 0. This implies the first bound as (1e -1 ) -1/2 ≈ 1.26 ≤ 1.316 ≈ 4 √ 3. When σ ≤ r we have

≤ (1e -1 ) -1/2 r = (1e -1 ) -1/2 max(σ, r).

When 0 ≤ r ≤ σ, we prove below that |α 1 (t)| ≤ (1e -1 ) -1/2 for every t ∈ [0, 1], so that |α σ (r)| = σ|α 1 (r/σ)| ≤ (1e -1 ) -1/2 σ = (1e -1 ) -1/2 max(σ, r).

To show that |α 1 (t)| ≤ (1e -1 ) -1/2 on [0, 1] observe that since u → e -u is convex, it has non-decreasing slopes so that (e

Since t ∈ (0, 1/(cα)), using (173) we have

Denoting h(u) := (1 + √ cu)e -αu 2 /2-u , it is enough to prove that h(t) ≥ 1 = h(1), which will follow if we establish that h (u) = √ c(1-u-αu 2 )-(αu+1) e -αu 2 /2-u ≥ 0 on (0, 1/(c-α)), or equivalently that the quadratic function

takes non-negative values at u = 0 and at u = 1/(cα). Indeed, its evaluation at u = 0 yields √ c-1 = 2(2 + α)-1 > 0, while its evaluation on 1/(c-α) = 1/(α+4) is lower bounded by 8/(α + 4) 2 > 0.

Case of t ∈ ( 1 c-α , +∞). Since 1 -(cα)t < 0, we get that ψ(t) ≤ 0 as soon as

Since t > 1/(cα), we have (cα)t > 1, and using (173) we get

Denoting g(u) := ue -αu 2 /2-u , it is thus enough to show that √ cg(t) ≤ 1 to conclude.

Since g (u) = -(-1 + u + αu 2 )e -αu 2 /2-u , the unique u ≥ 0 such that g (u) = 0 is u α := 2/( √ 4α + 1 + 1), which satisfies αu 2 α + u α -1 = 0, and the maximum of g(u) on R + is at u = u α . As a result

To conclude, we show that the r.h.s. is bounded by one, by distinguishing two cases. On the one hand, if α ≥ 2, we have 2 2(2 + α)/( √ 4α + 1 + 1) ≤ √ 2, and since u α ≥ 0 the r.h.s. of (178) is upper bounded by e -1/2 √ 2 ≤ 1. On the other hand, if α ≤ 2, we have u α /2 ≥ 1/4 and 2 2(2 + α)/( √ 4α + 1 + 1) ≤ 2 (the latter inequality holds for any α ≥ 0), so that the r.h.s. of (178) is upper bounded by 2e -3/4 ≤ 1. In both cases, we get as claimed that √ cg α (t) ≤ 1.