arXiv CSopen access

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

Separation Capacity of Scattering Networks on Low-Dimensional Datasets Konstantin Häberle ETH Zurich [email protected]

Helmut Bölcskei ETH Zurich [email protected]

arXiv:2607.06048v1 [stat.ML] 7 Jul 2026

Abstract We aim to identify scattering network architectures that maximize the separation capacity on data with low intrinsic dimension. The networks we consider employ a fixed monomial nonlinearity and no pooling, so that the only design variable is the frame generated by the network filters. For data modeled as rectifiable sets, we first characterize and bound the separation capacity of general feature extractors in terms of the geometry of the dataset. We then particularize to scattering networks and obtain two design criteria: (i) the filters should meet the data on sufficiently many frequencies, and (ii) the matrices coupling the frame to the geometry of the data should be well-conditioned. Keywords: Learning theory, pattern classification, feature extraction, scattering networks, convolutional neural networks, geometric measure theory.

1

Introduction

A common intuition for the success of deep learning models in classification and regression tasks is that real-world data, although embedded in high-dimensional spaces, often exhibit an intrinsic low-dimensional structure [1, 2]. In this paper, we model this intrinsic low-dimensional structure using the framework of geometric measure theory [3, 4]. Specifically, we assume that data lie on a rectifiable set, i.e., a set that, up to Hausdorff measure zero, is covered by a countable union of Lipschitz images of subsets of a Euclidean space. This class contains not only smooth submanifolds but also countable unions thereof, such as the unions of linear subspaces that constitute sparse-signal models. This paper studies the classification capabilities of scattering networks [5, 6, 7] on rectifiable sets, as measured by Cover’s separation capacity [8, 9]. Scattering networks are multilayered, neural-network-type architectures in which each layer computes convolutions with frame-generating filters [10], followed by pointwise nonlinearities and, in general, pooling operators. We particularize to the pooling-free case with a fixed monomial nonlinearity, so that the design freedom lies entirely in the choice of the frame. The central question addressed in this paper is how the geometry of the data should enter this choice. Our aim is to characterize the filters that maximize the separation capacity for a given rectifiable dataset. Two main contributions are reported. First, we relate the separation capacity of general feature extractors to the geometry of the underlying rectifiable set. Notably, the separation capacity is bounded below by the rank of the differential on the approximate tangent spaces and bounded above by the rank of a second-moment matrix, which couples the feature extractor to the global geometry of the dataset. Second, by applying these bounds to scattering networks, we establish filter-design criteria. The upper bounds prescribe that the spectral supports of the filters, intersected with the spectrum of the dataset, should not be contained in a coset of a proper subgroup. The lower bounds, in turn, suggest choosing the filters so that, for each Lipschitz parametrization of the underlying rectifiable set, an associated filter-dependent matrix

2

K. Häberle and H. Bölcskei

is as well-conditioned as possible. For sparse signals, the criterion reduces to minimizing the restricted isometry constant of a single matrix. The paper is organized as follows. Section 2 develops the connection between the separation capacity of general feature extractors on rectifiable sets and the geometry of those sets. In Section 3, we apply these results to scattering networks to establish filter-design criteria, first for sparse signals and then for more general rectifiable sets. Appendix A reviews the restricted isometry property used in the sparse-signal lower bound. Notation. We write µ⌞A for the restriction of a measure µ on a set X to a measurable subset A. For a measurable map φ : X → Y , the pushforward of µ by φ is the measure φ♯ µ on Y given by (φ♯ µ)(B) = µ(φ−1 (B)) for measurable B ⊆ Y . When X is a topological space, the support of µ is supp(µ) = {x ∈ X : µ(U ) > 0 for every open neighborhood U of x}. We write Ln for the n-dimensional Lebesgue measure on Rn (n ∈ N) and Hs for the s-dimensional Hausdorff measure (s ≥ 0). Finally, for K ∈ {R, C} and A ⊆ Kn , we write spanK (A) for the set of finite linear combinations of vectors in A with scalars in K, and dimK (V ) for the dimension of a linear space V over K.

2

Separation capacity computations on rectifiable sets

This section develops the capacity estimates used later for scattering networks. The first step is a subspace characterization of the separation capacity. The subsequent estimates relate that characterization to rectifiability, approximate tangent spaces, and second moments of the pushforward of Hs by the feature extractor. We begin by introducing the notion of s-separation capacity. Definition 2.1 (s-separation capacity, [9]). Let E ⊆ RM be Hs -measurable with Hs (E) > 0 for ′ some s ≥ 0, and let Φ : E → RM . Denote by SC s (Φ) the largest N ∈ N such that for (Hs )N -a.e. N -tuple F := (f1 , . . . , fN ) ∈ E N at least 50% of all possible dichotomies of F are Φ-separable. If there is no such N ∈ N, set SC s (Φ) := 0. We call SC s (Φ) the s-separation capacity of Φ. If s = M , we write SC(Φ) := SC M (Φ) and call SC(Φ) the separation capacity of Φ. The next lemma recasts the s-separation capacity as a minimization over linear subspaces that carry positive pushforward measure. ′

Lemma 2.2. Let Φ : E → RM be measurable. We have n o ′ SC s (Φ) = 2 · min dimR (V ) : V ⊆ RM linear subspace, (Φ♯ (Hs ⌞E))(V ) > 0 .

(2.1)

Proof. As shown in [9], it holds that SC s (Φ) = 2 min dimR (spanR (Φ(A))) . A⊆E

(2.2)

Hs (A)>0

To establish the claim of this lemma, we first prove that (2.1) holds with “≥”. To this end, let U = spanR (Φ(A)), where A ⊆ E with Hs (A) > 0 is such that SC s (Φ) = 2 · dimR (U ). We then have (Φ−1 (U ) ∩ E) ⊇ A, which implies (Φ♯ (Hs ⌞E))(U ) > 0, and the inequality “≥” follows. ′ Turning to the reverse inequality, i.e., “≤”, let V ⊆ RM be a linear subspace with Hs (Φ−1 (V ) ∩ E) > 0 such that 2 · dimR (V ) equals the right-hand side (RHS) of (2.1). Setting A′ := Φ−1 (V ) ∩ E, we have spanR (Φ(A′ )) ⊆ V , as V is a linear subspace. Consequently, as Hs (A′ ) > 0, (2.2) yields SC s (Φ) ≤ 2 · dimR (spanR (Φ(A′ ))) ≤ 2 · dimR (V ). But 2 · dimR (V ) equals the RHS of (2.1). This establishes the inequality “≤”, and the proof is complete.

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

3

Lemma 2.2 links the s-separation capacity to the lower Hausdorff dimension of a measure. ′ Writing dimH (B) for the Hausdorff dimension of a set B ⊆ RM , the lower Hausdorff dimension ′ of a measure µ on RM is defined to be n o ′ dimH (µ) = inf dimH (B) : B ⊆ RM measurable, µ(B) > 0 . Lemma 2.3 (s-separation capacity and lower Hausdorff dimension). For every measurable ′ Φ : E → RM , it holds that SC s (Φ) ≥ 2 · dimH (Φ♯ (Hs ⌞E)) . Proof. The claim follows immediately by relaxing the minimization in (2.1) from linear subspaces ′ ′ V ⊆ RM to arbitrary measurable subsets B ⊆ RM , upon noting that for every linear subspace V , one has dimH (V ) = dimR (V ). Next, we will leverage Lemma 2.2 to express the s-separation capacity in terms of the geometry of the input set E, when E is rectifiable. Recall the notion of a rectifiable set. Definition 2.4 (Countably Hs -rectifiable set, [3, 4, 11]). An Hs -measurable set E ⊆ RM is said to be countably Hs -rectifiable if there is a countable family of Lipschitz maps {ψk : Rs → RM }k∈N such that ! [ Hs E \ ψk (Rs ) = 0. k∈N

Lemma 2.5 (Bi-Lipschitz parametrization, [3, 4]). Let E ⊆ RM be countably Hs -rectifiable, and let t > 1. Then there exist finitely or countably many compact sets Kj ⊂ Rs and t-bi-Lipschitz maps ψj : Kj → ψj (Kj ) ⊆ E, indexed by J , such that {ψj (Kj )}j∈J are pairwise disjoint and  H s E \

 [

ψj (Kj ) = 0.

j∈J

Rectifiable sets admit linear approximation properties, formalized through the notion of approximate tangent spaces. For f ∈ RM and λ > 0, let ηf,λ : RM → RM , h 7→ (h − f )/λ. We use Cc (RM ) to denote the space of continuous, compactly supported functions on RM . Definition 2.6 (Approximate tangent space, [11]). Suppose that E ⊆ RM is Hs -measurable with Hs (E) < ∞, and let f ∈ RM . We call an s-dimensional linear subspace L ⊆ RM the approximate tangent space of E at f if Z Z lim ϕ dHs = ϕ dHs , for all ϕ ∈ Cc (RM ). λ→0+

ηf,λ (E)

L

We shall write Tf E := L. If E ⊆ RM is countably Hs -rectifiable, then the approximate tangent space Tf E exists for f ∈ E [3, 11]. This allows us to differentiate Lipschitz maps on E. For a Lipschitz ′ ′ map Φ : E → RM and a Lipschitz extension Φ : RM → RM of Φ, we write dΦf := dΦf for the ′ differential of Φ at f . By [12, Theorem 11.4], the restriction dΦf |Tf E : Tf E → RM exists for Hs -a.e. f ∈ E and, by [12, Lemma 11.5], it is independent of the choice of the extension Φ. With this notion at hand, we establish a connection between the separation capacity and the tangential geometry of E. Hs -a.e.

4

K. Häberle and H. Bölcskei

Lemma 2.7 (s-separation capacity and approximate tangent spaces). Let E be countably Hs ′ rectifiable with Hs (E) < ∞ and Φ : E → RM be Lipschitz. Then,   SC s (Φ) ≥ 2 · ess inf f ∈E rank dΦf T E . (2.3) f

′

Proof. To establish the claim, it suffices to show that for every linear subspace V ⊆ RM ,    
Hs (Φ−1 (V ) ∩ E) > 0 =⇒ ess inf f ∈E rank dΦf T E ≤ dimR (V ) . f

M′

Fix a linear subspace V ⊆ R with Hs (Φ−1 (V ) ∩ E) > 0 and set A := Φ−1 (V ) ∩ E. By the locality of approximate tangent spaces [12, Proposition 10.5], Tf A = Tf E for Hs -a.e. f ∈ A. Since Φ A : A → V , we thus have, for Hs -a.e. f ∈ A, dΦf (Tf E) = dΦf (Tf A) ⊆ TΦ(f ) V = V. But then dimR (dΦf (Tf E)) ≤ dimR (V ), for Hs -a.e. f ∈ A, and consequently, it holds that ess inf f ∈E dimR (dΦf (Tf E)) ≤ dimR (V ) . Upon noting that rank(dΦf |Tf E ) = dimR (dΦf (Tf E)), this completes the proof. Remark 2.8. The inequality in (2.3) is tight. Indeed, if Φ is linear and E an s-dimensional linear subspace of RM , then (2.3) holds with equality, see [9]. The subspace characterization of the s-separation capacity presented in Lemma 2.2 also gives an upper bound in terms of a second-moment matrix. R ′ Lemma 2.9 (Upper bound). Let Φ : E → RM be measurable such that E ∥Φ(f )∥2 dHs (f ) < ∞. Then, Z  s T s SC (Φ) ≤ 2 · rank yy dΦ♯ (H ⌞E) . (2.4) RM ′

R Proof. First note that the RHS of (2.4) is well-defined as RM ′ yy T dΦ♯ (Hs ⌞E) = R T s ′ E Φ(f )Φ(f ) dH (f ) and by the Cauchy–Schwarz inequality, we have, for k, ℓ ∈ {1, . . . , M }, Z 1/2 Z 1/2 Z s 2 s 2 s |(Φ(f ))k (Φ(f ))ℓ | dH (f ) ≤ |(Φ(f ))k | dH (f ) |(Φ(f ))ℓ | dH (f ) E E Z E ≤ ∥Φ(f )∥2 dHs (f ) < ∞. E

We write CΦ :=

R

RM ′ yy

T dΦ (Hs ⌞E) and note that for every w ∈ ker(C ), Φ ♯

Z

T

0 = w CΦ w =

′ RM

(⟨y, w⟩)2 dΦ♯ (Hs ⌞E) ,

which implies ⟨y, w⟩ = 0,

′

for Φ♯ (Hs ⌞E)-a.e. y ∈ RM .

(2.5)

Let V = (ker(CΦ ))⊥ . To establish the claim, it suffices to show that supp(Φ♯ (Hs ⌞E)) ⊆ V.

(2.6) ′

Indeed, (2.6) implies that (Φ♯ (Hs ⌞E))(V ) > 0, as (Φ♯ (Hs ⌞E))(RM ) = Hs (E) > 0, and thus SC s (Φ) ≤ 2 · dimR (V ) = 2 · rank(CΦ ). To see that (2.6) holds, let y0 ∈ supp(Φ♯ (Hs ⌞E)), and suppose for the sake of contradiction that y0 ∈ / V , i.e., ⟨y0 , w⟩ ̸= 0 for some w ∈ ker(CΦ ). But then there is an open neighborhood Ny0 containing y0 such that ⟨y, w⟩ ̸= 0,

for all y ∈ Ny0 .

As y0 ∈ supp(Φ♯ (Hs ⌞E)), we have (Φ♯ (Hs ⌞E))(Ny0 ) > 0. This is in contradiction to (2.5), thereby completing the proof.

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

5

Application of the area formula [3] to the RHS of (2.4) yields Z  SC s (Φ) ≤ 2 · rank yy T dΦ♯ (Hs ⌞E) M′ ZR  T s = 2 · rank Φ(f )Φ(f ) dH (f ) E   XZ = 2 · rank Φ(ψj (x))Φ(ψj (x))T J(d(ψj )x ) dx , j∈J

Kj

where J(d(ψj )x ) denotes the Jacobian of the linear map d(ψj )x . Corollary 2.9.1. Let E ⊆ RM be countably Hs -rectifiable with bi-Lipschitz parametrization ′ {ψj : Kj → ψj (Kj )}j∈J , and let Φ : E → RM . If, for each j ∈ J , the map Φ ◦ ψj admits a real-analytic extension to a connected open neighborhood of Kj , then ! Z SC s (Φ) = 2 min rank Φ(ψj (x))Φ(ψj (x))T J(d(ψj )x ) dx . (2.7) j∈J

Kj

Proof. Since Φ ◦ ψj is in particular continuous and Kj is compact, each integral in (2.7) is finite. As established in [9], SC s (Φ) = minj∈J SC s (Φ|ψj (Kj ) ). Application of Lemma 2.9 to Φ|ψj (Kj ) yields   SC

s



Φ ψ (K ) j



j

 Z   T s  ≤ 2 · rank  M ′ yy dΦ♯ (H ⌞ψj (Kj )) . | R {z }

(2.8)

=:CΦj

To show that (2.8) holds with equality, suppose for the sake of contradiction that there is a ′ linear subspace U ⊆ RM with dimR (U ) < rank(CΦj ) and (Φ♯ (Hs ⌞ψj (Kj )))(U ) > 0. Further, let V = (ker(CΦj ))⊥ , so that dimR (V ) = rank(CΦj ) and (Φ♯ (Hs ⌞ψj (Kj )))(V ) > 0, as argued in the proof of Lemma 2.9. Since dimR (U ⊥ ) > M ′ − rank(CΦj ) and dimR (V ) = rank(CΦj ),       dimR U ⊥ ∩ V = dimR U ⊥ + dimR (V ) − dimR U ⊥ + V   > M ′ − rank(CΦj ) + rank(CΦj ) − dimR U ⊥ + V   = M ′ − dimR U ⊥ + V ≥ 0. We next note that Φ(ψj (Kj ))⊥ ⊆ ker(CΦj ) = V ⊥ , so that V ⊆ spanR (Φ(ψj (Kj ))). One can thus choose v ∈ V ∩ U ⊥ such that v ̸= 0 and such that there is an xv ∈ Kj satisfying ⟨Φ(ψj (xv )), v⟩ ̸= 0. Setting φ(x) := ⟨(Φ ◦ ψj )(x), v⟩, x ∈ Kj , then, by assumption, φ extends real-analytically to a connected open neighborhood Ωj of Kj . Moreover, φ is not identically zero, as φ(xv ) ̸= 0. However, by construction, φ(x) = 0, for all x ∈ (Φ◦ψj )−1 (U ). This establishes the contradiction, as a nontrivial real-analytic function on the connected open set Ωj cannot vanish [13] on a set of measure


Ls (Φ ◦ ψj )−1 (U ) ≥ Hs ψj (Φ ◦ ψj )−1 (U ) (Lip(ψj ))−s
= Hs Φ−1 (U ) ∩ ψj (Kj ) = (Φ♯ (Hs ⌞ψj (Kj ))) (U ) > 0. Therefore, (2.8) holds with equality. Application of the area formula yields the desired expression, and the proof is complete.

6

K. Häberle and H. Bölcskei

Corollary 2.9.2. Under the hypotheses of Corollary 2.9.1, R 2 2 Kj ∥Φ(ψj (x))∥2 J(d(ψj )x ) dx . SC s (Φ) ≥ inf R R 2 j∈J Kj Kj |⟨Φ(ψj (x)), Φ(ψj (y))⟩| J(d(ψj )x )J(d(ψj )y ) dxdy R Proof. The matrix CΦj := Kj Φ(ψj (x))Φ(ψj (x))T J(d(ψj )x ) dx is symmetric, so that rj :=
rj rank CΦj is given by the number of nonzero eigenvalues of CΦj . Denoting by {λk }k=1 the nonzero eigenvalues of CΦj , we have

Tr CΦj =

rj X

λk

and

rj   X 2 Tr CΦj = λ2k .

k=1

k=1

Application of the Cauchy–Schwarz inequality yields !2 rj rj   X X
2 Tr CΦj = λk ≤ rj λ2k = rj Tr CΦ2 j , k=1

k=1

so that rank CΦj

2 Tr CΦj . ≥  Tr CΦ2 j

Computing Z   Tr Φ(ψj (x))Φ(ψj (x))T J(d(ψj )x ) dx =

Z

Tr CΦj =

∥Φ(ψj (x))∥2 J(d(ψj )x ) dx

Kj

Kj

and Z   2 Tr CΦj = Tr

Kj

Z

Z

= Kj

!

Z

Φ(ψj (x))Φ(ψj (x))T Φ(ψj (y))Φ(ψj (y))T J(d(ψj )x )J(d(ψj )y ) dxdy

Kj

|⟨Φ(ψj (x)), Φ(ψj (y))⟩|2 J(d(ψj )x )J(d(ψj )y ) dxdy

Kj

gives the desired bound upon application of Corollary 2.9.1.

3 3.1

Application: Separation capacity of scattering networks Scattering network theory

We now instantiate the preceding capacity bounds for finite-dimensional scattering networks. Input signals are functions f : Z/M Z → C. Scattering networks à la Wiatowski and Bölcskei [6] are built from sequences of the form {(Ψn , ρn , Pn )}n∈N , where the nth network layer, n ∈ N, is determined by the triplet (Ψn , ρn , Pn ) consisting of (i) a frame Ψn generated by a countable set of functions {χn } ∪ {gλn }λn ∈Λn ⊆ CZ/M Z such that X An ∥f ∥2 ≤ ∥f ∗ χn ∥2 + ∥f ∗ gλn ∥2 ≤ Bn ∥f ∥2 , for all f ∈ CZ/M Z , (3.1) λn ∈Λn

with constants 0 < An ≤ Bn < ∞, (ii) a pointwise nonlinearity ρn : C → C, and (iii) a pooling operator Pn : CZ/M Z → CZ/M Z . The operation in the node λn ∈ Λn in the nth network layer is set to be U [λn ] : f 7→ Pn (ρn (f ∗ gλn )),

f ∈ CZ/M Z ,

(3.2)

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

7

where (ρn (f ∗ gλn )) (k) := ρn ((f ∗ gλn )(k)), k ∈ Z/M Z. Extending (3.2) according to U [(λ1 , . . . , λn )]f = U [λn ] · · · U [λ1 ]f,

f ∈ CZ/M Z ,

for (λ1 , . . . , λn ) ∈ Λ1 × · · · × Λn =: Λn1 , and setting Λ01 := {e} as well as U [e]f := f , for all f ∈ CZ/M Z , the scattering network of depth nd ∈ N is given by Φ: C

Z/M Z



→ C

Z/M Z

d Λn Snn=0 1

,

f 7→

nd [

Φn (f ).

n=0

Here, Φn (f ) := {(U [q]f ) ∗ χn+1 }q∈Λn1 denotes the output of the nth network layer. Computing the separation capacity of scattering networks. To analyze the separation capacity, we shall identify Z/M Z with {0, . . . , M − 1} equipped with addition modulo M , and employ the usual chain of identifications CZ/M Z ≃ CM ≃ R2M , so that we are in the setting of the previous section. To see what these identifications mean in the context of binary classification ′ ′ based on the feature extractor Φ : E ⊆ CM → CM , we note that for f ∈ E and w ∈ CM ,     ℜ(Φ(f )) ℜ(w) ℜ(⟨Φ(f ), w⟩) = ⟨ℜ(Φ(f )), ℜ(w)⟩ + ⟨ℑ(Φ(f )), ℑ(w)⟩ = , . (3.3) ℑ(Φ(f )) ℑ(w) This motivates the following notion of Φ-separability for complex-valued maps Φ : E ⊆ CM → ′ ′ CM . A dichotomy {F+ , F− } of an N -point set F ⊆ E is Φ-separable if there is a w ∈ CM such that1 ℜ(⟨Φ(f ), w⟩) > 0,

if f ∈ F+ ,

ℜ(⟨Φ(f ), w⟩) < 0,

if f ∈ F− .

Furthermore, we define the s-separation capacity of Φ as the s-separation capacity of the map    ′ ℜ(Φ(f ′ + if ′′ )) f 2M 2M ′ e e , Φ: E ⊆ R →R , ′′ 7→ ℑ(Φ(f ′ + if ′′ )) f e := ι(E) and ι : CM → R2M , f 7→ (ℜ(f )T , ℑ(f )T )T , denotes the decomplexification map. where E e We shall write SC s (Φ) := SC s (Φ). We henceforth restrict ourselves to networks built from {(Ψ, ρ, Id)}n∈N , where Ψ is the frame generated by some functions {χ} ∪ {gλ }λ∈Λ ⊆ CZ/M Z in the sense of (3.1), and ρ(z) = z d , z ∈ C, is a fixed monomial. In this setting, Λn1 = Λn , the n-fold Cartesian product of Λ, and Λ01 = Λ0 := {e}. Given the input dataset E ⊆ CM ≃ CZ/M Z and the parameter s ≥ 0, the design problem is to choose the frame Ψ so as to maximize SC s (Φ). We treat two model geometries: sparse signals and polynomially parametrized rectifiable sets. 3.2

Sparse signals

We first take E to be a sparse-signal model. Let Ξ = {ξk }k∈K be a frame for CM , and suppose that every subset of cardinality s of Ξ is linearly independent, so that for each S ⊆ K with |S| = S s, ES := spanC ({ξk }k∈S ) is of dimension s. The set of s-sparse signals is given as e = ι(E) ⊂ R2M , this model E := S⊆K,|S|=s ES . After decomplexification according to E becomes a union of 2s-dimensional R-linear subspaces:     ! [ ℜ(ξ ) −ℑ(ξ ) k k e= E spanR , . (3.4) ℑ(ξk ) ℜ(ξk ) k∈S S⊆K,|S|=s

1

Equivalently, one may consider the sign of ℑ(⟨Φ(f ), w⟩).

8

K. Häberle and H. Bölcskei

Indeed, if {c′k , c′′k }k∈S ⊂ R satisfy   X  ℜ(ξk ) ′′ −ℑ(ξk ) ′ = 0, + ck ck ℜ(ξk ) ℑ(ξk )

k∈S

then X

(c′k + ic′′k )ξk = 0.

k∈S

The C-linear independence of {ξk }k∈S yields c′k = c′′k = 0, for all k ∈ S, and hence the set 

   ℜ(ξk ) −ℑ(ξk ) , ℑ(ξk ) ℜ(ξk ) k∈S

is linearly independent.

(3.5)

In particular, the set of s-sparse signals in CM is countably H2s -rectifiable. Upper bound on SC 2s (Φ). terms of complex spans.

The upper bound starts from an exact expression for SC 2s (Φ) in ′

Proposition 3.1. Let Φ : E → CM be real-analytic. Then, n  o
T φT , φT : φ ∈ Φ(ES ) SC 2s (Φ) = 2 min dimC spanC . S⊆K |S|=s

Proof. Thanks to (3.5), we can employ [9] to get     e = min SC Φ e ◦σ SC 2s (Φ) = SC 2s Φ eS , S⊆K |S|=s

(3.6)

where σ eS : R2s → R2M ,

    ′ s   X c ′′ −ℑ(ξkS,j ) ′ ℜ(ξkS,j ) → 7 c + c j j ℜ(ξkS,j ) ℑ(ξkS,j ) c′′ j=1

e ◦σ with the labeling S = {kS,j }sj=1 . Further, as Φ eS is real-analytic, we have, by [9],      e ◦σ e ◦σ SC Φ eS = 2 · dimR spanR (Φ eS )(R2s ) . Let σS : Cs → CM , c 7→



Ps

j=1 cj ξkS,j and T :=

IM ′ IM ′

(3.7)

  ′ iIM ′ c . Then, for ∈ R2s , −iIM ′ c′′

  (Φ ◦ σS )(c′ + ic′′ ) e ◦σ = T (Φ eS )(c′ + ic′′ ). (Φ ◦ σS )(c′ + ic′′ ) As T is invertible, we have 



e ◦σ dimR spanR (Φ eS )(R2s )



    (Φ ◦ σS )(c) s = dimC spanC :c∈C . (Φ ◦ σS )(c)

Combining (3.6) to (3.8) completes the proof.

(3.8)

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

9

Thus, maximizing SC 2s (Φ) requires     (Φ ◦ σS )(c) s to be maximized for all S ⊆ K with |S| = s. dimC spanC :c∈C (Φ ◦ σS )(c) To derive an upper bound on SC 2s (Φ), weSestablish a one-node estimate. Consider the map f 7→ ρ(f ∗ gλ ), f ∈ ES , and set Hλ,S := ( k∈S supp(ξbk )) ∩ supp(gbλ ). The d-fold sumset of Hλ,S ⊆ Z/M Z, formed with respect to the group operation + on Z/M Z, is denoted by Hd,λ,S := ⟨Hλ,S ⟩d := Hλ,S + · · · + Hλ,S = {h1 + · · · + hd : h1 , . . . , hd ∈ Hλ,S }. {z } | d times

Lemma 3.2. For S ⊆ K with |S| = s, and λ ∈ Λ, it holds that    s−1+d dimC (spanC ({ρ(f ∗ gλ ) : f ∈ ES })) ≤ min , |Hd,λ,S | . d

(3.9)

Furthermore, we have    s−1+d , |Hd,λ,S ∩ supp(b χ)| . dimC (spanC ({ρ(f ∗ gλ ) ∗ χ : f ∈ ES })) ≤ min d

(3.10)

Proof. As the DFT matrix FM is linear and invertible, we may equivalently consider the image of the map f 7→ FM (ρ(f ∗ gλ )) and compute, for k ∈ {0, . . . , M − 1}, (FM (ρ(f ∗ gλ )))k =

=

1 M d−1

X j1 ,...,jd ∈{0,...,M −1} j1 +···+jd ≡k (mod M )

1 M d−1

fbj1 (gbλ )j1 · · · fbjd (gbλ )jd

X α∈NM ,|α|=d PM −1 0 t=0 tαt ≡k (mod M )

  d gbλ α fbα . α

Thus, we can write FM (ρ(f ∗ gλ )) = AvM,d (fb),
where A is an M × M −1+d matrix with entries d (
P −1 M 1−d αd gbλ α , if M t=0 tαt ≡ k (mod M ) and supp(α) ⊆ Hλ,S , Akα = 0, otherwise, for k ∈ {0, . . . , M − 1} and α ∈ NM 0 with |α| = d in degree lexicographic order. Here, M −1+d vM,d : CM → C( d ) , z 7→ (z α )α∈NM 0

|α|=d

denotes the vector Veronese map in degree lexicographic P order. Note that each column of A has −1 at most one nonzero entry (since for a fixed column α, ( M t=0 tαt ) mod M results in a unique value in {0, . . . , M − 1}), and consequently, the nonzero rows of A are linearly independent. Thus, the rank of A is given by the number of nonzero rows of A; that is, ( M −1 ! ) X rank(A) = tαt mod M : α ∈ NM = |Hd,λ,S | . (3.11) 0 , |α| = d, supp(α) ⊆ Hλ,S t=0

10

K. Häberle and H. Bölcskei

By [14, Example 1], we have  dimC (spanC (vM,d (FM (ES )))) =

 s−1+d . d

(3.12)

From (3.11) and (3.12) the desired upper bound in (3.9) follows. To establish (3.10), note that FM (ρ(f ∗ gλ ) ∗ χ) = diag(b χ)AvM,d (fb). As rank(A) is given by the number of rows corresponding to Hd,λ,S , rank(diag(b χ)A) = |Hd,λ,S ∩ supp(b χ)|. This, together with (3.12), proves (3.10). Theorem 3.3. For the scattering network Φ of depth nd , we have SC 2s (Φ) ≤ 4 min

S⊆K |S|=s

[

  supp ξbk ∩ supp(b χ)

k∈S

   s−1+d + min , |Hd,λ,S ∩ supp(b χ)| d λ∈Λ ! nd X X |⟨supp(gc χ)| . + λn )⟩d ∩ supp(b X

n=2 (λ1 ,...,λn )∈Λn

S Proof. The root node outputs f ∗ χ, f ∈ ES , and thus contributes at most |( k∈S supp(ξbk )) ∩ supp(b χ)|. For the nodes of the first layer, one can directly apply Lemma 3.2. For a node of depth n ≥ 2, the input U [λ1 , . . . , λn−1 ]f need not lie in ES , but trivially lies in CM . Particularizing the proof of Lemma 3.2 to the case where the input space is CM yields 

dimC spanC ρ(u ∗ gλn ) ∗ χ : u ∈ CM ≤ |⟨supp(gc χ)| . λn )⟩d ∩ supp(b Summing these estimates over all nodes of the scattering tree and applying Proposition 3.1 establishes the desired bound. To maximize this upper bound, the filters {gλ }λ∈Λ should be chosen such that Hd,λ,S = Z/M Z. For d sufficiently large, this is the case if and only if Hλ,S is not contained in a coset of a proper subgroup of Z/M Z. Indeed, for h0 ∈ Hλ,S , let B := −h0 + Hλ,S . Then, by commutativity, Hd,λ,S = dh0 + ⟨B⟩d . As the identity element of Z/M Z lies in B, we have ⟨B⟩ℓ ⊆ ⟨B⟩ℓ+1 , for all ℓ ∈ N. Thus, there exists a d0 ∈ N with ⟨B⟩ℓ = ⟨B⟩d0 , for all ℓ ≥ d0 . Now, ⟨B⟩d0 + ⟨B⟩d0 = ⟨B⟩2d0 = ⟨B⟩d0 , which shows that ⟨B⟩d0 is closed under the group operation and thus, being a nonempty finite subset of Z/M Z, a subgroup [15, Theorem 3.3]. As ⟨B⟩d0 contains B and is contained in the subgroup ⟨B⟩ generated by B, it equals ⟨B⟩. Consequently, Hd,λ,S = dh0 + ⟨B⟩, whenever d ≥ d0 . It remains to verify that ⟨B⟩ = Z/M Z if and only if Hλ,S is not contained in a coset of a proper subgroup of Z/M Z. If ⟨B⟩ is proper, then Hλ,S = h0 + B ⊆ h0 + ⟨B⟩. Conversely, if Hλ,S ⊆ a + K for some a ∈ Z/M Z and some proper subgroup K, then h0 ∈ a + K implies a + K = h0 + K, so that B = −h0 + Hλ,S ⊆ K and ⟨B⟩ ⊆ K. Lower bound on SC 2s (Φ). For the lower bound, we follow the approach presented in Corollary 2.9.2. To this end, for S ⊆ K with |S| = s, let {KS,j }j∈JS ⊆ R2s be a countable sequence of compact sets such that {ψS,j : KS,j → ES,j }j∈JS ,S⊆K,|S|=s constitutes a bi-Lipschitz parametrization for E in the sense of Lemma 2.5, with ES,j = ψS,j (KS,j ). By carrying out the same computation as in (3.3), one can deduce that   ℜ(f ) e Φ = ∥Φ(f )∥ , f ∈ E, ℑ(f )      ℜ(f1 ) ℜ(f2 ) e e Φ ,Φ = ℜ(⟨Φ(f1 ), Φ(f2 )⟩), f1 , f2 ∈ E. ℑ(f1 ) ℑ(f2 )

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

11

Consequently, for complex-valued Φ on s-sparse signals in CM , Corollary 2.9.2 takes the form R 2 2 ES,j ∥Φ(f )∥2 dH2s (f ) SC 2s (Φ) ≥ inf inf R R 2 2s 2s S⊆K j∈JS E ES,j |ℜ(⟨Φ(f1 ), Φ(f2 )⟩)| dH (f1 )dH (f2 ) S,j |S|=s R 2 2 ES,j ∥Φ(f )∥2 dH2s (f ) ≥ inf inf R . R 2 2s 2s S⊆K j∈JS ES,j ES,j |⟨Φ(f1 ), Φ(f2 )⟩| dH (f1 )dH (f2 ) |S|=s

In what follows, we first analyze the RHS for the unfiltered first-layer map Φ1 (f ) = (ρ(f ∗ gλ ))λ∈Λ and subsequently extend the analysis to the first-layer feature map Φ1 (f ) = (ρ(f ∗ gλ ) ∗ M −1+d M −1+d χ)λ∈Λ , f ∈ E. To state our result, let us introduce the matrices AΛ ∈ C( d )×( d ) and M −1+d M −1+d GS,j ∈ C( d )×( d ) which are characterized by the filters {gλ }λ∈Λ and the geometry of ES,j , respectively. Specifically, Z GS,j := vM,d (fb)vM,d (fb)H dH2s (f ), ES,j 1 and AΛ := M

M ×(M −1+d H ) with entries d λ∈Λ Aλ Aλ , where Aλ ∈ C

P

(
P −1 M 1−d αd gbλ α , if M t=0 tαt ≡ k (mod M ), (Aλ )kα = 0, otherwise, H for all k ∈ {0, . . . , M − 1} and α ∈ NM 0 with |α| = d. For any such α, let γS,j,α denote the corresponding row of GS,j and aΛ,α denote the corresponding column of AΛ .

Lemma 3.4. For Φ1 (f ) = (ρ(f ∗ gλ ))λ∈Λ , f ∈ E, we have P 2 (Tr(GS,j AΛ ))2 2 ( α ⟨γS,j,α , aΛ,α ⟩)2 P SC (Φ1 ) ≥ inf inf = inf inf . S⊆K j∈JS Tr((GS,j AΛ )2 ) S⊆K j∈JS α,β ⟨γS,j,α , aΛ,β ⟩ ⟨γS,j,β , aΛ,α ⟩ 2s

|S|=s

|S|=s

1 H , so that for f , f ∈ E, Proof. The DFT matrix FM ∈ CM ×M has inverse M FM 1 2

⟨Φ1 (f1 ), Φ1 (f2 )⟩ =

X λ∈Λ

⟨ρ(f1 ∗ gλ ), ρ(f2 ∗ gλ )⟩ =

1 X ⟨FM (ρ(f1 ∗ gλ )), FM (ρ(f2 ∗ gλ ))⟩ . M λ∈Λ

As derived in the proof of Lemma 3.2, we can write2 FM (ρ(f ∗ gλ )) = Aλ vM,d (fb), f ∈ E. Consequently, E 1 XD ⟨Φ1 (f1 ), Φ1 (f2 )⟩ = Aλ vM,d (fb1 ), Aλ vM,d (fb2 ) M λ∈Λ * + 1 X H = Aλ Aλ vM,d (fb1 ), vM,d (fb2 ) M λ∈Λ D E = AΛ vM,d (fb1 ), vM,d (fb2 ) . This leads to Z Z ES,j

|⟨Φ1 (f1 ), Φ1 (f2 )⟩|2 dH2s (f1 )dH2s (f2 )

ES,j

2 In comparison to the matrix A defined in the proof of Lemma 3.2, we drop the condition supp(α) ⊆ Hλ,S here, so that Aλ depends only on gλ .

12

K. Häberle and H. Bölcskei

Z

Z

D E2 AΛ vM,d (fb1 ), vM,d (fb2 ) dH2s (f1 )dH2s (f2 )

= E

E

ES,j

ES,j

Z S,j Z S,j = Z

Z

  Tr AΛ vM,d (fb1 )vM,d (fb1 )H AΛ vM,d (fb2 )vM,d (fb2 )H dH2s (f1 )dH2s (f2 )

= ES,j

vM,d (fb2 )H AΛ vM,d (fb1 )vM,d (fb1 )H AΛ vM,d (fb2 ) dH2s (f1 )dH2s (f2 )

ES,j

Z = Tr AΛ

H

!

Z

2s

H

vM,d (fb1 )vM,d (fb1 ) dH (f1 )AΛ ES,j

2s

vM,d (fb2 )vM,d (fb2 ) dH (f2 ) ES,j

= Tr(AΛ GS,j AΛ GS,j )
= Tr (GS,j AΛ )2 X = (GS,j AΛ )α,β (GS,j AΛ )β,α α,β

=

X

⟨γS,j,α , aΛ,β ⟩ ⟨γS,j,β , aΛ,α ⟩ .

(3.13)

α,β

Likewise, we have Z

2

Z

2s

D

∥Φ1 (f )∥ dH (f ) = ES,j

E AΛ vM,d (fb), vM,d (fb) dH2s (f )

E

Z S,j =

  Tr AΛ vM,d (fb)vM,d (fb)H dH2s (f )

ES,j

!

Z = Tr AΛ

bH

2s

vM,d (fb)vM,d (f ) dH (f ) ES,j

= Tr(AΛ GS,j ) X = (GS,j AΛ )α,α α

=

X

⟨γS,j,α , aΛ,α ⟩ .

(3.14)

α

Combining (3.13) and (3.14) gives the desired bound. The trace ratio is maximized when, for all j ∈ JS and all S ⊆ K with |S| = s, the systems {γS,j,α }α and {aΛ,α }α are biorthogonal, i.e., ⟨γS,j,α , aΛ,β ⟩ = 1{α=β} , for all α, β. Exact biorthog
onality would make the lower bound equal to 2 M −1+d , but the structure of AΛ generally d prevents this. We therefore seek approximate biorthogonality, quantified through the restricted isometry property in Appendix A. Another drawback of directly inferring design choices for {gλ }λ∈Λ from Lemma 3.4 is that it is not readily apparent how GS,j depends on Ξ. We, however, aim to establish a design criterion for {gλ }λ∈Λ in terms of Ξ. To this end, consider the following setup. Assume from now on that |K| < ∞. With the labeling K = {k1 , . . . , k|K| }, define the matrix b = FM Ξ. Let ιS ∈ {0, 1}|K|×s be the matrix Ξ ∈ CM ×|K| with columns (ξk1 , . . . , ξk|K| ), and set Ξ with (ιS )ℓm := 1{kℓ =kS,m } for ℓ ∈ {1, . . . , |K|} and m ∈ {1, . . . , s}, so that ΞS := ΞιS ∈ CM ×s b S := FM ΞS . The biis the submatrix of Ξ with columns (ξkS,1 , . . . , ξkS,s ). Likewise, we set Ξ Lipschitz parametrization {ψS,j : KS,j → ES,j }j∈JS ,S⊆K,|S|=s can be chosen such that ψS,j (x) = ΞS (x′ + ix′′ ), where x = ((x′ )T , (x′′ )T )T ∈ KS,j . To isolate the dependence of GS,j on Ξ, we M −1+d |K|−1+d leverage the following property of the vector Veronese map v . Let T ∈ C( d )×( d ) M,d

be the unique matrix satisfying b = T b v|K|,d (z), vM,d (Ξz) Ξ

z ∈ C|K| .

b Ξ

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

13

|K|

Concretely, for multi-indices α ∈ NM b )αν is the 0 and ν ∈ N0 with |α| = |ν| = d, the entry (TΞ ν α b coefficient of z in the expansion of (Ξz) . Furthermore, we introduce Z CS,j := vs,d (x′ + ix′′ )vs,d (x′ + ix′′ )H dx. KS,j

The matrix CS,j depends on the parametrization domain but not on the frame Ξ. Denote by
δs,d (Ξ; Λ) the s−1+d th restricted isometry constant of (T bH AΛ TΞb )1/2 , see Definition A.1. d Ξ

Theorem 3.5. Let E ⊆ CM be the set of s-sparse signals, and assume that δs,d (Ξ; Λ) < 1. For Φ1 (f ) = (ρ(f ∗ gλ ))λ∈Λ , f ∈ E, it holds that   1 − δs,d (Ξ; Λ) 2 2 (Tr(CS,j ))2 2s  . SC (Φ1 ) ≥ min inf S⊆K j∈JS 1 + δs,d (Ξ; Λ) Tr (C )2

(3.15)

S,j

|S|=s

Proof. By the area formula, we have Z b S (x′ + ix′′ ))vM,d (Ξ b S (x′ + ix′′ ))H J(ΞS ) dx GS,j = vM,d (Ξ KS,j

Z = J(ΞS )TΞb S

KS,j

vs,d (x′ + ix′′ )vs,d (x′ + ix′′ )H dx TΞbH , S

{z

|

}

=CS,j

M −1+d d

where TΞb S ∈ C(

)×(s−1+d ) is the matrix defined by the relation d for z ∈ Cs .

b S z) = T b vs,d (z), vM,d (Ξ ΞS

Using the cyclic property of the trace, we then obtain 2   H A T 2 Tr C T S,j Λ b bS (Tr(GS,j AΛ )) ΞS Ξ =  2  2 Tr((GS,j AΛ ) ) Tr CS,j T bH AΛ TΞb S ΞS

≥

λmin (T bH AΛ TΞb S )

ΞS λmax (T bH AΛ TΞb S ) ΞS

!2

(Tr(CS,j ))2  , Tr (CS,j )2

(3.16)

where the inequality holds as T bH AΛ TΞb S , CS,j T bH AΛ TΞb S CS,j , and CS,j are positive semi-definite ΞS ΞS matrices, so that by [16, Eq. (1)],   Tr CS,j TΞbH AΛ TΞb S ≥ λmin (TΞbH AΛ TΞb S )Tr(CS,j ) S

S

and     Tr CS,j TΞbH AΛ TΞb S CS,j TΞbH AΛ TΞb S ≤ λmax (TΞbH AΛ TΞb S )Tr CS,j TΞbH AΛ TΞb S CS,j S S S S   H 2 H = λmax (TΞb AΛ TΞb S )Tr (CS,j ) TΞb AΛ TΞb S S S  2
≤ λmax (TΞbH AΛ TΞb S ) Tr (CS,j )2 . S

Here, λmin (T bH AΛ TΞb S ) and λmax (T bH AΛ TΞb S ) denote the smallest and largest eigenvalue of ΞS

ΞS

T bH AΛ TΞb S , respectively. Consequently, by Lemma 3.4, ΞS

2s

SC (Φ1 ) ≥ min

S⊆K |S|=s

λmin (T bH AΛ TΞb S )

ΞS λmax (T bH AΛ TΞb S ) ΞS

!2

2 (Tr(CS,j ))2  . inf j∈JS Tr (CS,j )2

(3.17)

14

K. Häberle and H. Bölcskei 1/2

We use (T bH AΛ TΞb )S to denote the submatrix of (T bH AΛ TΞb )1/2 with columns indexed by some Ξ Ξ
set S . By Lemma A.2, we have for all S with |S | = s−1+d , d λmin λmax

 

 1/2 H 1/2 (TΞbH AΛ TΞb )S (TΞbH AΛ TΞb )S



 1/2 H 1/2 (TΞbH AΛ TΞb )S (TΞbH AΛ TΞb )S



1/2

≥ 1 − δs,d (Ξ; Λ), (3.18) ≤ 1 + δs,d (Ξ; Λ). 1/2

As (T bH AΛ TΞb )1/2 is Hermitian, ((T bH AΛ TΞb )S )H (T bH AΛ TΞb )S is the submatrix of T bH AΛ TΞb with Ξ Ξ Ξ Ξ rows and columns indexed by S . Now, for every S ⊆ K with |S| = s there is an index set
such that (TΞb )S = TΞb S . Indeed, for every such S, there is a matrix S with |S | = s−1+d d |K|−1+d s−1+d I ∈ {0, 1}( d )×( d ) such that v (ι z) = I v (z), z ∈ Cs . Therefore, for every S

|K|,d

S

S

s,d

z ∈ Cs , we have b S z) = vM,d (Ξι b S z) = T b v|K|,d (ιS z) = T b IS vs,d (z), vM,d (Ξ Ξ Ξ
and thus TΞb S = TΞb IS = (TΞb )S for some index set S with |S | = s−1+d . Consequently, d H H for every S with |S| = s, the matrix T b AΛ TΞb S is the submatrix of T b AΛ TΞb with rows and ΞS Ξ columns indexed by S . Combining (3.17) with (3.18) establishes (3.15). It remains to verify that λmax (T bH AΛ TΞb S ) > 0, so that (3.16) and (3.17) are well-defined. If, to the contrary, ΞS

λmax (T bH AΛ TΞb S ) = 0, then positive semi-definiteness would imply T bH AΛ TΞb S = 0, which, in ΞS ΞS turn, yields δs,d (Ξ; Λ) = 1, contradicting the assumption δs,d (Ξ; Λ) < 1. This completes the proof.

1 (f ) = ρ(f ∗ g ) ∗ λ
The result in Theorem 3.5 extends readily to the first-layer feature P map Φ 1 H χ λ∈Λ , f ∈ E. To this end, set Aλ,χ := diag(b χ) Aλ and AΛ,χ := M λ∈Λ Aλ,χ Aλ,χ , and denote
by δs,d (Ξ; Λ, χ) the s−1+d th restricted isometry constant of (T bH AΛ,χ TΞb )1/2 . d Ξ

Corollary 3.5.1. Let E ⊂ CM be the set of s-sparse signals. Assuming that δs,d (Ξ; Λ, χ) < 1, the first-layer feature map Φ1 (f ) = (ρ(f ∗ gλ ) ∗ χ)λ∈Λ , f ∈ E, satisfies SC

2s

Φ

1

 ≥

1 − δs,d (Ξ; Λ, χ) 1 + δs,d (Ξ; Λ, χ)

2

2 (Tr(CS,j ))2  . 2 S⊆K j∈JS Tr (C ) S,j |S|=s min inf

Proof. Note that FM (ρ(f ∗ gλ ) ∗ χ) = diag(b χ)Aλ vM,d (fb). Hence the proof of Theorem 3.5 carries over verbatim upon replacing AΛ with AΛ,χ , which yields the claim.
The lower bound on SC 2s Φ1 therefore suggests the following design criterion: choose {χ} ∪
{gλ }λ∈Λ so that the s−1+d th restricted isometry constant of (T bH AΛ,χ TΞb )1/2 is as small as d Ξ possible. 3.3

Rectifiable sets

We now replace the sparse-signal model by a countably Hs -rectifiable set E ⊆ CM . We assume that E admits a bi-Lipschitz parametrization {ψj : Kj → ψj (Kj )}j∈J , with Kj ⊂ Rs compact, and that each ψj is a polynomial of degree nj , i.e., ψj (x) =

X α : |α|≤nj

cj,α xα ,

x ∈ Kj , for some cj,α ∈ CM .

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

15

′

Upper bound on SC s (Φ). For Φ : E → CM real-analytic, we have by [9],        e = min SC Φ e ◦ ψej = 2 min dimR spanR (Φ e ◦ ψej )(Kj ) , SC s (Φ) = SC s Φ j∈J

j∈J

where ψej := ι ◦ ψj . By the same approach as in the derivation of (3.8), we obtain  n o
T φT , φT : φ ∈ Φ(Ej ) SC s (Φ) = 2 min dimC spanC , j∈J

(3.19)

where Ej := ψj (Kj ). To develop an upper bound on SC s (Φ), we again start with a one-node estimate. Let S \ Hλ,ψj := ( x∈Kj supp(ψ j (x))) ∩ supp(gbλ ), and define Hd,λ,ψj = Hλ,ψj + · · · + Hλ,ψj . {z } | d times

Lemma 3.6. Suppose that ψj : Kj → Ej is a polynomial of degree nj , j ∈ J . Then, for each j ∈ J,    s + nj d dimC (spanC ({ρ(f ∗ gλ ) : f ∈ Ej })) ≤ min , |Hd,λ,ψj | (3.20) nj d and    s + nj d χ)| . , |Hd,λ,ψj ∩ supp(b dimC (spanC ({ρ(f ∗ gλ ) ∗ χ : f ∈ Ej })) ≤ min nj d

(3.21)

Proof. As in the proof of Lemma 3.2, we take the DFT and obtain FM (ρ(f ∗ gλ )) = AvM,d (fb),

f ∈ Ej ,

M −1+d d

) with entries

where A ∈ CM ×(

(
P −1 M 1−d αd gbλ α , if M t=0 tαt ≡ k (mod M ) and supp(α) ⊆ Hλ,ψj , Akα = 0, otherwise, for k ∈ {0, . . . , M − 1} and α ∈ NM 0 with |α| = d in degree lexicographic order. Then, by the same argument as in the proof of Lemma 3.2, rank(A) = |Hd,λ,ψj |. Furthermore, it holds that dimC (spanC (vM,d (FM (Ej )))) ≤

 nj d  X s−1+ℓ ℓ=0

ℓ

 =

 s + nj d , nj d

as x 7→ vM,d (FM (ψj (x))) is a multivariate polynomial of degree at most nj d. This establishes (3.20). The assertion in (3.21) holds because FM (ρ(f ∗ gλ ) ∗ χ) = diag(b χ)AvM,d (fb), so that rank(diag(b χ)A) = |Hd,λ,ψj ∩ supp(b χ)|. Theorem 3.7. For the scattering network Φ of depth nd , we have       s + n    [ j s \    SC (Φ) ≤ 4 min min , supp ψj (x) ∩ supp(b χ)   j∈J nj x∈Kj

+

nd X

X

n=1 (p,λn )∈Λn−1 ×Λ

     n s + nj d . min , Hd,λn ,U [p]◦ψj ∩ supp(b χ) nj dn

16

K. Häberle and H. Bölcskei

Proof. The input of the node indexed by (p, λn ) ∈ Λn−1 × Λ is parametrized by U [p] ◦ ψj , which is a polynomial of degree at most nj d n−1 . Indeed, U [p] consists of n − 1 node operations (3.2), each of which multiplies the degree by at most d. Note that the proof of Lemma 3.6 directly applies to U [p] ◦ ψj in place of ψj and bounds the span dimension of this n
jd node’s outputs by min{ s+n , |Hd,λn , U [p]◦ψj ∩ supp(b χ)|}. The output of the root node takes nj d n the form ψj (x) ∗ χ, for x ∈ Kj , which is a polynomial of degree at most nj in x and whose S \ Fourier transform is supported in ( x∈Kj supp(ψ χ). Hence it contributes at most j (x))) ∩ supp(b
S s+nj \ min{ , |( supp(ψ χ)|}. Summing over all nodes of the tree and applying j (x))) ∩ supp(b nj

x∈Kj

(3.19) yields the desired bound. The nonlinear nature of E is captured in this upper bound by the degrees of the maps ψj and the sets Hd,λn ,U [p]◦ψj . Both a higher degree of ψj and larger sets Hd,λn ,U [p]◦ψj reflect a richer geometry, and both raise the upper bound. As the degree of U [p] ◦ ψj grows like nj dn−1 along the tree, both effects are amplified with depth. Lower bound on SC s (Φ). |⟨Φ(f1 ), Φ(f2 )⟩|, yields

Corollary 2.9.2, together with the bound |ℜ(⟨Φ(f1 ), Φ(f2 )⟩)| ≤

SC s (Φ) ≥ inf R j∈J

2 R

Ej

2 2 s (f ) ∥Φ(f )∥ dH Ej

R

. 2 s s Ej |⟨Φ(f1 ), Φ(f2 )⟩| dH (f1 ) dH (f2 )

We first consider again the unfiltered first-layer map Φ1 (f ) = (ρ(f ∗ gλ ))λ∈Λ , f ∈ E. With Z vM,d (fb)vM,d (fb)H dHs (f ), Gj := Ej

the same computation as in the proof of Lemma 3.4 particularizes the lower bound for Φ1 to 2(Tr(Gj AΛ ))2 . j∈J Tr((Gj AΛ )2 )

SC s (Φ1 ) ≥ inf

(3.22)

As in the sparse case, it is not immediate how Gj depends on the geometry of E. To isolate this dependence, let Tψbj be the unique matrix satisfying \ vM,d (ψ j (x)) = Tψ bj ws,nj d (x), where ws,nj d (x) = (xα )|α|≤nj d , x ∈ Rs .

In particular, Tψbj depends on the coefficients

(cj,α )|α|≤nj ⊂ CM of the parametrization ψj . We further set Z Mj :=

ws,nj d (x) ws,nj d (x)H dx,

Kj

which, unlike Tψbj , depends only on the domain Kj of the parametrization ψj and not on its coefficients. Let λmin (T bH AΛ Tψbj ) and λmax (T bH AΛ Tψbj ) denote the smallest and largest eigenvalue ψj

ψj

of T bH AΛ Tψbj , respectively. ψj

Theorem 3.8. Let E ⊆ CM be countably Hs -rectifiable with bi-Lipschitz parametrization {ψj : Kj → Ej }j∈J , where each ψj is t-bi-Lipschitz. Suppose that ψj : Kj → Ej is a polynomial of degree nj , j ∈ J , and consider Φ1 (f ) = (ρ(f ∗ gλ ))λ∈Λ , f ∈ E. (a) If Φ1 vanishes Hs -a.e. on Ej , for some j ∈ J , then SC s (Φ1 ) = 0.

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

17

(b) If Φ1 does not vanish Hs -a.e. on Ej , for any j ∈ J , then    2 H  λmin Tψbj AΛ Tψbj  2(Tr(Mj ))2   SC s (Φ1 ) ≥ t−4s inf   Tr((Mj )2 ) . j∈J  H λmax T b AΛ Tψbj ψj

Proof. (a) The assertion follows from (2.2), applied with A = {f ∈ Ej : Φ1 (f ) = 0}, upon noting that Hs (A) = Hs (Ej ) > 0 and dimR (spanR (Φ1 (A))) = 0. (b) Application of the area formula gives Z \ \ H Gj = vM,d (ψ j (x))vM,d (ψj (x)) J(d(ψj )x ) dx Kj Z = Tψbj ws,nj d (x)ws,nj d (x)H J(d(ψj )x ) dx TψbH . j

Kj

As ψj : Kj → Ej is t-bi-Lipschitz, we have t−s ≤ J(d(ψj )x ) ≤ ts , for Ls -a.e. x ∈ Kj and j ∈ J . Thus, t−s Tψbj Mj TψbH ⪯ Gj ⪯ ts Tψbj Mj TψbH . j

j

As AΛ is positive semi-definite, we have   Tr(Gj AΛ ) ≥ t−s Tr Tψbj Mj TψbH AΛ j   −s H = t Tr Mj Tψb AΛ Tψbj .

(3.23)

j

Furthermore, since AΛ Gj AΛ and AΛ Tψbj Mj T bH AΛ are positive semi-definite, we have ψj

  Tr(Gj AΛ Gj AΛ ) ≤ ts Tr Tψbj Mj TψbH AΛ Gj AΛ j   s = t Tr AΛ Tψbj Mj TψbH AΛ Gj j   2s ≤ t Tr AΛ Tψbj Mj TψbH AΛ Tψbj Mj TψbH j j   2s H H = t Tr Mj Tψb AΛ Tψbj Mj Tψb AΛ Tψbj j j  2  = t2s Tr Mj TψbH AΛ Tψbj . j

Thus,   2 −2s Tr M T H A T t j Λ b b ψj (Tr(Gj AΛ )) ψj  ≥  2 ! . 2 Tr (Gj AΛ ) t2s Tr Mj T bH AΛ Tψbj 2

ψj

Application of (3.16) together with (3.22) establishes the result. Note that λmax (T bH AΛ Tψbj ) > 0. Indeed, suppose, for contradiction, that λmax (T bH AΛ Tψbj ) = 0, ψj

ψj

then, as T bH AΛ Tψbj is positive semi-definite, we have T bH AΛ Tψbj = 0. This, in turn, imψj

ψj

plies that Tr(Gj AΛ ) = 0 upon application of (3.23) together with the analogous upper R s H bound Tr(Gj AΛ ) ≤ t Tr(Mj T b AΛ Tψbj ). But Tr(Gj AΛ ) = Ej ∥Φ1 (f )∥2 dHs (f ), so that Φ1 ψj

vanishes Hs -a.e. on Ej , a contradiction. This completes the proof.

18

K. Häberle and H. Bölcskei

Analogously to the sparse-signal model, the result in Theorem 3.8 extends to the first-layer feature map Φ1 . Corollary 3.8.1. Under the hypotheses of Theorem 3.8, the following statements hold for Φ1 (f ) = (ρ(f ∗ gλ ) ∗ χ)λ∈Λ , f ∈ E.
(a) If Φ1 vanishes Hs -a.e. on Ej , for some j ∈ J , then SC s Φ1 = 0. (b) If Φ1 does not vanish Hs -a.e. on Ej , for any j ∈ J , then 



T bH AΛ,χ Tψbj ψj

 λmin
 SC s Φ1 ≥ t−4s inf  j∈J  λmax T bH AΛ,χ Tψbj

 2  2(Tr(Mj ))2   Tr((Mj )2 ) .

ψj

Proof. As FM (ρ(f ∗ gλ ) ∗ χ) = diag(b χ) Aλ vM,d (fb), the output-generating atom χ enters the analysis only through the substitution of AΛ,χ for AΛ . Repeating the proof of Theorem 3.8 with this modification yields the claim. We conclude with the design criterion that the filters {χ} ∪ {gλ }λ∈Λ should be chosen so that T bH AΛ,χ Tψbj is well-conditioned, for all j ∈ J , in the sense that the ratio ψj

λmin (T bH AΛ,χ Tψbj )/λmax (T bH AΛ,χ Tψbj ) is close to 1. ψj

A

ψj

Restricted isometry property

Definition A.1 (sth restricted isometry constant, [17]). The sth restricted isometry constant δs (B) of a matrix B ∈ Cm×N is the smallest δ ≥ 0 such that (1 − δ)∥x∥2 ≤ ∥Bx∥2 ≤ (1 + δ)∥x∥2 , for all x ∈ CN with |supp(x)| ≤ s. Denote by Bτ the (m × |τ |)-submatrix of B with columns indexed by some set τ , and let λmin (BτH Bτ ) and λmax (BτH Bτ ) be the smallest and largest eigenvalues of BτH Bτ , respectively. Lemma A.2 ([18]). For B ∈ Cm×N , and all index sets τ with |τ | ≤ s, it holds that 1 − δs (B) ≤ λmin (BτH Bτ ) ≤ λmax (BτH Bτ ) ≤ 1 + δs (B).

References [1] Y. Bengio, A. Courville, and P. Vincent, “Representation learning: A review and new perspectives,” IEEE transactions on pattern analysis and machine intelligence, vol. 35, no. 8, pp. 1798–1828, 2013. [2] C. Fefferman, S. Mitter, and H. Narayanan, “Testing the manifold hypothesis,” Journal of the American Mathematical Society, vol. 29, no. 4, pp. 983–1049, 2016. [3] H. Federer, Geometric measure theory.

Springer, 2014.

[4] L. Ambrosio and B. Kirchheim, “Currents in metric spaces,” Acta Mathematica, vol. 185, pp. 1–80, 2000. [5] S. Mallat, “Group invariant scattering,” Communications on Pure and Applied Mathematics, vol. 65, no. 10, pp. 1331–1398, 2012.

Separation Capacity of Scattering Networks on Low-Dimensional Datasets

19

[6] T. Wiatowski and H. Bölcskei, “A mathematical theory of deep convolutional neural networks for feature extraction,” IEEE Transactions on Information Theory, vol. 64, no. 3, pp. 1845–1866, 2017. [7] K. Häberle and H. Bölcskei, “Separation capacity of scattering networks,” arXiv preprint arXiv:2606.30822, 2026. [8] T. M. Cover, “Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition,” IEEE Transactions on Electronic Computers, no. 3, pp. 326–334, 1965. [9] K. Häberle and H. Bölcskei, “Function-counting theory for low-dimensional data structures,” arXiv preprint arXiv:2607.01010, 2026. [10] O. Christensen, An introduction to frames and Riesz bases.

Springer, 2003, vol. 7.

[11] L. Simon, “Introduction to geometric measure theory,” Tsinghua Lectures, 2014. [12] F. Maggi, Sets of finite perimeter and geometric variational problems: An introduction to geometric measure theory. Cambridge University Press, 2012, no. 135. [13] B. Mityagin, “The zero set of a real analytic function,” Mathematical Notes, vol. 107, no. 3, pp. 529–530, 2020. [14] M. Feinberg, “On a generalization of linear independence in finite-dimensional vector spaces,” Journal of Combinatorial Theory, Series B, vol. 30, no. 1, pp. 61–69, 1981. [15] J. A. Gallian, Contemporary abstract algebra, 7th ed. 2010.

Brooks/Cole Cengage Learning,

[16] Y. Fang, K. A. Loparo, and X. Feng, “Inequalities for the trace of matrix product,” IEEE Transactions on Automatic Control, vol. 39, no. 12, pp. 2489–2490, 1994. [17] S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing. Birkhäuser New York, NY, 2013. [18] E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE transactions on information theory, vol. 51, no. 12, pp. 4203–4215, 2005.