Function-Counting Theory for Low-Dimensional Data Structures

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Function-Counting Theory for Low-Dimensional Data Structures

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Function-Counting Theory for Low-Dimensional Data Structures Konstantin Häberle ETH Zurich [email protected]

Helmut Bölcskei ETH Zurich [email protected]

arXiv:2607.01010v1 [stat.ML] 1 Jul 2026

Abstract The success of deep learning models in classification and regression is widely attributed to the low-dimensional structure that real-world data tend to exhibit, despite their highdimensional representation. This work attempts to provide a mathematical framework for binary classification on low-dimensional data, building on Cover’s (1965) function-counting theory. With our framework, we aim to address the question of how the low-dimensional structure of the data affects the classification capabilities of learning models. Cover’s theory relies on a general position assumption that blinds it to the underlying data structure. We refine this assumption to account for the low-dimensionality of the data and derive dichotomy counts that reflect the data structure. We further extend Cover’s separation capacity and problem of generalization to the low-dimensional setting, enabling the impact of the underlying data structure on both to be analyzed. Keywords: Learning theory, pattern classification, geometric measure theory.

Introduction

Function-counting theory, as initiated by Cover [1], stands as a pivotal cornerstone in learning theory, providing a framework for the analysis of the classification capabilities of learning models such as neural networks. A core result in this theory is the so-called function-counting theorem [1, 2, 3, 4]. It quantifies the number of binary classification functions, or dichotomies, that can be realized by a learning model when data points are assumed to be in general position (with respect to the learning model). A key motivation for extending this theory is that real-world data typically exhibits lowdimensional structure [5]. Existing function-counting results [1, 6, 7], however, discard this structure entirely: Under the general position assumption, the number of realizable dichotomies depends only on the number of data points and the ambient feature dimension, leaving the underlying geometry of the dataset unconsidered. Furthermore, the general position assumption becomes increasingly restrictive, and indeed usually fails, when data concentrates on lowdimensional structures. In this paper, we present an extension of the existing function-counting framework sensitive to the low-dimensional structure of datasets. The central question we aim to address with our framework is: How does the low-dimensional structure of the dataset affect the classification capabilities of learning models? We report three main contributions. (i) By refining the general position assumption to the given data structure, we derive functioncounting results for a broad class of s-dimensional sets that includes sparse signals and rectifiable sets, with s a positive integer much smaller than the ambient dimension. More precisely, instead of imposing general position on the dataset as a whole, we decompose it into components on which the linear spanning dimension is constant across all subsets of positive s-dimensional measure, and impose general position within each separately. Our dichotomy counts depend on the following quantities invisible to the classical functioncounting theorem: the intrinsic dimension s, the geometry of the individual components,

K. Häberle and H. Bölcskei

and their relative geometric configuration. For sparse signals, the constituent components are s-dimensional linear subspaces, and we show that the dichotomy count is governed by s and independent of the ambient dimension. For rectifiable sets, the components are in general nonlinear, and we establish that the number of realizable dichotomies reflects the geometric richness of the components arising from this nonlinearity: The dichotomy count is higher for sets spread across more directions. (ii) Based on the function-counting theorem, Cover introduced the notion of separation capacity [6, 7], a quantity closely related to the Vapnik–Chervonenkis (VC) dimension [8]. While VC dimension is an existential threshold on the cardinality of the dataset, separation capacity is a universal one, indicating where the majority of dichotomies becomes unrealizable for almost all datasets. Under the general position assumption, Cover established that the separation capacity is twice the ambient feature dimension. We extend Cover’s separation capacity to s-dimensional sets, and derive explicit characterizations thereof. Notably, by leveraging our dichotomy counts, we show that the separation capacity equals twice the smallest linear spanning dimension across the constituent components of the above decomposition. Our extension thus allows identifying the properties of the low-dimensional structure of the dataset that govern the separation capacity, sharpening Cover’s theory, which captures only the ambient feature dimension. (iii) Finally, we investigate Cover’s problem of generalization for low-dimensional sets. While Cover’s treatment relies on the general position assumption, and is thus blind to the underlying data structure, our framework allows us to analyze how the low-dimensional structure of the dataset influences a learning model’s ability to generalize ambiguously. Here and throughout, generalization refers to whether a dichotomy realized by a learning model uniquely determines the label of a new point, or leaves both assignments compatible with the realized dichotomy. We derive an exact expression for the probability of ambiguous generalization and establish a connection to our extended notion of separation capacity. The paper is organized as follows. In Section 2, we derive function-counting bounds which hold true for arbitrary datasets and are fundamental for our extension of separation capacity. Section 3 addresses the separation of points on low-dimensional datasets. In Section 4, we generalize the notion of separation capacity to encompass low-dimensional data structures. Section 5 is devoted to the problem of generalization. The notation used throughout this paper is summarized in Appendix A. Appendices B and C review key results from function-counting theory and basic properties of the Hausdorff measure, respectively.

Function-counting bounds

Let E ⊆ RM be an arbitrary subset of the pattern space (RM , ⟨·, ·⟩) with the standard inner product ⟨f, g⟩ = g T f , f, g ∈ RM , M ∈ N. In this setting, patterns correspond to raw input data, such as, e.g., images, audio signals, or videos, represented as elements of RM . The set E may serve as a formal model for real-world data. It is often assumed that data lie on sets of low-dimensional structure. Intuitively, this assumption may be motivated by the following observations. High-dimensional real-world data typically exhibit some redundancy and are often correlated. Furthermore, especially in the context of classification, data of the same class often show invariance or equivariance with respect to certain transformations or deformations. For example, in the MNIST dataset [9], data belonging to the same class are invariant under translations and small deformations, see Fig. 2.1. A popular hypothesis for the low-dimensional structure of data is that of manifolds; concretely, in our notation, the assumption that E is a submanifold of RM . This hypothesis is also referred to as the manifold hypothesis. While a detailed technical treatment of testing model choices E lies beyond the scope of this paper, for

Function-Counting Theory for Low-Dimensional Data Structures

Figure 2.1: The class ‘2’ of the MNIST dataset [9] is invariant with respect to translations (middle) and small deformations (right).

comprehensive discussions on the manifold hypothesis and related work, we refer the reader to [5, 10, 11, 12]. Building upon Cover’s framework [1] for quantifying the classification capabilities of a map ′ Φ : E → RM , we analyze the number of Φ-separable dichotomies, CF , of an arbitrary N -point set F = {f1 , . . . , fN } ⊆ E, where N, M ′ ∈ N. A review of Cover’s framework together with some key results of function-counting theory is provided in Appendix B. This section develops novel lower and upper bounds on CF that generalize beyond the standard assumption of Φ-general position. Such a generalization is essential for our setting, where the arbitrary nature of E, F , and Φ likely introduces degeneracies. These bounds are expressed in terms of the counting function C(·, ·), defined in (B.1), as well as the quantities1 N r := rank({Φ(fk )}N k=1 ) and s := kr({Φ(fk )}k=1 ), which measure the degeneracy of E, F , and Φ. Theorem 2.1. The following holds: (a) If s = 0, then CF = 0. (b) If 0 < s = r, then CF = C(N, s). (c) If 0 < s < r, then C(N, s) < CF < C(N, r).

(2.1)

Remark 2.2. If s < r, then F is in particular not in Φ-general position, and the upper bound reads CF < C(N, r) ≤ C(N, M ′ ). That is, fewer than C(N, M ′ ) dichotomies of F are Φ-separable, as expected. The proof of Theorem 2.1 utilizes the next two lemmata. To this end, let us introduce the following notation. For each k ∈ {1, . . . , N }, let Hk := {φk }⊥ , where φk := Φ(fk ). For t ∈ {0, . . . , N }, denote by Et and Ot the sets of all even- and odd-degenerate hyperplane arrangements consisting of t hyperplanes, respectively. That is, Et := {{Hk }k∈K : K ⊆ {1, . . . , N }, |K| = t, and {Hk }k∈K is even-degenerate} and Ot := {{Hk }k∈K : K ⊆ {1, . . . , N }, |K| = t, and {Hk }k∈K is odd-degenerate} . Lemma 2.3. If 2 ≤ s < r, then N X

|Ot | <

t=s+2 (t−s) is even

N X

|Et |.

(2.2)

t=s+1 (t−s) is odd

1 Recall that kr({Φ(fk )}N k=1 ) denotes the Kruskal rank, i.e., the largest integer s such that every subset of s elements of {Φ(fk )}N k=1 is linearly independent.

K. Häberle and H. Bölcskei

Proof. See Subsection 2.1. Lemma 2.4. If 2 ≤ s < r, then N X

|Et | <

t=r+1 (t−r) is odd

r X

N X

|Ot | +

t=s+1

|Ot |.

(2.3)

t=r+2 (t−r) is even

Proof. See Subsection 2.2. Proof of Theorem 2.1.

(a) The claim is immediate by Definition B.1.

(b) Let π : spanR (Φ(F )) → Rs be the linear map to the space of expansion coefficients with respect to {Φ(fk )}sk=1 . Then, F is in (π ◦ Φ)-general position. Moreover, every dichotomy ′ of F is Φ-separable if and only if it is (π ◦ Φ)-separable. Indeed, for every w ∈ RM and k ∈ {1, . . . , N }, we have2 ⟨w, Φ(fk )⟩RM ′ = w′ + w′′ , Φ(fk ) RM ′ = w′ , Φ(fk ) RM ′ = π(w′ ), π(Φ(fk )) Rs , where w′ and w′′ denote the orthogonal projections of w onto spanR (Φ(F )) and Φ(F )⊥ , respectively. Application of Theorem B.3 thus yields CF = C(N, s),

(2.4)

as desired. (c) The proof proceeds in two steps. We first show that if (2.1) holds for 2 ≤ s < r, then (2.1) necessarily extends to s = 1. We then provide the proof for the case 2 ≤ s < r. Step (c.1): Extension to s = 1. Suppose that (2.1) holds for 2 ≤ s < r. Assume with′ out loss of generality that N ′ ∈ {2, . . . , N − 1} is such that {Hk }N contains no k=1 ′ ′ := rank({φ }N ′ ) = r. Deduplicates (i.e., s′ := kr({φk }N ) ≥ 2) and such that r k k=1 k=1 noting by F ′ the corresponding N ′ -point set, we then have CF = CF ′ . As 2 ≤ s′ ≤ r′ , it holds by assumption that C(N ′ , s′ ) ≤ CF ′ ≤ C(N ′ , r′ ), but C(N ′ , r′ ) < C(N, r) and C(N ′ , s′ ) > C(N, s) = 2. This establishes the extension of (2.1) from 2 ≤ s < r to 0 < s < r. Step (c.2): The case 2 ≤ s < r. We first show the lower bound in (2.1) and then the upper bound in (2.1). Step (c.2.1): Lower bound. Note that φk ̸= 0, k ∈ {1, . . . , N }, as s > 0 by assumption, so that application of Theorem B.5, together with Remark B.6, yields CF = 2N − 2|O|. P N N 3 Using (B.2) and the identity N t=0 t = 2 , we can write C(N, s) as C(N, s) = 2N − 2

N X t=s+1 (t−s) is odd

2 3

N . t

Here, we write inner products with subscripts to indicate the space in which they are defined. P We use the convention t∈∅ ξt = 0 for any {ξt }t .

(2.5)

(2.6)

Function-Counting Theory for Low-Dimensional Data Structures

Thus, it follows from (2.5) and (2.6) that the lower bound in (2.1) is equivalent to N X N |O| < . (2.7) t t=s+1 (t−s) is odd

SN S N We have E = N t=0 Ot . As every subset of {Φ(fk )}k=1 of t=0 Et and O = cardinality s is linearly independent, we have dimR (∩k∈K Hk ) = M ′ − dimR (spanR ({φk }k∈K )) = M ′ − |K|, whenever K ⊆ {1, . . . , NP } with |K| ≤ t. In particular, this implies |Ot | =0 for N t ≤ s, and hence |O| = N t=s+1 |Ot |. Using the identities |Et | + |Ot | = t and PN |O| = t=s+1 |Ot |, one can deduce that (2.7) holds if and only if N X

N X

|Ot | <

t=s+2 (t−s) is even

|Et |.

t=s+1 (t−s) is odd

Application of Lemma 2.3 then completes the proof of Step (c.2.1). Step (c.2.2): Upper bound. As N X

C(N, r) = 2 − 2

t=r+1 (t−r) is odd

N , t

and CF = 2N − 2|O|, the upper bound in (2.1) is equivalent to N X t=r+1 (t−r) is odd

With the identities |Et | + |Ot | = N X

N t

|Et | <

t=r+1 (t−r) is odd

N < |O|. t

and |O| =

r X

t=s+1 |Ot |, (2.8) reads

N X

|Ot | +

t=s+1

(2.8)

|Ot |,

t=r+2 (t−r) is even

and the proof of Step (c.2.2) is complete upon application of Lemma 2.4.

2.1

Proof of Lemma 2.3

Proof. To show (2.2), it will be convenient to establish at the same time the complementary inequality N X

|Ot | <

t=s+1 (t−s) is odd

N X

|Et |.

(2.9)

t=s (t−s) is even

We shall prove (2.2) and (2.9) simultaneously by induction on the number of hyperplanes N . The induction step employs a deletion–contraction argument, a Tutte–Grothendieck method standard in the study of hyperplane arrangements, see, e.g., [13].

K. Häberle and H. Bölcskei

As 2 ≤ s < r, we consider, for the base case, N = 4, the hyperplanes {Hk }4k=1 with Hk = {φk }⊥ , where {Hk }3k=1 are in general position and H4 is such that, e.g., φ4 = φ1 + φ2 . In this setting, we have s = 2, r = 3, and |E0 | = 1,

|E1 | = 4,

|E2 | = 6,

|E3 | = 3,

|E4 | = 0,

|O0 | = 0, |O1 | = 0, |O2 | = 0, |O3 | = 1, |O4 | = 1. Thus, (2.2) is realized as |O4 | < |E3 |, while (2.9) holds in the form |O3 | ≤ |E2 | + |E4 |, as required. Now suppose that (2.2) and (2.9) is true for an arbitrary set of N − 1 hyperplanes, denoted −1 4 by {H̃k }N k=1 , i.e., N −1 X

−1 |Ot ({H̃k }N k=1 )| <

N −1 X

−1 |Et ({H̃k }N k=1 )|

t=s̃+2 (t−s̃) is even

t=s̃+1 (t−s̃) is odd

N −1 X

(2.10)

and −1 |Ot ({H̃k }N k=1 )| <

t=s̃+1 (t−s̃) is odd

−1 |Et ({H̃k }N k=1 )|,

(2.11)

t=s̃ (t−s̃) is even

−1 N −1 N −1 where s̃ := kr({φ̃k }N k=1 ) and r̃ := rank({φ̃k }k=1 ) satisfying 2 ≤ s̃ < r̃. Here, {φ̃k }k=1 are such that H̃k = {φ̃k }⊥ , for all k ∈ {1, . . . , N − 1}. To establish the induction step, we require the identities N N |Et ({Hk }N k=1 )| = |Et ({Hk }k=2 )| + |Et−1 ({H1 ∩ Hk }k=2 )|

(2.12)

N N |Ot ({Hk }N k=1 )| = |Ot ({Hk }k=2 )| + |Ot−1 ({H1 ∩ Hk }k=2 )|.

(2.13)

and

describes the arrangement of all hyperplanes except for H1 in the same The deletion {Hk }N k=2 ′ M ambient space R . The contraction {H1 ∩ Hk }N k=2 refers to the hyperplane arrangement in the new (M ′ − 1)-dimensional ambient space H1 . Note that, as s ≥ 2 (i.e., {Hk }N k=1 are N ′ distinct), {H1 ∩ Hk }k=2 are indeed (M − 2)-dimensional hyperplanes in H1 . Denoting by PH1 the orthogonal projection onto H1 , we can write5 H1 ∩ Hk = {PH1 φk }⊥ . To see that (2.12) holds, let {Hk }k∈K ∈ Et ({Hk }N k=1 ) be even-degenerate, where K ⊆ {1, . . . , N } with |K| = t. If 1∈ / K, then {Hk }k∈K ∈ Et ({Hk }N k=2 ). If 1 ∈ K, then {H1 ∩ Hk }k∈K\{1} is even-degenerate in the space H1 . Indeed,   ! \ \ dimR  (H1 ∩ Hk ) = dimR Hk k∈K

k∈K\{1} ′

≡M −t ′

≡ (M − 1) − (t − 1)

(mod 2) (mod 2), ′

where we used in the second line that {Hk }k∈K is even-degenerate in RM . Thus, (2.12) holds with “≤”. Conversely, if {Hk }k∈K ∈ Et ({Hk }N k=2 ), where K ⊆ {2, . . . , N } with |K| = t, then −1 To highlight the dependency of |Et | and |Ot | on the set of hyperplanes under consideration, namely, {H̃k }N k=1 , we included it in parenthesis. 5 Here, ⊥ denotes the orthogonal complement in the ambient space H1 . 4

Function-Counting Theory for Low-Dimensional Data Structures

N {Hk }k∈K ∈ Et ({Hk }N k=1 ). Furthermore, if {H1 ∩ Hk }k∈K ∈ Et−1 ({H1 ∩ Hk }k=2 ), where K ⊆ N {2, . . . , N } with |K| = t − 1, then {Hk }k∈K∪{1} ∈ Et ({Hk }k=1 ) because   ! \ \ Hk  = dimR dimR  (H1 ∩ Hk ) k∈K

k∈K∪{1} ′

≡ (M − 1) − (t − 1)

(mod 2)

′

≡M −t

(mod 2),

where the second line holds because {H1 ∩Hk }k∈K is even-degenerate in the (M ′ −1)-dimensional space H1 . Consequently, (2.12) remains valid with “≥”, and the identity follows. Likewise, one can show that (2.13) is true. By definition of the Kruskal rank, there exists a K ⊆ {1, . . . , N } with |K| = s + 1 such that {φk }k∈K is linearly dependent. Without loss of generality assume that 1 ∈ K. Note that, N upon deleting H1 from {Hk }N k=1 and contracting {Hk }k=1 onto H1 , in the resulting hyperplane N 6 N arrangements {Hk }N k=2 and {H1 ∩ Hk }k=2 , the corresponding quantities r\1 := rank({φk }k=2 ), N N N s\1 := kr({φk }k=2 ) and r/1 := rank({PH1 φk }k=2 ), s/1 := kr({PH1 φk }k=2 ), respectively, may, in general, change. Specifically, as {φk }k∈K is linearly dependent and 1 ∈ K, it is immediate that r\1 = r and moreover, since r < s, we have s\1 ≥ s. Now by the rank–nullity theorem, we have for every K/1 ⊆ {2, . . . , N }, dimR spanR {PH1 φk }k∈K/1 = dimR spanR {φk }k∈K/1 − dimR H1⊥ ∩ spanR {φk }k∈K/1 = dimR spanR {φk }k∈K/1 − dimR spanR ({φ1 }) ∩ spanR {φk }k∈K/1 = dimR spanR {φk }k∈K/1 ∪{1} − 1. Setting K/1 = {2, . . . , N } and K/1 = K \ {1}, we can deduce that r/1 = r − 1 and s/1 = s − 1, respectively. To complete the induction step, we consider two cases s ≡ s\1 (mod 2) and s ̸≡ s\1 (mod 2). Case 1: s ≡ s\1 (mod 2). We compute N X

|Ot ({Hk }N k=1 )| =

N X

N −1 X

|Ot ({Hk }N k=2 )| +

t=s+2 (t−s) is even

|Ot−1 ({H1 ∩ Hk }N k=2 )| (2.14)

t=s+2 (t−s) is even

N X

|Ot ({Hk }N k=2 )| +

|Ot ({H1 ∩ Hk }N k=2 )|

t=(s−1)+2 (t−(s−1)) is even

N −1 X

|Ot ({Hk }N k=2 )| +

t=s\1 +2 (t−s\1 ) is even

N −1 X

|Ot ({H1 ∩ Hk }N k=2 )|

t=s/1 +2 (t−s/1 ) is even

(2.15) ≤

N −1 X

|Et ({Hk }N k=2 )| +

|Et ({H1 ∩ Hk }N k=2 )|

t=s\1 +1 (t−s\1 ) is odd

t=s/1 +1 (t−s/1 ) is odd

N −1 X

|Et ({Hk }N k=2 )| +

t=s\1 +1 (t−s\1 ) is odd 6

N −1 X

|Et−1 ({H1 ∩ Hk }N k=2 )|

t=s+1 (t−s) is odd

The subscripts \1 and /1 refer to deletion and contraction of H1 , respectively.

(2.16)

K. Häberle and H. Bölcskei N X

≤

t=s+1 (t−s) is odd N X

N X

|Et ({Hk }N k=2 )| +

|Et−1 ({H1 ∩ Hk }N k=2 )|

(2.17)

t=s+1 (t−s) is odd

|Et ({Hk }N k=1 )|,

(2.18)

t=s+1 (t−s) is odd

where (2.14) is by (2.13). In (2.15), we used that |Ot ({Hk }N k=2 )| = 0 for t ≤ s\1 and s ≡ s\1 (mod 2). The first term in (2.16) follows from the induction hypothesis (2.10) applied with −1 N −1 {H̃k }N k=1 = {Hk }k=2 , s̃ = s\1 , and r̃ = r\1 whenever s\1 < r\1 . If s\1 = r\1 , we know from (2.4) that N −1 X

|Ot ({Hk }N k=2 )| =

t=s\1 +2 (t−s\1 ) is even

N −1 X

|Et ({Hk }N k=2 )|.

(2.19)

t=s\1 +1 (t−s\1 ) is odd

−1 Now, for the second term in (2.16) the induction hypothesis (2.10) is employed with {H̃k }N k=1 = −1 {H1 ∩ Hk }N k=2 , s̃ = s/1 = s − 1, and r̃ = r/1 = r − 1 whenever s/1 ≥ 2. For the case s/1 = 1, i.e., N {H1 ∩ Hk }k=2 are not distinct, we argue as follows. Suppose that {H1 ∩ Hk }N k=2 are ordered such N n that {H1 ∩ Hk }k=2 are distinct and each of {H1 ∩ Hk }k=n+1 is identical to one of the first (n − 1), for some n ∈ {2, . . . , N − 1}. Then, by assumption, for H1 ∩ Hn+1 , there is an ℓ ∈ {2, . . . , n} such that H1 ∩ Hn+1 = H1 ∩ Hℓ . Considering subsets of {H1 ∩ Hk }N k=2 containing H1 ∩ Hn+1 but , for each such subset containing H ∩ H there is one identical lacking none of {H1 ∩ Hn+2 }N 1 ℓ k=n+2 SN −1 H1 ∩ Hℓ . Then, if one subset of such a pair belongs to t=s/1 +2, (t−s/1 ) even Ot ({H1 ∩ Hk }N k=2 ), SN −1 N the other one of this pair is in t=s/1 +1, (t−s/1 ) odd Et ({H1 ∩ Hk }k=2 ). Using this cancellation and

repeating this argument with each of {H1 ∩ Hk }N k=n+2 , we arrive at the equivalence      

N −1 X

|Ot ({H1 ∩ Hk }N k=2 ) ≤

  )| |Et−1 ({H1 ∩ Hk }N k=2  

t=s/1 +1 (t−s/1 ) is odd

t=s/1 +2 (t−s/1 ) is even

   ⇐⇒  

 n−1 X

n−1 X

|Ot ({H1 ∩ Hk }nk=2 ) ≤

t=s̄/1 +2 (t−s̄/1 ) is even

(2.20)

  |Et−1 ({H1 ∩ Hk }nk=2 )| , 

t=s̄/1 +1 (t−s̄/1 ) is odd

where s̄/1 := kr({PH1 φk }nk=2 ) ≥ 2. Note that r̄/1 := rank({PH1 φk }nk=2 ) = r/1 . Now to establish −1 the second term in (2.16), we apply the induction hypothesis (2.10) with {H̃k }N k=1 = {H1 ∩ n Hk }k=2 , s̃ = s̄/1 , and r̃ = r̄/1 if s̄/1 < r̄/1 ; and otherwise, if s̄/1 = r̄/1 , we apply (2.19). Finally, (2.17) holds as s\1 ≥ s and (2.18) follows from (2.12). Upon noting that the inequality in (2.16) is strict if s\1 = s, and that the inequality in (2.17) is strict if s\1 > s, we obtain N X

|Ot ({Hk }N k=1 )| <

t=s+2 (t−s) is even

N X

|Et ({Hk }N k=1 )|.

t=s+1 (t−s) is odd

Similarly, we have N X

|Ot ({Hk }N k=1 )| =

t=s+1 (t−s) is odd

N X

|Ot ({Hk }N k=2 )| +

t=s+1 (t−s) is odd

N X

|Ot−1 ({H1 ∩ Hk }N k=2 )|

t=s+1 (t−s) is odd

(2.21)

Function-Counting Theory for Low-Dimensional Data Structures N −1 X

t=s+1 (t−s) is odd

N −1 X

|Ot ({Hk }N k=2 )| +

t=s\1 +1 (t−s\1 ) is odd N −1 X

|Ot ({H1 ∩ Hk }N k=2 )|

t=(s−1)+1 (t−(s−1)) is odd

N −1 X

|Ot ({Hk }N k=2 )| +

|Ot ({H1 ∩ Hk }N k=2 )| (2.22)

t=s/1 +1 (t−s/1 ) is odd N −1 X

|Et ({Hk }N k=2 )| +

|Et ({H1 ∩ Hk }N k=2 )| (2.23)

t=s\1 (t−s\1 ) is even

t=s/1 (t−s/1 ) is even

N −1 X

N X

|Et ({Hk }N k=2 )| +

t=s\1 (t−s\1 ) is even N X

≤

N X

|Et−1 ({H1 ∩ Hk }N k=2 )|

t=s (t−s) is even N X

|Et ({Hk }N k=2 )| +

t=s (t−s) is even

|Et−1 ({H1 ∩ Hk }N k=2 )|

(2.24)

t=s (t−s) is even

|Et ({Hk }N k=1 )|,

(2.25)

t=s (t−s) is even

where, as in the preceding derivation, in (2.21) we used (2.13), and (2.22) holds as |Ot ({Hk }N k=2 )| = 0 for t ≤ s\1 , upon noting that s ≡ s\1 (mod 2). Whenever s\1 < r\1 , the first N −1 −1 term in (2.23) follows from the induction hypothesis (2.11) with {H̃k }N k=1 = {Hk }k=2 , s̃ = s\1 , and r̃ = r\1 . If s\1 = r\1 , we have, by (2.4) and the fact that C(N − 1, s\1 − 1) < C(N − 1, s\1 ) whenever N − 1 ≥ s\1 ,   −1  NX  |Ot ({Hk }N k=2 )| <  t=s\1 +1

N −1 X

t=s\1 (t−(s\1 −1)) is odd

N −1 t

   ⇐⇒  

    

N −1 X

|Ot ({Hk }N k=2 )| <

  )| |Et ({Hk }N k=2  . 

(2.26)

t=s\1 (t−s\1 ) is even

t=s\1 +1 (t−s\1 ) is odd

Note that N − 1 ≥ s\1 is satisfied whenever s\1 = r\1 = r as s < r. The second term in (2.23) is −1 N −1 obtained by applying the induction hypothesis (2.11) with {H̃k }N k=1 = {H1 ∩ Hk }k=2 , s̃ = s/1 , and r̃ = r/1 whenever s/1 ≥ 2. If s/1 = 1, we employ the analogous cancellation argument as in (2.20) with (2.26) in case s̄/1 = r̄/1 . Finally, (2.24) follows as s\1 ≥ s, and (2.25) is a consequence of (2.12). Case 2: s ̸≡ s\1 (mod 2). It holds that N X

|Ot ({Hk }N k=1 )| =

t=s+2 (t−s) is even

N X

|Ot ({Hk }N k=2 )| +

t=s+2 (t−s) is even

N −1 X

|Ot ({Hk }N k=2 )| +

t=s+2 (t−s) is even

N X

|Ot−1 ({H1 ∩ Hk }N k=2 )|

t=s+2 (t−s) is even N −1 X

|Ot ({H1 ∩ Hk }N k=2 )|

t=(s−1)+2 (t−(s−1)) is even

K. Häberle and H. Bölcskei

N −1 X

|Ot ({Hk }N k=2 )| +

t=s\1 +1 (t−s\1 ) is odd

N −1 X

|Et ({Hk }N k=2 )| +

N −1 X

|Et ({H1 ∩ Hk }N k=2 )|

t=s\1 (t−s\1 ) is even

t=s/1 +1 (t−s/1 ) is odd

N −1 X

|Et ({Hk }N k=2 )| +

N X

(2.28)

|Et−1 ({H1 ∩ Hk }N k=2 )|

t=s+1 (t−s) is odd N X

|Et ({Hk }N k=2 )| +

t=s+1 (t−s) is odd

|Ot ({H1 ∩ Hk }N k=2 )| (2.27)

t=s/1 +2 (t−s/1 ) is even

t=s\1 (t−s\1 ) is even

≤

N −1 X

|Et−1 ({H1 ∩ Hk }N k=2 )|

(2.29)

t=s+1 (t−s) is odd

|Et ({Hk }N k=1 )|,

t=s+1 (t−s) is odd

where (2.27) follows as |Ot ({Hk }N k=2 )| = 0 for t ≤ s\1 and s ̸≡ s\1 (mod 2). For the first term −1 N −1 in (2.28), we apply the induction hypothesis (2.11) with {H̃k }N k=1 = {Hk }k=2 , s̃ = s\1 , and r̃ = r\1 whenever s\1 < r\1 , and use (2.26) otherwise. The second term in (2.28) is by the N −1 −1 induction hypothesis (2.10) with {H̃k }N k=1 = {H1 ∩ Hk }k=2 , s̃ = s/1 , and r̃ = r/1 if s/1 ≥ 2. For s/1 = 1, the same cancellation argument as in (2.20) is employed. In (2.29) we used that s\1 ≥ s and s ̸≡ s\1 (mod 2). Finally, we compute N X

|Ot ({Hk }N k=1 )| =

t=s+1 (t−s) is odd

N X

t=s+1 (t−s) is odd

N −1 X

≤

N −1 X

|Ot ({Hk }N k=2 )| +

|Ot ({H1 ∩ Hk }N k=2 )|

t=(s−1)+1 (t−(s−1)) is odd

N −1 X

|Ot ({Hk }N k=2 )| +

N −1 X

|Ot ({H1 ∩ Hk }N k=2 )| (2.30)

t=s\1 +2 (t−s\1 ) is even

t=s/1 +1 (t−s/1 ) is odd

N −1 X

|Et ({Hk }N k=2 )| +

|Et ({H1 ∩ Hk }N k=2 )|

t=s\1 +1 (t−s\1 ) is odd

t=s/1 (t−s/1 ) is even

N −1 X

N X

|Et ({Hk }N k=2 )| +

t=s (t−s) is even

N X

|Et ({Hk }N k=2 )| +

N X

|Et ({Hk }N k=1 )|,

t=s (t−s) is even

(2.31)

|Et−1 ({H1 ∩ Hk }N k=2 )|

t=s\1 +1 (t−s\1 ) is odd

t=s (t−s) is even

|Ot−1 ({H1 ∩ Hk }N k=2 )|

t=s+1 (t−s) is odd

N X

|Ot ({Hk }N k=2 )| +

|Et−1 ({H1 ∩ Hk }N k=2 )|

t=s (t−s) is even

(2.32)

Function-Counting Theory for Low-Dimensional Data Structures

where in (2.30), we used that |Ot ({Hk }N k=2 )| = 0 for t ≤ s\1 and s ̸≡ s\1 (mod 2). The first −1 N −1 term in (2.31) is by the induction hypothesis (2.10) with {H̃k }N k=1 = {Hk }k=2 , s̃ = s\1 , r̃ = r\1 if s\1 < r\1 and by (2.19) if s\1 = r\1 . The second term in (2.31) follows from the induction −1 N −1 hypothesis (2.11) with {H̃k }N k=1 = {H1 ∩ Hk }k=2 , s̃ = s/1 , and r̃ = r/1 if s/1 ≥ 2. Whenever s/1 = 1, we use the analogous cancellation argument as in (2.20) with (2.26) in case s̄/1 = r̄/1 . Finally, (2.32) holds as s\1 ≥ s and s ̸≡ s\1 (mod 2). This completes the induction step in the proof of (2.2) and (2.9). 2.2

Proof of Lemma 2.4

Proof. The proof of (2.3) is again by induction on the number of hyperplanes N , employing the deletion–contraction argument in the induction step. In the regime 2 ≤ s < r, we consider for the base case N = 4, as above, the hyperplanes {Hk }4k=1 with Hk = {φk }⊥ , where {Hk }3k=1 are in general position and H4 is such that, e.g., φ4 = φ1 + φ2 . Then, s = 2, r = 3, and |E0 | = 1,

|E1 | = 4,

|E2 | = 6,

|E3 | = 3,

|E4 | = 0,

|O0 | = 0, |O1 | = 0, |O2 | = 0, |O3 | = 1, |O4 | = 1. Thus, (2.3) holds in the form |E4 | < |O3 |, verifying the base case. Next, suppose that (2.3) is −1 true for an arbitrary set of N − 1 hyperplanes, {H̃k }N k=1 , i.e., N −1 X

r̃ X

−1 |Et ({H̃k }N k=1 )| <

t=s̃+1

t=r̃+1 (t−r̃) is odd

N −1 X

−1 |Ot ({H̃k }N k=1 )| +

−1 |Ot ({H̃k }N k=1 )|,

(2.33)

t=r̃+2 (t−r̃) is even

−1 N −1 N −1 where s̃ := kr({φ̃k }N k=1 ) and r̃ := rank({φ̃k }k=1 ) with 2 ≤ s̃ < r̃. Furthermore, {φ̃k }k=1 are such that H̃k = {φ̃k }⊥ , for all k ∈ {1, . . . , N − 1}. Recall that there exists a K ⊆ {1, . . . , N } with |K| = s + 1 such that {φk }k∈K is linearly dependent. We again assume without loss of generality that 1 ∈ K, so that s\1 ≥ s, r\1 = r, s/1 = s − 1, and r/1 = r − 1. We compute N X

N X

|Et | =

t=r+1 (t−r) is odd

t=r+1 (t−r) is odd N −1 X

N X

|Et ({Hk }N k=2 )| +

N −1 X

|Et ({Hk }N k=2 )| +

< |Ot ({Hk }N k=2 )| + t=s\1 +1

N −1 X

|Ot ({Hk }N k=2 )|

(2.35)

t=r\1 +2 (t−r\1 ) is even

N −1 X

/1 X

+ |Ot ({H1 ∩ Hk }N k=2 )| + t=s/1 +1 ≤ |Ot ({Hk }N k=2 )| + t=s+1

|Et ({H1 ∩ Hk }N k=2 )|

t=r/1 +1 (t−r/1 ) is odd

\1 X

r X

(2.34)

t=r+1 (t−r) is odd

t=r\1 +1 (t−r\1 ) is odd

r X

|Et−1 ({H1 ∩ Hk }N k=2 )|

|Ot ({H1 ∩ Hk }N k=2 )|

t=r/1 +2 (t−r/1 ) is even

N −1 X

|Ot ({Hk }N k=2 )|

t=r+2 (t−r) is even

+ |Ot−1 ({H1 ∩ Hk }N k=2 )| + t=s+1

N X t=r+2 (t−r) is even

|Ot−1 ({H1 ∩ Hk }N k=2 )|

(2.36)

K. Häberle and H. Bölcskei r X

N X

|Ot ({Hk }N k=1 )| +

t=s+1

|Ot ({Hk }N k=1 )|,

(2.37)

t=r+2 (t−r) is even

where (2.34) is by (2.12). If s\1 < r\1 , the first two terms in (2.35) follow from the induction −1 N −1 hypothesis (2.33) applied with {H̃k }N k=1 = {Hk }k=2 , s̃ = s\1 , r̃ = r\1 ; if s\1 = r\1 , they follow from (2.19). The third and fourth terms in (2.35) are by the induction hypothesis (2.33) −1 N −1 with {H̃k }N k=1 = {H1 ∩ Hk }k=2 , s̃ = s/1 , and r̃ = r/1 whenever s/1 ≥ 2. For s/1 = 1, assume without loss of generality that {H1 ∩ Hk }nk=2 are distinct and each of {H1 ∩ Hk }N k=n+1 is a duplicate of one of the first (n − 1) with n ∈ {2, . . . , N − 1}. In particular, for H1 ∩ Hn+1 , there exists an ℓ ∈ {2, . . . , n} such that H1 ∩ Hn+1 = H1 ∩ Hℓ . Consider now subsets N of {H1 ∩ Hk }N k=2 that contain H1 ∩ Hn+1 but exclude any of {H1 ∩ Hk }k=n+2 . Then, these subsets naturally form pairs; namely, for every such subset which includes H1 ∩ Hℓ , there is a corresponding subset S −1that is identical but does notNcontain H1 ∩ Hℓ . Therefore, if one subset of such a pair is in N t=r/1 +1, (t − r/1 ) odd Et ({H1 ∩ Hk }k=2 ), the other subset of this pair belongs to SN −1 N N t=r/1 , (t − r/1 ) even Ot ({H1 ∩ Hk }k=2 ). Applying this argument to each of {H1 ∩ Hk }k=n+2 , we obtain the implication     

n−1 X

r̄

|Et ({H1 ∩ Hk }nk=2 )| ≤

t=r̄/1 +1 (t−r̄/1 ) is odd

/1 X

|Ot ({H1 ∩ Hk }nk=2 )|

t=s̄/1 +1

 n−1 X

(2.38)

  |Ot ({H1 ∩ Hk }nk=2 )| 

t=r̄/1 +2 (t−r̄/1 ) is even

   =⇒  

N −1 X

|Et ({H1 ∩ Hk }N k=2 )| <

t=r/1 +1 (t−r/1 ) is odd

/1 X

|Ot ({H1 ∩ Hk }N k=2 )|

t=s/1 +1

 N −1 X

(2.39)

  |Ot ({H1 ∩ Hk }N k=2 )| . 

t=r/1 +2 (t−r/1 ) is even

Here, s̄/1 := kr({PH1 φk }nk=2 ) ≥ 2 and r̄/1 := rank({PH1 φk }nk=2 ) = r/1 . The inequality in (2.39) is strict because |Os/1 +1 ({H1 ∩Hk }N k=2 )| > 0. Note that (2.38) holds by the induction hypothesis (2.33) if s̄/1 < r̄/1 and by (2.19) if s̄/1 = r̄/1 . This shows (2.35). In (2.36), we used that s ≤ s\1 , and finally, (2.37) is by (2.13).

Separation on low-dimensional datasets

The framework introduced in the previous section applies to arbitrary subsets E, as the presented results are of pure combinatorial nature. In this section, we particularize E to subsets of RM that exhibit low-dimensional structure in a measure-theoretic sense, i.e., LM (E) = 0. More precisely, we consider sets E ⊆ RM which are Hs -measurable and of positive and σ-finite Hs -measure for some s ≥ 0. Under these conditions, this section addresses the problem of determining the number of Φ-separable dichotomies of an N -point set F ⊆ E. The particularization of E to Hs -measurable sets of positive Hs -measure is motivated by the following considerations:

Function-Counting Theory for Low-Dimensional Data Structures

(i) This measure-theoretic notion of intrinsic low-dimensionality includes several examples which are often assumed to be reasonable models for real-world high-dimensional data; namely, sets of sparse vectors (i.e., union of linear subspaces), submanifolds, as well as union of submanifolds, see, e.g., [5, 10, 11, 12, 14]. (ii) Addressing the problem of counting the number of Φ-separable dichotomies of N -point sets from a measure-theoretical viewpoint allows us to exclude N -point sets which yield degenerate configurations. This, in turn, enables us to understand the factors that affect the number of Φ-separable dichotomies of most N -point sets, in terms of the properties of E. (iii) It lays the foundation for studying how the low-dimensional structure of the dataset affects the separation capacity, a measure-theoretic quantity. Our analysis proceeds through a chain of increasingly rich geometries for the set E. We begin by deriving function-counting results for homogeneous linear separation on sets of s-sparse vectors in RM (i.e., sets of finite unions of s-dimensional linear subspaces). This analysis makes explicit how the sparsity parameter s affects the number of homogeneously linearly separable dichotomies. Motivated by this result, we then extend our analysis to homogeneous linear separation on so-called countably Hs -rectifiable sets. The latter are sets which can be decomposed as countable unions of s-dimensional C 1 -submanifolds up to a set of Hs -measure zero and thus constitute a natural (and geometrically richer) generalization of the sets of s-sparse vectors. Finally, the function-counting results for countably Hs -rectifiable sets let us treat Φ-separability on general Hs -measurable sets with positive and σ-finite Hs -measure. 3.1

Sparse vectors

Sparse models for datasets naturally arise in the context of representations based on bases or frames (i.e., redundant spanning sets [15, 16]) in which a given vector (signal) can be written as a linear combination of only a few basis or frame elements. For example, natural images often exhibit sparsity when represented in wavelet bases [16]. In this subsection, we aim to determine the number of homogeneously separable dichotomies of an N -point set consisting of vectors that are sparse in a given basis or frame. We start with sparsity in an arbitrary basis for RM , and then generalize to sparsity in frames. The former allows for a simple and clean statement of the result and serves as a natural stage for developing the general ideas. 3.1.1

Bases

M Let Ξ = {ξk }M k=1 be an arbitrary basis for R , M ∈ N, and fix s ∈ {1, . . . , M }. The set of s-sparse vectors E is given by the union of J := M distinct linear subspaces Ej := s S spanR ({ξk }k∈Sj ), for j ∈ {1, . . . , J}, each of dimension s, i.e., E = Jj=1 Ej . Here, {Sj }Jj=1 denotes the set of pairwise distinct subsets of {1, . . . , M } with |Sj | = s, j ∈ {1, . . . , J}. In words, f ∈ RM is s-sparse (i.e., f ∈ E) if it can be written as a linear combination of at most s elements of Ξ. We further denote by πj : Ej → Rs the map from the linear subspace Ej , j ∈ {1, . . . , J}, to the space of expansion coefficients, i.e.,

πj :

s X

ci ξkj,i 7→ c

(3.1)

i=1

with the labeling Sj = {kj,i }si=1 . Consider now an N -point set F := {f1 , . . . , fN } ⊂ E. We write Fj := F ∩ Ej for the points of F in the subspace Ej , j ∈ {1, . . . , J}, and make the following assumption. The shift from general position to this assumption allows the intrinsic structure to surface in the dichotomy count.

K. Häberle and H. Bölcskei

Assumption 3.1. For every j ∈ {1, . . . , J}, assume that, whenever Fj ̸= ∅, (b-i) Fj is in πj -general position, (b-ii) Fj ∩ Ei = ∅, for every i ∈ {1, . . . , J} with i ̸= j. Item (b-i) ensures that the coefficient vectors of the vectors in Fj are in general position, while Item (b-ii) excludes point sets consisting of (s − 1)-sparse vectors. As we shall see later, in Remark 4.9, Assumption 3.1 is very mild in the sense that for (Hs )N -a.e. N -tuple (f1 , . . . , fN ) ∈ E N , the corresponding N -point set {f1 , . . . , fN } satisfies Assumption 3.1. Our objective is to determine the number of homogeneously linearly separable dichotomies of F under Assumption 3.1. The particular case where M = 2 and s = 1 is illustrated in Fig. B.1, and one may observe that here the number of homogeneously separable dichotomies of F is given by 4 irrespective of N . For general M and s, however, counting the homogeneously linearly separable dichotomies becomes more challenging. To this end, let Nj := |Fj |, j ∈ {1, . . . , J}, so P that N = Jj=1 Nj , and set N := (Nj )Jj=1 . We shall refer to N as the configuration associated with F . With Theorem B.5 as a cornerstone, we obtain the following dichotomy count. Proposition 3.2 (Sparsity in a basis). Under Assumption 3.1 the number of homogeneously linearly separable dichotomies of F is given by N

Csp,b (N , M, s) := 2 − 2

N X

X N , ν sp,b

t=s+1 ν∈I

where Itsp,b := {ν ∈ NJ0 : |ν| = t, Υsp,b (ν) ̸≡ t (mod 2)} with7   X  [ Υsp,b (ν) := min νj + Sj , ν = (νj )Jj=1 ∈ NJ0 .  s⊆supp(ν)  c j∈s

j∈s

Remark 3.3 (Graph-theoretic interpretation). The quantity Υsp,b (ν) admits a natural interpretation in terms of a minimum weighted vertex cover in a bipartite graph. Namely, consider the bipartite graph G = (X, Y ; L), illustrated in Fig. 3.1, where • X = {x1 , . . . , xJ } is a vertex set with each xj of weight νj , j ∈ {1, . . . , J}, • Y = {y1 , . . . , yM } is a vertex set disjoint from X with each vertex ym carrying weight 1, m ∈ {1, . . . , M }, and • the edge set L is defined such that (xj , ym ) ∈ L whenever m ∈ Sj . In particular, each xj ∈ X is connected to exactly s distinct vertices in Y . A minimum weighted vertex cover of G is a set of vertices C ⊆ X ∪ Y such that every edge in L has at least one endpoint in C, and the sum of the weights of all vertices in C is as small as possible. The set Itsp,b is then the set of all ν ∈ NJ0 with |ν| = t for which the resulting minimum vertex cover Υsp,b (ν) differs in parity from t. Proof of Proposition 3.2. The proof follows from particularizing Proposition 3.9. Namely, as Ej = spanR ({ξk }k∈Sj ) and Ξ is a basis, we can write   [ X dimR  Ej  = Sj . (3.2) j∈sc

Here, sc denotes the complement of s in supp(ν).

j∈sc

Function-Counting Theory for Low-Dimensional Data Structures X

x1 ν1

x1 4

x2 ν2

y1 1

x2 0

y1 1

x3 ν3

y2 1

x3 3

y2 1

x4 ν4

y3 1

x4 0

y3 1

x5 ν5

y4 1

x5 0

y4 1

x6 ν6

x6 0

(a)

(b)

Figure 3.1: Illustration of the bipartite graph G = (V1 , V2 ; L), whose minimum weighted vertex cover equals Υsp,b (ν). a Bipartite graph with M = 4, s = 2, and J = 42 = 6. b Minimum weighted vertex cover highlighted in green for ν = (4, 0, 3, 0, 0, 0)T .

Let us discuss the ramifications of Proposition 3.2. The number of homogeneously linearly separable dichotomies of F , Csp,b (N , M, s), depends only on N and not on the specific location of the points in F within each subspace Ej , j ∈ {1, . . . , J}. As the points in F are, by Assumption 3.1, not (s − 1)-sparse with respect to Ξ the assignment of the points to the subspaces {Ej }Jj=1 is unique. It is important to highlight that Csp,b (N , M, s) is independent of the choice of the basis Ξ. Furthermore, Proposition 3.2 can be leveraged to easily compute the number of homogeneously linearly separable dichotomies for the special case where all points lie in one subspace, as will be carried out in the next remark. Remark 3.4. If Nj0 = N for some j0 ∈ {1, . . . , J} and Nj = 0 for j ̸= j0 , the number of homogeneously linearly separable dichotomies is given by C(N, s). Indeed, since Nj = 0 for j ̸= j0 , it holds that Nνjj = 0 if νj > 0 for j ̸= j0 . Thus, for t ≥ s + 1, it suffices to consider the J-tuple (ν1 , . . . , νJ ) where νj = 0 for j ̸= j0 and νj0 = t. Upon noting that this J-tuple belongs to Itsp,b if and only if s ̸≡ t (mod 2), we obtain N X

Csp,b (N , M, s) = 2 − 2

t=s+1 (t−s) is odd N X

=2 −2

t=s+1 (t−s) is odd N

=2 −2

t=0

(3.3)

N X N −1 t=0 s−1 X

N −1 N −1 + t t−1

N X N −1 t=s

N t

t N −1 t

−2

N X N −1 t=s

(3.4)

= C(N, s), where (3.3) and (3.4) follow from the well-known identities

(3.5) N t

N −1 t

N −1 t−1

and 2N −1 =

K. Häberle and H. Bölcskei

PN −1 N −1 t=0

, respectively.

Finally, we will discuss the influence of the ambient dimension M and the sparsity parameter s on Csp,b (N , M, s) in the next two paragraphs. Before doing so, note that from (3.5) one can already deduce that, for the special case in Remark 3.4, Csp,b (N , M, s) is independent of M and nondecreasing in s. ′ Ambient dimension. Let M ′ ∈ N with M ≤ M ′ , and set J ′ := Ms . Note that J ≤ J ′ . ′ Denoting by {Sj′ }Jj=1 all pairwise distinct subsets of {1, . . . , M ′ } of cardinality s, we order these S S subsets such that for every s ⊆ {1, . . . , J}, | j∈s Sj′ | = | j∈s Sj |. Let N ∈ NJ0 . To investigate the effect of the ambient dimension M on Csp,b (N , M, s), consider the following embedding of ′ N into NJ0 , given by ′

ι : NJ0 → NJ0 , N 7→ (N T , 0, . . . , 0 )T . | {z }

(3.6)

(J ′ − J) times

Lemma 3.5 (Independence of the ambient dimension). For M, M ′ ∈ N with M ≤ M ′ , s ∈ {1, . . . , M }, and N ∈ NJ0 , it holds that Csp,b (N , M, s) = Csp,b (ι(N ), M ′ , s). ′

Proof. To see this, simply note that for every ν ∈ NJ0 , we have

(3.7)

ι(N ) ν

= 0 whenever supp(ν) ̸⊆ S

′ supp(ι(N )). Moreover, the ordering of the sets {Sj′ }Jj=1 ensures that | j : νj >0 Sj′ | = | j : νj >0 Sj |, ′ for every ν ∈ NJ0 with supp(ν) ⊆ supp(ι(N )) ⊆ {1, . . . , J}. This, together with the definition of Csp,b (ι(N ), M ′ , s), establishes (3.7).

We can thus conclude that the number of homogeneously linearly separable dichotomies of an N -point subset of the set of s-sparse vectors is independent of the ambient dimension, when embedded in the sense of (3.6). Sparsity parameter. Let s′ ∈ {1, . . . , M } with s ≤ s′ . We now set J ′ := M s′ , and ′ denote by {Sj′ }Jj=1 all pairwise distinct subsets of {1, . . . , M } of cardinality s′ . Note that J ≤ J ′ does not necessarily hold. Given a configuration N = (Nj )Jj=1 ∈ NJ0 , our goal is to construct a representation of N that is compatible with the set of s′ -sparse vectors. This will allow us to analyze the effect of the sparsity parameter s on Csp,b (N , M, s). To this end, consider the transformation P T P ′ N , . . . , N ϖ : NJ0 → NJ0 , N 7→ . (3.8) j j j∈s1 j∈sJ ′ ′

Here, {sk }Jk=1 ⊆ {1, . . . , J} constitute a disjoint decomposition8 of {1, . . . , J} and are defined according to the following rule: For each j ∈ {1, . . . , J} and k ∈ {1, . . . , J ′ }, (j ∈ sk ) ⇐⇒

Sj ⊆ Sk′ and j ∈ /

k−1 [

! sℓ

(3.9)

ℓ=1

with the convention

ℓ=1 sℓ = ∅.

Lemma 3.6 (Monotonicity in the sparsity parameter). For M ∈ N, s, s′ ∈ {1, . . . , M } with s ≤ s′ , and N ∈ NJ0 , we have Csp,b (N , M, s) ≤ Csp,b (ϖ(N ), M, s′ ). To prove this lemma, we require the following result. 8

Specifically, we allow sk = ∅, k ∈ {1, . . . , J ′ }.

(3.10)

Function-Counting Theory for Low-Dimensional Data Structures

′

Lemma 3.7. Let {Ēj }Jj=1 and {Ēk′ }Jk=1 be linear subspaces of RM , and suppose that there exists P P a map ϕ : {1, . . . , J} → {1, . . . , J ′ } is such that dimR ( j∈s Ēj ) ≤ dimR ( k∈ϕ(s) Ēk′ ), for all s ⊆ {1, . . . , J}. Then, for every N ∈ N and every N ∈ NJ0 with |N | = N , N X X N

t=1 ν∈It

≥

N X X ϖ̄(N ) , ν′ ′ ′

(3.11)

t=1 ν ∈It

P where It := {ν ∈ NJ0 : |ν| = t, Υ(ν) ̸≡ t (mod 2)} with Υ(ν) = mins⊆supp(ν) { j∈s νj + P ′ dimR ( j∈sc Ēj )}, for ν ∈ NJ0 , and It′ := {ν ′ ∈ NJ0 : |ν ′ | = t, Υ′ (ν ′ ) ̸≡ t (mod 2)} with P P ′ ′ Υ′ (ν ′ ) = mins⊆supp(ν)′ { k∈s νk′ + dimR ( k∈sc Ēk′ )}, for ν ′ ∈ NJ0 . Here, ϖ̄ : NJ0 → NJ0 is the map of the form (3.8) with sk := ϕ−1 ({k}). Proof. The proof of (3.11) is by induction on N . For the base case N = 1, let j0 be the unique element in supp(N ). By assumption, dimR (Ēj0 ) ≤ dimR (Ēk′ 0 ), where k0 = ϕ(j0 ). Denoting by ′ ej0 ∈ NJ0 and e′k0 ∈ NJ0 the multi-indices whose j0 th and k0 th entries equal 1, respectively, and all others are 0, we have Υ(ej0 ) = min 1, dimR Ēj0 ≤ min 1, dimR Ēk′ 0 = Υ′ (e′k0 ). Thus, if Υ′ (e′k0 ) ̸≡ 1 (mod 2), i.e., Υ′ (e′k0 ) = 0, then Υ(ej0 ) ̸≡ 1 (mod 2). Upon noting that ϖ̄(ej0 ) = e′k0 , it follows that ej0 ∈ I1 if ej0 ∈ ϖ̄−1 (I1′ ), and hence X N ν∈I1

X ϖ̄(N ) N = , ν ν′ ′ ′ ′

≥

ν∈ϖ̄−1 (I1 )

ν ∈I1

verifying the base case. Now suppose (3.11) is true for N − 1. To establish the induction step, let j0 ∈ supp(N ) /j and k0 = ϕ(j0 ). We further introduce It 0 := {ν ∈ NJ0 : |ν| = t, Υ/j0 (ν) ̸≡ t (mod 2)} and P ′ ′/k It 0 := {ν ′ ∈ NJ0 : |ν ′ | = t, Υ′/k0 (ν ′ ) ̸≡ t (mod 2)}, where Υ/j0 (ν) = mins⊆supp(ν) { j∈s νj + P P P dimR ( j∈sc Pj0 Ēj )}, for ν ∈ NJ0 , and Υ′/k0 (ν ′ ) = mins⊆supp(ν ′ ) { k∈s νk′ + dimR ( k∈sc Pk′ 0 Ēk′ )}, ′ for ν ′ ∈ NJ0 . Here, Pj0 and Pk′ 0 denote the orthogonal projections onto {f j0 }⊥ and {f ′k0 }⊥ for some f j0 ∈ Ēj0 \ U j0 and f ′k0 ∈ Ēk′ 0 \ V k0 . Here,  U j0 :=

[ s : Ēj0 ̸⊆



Ēj0 ∩

Ēj  , and V k0 :=

Ēk′ 0 ∩

P s : Ēk′ ̸⊆ k∈s Ēk′

j∈s

j∈s Ēj

[ 0

Ēk′

k∈s

As a linear space cannot be covered by finitely many proper linear subspaces, the sets Ēj0 \ U j0 and Ēk′ 0 \ V k0 are non-empty. This choice of f j0 and f ′k0 ensures that (i) for every s ⊆ {1, . . . , J},   f j0 ∈

 X





Ēj  ⇐⇒ Ēj0 ⊆

j∈s

Ēj  ,

j∈s

(ii) and for every s ⊆ {1, . . . , J ′ }, ! f ′k0 ∈

X k∈s

Ēk′

! ⇐⇒

Ēk′ 0 ⊆

X k∈s

Ēk′

K. Häberle and H. Bölcskei

Items (i) and (ii) can be leveraged to show for every s ⊆ {1, . . . , J},  dimR 

 X



 X

Pj0 Ēj  ≤ dimR 

j∈s

P̄k′ 0 Ek′  .

(3.12)

k∈ϕ(s)

Indeed, we have, by the rank–nullity theorem and Item (i),       X X X dimR  Pj0 Ēj  = dimR  Ēj  − dimR spanR {f j0 } ∩ Ēj  j∈s

j∈s

  X = dimR  Ēj  − 1 j∈s

{Ēj0 ⊆

j∈s Ēj

and likewise,  dimR 

 X



Pk′ 0 Ēk′  = dimR 

k∈ϕ(s)

 X

Ēk′  − 1nĒ ′ ⊆P k0

k∈ϕ(s)

′ k∈ϕ(s) Ēk

so that (3.12) holds whenever  Ēk′ ⊆ 0

 X

Ēk′ and dimR 

 X



Ēj  = dimR 

j∈s

k∈ϕ(s)

 X



Ēk′  =⇒ Ēj0 ⊆

 X

Ēj  .

(3.13)

j∈s

k∈ϕ(s)

Now note that whenever the left-hand side (LHS) of the implication in (3.13) is true, we have  dimR 

 X



 X

Ēj  ≤ dimR 

j∈s∪{j0 }

Ēk′ 

k∈ϕ(s∪{j0 })



 X

= dimR 

Ēk′ 

k∈ϕ(s)∪{k0 }

 = dimR 

 X

Ēk′ 

k∈ϕ(s)

 = dimR 

 X

Ēj  ,

j∈s

and the right-hand side (RHS) of (3.13) follows. This establishes (3.12). We next prove that for t ∈ N,

ν ∈ It−10

⇐⇒

(ν + ej0 ) ∈ It ,

(3.14)

′/k

⇐⇒

(ν ′ + e′k0 ) ∈ It′ ,

(3.15)

and ν ′ ∈ It−10

Function-Counting Theory for Low-Dimensional Data Structures

where ej0 ∈ NJ0 denotes the multi-index whose j0 th entry equals 1 and all others are 0. To see that (3.14) holds, note that9     X  X Υ(ν + ej0 ) = min νj + dimR  Ēj  + 1{j0 ∈s}  s⊆supp(ν+ej )  0 j∈s j∈sc     X  X   = min νj + dimR Ēj + 1{j0 ∈s}  s⊆{1,...,J}  j∈s j∈sc     X  X = min νj + dimR  Ēj  − 1{j0 ∈sc } + 1  s⊆{1,...,J}  j∈s j∈sc      X X (3.16) = min νj + dimR  Ēj  − 1{Ēj ⊆P c Ēj } + 1 j∈s 0  s⊆{1,...,J}  j∈sc

j∈s

 X

min

s⊆{1,...,J} 



 νj + dimR 



Ēj  − dimR spanR {f j0 } ∩

j∈sc

j∈s

  Ēj  + 1  c

X j∈s

(3.17)  X

  X = min νj + dimR  Pj0 Ēj  + 1  s⊆{1,...,J}  j∈s j∈sc     X X νj + dimR  Pj0 Ēj  + 1 = min  s⊆supp(ν)  c 

j∈s

/j0

=Υ

(3.18)

j∈s

(ν) + 1.

P Indeed, (3.16) holds since j0 ∈ sc implies Ēj0 ⊆ j∈sc Ēj , and since, conversely, whenever P Ēj0 ⊆ j∈sc Ēj , the minimization allows us to include j0 ∈ sc . In (3.17), we used Item (i), and (3.18) follows from the rank–nullity theorem. This establishes (3.14). Likewise, by employing the same arguments, we obtain ( ! ) X X ′ ′ ′ ′ ′ Υ (ν + ek0 ) = min ′ νk + dimR Ēk + 1{k0 ∈s} s⊆supp(ν ′ +ek ) 0

min

( X

s⊆supp(ν ′ )

k∈sc

k∈s

!) νk′ + dimR

Pk′ 0 Ēk′

k∈sc

k∈s

= Υ′/k0 (ν ′ ) + 1 from which (3.15) follows. We are now ready to establish the induction step and, to this end, compute N X X N t=1 ν∈It

N −1 X X t=1 ν∈It

N − e j0 ν

N −1 X X t=1 ν∈It

N − e j0 ν

N X X N −e j0

t=1 ν∈It

ν − ej0

N X X N − e j0 + ν /j t=1 ν∈I

(3.19)

(3.20)

0 t−1

9 By sc we denote the complement with respect to the indexing set appearing in the minimization (here, either supp(·) or {1, . . . , J}).

K. Häberle and H. Bölcskei

N −1 X X t=1 ν∈It

≥

N −1 X

X N − e j0

(3.21)

t=1 ν∈I /j0 t

NX −1 X ϖ̄(N − ej0 ) ϖ̄(N − ej0 ) + ν′ ν′ ′/k t=1 ν ′ ∈I

ϖ̄(N ) − e′k0 ν′

N −1 X X t=1 ν ′ ∈It′

N − e j0 ν

ϖ̄(N ) − e′k0 ν′

N −1 X

t=1 ν ′ ∈I

ϖ̄(N ) − e′k0 ν′

X ϖ̄(N ) − e′ k0 ′ ν ′/k t

N X X ϖ̄(N ) − e′ k0 + ′ ν ′/k t=1 ν ′ ∈I

N −1 X X t=1 ν ′ ∈It′

(3.22)

(3.23)

0 t−1

N X X ϖ̄(N ) − e′ k0

t=1 ν ′ ∈It′

(3.24)

ν ′ − e′k0

N X X ϖ̄(N ) = , ν′ ′ ′

(3.25)

t=1 ν ∈It

where (3.19) is by Pascal’s rule, (3.20) follows from (3.14), and (3.21) holds as I0 0 = ∅. In ′ (3.22), we employed the induction hypothesis with {Ēj }Jj=1 and {Ēk′ }Jk=1 . The second term in ′ (3.22) is by the induction hypothesis particularized to {Pj0 Ēj }Jj=1 and {Pk′ 0 Ēk′ }Jk=1 , together ′/k

with (3.12). Finally, in (3.23), we used that I0 0 = ∅, (3.24) holds by (3.15), and (3.25) is again a consequence of Pascal’s rule. Proof of Lemma 3.6. The proof is immediate by Lemma 3.7 particularized to {Ej }Jj=1 and ′

{spanR ({ξk }k∈Sj′ )}Jj=1 . The map ϕ is determined by (3.9). Note that Itsp,b = 0 for t ≤ s := {ν ′ ∈ NJ0 : |ν ′ | = t, Υ′sp,b (ν ′ ) ̸≡ t (mod 2)} with and It′sp,b = 0 for t ≤ s′ ,Pwhere It′sp,b S ′ Υ′sp,b (ν ′ ) := mins⊆supp(ν ′ ) { j∈s νj′ + | j∈sc Sj′ |} for ν ′ = (νj′ )Jj=1 ∈ NJ0 . ′

Lemma 3.6 establishes that, under transformation (3.8), the number of homogeneously linearly separable dichotomies of an N -point set of the set of s-sparse vectors is nondecreasing in the sparsity parameter s. The sparsity parameter s, rather than the ambient dimension M , can therefore be interpreted as the effective complexity parameter of the dataset E, in the sense that it is the fundamental quantity which determines how many dichotomies can be realized. Next, we proceed to deriving function-counting results for the case when the dataset exhibits sparsity in frames. 3.1.2

Frames

In practical applications, sparsity typically arises with respect to frames rather than bases, as representations in redundant systems (i.e., frames) often yield sparser representations. Let now Ξ := {ξk }k∈K be a frame for RM , where K is a countable index set. That is, there exist constants 0 < A ≤ B < ∞ such that [15] A∥f ∥2 ≤

|⟨f, ξk ⟩|2 ≤ B∥f ∥2 ,

for all f ∈ RM .

(3.26)

k∈K

If K is finite, (3.26) is equivalent to simply spanR (Ξ) = RM . Fix s ∈ {1, . . . , M }, and let {Sj }j∈J be the set of all pairwise distinct index subsets Sj ⊆ K with |Sj | = s. Assume that {ξk }k∈Sj is

Function-Counting Theory for Low-Dimensional Data Structures

S linearly independent for every j ∈ J . Denote by E := j∈J Ej the set of s-sparse vectors in the frame Ξ, where Ej := spanR ({ξk }k∈Sj ). Furthermore, let πj : Ej → Rs ,

s X

ci ξkj,i 7→ c

i=1

be the map from Ej to the space of expansion coefficients with the labeling Sj = {kj,i }si=1 . Consider an N -point set F := {f1 , . . . , fN } ⊂ E, where N ∈ N. The set of points in the subspace Ej are written as Fj := F ∩ Ej , j ∈ J . Similarly to the basis case, we impose the following very mild assumption; the only difference is that in the frame case, we may have Ei = Ej for i, j ∈ J with i ̸= j. As will be shown in Remark 4.9, for (Hs )N -a.e. N -tuple (f1 , . . . , fN ) ∈ E N the corresponding N -point set {f1 , . . . , fN } satisfies this assumption. Assumption 3.8. Assume that for each j ∈ J , whenever Fj ̸= ∅, (f-i) Fj is in πj -general position, (f-ii) Fj ∩ Ei = ∅, for every i ∈ J with i ̸= j whenever Ei ̸= Ej . Informally, Item (f-i) guarantees that in each subspace Ej the points are in general position. By Item (f-ii) we ensure that no vector in F is (s − 1)-sparse, so that the assignment of the points in F to the subspaces (Ej )j∈J is unique. Writing Nj for the number of points of F which are in Ej , j ∈ J , and setting N = (Nj )j∈J , we have the following result. Proposition 3.9 (Sparsity in a frame). Under Assumption 3.8 the number of homogeneously linearly separable dichotomies of F is given by N

Csp,f (N , Ξ, s) := 2 − 2

N X

X Y Nj , νj sp,f

t=s+1 ν∈I

j∈J0

sp,f (ν) ̸≡ 0 where J0 := supp(N ) ⊆ J is a finite subset, and where Itsp,f := {ν ∈ NJ 0 : |ν| = t, Υ t (mod 2)} with    X  X 0 νj + dimR  Υsp,f (ν) := min Ej  , ν = (νj )j∈J0 ∈ NJ 0 .  s⊆supp(ν)  c j∈s

j∈s

Proof. We apply Theorem B.5, and, to this end, consider the (M − 1)-dimensional hyperplanes Hk := {fk }⊥ , k ∈ {1, . . . , N }, and count the number of even- and odd-degenerate sets of these hyperplanes, denoted by |E| and |O|, respectively. As |E| + |O| = 2N , see Remark B.6, we have, M is given by by Theorem B.5, that the number of regions into which {Hk }N k=1 divide R |E| − |O| = 2N − 2|O|.

(3.27)

It hence suffices to determine the number of odd-degenerate sets of hyperplanes. To this end, consider an arbitrary set of hyperplanes {Hk }k∈K with K ⊆ {1, . . . , N } and |K| = t, and compute ! \ dimR Hk = dimR (spanR ({fk }k∈K ))⊥ k∈K

= M − dimR (spanR ({fk }k∈K )) .

(3.28)

We first note that, byTAssumption 3.8, every set of t ≤ s vectors {fk }k∈K is linearly independent, which implies dimR k∈K Hk = M − t, and hence all sets of t hyperplanes with t ≤ s are evendegenerate. Consider next the case t ≥ s + 1, and decompose the index set K into disjoint sets10 10

Specifically, we allow Kj = ∅, j ∈ J0 .

K. Häberle and H. Bölcskei

{Kj }j∈J0 such that {fk }k∈Kj ⊂ Ej , for all j ∈ J0 . Then |Kj | =: νj is equal to the number of vectors in {fk }k∈K which belong to the s-dimensional linear subspace Ej , j ∈ J0 . Setting 0 ν = (νj )j∈J0 ∈ NJ 0 , we claim    X  X dimR (spanR ({fk }k∈K )) = min νj + dimR  (3.29) Ej  =: Υ(ν).  s⊆supp(ν)  c j∈s

j∈s

Indeed, (3.29) follows by induction on |supp(ν)|. For the base case |supp(ν)| = 1, let j0 be the unique element of supp(ν). Then, νj = 0 for all j ̸= j0 . By Assumption 3.8(f-i), we therefore get dimR (spanR ({fk }k∈K )) = dimR spanR {fk }k∈Kj0 = min{νj0 , s}. Moreover, we observe that min

 X

s⊆{j0 } 

 νj + dimR 

j∈s

  Ej  = min{νj0 , s},  c

X j∈s

which confirms the base case. Proceeding to the induction step, now assume that (3.29) holds 0 for all ν ∈ NJ 0 with |supp(ν)| ≤ r for some r ∈ {1, . . . , |J0 | − 1}. By Assumption 3.8, for every s ⊆ J0 and {kj }j∈s with kj ⊆ Kj and |kj | ≤ s, [ {fk }k∈kj is in πs -general position, (3.30) j∈s

P P ds with d Ej → Rds is the linear embedding of where πs : s := j∈s Ej into R j∈s P dimR j∈s Ej . As a result of (3.30), we have, for every j0 ∈ supp(ν), dimR (spanR ({fk }k∈K ))    + dimR spanR {fk }k∈Kj0 , dimR  = min dimR spanR {fk }k∈K\Kj0 

X j∈supp(ν)

   Ej . 

Denoting by ν \j0 the multi-index ν with νj0 set to zero, we obtain, under the induction hypothesis,      X Ej  , dimR (spanR ({fk }k∈K )) = min Υ(ν \j0 ) + min{νj0 , s}, dimR    j∈supp(ν)

for all j0 ∈ supp(ν). In particular,    n o dimR (spanR ({fk }k∈K )) = min min Υ(ν \j0 ) + νj0 , dimR  j0 ∈supp(ν)

X j∈supp(ν)

  Ej  . 

(3.31)

We now show that the RHS of (3.31) is equal to Υ(ν). To this end, first note that, by choosing s = ∅ in the definition of Υ(ν), one obtains     X X X νj + dimR  Ej  = dimR  Ej  . (3.32) j∈∅

j∈supp(ν)\∅

j∈supp(ν)

Function-Counting Theory for Low-Dimensional Data Structures

Second, we have min

 X

s⊆supp(ν)  j∈s s̸=∅

= =

min

 

νj + dimR 

j∈s

min

 X

j0 ∈supp(ν) s⊆supp(ν \j0 ) 

min

j0 ∈supp(ν)

  Ej   c



     Ej + νj0   c

 νj + dimR 

j∈s

(3.33)

j∈s

o n Υ(ν \j0 ) + νj0 .

From (3.32) and (3.33) one observes that all possible candidates for the minimum in the definition of Υ(ν) are captured by all candidates for the minimum in the RHS of (3.31).This shows that the RHS of (3.31) is equal to Υ(ν), completing the proof of (3.29). Thus, by (3.28), the set {Hk }k∈K is odd-degenerate if and only if Υsp,f (ν) ̸≡ t (mod 2). Given N , it follows that the number of all odd-degenerate sets {Hk }k∈K with |Kj | ≤ Nj , j ∈ J0 , is given by |O| =

N X

X Y Nj νj

t=s+1 ν∈I sp,f j∈J0

Finally, application of Theorem B.5 in the form (3.27) yields the desired expression. As in the case of sparsity in a basis (see Proposition 3.2), the number of homogeneously linearly separable dichotomies is independent of the specific location in E of the points in F ; it is determined by the configuration N only. In contrast, however, to Proposition 3.2, Csp,f (N , Ξ, s) now depends on the specific choice of the frame elements in Ξ. In the following the effect of the frame elements will be analyzed. To this end, we introduce the Gram operator associated with Ξ * + X G : ℓ2 (K) → ℓ2 (K), (ck )k∈K 7→  cj ξj , ξk  . (3.34) j∈K

k∈K

Here, (ℓ2 (K), ⟨·, ·⟩ℓ2 (K) ) denotes the space of square-summable sequences indexed by K, equipped P with the standard inner product ⟨c, d⟩ℓ2 (K) := k∈K ck dk , c, d ∈ ℓ2 (K). As Ξ constitutes a frame in the sense of (3.26), the linear operator G is bounded [15, Lemma 3.5.1], and moreover, G is self-adjoint. The Gram operator can be leveraged to compare the number of realizable dichotomies of point sets of datasets exhibiting sparsity in different frames. Lemma 3.10. Let Ξ = {ξk }k∈K , Ξ′ = {ξk′ }k∈K be frames for RM indexed by the same set K, and let G, G′ be the Gram operators associated with Ξ, Ξ′ , respectively. If (G′ − G) is positive semidefinite11 , then for all N ∈ N and all N ∈ NJ 0 with |N | = N , Csp,f (N , Ξ, s) ≤ Csp,f (N , Ξ′ , s). Proof. We first show that dimR (spanR ({ξk }k∈S )) ≤ dimR spanR {ξk′ }k∈S 11

That is, ⟨(G′ − G)c, c⟩ℓ2 (K) ≥ 0, for all c ∈ ℓ2 (K).

for every finite S ⊆ K.

(3.35)

K. Häberle and H. Bölcskei

′ To D thisEend, let S ⊆ K be finite, and consider the matrices GS := (⟨ξj , ξk ⟩)j,k∈S and GS := ( ξj′ , ξk′ )j,k∈S . The assumption on the positive semidefiniteness of (G′ − G) implies that the

matrix (G′S − GS ) is positive semidefinite. Indeed, (G′ − G)c, c ≥ 0, ∀c ∈ ℓ2 (K) =⇒ (G′ − G)c, c ≥ 0, ∀c ∈ ℓ2 (K), supp(c) ⊆ S =⇒ (G′S − GS )c, c ≥ 0, ∀c = (ck )k∈S ∈ RS , where supp(c) := {k ∈ K : ck ̸= 0}. It follows that rank(GS ) ≤ rank(G′S ), see, e.g., [17, Corollary 7.7.4(c)]. But as GS , G′S are Gram matrices of {ξk }k∈S and {ξk′ }k∈S , respectively, we have, by [17, Theorem 7.2.10(c)], rank(GS ) = dimR (spanR ({ξk }k∈S )) and rank(G′S ) = dimR (spanR ({ξk′ }k∈S )). This establishes (3.35). ′ ′ Fix now N ∈ NJ 0 with J0 = supp(N ), and let Ej := spanR ({ξk }k∈Sj ), j ∈ J . Then,     X X dimR  Ej  ≤ dimR  Ej′  , for all s ⊆ J0 . (3.36) j∈s

j∈s

Indeed, (3.36) follows from (3.35) upon noting that   X dimR  Ej  = dimR spanR {ξk }k∈Sj∈s Sj

and

j∈s

 dimR 

 X

Ej′  = dimR spanR {ξk′ }k∈Sj∈s Sj .

j∈s J0 0 Thanks to (3.36), application of Lemma 3.7 with {Ej }j∈J0 , {Ej′ }j∈J0 , and ϕ = Id : NJ 0 → N0 yields the desired bound.

Lemma 3.10 establishes that the number of realizable dichotomies is nondecreasing with respect to the ordering induced by the Gram operator associated with the frame. Connection to compressed sensing. Compressed sensing [18, 19, 20, 21] is concerned with the recovery of sparse vectors in R|K| from a number of linear measurements M that is small relative to |K|, assuming |K| < ∞. More concretely, in ourPnotation, the goal is to reconstruct (ck )k∈K ∈ RK from M measurements of the form f = k∈K ck ξk , where (ck )k∈K has at most s nonzero entries. Deterministic recovery guarantees typically rely on properties of the Gram operator associated with Ξ. In particular, a straightforward, yet computationally hard to verify, sufficient recovery condition is based on the so-called spark of the frame Ξ, see [18]. The spark of Ξ, denoted spark(Ξ), is defined as the cardinality of the smallest subset of Ξ which is linearly dependent. Note that spark(Ξ) = kr(Ξ) + 1. The recovery guarantee states that if s < spark(Ξ)/2, then (ck )k∈K can be uniquely recovered through a combinatorial search according to X argmin ∥e c∥0 subject to e ck ξk = f, e c∈RK

k∈K

where ∥e c∥0 denotes the number of nonzero entries of e c. Considering now the setup of Lemma 3.10, we note that, as demonstrated in the proof of Lemma 3.10, (G′ − G) being positive semidefinite implies (3.35), and from (3.35) we can deduce that spark(Ξ) ≤ spark(Ξ′ ). Thus, recalling the recovery threshold s < spark(Ξ)/2, the recovery performance under measurements with respect to Ξ′ is guaranteed to be at least as good as that under Ξ. Comparing to Lemma 3.10, we have the analogous result in the context of separation (rather than recovery). Namely, performing homogeneous linear separation on the set of sparse vectors with respect to Ξ′ yields at least as many realizable dichotomies as with respect to Ξ.

Function-Counting Theory for Low-Dimensional Data Structures

Φ-separability. Finally, let us briefly comment on Φ-separability ofPpoint sets on the set P ′ of sparse vectors. If Φ : E → RM is a linear map, then Φ( k∈Sj ck ξk ) = k∈Sj ck Φ(ξk ), for all (ck )k∈Sj ∈ RSj . So, in particular, we have Φ(E) =

[ j∈J

Φ(Ej ) =

[

spanR {Φ(ξk )}k∈Sj .

j∈J

In words, the union of linear subspaces structure is preserved under linear maps. If, moreover, the linear map Φ has full rank, the sparsity level s remains unchanged. That is, Φ(E) constitutes again a set of s-sparse vectors, but now with respect to a different frame, namely, {Φ(ξk )}k∈K . To determine the number of Φ-separable dichotomies of the N -point set F ⊂ E, one may thus apply Proposition 3.9. For nonlinear transformations Φ, the structure of sparsity is generally not preserved, and depending on Φ, we obtain a different data structure. This case will be discussed in the next subsections. 3.2

Rectifiable sets

The set of sparse vectors forms a special case within the broader class of rectifiable sets. In this subsection, we generalize our analysis to separation on rectifiable sets. We begin by stating the definition of rectifiable sets. Definition 3.11 (Countably Hs -rectifiable set, [22, 23, 24]). 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

Countably Hs -rectifiable sets also admit the following useful parametrization. Lemma 3.12 (Bi-Lipschitz parametrization, [22, 23]). Let E ⊆ RM be countably Hs -rectifiable. Then there exist finitely or countably many compact sets Kj ⊂ Rs and 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

Let E ⊆ RM be a countable Hs -rectifiable set with bi-Lipschitz parametrization {ψj : Kj → ψj (Kj )}j∈J as in Lemma 3.12, and define {sj }j∈J according to sj := dimR (spanR (ψj (Kj ))) ,

j ∈ J.

We further introduce the map πj : ψj (Kj ) → Rsj as a linear embedding of ψj (Kj ) into Rsj , j ∈ J . Concretely, choosing a set of sj linearly independent vectors in ψj (Kj ), we define πj as the linear map that assigns to each f ∈ ψj (Kj ) the vector of its expansion coefficients πj (f ) ∈ Rsj with respect to the chosen sj linearly independent vectors. The extension of the map πj to spanR (ψj (Kj )) shall be denoted by π ej . The following remark provides a simple lower bound for the quantity sj , which will play a crucial role in our analysis. Remark 3.13. First observe that without loss of generality one may assume that Hs (ψj (Kj )) > 0, as otherwise ψj can be omitted from the bi-Lipschitz parametrization, and we still retain a biLipschitz parametrization in the sense of Lemma 3.12. Application of Proposition C.2 then establishes that sj ≥ s.

K. Häberle and H. Bölcskei

Consider now the N -point set F := {f1 , . . . , fN } ⊂ E with N ∈ N and denote by Fj := F ∩ ψj (Kj ) the points of F in the bi-Lipschitz image ψj (Kj ). In line with the philosophy of Assumptions 3.1 and 3.8, we impose the following very mild assumption, and, as we shall see in Remark 4.9, the bi-Lipschitz parametrization of E can be chosen such that for (Hs )N -almost every N -tuple (f1 , . . . , fN ), the corresponding N -point set {f1 , . . . , fN } satisfies this assumption. S Assumption 3.14. Suppose that F ⊂ j∈J ψj (Kj ) and, for every j ∈ J , whenever Fj ̸= ∅, we assume the following: (r-i) Fj is in πj -general position. ′ ′ (r-ii) If there S is an index set J ⊆ J such that spanR (ψi (Ki )) = spanR (ψj (Kj )), for all i ∈ J , then i∈J ′ Fi is in π ej -general position. P P (r-iii) Fj ∩ i∈J ′′ spanR (ψi (Ki )) = ∅ whenever ψj (Kj ) ̸⊆ i∈J ′′ spanR (ψi (Ki )), for every J ′′ ⊂ J.

Item (r-i) means that the points of F in ψj (Kj ) are in general position when embedded into Rsj . Item (r-ii) ensures that, whenever multiple images {ψi (Ki )}i∈J ′ span the same subspace as ψj (Kj ), the points of F in {ψi (Ki )}i∈J ′ are in general position with respect to the common embedding π ej . This prevents degeneracies within shared subspaces. Finally, Item (r-iii) prevents the points in Fj from lying in a lower-dimensional subspace of spanR (ψj (Kj )) that is also containedP in the span of other components {ψi (Ki )}i∈J ′′ , unless ψj (Kj ) itself is entirely contained in i∈J ′′ spanR (ψi (Ki )). In contrast to Assumption 3.8, Items (r-i) and (r-ii) constitute a refined version of Item (f-i), while Item (r-iii) extends Item (f-ii). With N := (Nj )j∈J and Nj = |Fj |, we have the following result. Proposition 3.15. Under Assumption 3.14 the number of homogeneously separable dichotomies of F is given by N X X Y Nj Cr (N , E) := 2 − 2 , νj r N

t=s+1 ν∈It j∈J0

r 0 where J0 := supp(N ) ⊆ J is a finite subset, and where Itr := {ν ∈ NJ 0 : |ν| = t, Υ (ν) ̸≡ t (mod 2)} with     X  [ 0 Υr (ν) := min νj + dimR spanR  ψj (Kj ) , ν = (νj )j∈J0 ∈ NJ 0 .  s⊆supp(ν)  c j∈s

j∈s

Proof. By particularizing Proposition 3.18 to Φ = Id and Ej = ψj (Kj ), j ∈ J0 , the desired expression for the number of homogeneously separable dichotomies of F follows. Let us now analyze the impact of the geometry of E on the number of realizable dichotomies. To this end, let Ki,j := Ki × Kj , for i, j ∈ J , and define the kernel functions κi,j associated with {ψj : Kj → ψj (Kj )}j∈J according to κi,j : Ki,j × Ki,j → R,

(x, y) 7→

1 (⟨ψi (x1 ), ψj (y2 )⟩ + ⟨ψj (x2 ), ψi (y1 )⟩) . 2

Note that κi,j is symmetric in the sense that κi,j (x, y) = κi,j (y, x), for x, y ∈ Ki,j . Lemma 3.16. Let E, E ′ be countable Hs -rectifiable sets with bi-Lipschitz parametrizations {ψj : Kj → ψj (Kj )}j∈J , {ψj′ : Kj → ψj′ (Kj )}j∈J and kernel functions {κi,j }i,j∈J , {κ′i,j }i,j∈J ,

Function-Counting Theory for Low-Dimensional Data Structures

respectively. Suppose that (κ′i,j − κi,j ) is positive semidefinite12 , for all i, j ∈ J . Then, for all N ∈ N and all N ∈ NJ 0 with |N | = N , Cr (N , E) ≤ Cr (N , E ′ ). Proof. We begin by showing that for every S ⊆ J ,       [ [ dimR spanR  ψj (Kj ) ≤ dimR spanR  ψj′ (Kj ) . j∈S

(3.37)

j∈S

To see this, let S0 ⊆ S be a finite subset and, for each j ∈ S0 , choose a finite set {xj,k }k∈s ⊆ Kj such that    [ dimR (spanR ({ψj (xj,k ) : j ∈ S0 , k ∈ s})) = dimR spanR  ψj (Kj ) (3.38) j∈S

and    [ ′ = dimR spanR  dimR spanR ψj (xj,k ) : j ∈ S0 , k ∈ s ψj′ (Kj ) .

(3.39)

j∈S

Consider the Gram matrices G := (⟨ψi (xi,k ), ψj (xj,ℓ )⟩)i,j∈S0 ∈ Rn×n and G′ := k,ℓ∈s D E (k) ′ ′ n×n ( ψi (xi,k ), ψj (xj,ℓ ) )i,j∈S0 ∈ R , where n := S0 × s. Setting xi,j := (xi,k , xj,k ), we obtain, k,ℓ∈s

for c = (cj,k )j∈S0 ,k∈s ∈ Rn , cT (G′ − G)c =

ψi′ (xi,k ), ψj′ (xj,ℓ ) − ⟨ψi (xi,k ), ψj (xj,ℓ )⟩

ci,k cj,ℓ

i,j∈S0 k,ℓ∈s

X i,j∈S0 k,ℓ∈s

ci,k cj,ℓ

1 ′ 1 ′ ψi (xi,k ), ψj′ (xj,ℓ ) + ψ (xj,k ), ψi′ (xi,ℓ ) 2 2 j

1 1 − ⟨ψi (xi,k ), ψj (xj,ℓ )⟩ − ⟨ψj (xj,k ), ψi (xi,ℓ )⟩ 2 2 X (k) (ℓ) (k) (ℓ) = ci,k cj,ℓ κ′i,j xi,j , xi,j − κi,j xi,j , xi,j i,j∈S0 k,ℓ∈s

≥ 0, where the inequality is by the assumption that (κ′i,j −κi,j ) is positive semidefinite, for all i, j ∈ J . Thus, rank(G) ≤ rank(G′ ). As rank(G) and rank(G) are equal to the LHSs of (3.38) and (3.39), respectively, (3.37) follows. Letting J0 = supp(N ), application of Lemma 3.7 with {spanR (ψj (Kj ))}j∈J0 , J0 0 {spanR (ψj′ (Kj′ ))}j∈J0 , and ϕ = Id : NJ 0 → N0 yields, thanks to (3.37), the desired bound. Lemma 3.16 shows that the number of homogeneously separable dichotomies realizable on a countably Hs -rectifiable set E is bounded from above by the number of realizable dichotomies on a countably Hs -rectifiable set E ′ whenever (κ′i,j −κi,j ) for all i, j ∈ J . Intuitively, the positive semi-definiteness of (κ′i,j − κi,j ) means that E ′ is spread out in at least as many directions as E. ′ Φ-separability. Whenever Φ : E → RM is a Lipschitz map, Φ(E) is also countably Hs rectifiable, so that Proposition 3.15 can be leveraged to determine the number of Φ-separable dichotomies of the N -point set F ⊂ E. The case where Φ is non-Lipschitz will be covered in the next subsection. 12

n That is, for every n ∈ N, {x(k) }n k=1 ⊆ Ki,j , and {ck }k=1 ⊆ R, we have (k) (ℓ) κi,j (x , x )) ≥ 0.

k=1

′ (k) , x(ℓ) ) − ℓ=1 ck cℓ (κi,j (x

K. Häberle and H. Bölcskei

3.3

Measurable and σ-finite sets

Let now E ⊆ RM be Hs -measurable with Hs (E) > 0 for some s ≥ 0, suppose that Hs ⌞E is ′ σ-finite, and let Φ : E → RM be measurable. Inspired by the previous subsections, consider the following decomposition of E: let {Ej }j∈J be a countable family of Hs -measurable sets of positive Hs -measure such that13 (d-i) Hs (E \

j∈J Ej ) = 0,

(d-ii) Hs (Ei ∩ Ej ) = 0, i, j ∈ J with i ̸= j, and (d-iii) for every j ∈ J , min dimR (spanR (Φ(A))) = sj ,

A⊆Ej Hs (A)>0

where sj := dimR (spanR (Φ(Ej ))). Such a decomposition of E into {Ej }j∈J may be obtained through the following procedure. Consider min dimR (spanR (Φ(A))) =: s1 .

A⊆E

(3.40)

Hs (A)>0

As dimR (spanR (Φ(A))) ∈ {0, . . . , M ′ }, for every Hs -measurable A ⊆ E with Hs (A) > 0, the minimum in (3.40) is attained. Thus there exists an Hs -measurable set E1 ⊆ E with Hs (E1 ) > 0 such that dimR (spanR (Φ(E1 ))) = s1 . By (3.40), the set E1 satisfies Item (d-iii). Replacing E by E \ E1 and repeating the above procedure, we construct successively the sets E2 , E3 , . . .. As Hs ⌞E is σ-finite and {Ej }j∈J are pairwise disjoint with Hs (Ej ) > 0, the index set J is at most countable. Note that the constructed sets {Ej }j∈JSsatisfy stronger properties than those in (d-i) and (d-ii): they are pairwise disjoint and E = j∈J Ej . We have intentionally stated (d-i) and (d-ii) in a weaker form so that the decomposition (d-i)–(d-iii) aligns with the natural decompositions arising in the two main examples of interest: for sets of sparse vectors (i.e., unions of linear subspaces), where Ei and Ej are typically only essentially disjoint (Hs (Ei ∩ Ej ) = 0); and for rectifiable sets, where the bi-Lipschitz decomposition {Ej }j∈J covers E only up to an Hs -nullset. See Remark 3.19 for further discussion. For the N -point set F := {f1 , . . . , fN } ⊆ E, we write Fj := F ∩ Ej , and let πj : Φ(Ej ) → Rsj be a linear embedding of Φ(Ej ) into Rsj . The extension of πj to spanR (Φ(Ej )) is denoted by π ej . The following assumption adapts Assumption 3.14 to the present setting, with the additional requirement that F contains no points in nonempty intersections Ei ∩ Ej , i, j ∈ J . S Assumption 3.17. Suppose that F ⊂ j∈J Ej , and F ∩ Ei ∩ Ej = ∅, i, j ∈ J with i ̸= j. Whenever Fj ̸= ∅, for j ∈ J , we assume the following: (i) Fj is in (πj ◦ Φ)-general position. (ii) S If there is an index set J ′ ⊆ J such that spanR (Φ(Ei )) = spanR (Φ(Ej )), for all i ∈ J ′ , πj ◦ Φ)-general position. i∈J ′ Fi is in (e (iii) Φ(Fj )∩ J.

i∈J ′′ spanR (Φ(Ei )) = ∅ whenever Φ(Ej ) ̸⊆

i∈J ′′ spanR (Φ(Ei )), for every J

′′ ⊂

13 The minimum in (d-iii) is taken over all Hs -measurable sets A ⊆ Ej with Hs (A) > 0. We dropped the measurability constraint for notational convenience.

Function-Counting Theory for Low-Dimensional Data Structures

Assumption 3.17 prevents degenerate configurations. Specifically, by Item (i) we ensure that Φ(Fj ) is in general position when linearly embedded into Rsj . Item S (ii) guarantees that, if several components {Φ(Ei )}i∈J ′ span the same subspace, then F ∩ i∈J ′ Ei remains in general position with respect to the common embedding π ej . Finally, Item (iii) ensures that the points of Φ(Fj ) do not lie in any lower-dimensional subspace of spanR (Φ(Ej )) that isP also contained in the span of other components {Φ(Ei )}i∈J ′′ , except in the case where Φ(Ej ) ⊆ i∈J ′′ spanR (Φ(Ei )). In Remark 4.9, we will leverage the properties of the decomposition (d-i)–(d-iii) to show that for (Hs )N -a.e. N -tuple, the corresponding N -point set satisfies Assumption 3.17. Setting N = (Nj )j∈J := (|Fj |)j∈J , we obtain the following dichotomy count. Proposition 3.18. Under Assumption 3.17 the number of Φ-separable dichotomies of F is given by N X X Y Nj , C(N , Φ, s) := 2 − 2 νj ∗ N

t=s +1 ν∈It j∈J0

0 where J0 := supp(N ) ⊆ J is a finite subset, s∗ := minj∈J0 sj , and where It := {ν ∈ NJ 0 : |ν| = t, Υ(ν) ̸≡ t (mod 2)} with     X  [ 0 Υ(ν) := min νj + dimR spanR  Φ(Ej ) , ν = (νj )j∈J0 ∈ NJ 0 .  s⊆supp(ν)  c

j∈s

Proof. Let K ⊆ {1, . . . , N } and consider the disjoint decomposition of K into {Kj }j∈J0 such that {fk }k∈Kj ⊆ Φ(Ej ), for all j ∈ J0 . We first show that dimR (spanR ({fk }k∈K )) = Υ(ν),

(3.41)

0 where νj := |Kj | and ν = (νj )j∈J0 ∈ NJ 0 . To this end, we proceed by induction on |supp(ν)|. For the base case |supp(ν)| = 1, we note that Assumption 3.17(i) implies dimR (spanR ({fk }k∈K )) = min{νj0 , sj0 }, where j0 ∈ supp(ν). As     X  [ min νj + dimR spanR  Φ(Ej ) = min{νj0 , sj0 },  s⊆{j0 }  c

j∈s

the base case follows. Next, for the induction step we need to show that if (3.41) holds for all 0 ν ∈ NJ 0 with |supp(ν)| ≤ r for some r ∈ {1, . . . , |J0 | − 1}, then it also holds for all ν with |supp(ν)| = r + 1. Now, by Assumption 3.17, for every s ⊆ J0 and every {kj }j∈s with kj ⊆ Kj and |kj | ≤ sj , [ {fk }k∈kj is in πs -general position, j∈s

S S ds is the linear embedding of ds with d := where πs : S s j∈s Φ(Ej ) → R j∈s Φ(Ej ) into R dimR (spanR ( j∈s Φ(Ej ))). We thus have for every j0 ∈ supp(ν),   dimR (spanR ({fk }k∈K )) = min dimR spanR {fk }k∈K\Kj0 + dimR spanR {fk }k∈Kj0 ,      [ dimR spanR  Φ(Ej ) .  j∈supp(ν)

K. Häberle and H. Bölcskei

Denoting by ν \j0 the multi-index ν with νj0 set to zero, we obtain, under the induction hypothesis,       [ dimR (spanR ({fk }k∈K )) = min Υ(ν \j0 ) + min{νj0 , sj0 }, dimR spanR  Φ(Ej ) ,   j∈supp(ν)

for all j0 ∈ supp(ν). Now, by the same argument as in the proof of (3.29), we obtain dimR (spanR ({fk }k∈K )) = Υ(ν), as desired. Thus, the set of hyperplanes {Hk }k∈K , where Hk := {fk }⊥ , is odd-degenerate if and only if Υ(ν) ̸≡ t (mod 2). Summing over all possible configurations, we can deduce that the number of odd-degenerate sets of the hyperplanes {Hk }N k=1 is given by N X X Y Nj . νj ∗

t=s +1 ν∈It j∈J0

Finally, application of Theorem B.5, together with Remark B.6, completes the proof. Remark 3.19. Let us revisit the setup from Subsection 3.1, i.e., the case where E is theS set of ssparse vectors in a certain basis or frame Ξ and Φ = Id. The set of s-sparse vectors E = j∈J Ej naturally admits the decomposition (d-i)–(d-iii), where Ej := spanR ({ξk }k∈Sj ). Indeed, (d-i) is obvious, and (d-ii) holds because, by assumption, {ξk }k∈Sj are linearly independent for all index subsets Sj with |Sj | = s, so that the linear subspace Ei ∩ Ej is at most (s − 1)-dimensional for all distinct i, j ∈ J . Property (d-iii) is satisfied because for every Hs -measurable set A ⊆ Ej with Hs (A) > 0, dimR (spanR (A)) = s. To see this, suppose, for the sake of contradiction, that dimR (spanR (A)) = s′ < s, then A is a subset of an s′ -dimensional subspace U of RM . But Hs (U) = 0 since s′ < s, see Proposition C.2, which establishes the contradiction. Likewise, this is the case for rectifiable sets discussed in Subsection 3.2, namely, the biLipschitz parametrization in the sense of Lemma 3.12 can be chosen such that (d-i)–(d-iii) are satisfied. First note that the properties (d-i) and (d-ii) hold trivially for any such parametrization. Regarding (d-iii), consider the bi-Lipschitz parametrization {ψj : Kj → ψj (Kj )}j∈J . If (d-iii) does not hold for ψj (Kj ), decompose ψj (Kj ) into {ψj (Kj,k )}k∈Kj such that {ψj (Kj,k )}k∈Kj satisfies (d-i)–(d-iii). Since Hs (ψj (Kj )) ≤ Lip(ψj )s Ls (Kj ) < ∞ and Hs (ψj (Kj,k )) > 0 for all k ∈ Kj , the index set of the decomposition, Kj , is (at most) countable, e.g., S we may set Kj = N0 or Kj = {0, . . . , Lj } for some Lj ∈ N0 . Now exhaust Kj,0 and each Kj,k \ ℓ : ℓ<k Kj,ℓ , k ∈ K\{0}, up to an Ls -nullset by a countable family of pairwise disjoint compact sets. By doing so, we obtain a bi-Lipschitz parametrization, denoted by {ψ̃j : K̃j → ψ̃j (K̃j )}j∈J˜ , such that {ψ̃j (K̃j )}j∈J˜ satisfies (d-i)–(d-iii).

Separation capacity for low-dimensional data structures ′

A natural question one may ask about transformations Φ : E → RM , where E ⊆ RM with M, M ′ ∈ N, is: How can we efficiently compare different transformations with respect to their classification capabilities on a given dataset E? The so-called separation capacity of Φ provides a measure for this. In particular, the separation capacity characterizes the classification capa′ bilities of the function class {f 7→ sign(⟨Φ(f ), w⟩) : w ∈ RM } induced by the transformation ′ Φ : E → RM . However, the standard definition of separation capacity in the sense of [1], for′ mally stated in [6, 7], only encompasses maps between Euclidean spaces, i.e., Φ : RM → RM .

Function-Counting Theory for Low-Dimensional Data Structures

In this section, we will generalize the notion of separation capacity to maps on Hs -measurable sets E with Hs (E) > 0, for some s ≥ 0. This extension encompasses a broad class of datasets E ⊂ RM of LM -measure zero, thereby including many practically relevant examples such as the set of s-sparse signals. Definition 4.1 (s-separation capacity). Let M, M ′ ∈ N, and let E ⊆ RM be Hs -measurable ′ with Hs (E) > 0 for s ≥ 0. 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 Φ. Remark 4.2 (Notation). With slight abuse of notation, we will use from now on F to denote the set {f1 , . . . , fN } ⊆ E as well as the tuple (f1 , . . . , fN ) ∈ E N . It should be clear from the context in which sense F has to be understood. Remark 4.3. On RM , we have by Proposition C.2, HM = LM . Thus, this definition of SC (Φ) coincides with the standard definition of separation capacity of Φ in [6, 7]. Remark 4.4 (VC dimension). The concept of s-separation capacity closely relates to another, well-known measure of classification capabilities, namely the Vapnik–Chervonenkis (VC) dimen′ sion [8]. Concretely, the VC dimension of the function class {f 7→ sign(⟨Φ(f ), w⟩) : w ∈ RM } is defined to be the largest N ∈ N for which there exists an N -point set F ⊆ E such that all possible 2N dichotomies of F are Φ-separable. By contrast, the s-separation capacity is a measure-theoretic, average-case notion, which evaluates separability on the whole dataset E up to Hs -nullsets, but requiring only that at least 50% of all dichotomies be Φ-separable. In general, neither quantity uniformly bounds the other without additional assumptions on E and Φ [7]. Furthermore, the s-separation capacity is therefore, intuitively, more strongly governed by the geometry of E than the VC dimension. Consequently, s-separation capacity provides a more natural framework for analyzing how the dataset E affects the classification capabilities of Φ. Let now E ⊆ RM be Hs -measurable with Hs (E) > 0, and suppose that Hs ⌞E is σ-finite. In the following, we will derive a ready-to-use expression for the s-separation capacity of Φ. To this end, let F ∈ E N , and recall the number of Φ-separable dichotomies of F given in Proposition 3.18, be denoted by C(N , Φ, s). Here, N = (Nj )j∈J ∈ NJ 0 with Nj being the number of points of F in Ej , j ∈ J , and (Ej )j∈J constitute the decomposition in the sense of (d-i)–(d-iii) in Subsection 3.3. Suppose for now that for (Hs )N -a.e. F ∈ E N , Assumption 3.17 is satisfied. Then, by Definition 4.1, the s-separating of Φ is the largest N ∈ N such that min

N ∈NJ 0

1 C(N , Φ, s) ≥ . N 2 2

|N |=N

It holds that

min C(N , Φ, s) = C N, min sj ,

N ∈NJ 0 |N |=N

j∈J

(4.1)

where sj := dimR (spanR (Φ(Ej ))). Indeed, we first show that (4.1) holds with “≤”. To this end, ∗ let j ∗ ∈ J be such that sj ∗ = minj∈J sj , and let N ∗ = (Nj∗ )j∈J ∈ NJ 0 , where Nj = 0 for all j ∈ J \ {j ∗ } and Nj∗∗ = N . By Proposition 3.18, ∗

C(N , Φ, s) = 2 − 2

N X t=sj ∗ +1 (t−sj ∗ ) is odd

N . t

(4.2)

K. Häberle and H. Bölcskei

Following the derivation in Remark 3.4, we obtain C(N ∗ , Φ, s) = C (N, sj ∗ ) .

(4.3)

The reverse inequality (i.e., “≥”) follows from Theorem 2.1 upon noting that under Assumption 3.17 every subset of sj ∗ elements of {Φ(f1 ), . . . , Φ(fN )} is linearly independent. Thus, to determine the s-separation capacity of Φ, one needs to find the largest N ∈ N such that C(sj∗ , N ) 1 ≥ . N 2 2 By a symmetry argument (carried out in, e.g., [1]), it follows that the s-separation capacity of Φ is given by SC s (Φ) = 2sj∗ = 2 min dimR (spanR (Φ(Ej ))) .

(4.4)

j∈J

Note that in this derivation, it was assumed that for (Hs )N -a.e. F ∈ E N , Assumption 3.17 is satisfied.

(4.5)

It is natural to ask whether (4.5), and hence (4.4), is indeed valid in general. This will now be analyzed. To do so, let us first extend the notion of Φ-general position. ′

Definition 4.5. For M, M ′ , N ∈ N, let Φ : E → RM , where E ⊆ RM , and let M ♮ ∈ N with M ♮ ≤ M ′ . The set F := {f1 , . . . , fN } ⊆ E is said to be in (M ♮ , Φ)-general position if every subset ′ of k elements of {Φ(f1 ), . . . , Φ(fN )} ⊆ RM is linearly independent for all k ≤ min{M ♮ , N }. Note that if M ♮ = M ′ , then F is in Φ-general position. Consider the following key lemma. Lemma 4.6. Fix M, M ′ ∈ N, let E ⊆ RM be Hs -measurable with Hs (E) > 0 for s ≥ 0, and ′ consider the measurable function Φ : E → RM . Let M ♮ , N ∈ N with M ♮ ≤ M ′ ≤ N . The set of N -tuples F := (f1 , . . . , fN ) ∈ E N which are not in (M ♮ , Φ)-general position has (Hs )N -measure zero if and only if there is no Hs -measurable set A ⊆ E with Hs (A) > 0 such that dimR (spanR (Φ(A))) < M ♮ .

(4.6)

Remark 4.7. The “if” statement remains valid in the regime N ≤ M ♮ ≤ M ′ . Remark 4.8 (Measurability). The subset of N -tuples F = (f1 , . . . , fN ) not in (M ♮ , Φ)-general position, denoted PM ♮ ,Φ , is given by  PM ♮ ,Φ =

[ 1≤j1 <···<jL ≤N

 πj−1 1 ,...,jL

 \

δk−1 ({0}) , 1 ,...,kL

1≤k1 <···<kL ≤M ′

where L := min{M ♮ , N }, πj1 ,...,jL : E N → E L , (f1 , . . . , fN ) 7→ (fj1 , . . . , fjL ) is the canonical projection, and where   Φk1 (f1 ) · · · Φk1 (fL )   .. .. .. δk1 ,...,kL : E L → R, (f1 , . . . , fL ) 7→ det  . . . . ΦkL (f1 ) · · · ΦkL (fL ) It follows that PΦ ⊆ E N is (Hs )N -measurable whenever Φ is measurable.

Function-Counting Theory for Low-Dimensional Data Structures

Proof of Lemma 4.6. We first show the contrapositive of the “only if” statement. Namely, suppose there is an Hs -measurable set A ⊆ E with Hs (A) > 0 such that (4.6) holds. Then, ♮ , Φ)-general position for N ≥ M ♮ . Indeed, if F ∈ AN , then all N -tuples in AN are not in (M N ♮ dimR spanR ({Φ(fk )}k=1 ) < M , which implies that every subset of M ♮ elements of {Φ(fk )}N k=1 is linearly dependent. Thus, the “only if” part follows as (Hs )N (AN ) = N Hs (A) > 0. Next, consider the “if” statement. That is, assume that there is no Hs -measurable set of positive Hs -measure such that (4.6) holds. We prove the claim (in the form of Remark 4.7) by induction on N . For N = 1, f1 ∈ E is in (M ♮ , Φ)-general position if and only if Φ(f1 ) ̸= 0. Set A := {f ∈ E : Φ(f ) = 0}. Then, by assumption, we must have Hs (A) = 0 since dimR (spanR (Φ(A))) = 0. Now suppose the claim is true for N − 1, i.e., (Hs )N −1 -a.e. (f1 , . . . , fN −1 ) ∈ E N −1 is in (M ♮ , Φ)-general position. Fix such an (N − 1)-tuple which is in (M ♮ , Φ)-general position, and let fN ∈ E. Then, (f1 , . . . , fN ) is in (M ♮ , Φ)-general position if and only if Φ(fN ) ∈ / spanR ({Φ(fjk )}L−1 k=1 ) for every 1 ≤ j1 < · · · < jL−1 ≤ N − 1, where L := min{M ♮ , N }. Define Aj1 ,...,jL−1 := {f ∈ E : Φ(f ) ∈ spanR ({Φ(fjℓ )}L−1 ℓ=1 )}. But ♮ s H (Aj1 ,...,jL−1 ) = 0 as dimR spanR Φ(Aj1 ,...,jL−1 ) ≤ L − 1 < M . Consequently, (Hs )N -a.e. (f1 , . . . , fN ) ∈ E N is in (M ♮ , Φ)-general position. Building on Lemma 4.6, we proceed to demonstrate the validity of (4.5) in the next remark. s )N -a.e. F ∈ E N . Remark 4.9. In the following, we prove that Assumption 3.17 holds for (HS s First note that by (d-i) of the decomposition from Subsection 3.3, H (E \ j∈J Ej ) = 0, and S hence (Hs )N -a.e. (f1 , . . . , fN ) ∈ E N is such that {f1 , . . . , fN } ⊂ j∈J Ej . Furthermore, (d-ii) ensures that for (Hs )N -a.e. (f1 , . . . , fN ) ∈ E N , we have {f1 , . . . , fN } ∩ Ei ∩ Ej = ∅ whenever i, j ∈ J with i ̸= j. Next, we show that (Hs )N -a.e. F ∈ E N satisfies Items (i) to (iii) of Assumption 3.17. To this end, fix j ∈ J .

(i) By (d-iii), there is no A ⊆ Ej of positive Hs -measure such that dimR (spanR (Φ(A))) < sj , so that application of Lemma 4.6 yields that (Hs )N -a.e. F ∈ EjN is in (sj , Φ)-general position. Consequently, for (Hs )N -a.e. F ∈ E N , Fj is in (πj ◦ Φ)-general position if Fj ̸= ∅. This establishes Item (i) of Assumption 3.17. S (ii) Similarly, for Item (ii) of Assumption 3.17, note that, by (d-iii), there is no A ⊆ i∈J ′ Ei of positive Hs -measure such dimR (spanR (Φ(A))) < sj . Using Lemma 4.6, we obtain S that N N -a.e. F ∈ ( E ) is in (sj , Φ)-general position. Thus, for (Hs )N -a.e. that (Hs )S ′ i i∈J S N F ∈ E , i∈J ′ Fi is in (e πj ◦ Φ)-general position whenever i∈J ′ Fi ̸= ∅. (iii) Finally, for Item (iii) of Assumption 3.17, let J ′′ ⊂ J and set ( ) X A := f ∈ Ej : Φ(f ) ∈ spanR (Φ(Ei )) , i∈J ′′

then Hs (A) = 0 whenever Φ(Ej ) ̸⊆ P i∈J ′′ spanR (Φ(Ei )), then

i∈J ′′ spanR (Φ(Ei )).

Indeed, if Φ(Ej ) ̸⊆

! dimR spanR (Φ(Ej )) ∩

spanR (Φ(Ei ))

< sj .

(4.7)

i∈J ′′

But the LHS of (4.7) equals dimR (spanR (Φ(A))). Hence, by (d-iii), Hs (A) = 0. ConP sequently,Pit holds that for (Hs )N -a.e. F , Φ(Fj ) ∩ i∈J ′′ spanR (Φ(Ei )) = ∅ whenever Φ(Ej ) ̸⊆ i∈J ′′ spanR (Φ(Ei )) and Fj ̸= ∅, as desired. This also establishes the analogous results for Assumptions 3.1, 3.8 and 3.14. Note that, as discussed in Remark 3.19, the bi-Lipschitz parametrization of a countably Hs -rectifiable set can be chosen such that it admits the decomposition (d-i)–(d-iii) from Subsection 3.3.

K. Häberle and H. Bölcskei

In the next theorem, the obtained expression for the s-separation capacity is stated. Additionally, we provide an alternative proof which does not rely on the decomposition (d-i)–(d-iii), so that the assumption of Hs ⌞E being σ-finite can be dropped. Theorem 4.10. Let M, M ′ ∈ N, and let E ⊆ RM be Hs -measurable with Hs (E) > 0 for s ≥ 0. ′ Let Φ : E → RM be measurable. The s-separation capacity of Φ is given by SC s (Φ) = 2 min dimR (spanR (Φ(A))) . A⊆E Hs (A)>0

Proof. Let E ♮ ⊆ E be an Hs -measurable set of positive Hs -measure such that dimR spanR Φ(E ♮ ) = min dimR (spanR (Φ(A))) =: M ♮ . A⊆E

(4.8)

Hs (A)>0 ′

♮

There exists a linear map π ♮ : RM → RM such that Φ♮ := π ♮ ◦ Φ : E ♮ → M ♮ satisfies min dimR spanR Φ♮ (A) = M ♮ . A⊆E ♮ Hs (A)>0

Thus, by Lemma 4.6, (Hs )N -a.e. F ∈ (E ♮ )N is in Φ♮ -general position. It follows from Theorem B.3, that the number of Φ♮ -separable dichotomies is C(N, M ♮ ), and hence SC s Φ♮ = 2M ♮ . ♮ , Φ-separability is equivalent to Φ♮ -separability. Thus, we have SC s (Φ) ≤ Note that on E s ♮ ♮ SC Φ = 2M . To show that equality holds, recall (4.8) and apply Lemma 4.6 to deduce that (Hs )N -a.e. F = (f1 , . . . , fN ) ∈ E N is in (M ♮ , Φ)-general position. That is, every subset of {Φ(f1 ), . . . , Φ(fN )} containing M ♮ elements is linearly independent for N ≥ M ♮ . Then the number of Φ-separable dichotomies is at least C(N, M ♮ ) by Theorem 2.1, and SC s (Φ) ≥ 2M ♮ . This completes the proof. In the following, we apply the expression in Theorem 4.10 to two specific cases to analyze the effective dimension which determines the separation capacity: first, when E is the set of s-sparse vectors, and second, when E is a countably Hs -rectifiable set. 4.1

Sparse vectors

We begin by expressing the s-separation capacity in terms of the standard separation capacity SC (·). This reformulation allows a direct application of the computational framework developed in [7] for the standard separation capacity SC (·). In doing so, we therefore obtain a method to ′ compute the s-separation capacity of a transformation Φ : E → RM . Proposition 4.11 (s-sparse vectors). Let Ξ = {ξk }k∈K be a frame for RM , M ∈ N, and fix s ∈ {1, . . S . , M }. Assume that {ξk }k∈S is linearly independent for every S ⊆ K with |S| = s, and ′ set E := S⊆K : |S|=s (spanR ({ξk }k∈S )). For Φ : E → RM measurable, we have SC s (Φ) = min SC (Φ ◦ σS ) , S⊆K |S|=s

where σS : Rs → RM , c 7→ real-analytic, then

i=1 ci ξkS,i

(4.9)

with the labeling S = {kS,i }si=1 . If, moreover, Φ is

SC s (Φ) = 2 min dimR (spanR ((Φ ◦ σS )(Rs ))) . S⊆K |S|=s

(4.10)

Function-Counting Theory for Low-Dimensional Data Structures

Proof. We first show (4.9). Note that SC s (Φ) = 2 min dimR (spanR (Φ(A))) A⊆E Hs (A)>0

= 2 min

min

S⊆K A⊆spanR ({ξk }k∈S ) |S|=s Hs (A)>0

dimR (spanR (Φ(A)))

(4.11) (4.12)

= 2 min mins dimR (spanR ((Φ ◦ σS )(A)))

(4.13)

= 2 min SC (Φ ◦ σS ) ,

(4.14)

S⊆K A⊆R |S|=s Ls (A)>0 S⊆K |S|=s

where (4.11) is by Theorem 4.10. We next note that (4.12) holds with “≤”, as spanR ({ξk }k∈S ) ⊆ E, for every S ⊆ K with |S| = s. To see that the reverse inequality in (4.12), i.e., “≥”, is also satisfied, observe that if A ⊆ E with Hs (A) > 0, there is an S ⊆ K with |S| = s such that A ∩ spanR ({ξk }k∈S ) =: A′ is of positive Hs -measure. As A′ ⊆ A, dimR (spanR (Φ(A′ ))) ≤ dimR (spanR (Φ(A))). Consequently, (4.12) holds also with “≥”, establishing (4.12). To show (4.13), we again prove both inequalities. For the inequality “≤”, first note that for every Ls measurable A ⊆ Rs with Ls (A) > 0, σS (A) is Hs -measurable and 0 < Ls (A) = Hs σS−1 (σS (A)) ≤ Lip σS−1 Hs (σS (A)),

(4.15)

since σS : Rs → spanR ({ξk }k∈S ) is linear and bijective with linear inverse. It now follows from (4.15) that (4.13) holds with “≤”. For the reverse inequality, i.e., “≥”, let A ⊆ spanR ({ξk }k∈S ) be Hs -measurable with Hs (A) > 0. By Proposition C.3, there is a closed set A′ ⊆ A such that Hs (A′ ) > 0. As σS has a linear inverse and A′ is Borel, σS−1 (A′ ) is Ls -measurable and 0 < Hs (A′ ) = Hs σS (σS−1 (A′ )) ≤ Lip(σS )Hs (σS−1 (A′ )) = Lip(σS )Ls (σS−1 (A′ )).

(4.16)

Since A′ ⊆ A implies dimR (spanR (Φ(A′ ))) ≤ dimR (spanR (Φ(A))), (4.16) yields the inequality “≥”, thereby establishing (4.13). Finally, (4.14) is again by Theorem 4.10. Application of the result from [6] to (4.9) yields (4.10). This completes the proof. Considering the identity map Φ = Id : RM → RM and applying Proposition 4.11 to the restriction of Φ to E, denoted Φ|E , we obtain SC s (Id|E ) = 2s. Thus, in this case, the sseparation capacity is determined entirely by the sparsity parameter s. In comparison with the function-counting results for the homogeneous linear case presented in Subsection 3.1, we note that SC s (Id|E ) is independent of the frame Ξ, whereas Csp,f (N , Ξ, s) depends on Ξ (see also Lemma 3.10). Intuitively, SC s (Id|E ) is as a coarser, summary measure of separation capabilities, while Csp,f (N , Ξ, s) is a finer combinatorial quantity containing information about the separation behavior for each configuration N . ′ In general, however, if Φ : RM → RM is not a full-rank linear map, the union-of-linearsubspaces structure is no longer preserved, and SC s (Φ|E ) depends on Ξ. For instance, let ′ Ξ′ = {ξk′ }k∈K be another frame for RM , and suppose that Φ : RM → RM vanishes on a set containing the s-dimensional linear subspace spanR ({ξk }k∈S0 ) for some S0 ⊆ K with |S0 | = s, while it does not vanish on any of the subspacesS spanR ({ξk′ }k∈S ) for S ⊆ K with |S| = s. Then, 0 = SC s (Φ|E ) < SC s (Φ|E ′ ), where E ′ := S⊆K : |S|=s (spanR ({ξk′ }k∈S )). This example illustrates that SC s (Φ|E ) depends critically on how Φ interacts with all s-dimensional linear subspaces spanned by elements of the frame. In particular, to maximize SC s (Φ|E ), one needs to ensure that SC (Φ|E ◦ σS ) is maximized for all S ⊆ K with |S| = s.

4.2

K. Häberle and H. Bölcskei

Rectifiable sets

Let us now investigate how to compute the s-separation capacity of transformations on countably Hs -rectifiable sets. Proposition 4.12. Let M, M ′ ∈ N, and let E ⊆ RM be Hs -measurable with Hs (E) > 0 for ′ s ≥ 0 and countably Hs -rectifiable. Consider the measurable map Φ : E → RM . Let {ψj : Kj → ψj (Kj )}j∈J be a bi-Lipschitz parametrization of E according to Lemma 3.12. It holds that SC s (Φ) = min SC (Φ ◦ ψj ) , j∈J

′

where Φ ◦ ψj : Kj ⊂ Rs → RM . Remark 4.13. Note that SC (Φ ◦ ψj ) is well-defined because Ls (Kj ) > 0. Indeed, if ψj : Kj ⊂ Rs → ψj (Kj ) ⊂ RM is bi-Lipschitz, then ψj (A) is Hs -measurable if A ⊂ Kj is Ls -measurable, and for every Ls -measurable set A ⊆ Kj , (Hs (ψi (A)) = 0) ⇐⇒ (Hs (A) = Ls (A) = 0) . Thus, the compact sets {Kj }j∈J can assumed to be of positive Ls -measure. Proof of Proposition 4.12. By Theorem 4.10, we have SC s (Φ) = 2 min dimR (spanR (Φ(A))) A⊆E Hs (A)>0

≤2

dimR (spanR (Φ(A))) , S min A⊆ j∈J ψj (Kj ) Hs (A)>0

(4.17)

S s -measurable where the inequality holds since j∈J ψj (Kj ) ⊆ E. On the other hand, for every HS s ′ set A ⊆ E with H (A) > 0, it holds, as a consequence of Lemma 3.12, that A := A∩ j∈J ψj (Kj ) is Hs -measurable with Hs (A′ ) > 0. Since A′ ⊆ A, we have dimR spanR Φ(A′ ) ≤ dimR (spanR (Φ(A))) . (4.18) Furthermore, observe that dimR (spanR (Φ(B))) ≤ dimR spanR Φ(A′ ) S min B⊆ j∈J ψj (Kj ) Hs (B)>0

(4.19)

Since A ⊆ E was an arbitrarily chosen Hs -measurable set with Hs (A) > 0, it follows, by combining (4.18) and (4.19), that B⊆

dimR (spanR (Φ(B))) ≤ min dimR (spanR (Φ(A))) , S min A⊆E j∈J ψj (Kj ) Hs (A)>0 Hs (B)>0

and consequently, (4.17) holds with equality. Therefore, we have SC s (Φ) = 2

dimR (spanR (Φ(A))) S min A⊆ j∈J ψj (Kj ) Hs (A)>0

≤ 2 min

min

j∈J A⊆ψj (Kj ) Hs (A)>0

dimR (spanR (Φ(A)))

≤ 2 min min dimR (spanR ((Φ ◦ ψj )(A))) j∈J

A⊆Kj Ls (A)>0

= min SC (Φ ◦ ψj ) , j∈J

(4.20) (4.21)

Function-Counting Theory for Low-Dimensional Data Structures

where (4.21) followsSfrom Remark 4.13. We next show that (4.20) holds with equality. To this end, let now A ⊆ j∈J ψj (Kj ) be Hs -measurable with Hs (A) > 0. Then, there must be an index i ∈ J such that the Hs -measurable set A′ := A ∩ ψi (Ki ) satisfies Hs (A′ ) > 0. Since A′ ⊆ A, dimR spanR Φ(A′ ) ≤ dimR (spanR (Φ(A))) , from which we deduce, following the same argument as above, min

min

j∈J A⊆ψj (Kj ) Hs (A)>0

dimR (spanR (Φ(A))) ≤

dimR (spanR (Φ(A))) . S min A⊆ j∈J ψj (Kj ) s H (A)>0

Finally, to show that (4.21) holds with equality, we use again the same argument. Consider an arbitrary Hs -measurable set A ⊆ ψj (Kj ) be with Hs (A) > 0. By Proposition C.3, there is a closed set A′ ⊂ A with Hs (A′ ) > 0. Then, dimR spanR Φ(A′ ) ≤ dimR (spanR (Φ(A))) , and since ψj is bi-Lipschitz, ψi−1 (A′ ) is Ls -measurable with Ls (ψj−1 (A′ )) > 0. It follows that min dimR (spanR ((Φ ◦ ψj )(A))) ≤

A⊆Kj Ls (A)>0

min A⊆ψj (Kj ) Hs (A)>0

dimR (spanR (Φ(A))) ,

which completes the proof. Let us also study the identity map restricted to E, when E countably Hs -rectifiable. Recalling Remark 3.19, the bi-Lipschitz parametrization can be chosen such that the decomposition from Subsection 3.3 holds. Using Proposition 4.12, we compute SC s (Id|E ) = 2 min sj ≥ 2s, j∈J

(4.22)

where sj := dimR (spanR (ψj (Kj ))), and where the inequality follows from Remark 3.13. Thus, the rectifiability parameter s determines a lower bound for the s-separation capacity of the identity map on E. Note that (4.22) holds with equality if one of the parametrization maps in {ψj : Kj → ψj (Kj )}j∈J is linear, i.e., if on a set of positive Hs -measure, E coincides with an s-dimensional linear subspace. For nonlinear parametrization maps {ψj : Kj → ψj (Kj )}j∈J , the images {ψj (Kj )}j∈J may exceed s-dimensional linear structure, and SC s (Id|E ) can become strictly larger than 2s. Intuitively, we can therefore conclude that datasets E with nonlinear parametrizations and large rectifiability parameter s (i.e., rich geometric structure and high intrinsic dimension) tend to yield high s-separation capacity SC s (Id|E ).

Generalization and learning on low-dimensional datasets

In this section, we study another measure of classification capabilities closely related to the s-separation capacity: the probability of ambiguous generalization introduced by Cover [1]. It characterizes the ability of a transformation Φ to generalize beyond the points it has already separated. More precisely, given a Φ-separable dichotomy {F+ , F− } of an N -point set F ⊂ E, the question is whether the realized dichotomy uniquely determines the label of a new point g ∈ E, or whether both assignments g ∈ F+ and g ∈ F− remain compatible with {F+ , F− }. It is clear that for certain dichotomies of F , the classification of g will not be unique. In general, one may expect, however, that for N large enough, the labeling of g is unique. In [1], the question of when unique generalization becomes probable was studied under the assumption that F is

K. Häberle and H. Bölcskei

F+ F− g2 g1

Figure 5.1: Ambiguous generalization with respect to the homogeneously linearly separable dichotomy {F+ , F− }. The point g1 is unambiguous and the point g2 is ambiguous with respect to {F+ , F− }. Indeed, the dashed separating surface assigns g2 to F− , while the dichotomy {F+ ∪ {g2 }, F− } is realized by the dashed-dotted separating surface.

in Φ-general position. However, as previously noted, in general this assumption may not hold, specifically when E exhibits low-dimensional structure in a measure-theoretic sense, i.e., when LM (E) = 0. The goal of this section is to investigate when unique generalization becomes probable in the setting where E is Hs -measurable with positive and σ-finite Hs -measure for some s ≥ 0, and where the Φ-general position assumption may fail. To this end, we will identify which results from [1] carry over directly to this setting and which require modification. We start with the formal definition of ambiguous generalization as introduced in [1]. Definition 5.1 (Ambiguous generalization, [1]). For M, M ′ , N ∈ N, let F := {f1 , . . . , fN } ⊆ E, ′ where E ⊆ RM , and let Φ : E → RM . Suppose the dichotomy {F+ , F− } is Φ-separable. We call g ∈ E ambiguous with respect to {F+ , F −} if both dichotomies {F+ ∪{g}, F− } and {F+ , F− ∪{g}} are Φ-separable. Otherwise, g ∈ E is said to be unambiguous with respect to {F+ , F −}. The concept of ambiguous generalization is illustrated in Fig. 5.1. To determine whether a point is ambiguous or unambiguous with respect to a given dichotomy, the following lemma, established in [1], is particularly useful and can be applied directly in our setting. It provides a necessary and sufficient condition for ambiguous generalization. Lemma 5.2 ([1]). Let F := {f1 , . . . , fN } ⊆ E, where E ⊆ RM with M, M ′ , N ∈ N. Suppose ′ Φ : E → RM is such that the dichotomy {F+ , F− } is Φ-separable. The point g ∈ E is ambiguous with respect to {F+ , F− } if and only if there is a Φ-surface containing g which realizes the dichotomy {F+ , F− }. Fix now an N -point set F ⊂ E, and let g ∈ E. We wish to compute the probability that g is ambiguous with respect to a uniformly at random chosen Φ-separable dichotomy of F , denoted P (Φ, F, g). It follows from Lemma 5.2 that P (Φ, F, g) =

# of Φ-sep. dichotomies of F s.t. sep. Φ-surface contains g . # of Φ-sep. dichotomies of F

(5.1)

Note that the separating Φ-surface containing g achieves the dichotomy {F+ , F− } of F if and ′ only if there is a separating vector w ∈ RM such that ⟨Φ(f ), w⟩ ≥ 0, if f ∈ F+ ,

(5.2)

⟨Φ(f ), w⟩ < 0, if f ∈ F− ,

(5.3)

⟨Φ(g), w⟩ = 0.

Function-Counting Theory for Low-Dimensional Data Structures

P ∗ (β)

0.75

0.5

0.25

0 0

3 β

Figure 5.2: Asymptotic probability of ambiguous generalization under Φ-general position assumption.

In other words, there exists w ∈ {Φ(g)}⊥ satisfying (5.2) and (5.3). Thus, we may also write ′ ′ ′ ⟨Φ(f ), P{Φ(g)}⊥ w⟩ in (5.2) and (5.3), and take w ∈ RM , where P{Φ(g)}⊥ : RM → RM denotes the orthogonal projection onto the linear subspace {Φ(g)}⊥ . But orthogonal projections are selfe g := P{Φ(g)}⊥ ◦ Φ, adjoint, which implies ⟨Φ(f ), P{Φ(g)}⊥ w⟩ = ⟨P{Φ(g)}⊥ Φ(f ), w⟩. Hence, setting Φ one can write (5.1) as P (Φ, F, g) =

e g -sep. dichotomies of F # of Φ . # of Φ-sep. dichotomies of F

(5.4)

We emphasize that for (5.4) to hold, F ∪ {g} need not be in Φ-general position. Let us analyze (5.4) first under the assumptions made in [1], namely, when E = RM and ′ ′ Φ : RM → RM is such that (LM )N -a.e. N ′ -tuple is in Φ-general position for every N ′ ∈ N, i.e., SC (Φ) = 2M ′ . In particular, F ∪ {g} can assumed to be in Φ-general position. It follows that e g (fk )}N lie in an (M ′ −1)-dimensional linear subspace, satisfying Assumption 3.1 the points {Φ k=1 egwith s = M ′ − 1. Consequently, Remark 3.4 can be leveraged to compute the number of Φ ′ separable dichotomies of F , yielding the result of C(N, M − 1). Thus, assuming F ∪ {g} is in Φ-general position, we obtain P (Φ, F, g) =

C(N, M ′ − 1) . C(N, M ′ )

In [1], the asymptotic properties of this quantity are studied as M ′ → ∞. Specifically, it is shown that ( ′ − 1) 1, if β ∈ [0, 2], C(N, M (5.5) β ∈ R+ P ∗ (β) := lim ′ = 0. 1 ′ C(N, M ) N =⌊βM ⌋ , if β ∈ (2, ∞), β−1 M ′ →∞

We refer to P ∗ (β), β ∈ R+ 0 , as the asymptotic probability of ambiguous generalization under Φ-general position assumption. See Fig. 5.2 for an illustration. Observe that P ∗ exhibits a decline at β = 2. Unambiguous generalization occurs with positive probability if N > 2M ′ . ′ ′ But recall that SC (Φ) = 2M ′ if we assume Φ : RM → RM is such that (LM )N -a.e. N ′ -tuple is in Φ-general position for every N ′ ∈ N. Thus, the separation capacity serves as the threshold indicating when unambiguous generalization becomes probable. Let us now generalize the results of [1] by analyzing (5.4) in the broader setting where E is ′ s H -measurable with positive and σ-finite Hs -measure, Φ : E → RM is arbitrary, and F ∪ {g} need not be Φ-general position. To this end, we recall the framework introduced in Subsection 3.3 and decompose E into {Ej }j∈J according to (d-i)–(d-iii). We next extend Proposition 3.18 by imposing the additional constraint that the separating surface must pass through a prescribed point g.

K. Häberle and H. Bölcskei

Proposition 5.3. Let g ∈ Eℓ , for some ℓ ∈ J , be such that for all s ⊆ J , X X Φ(g) ∈ / spanR (Φ(Ej )) , whenever Φ(Eℓ ) ̸⊆ spanR (Φ(Ej )) . j∈s

(5.6)

j∈s

eg. Moreover, suppose that the N -point set F ⊆ E satisfies Assumption 3.17 with respect to Φ Then, the number of Φ-separable dichotomies of F subject to the condition that the Φ-separating surface contains g is given by Y N +1 X X Nℓ Nj N . C(N , ℓ, Φ, s) := 2 − 2 νj νℓ − 1 ∗ t=s +1 ν∈It

j∈J0 \ℓ

0 Here, J0 := supp(N ) ∪ {ℓ}, s∗ := minj∈J0 sj , and It := {ν ∈ NJ 0 : |ν| = t, Υ(ν) ̸≡ t (mod 2)} with      X [ Υ(ν) := min νj + dimR spanR  Φ(Ej ) ,  s⊆supp(ν)  c

j∈s

0 for all ν = (νj )j∈J0 ∈ NJ 0 .

Remark 5.4. For (Hs )N -a.e. N -tuple F ∈ E N and Hs -a.e. g ∈ E, the assumptions of Proposition 5.3 hold. Indeed, from Remark 4.9, we know that Hs -a.e. g ∈ E satisfies Assumption 3.17, but Item (iii) in Assumption 3.17 coincides with (5.6). Furthermore, we have, for every Hs measurable A ⊆ Ej , j ∈ J , with positive Hs -measure, e g (A) dimR spanR Φ = dimR (spanR (Φ(A))) − dimR (spanR ({Φ(g)}) ∩ spanR (Φ(A)))

(5.7)

= dimR (spanR (Φ(Ej ))) − dimR (spanR ({Φ(g)}) ∩ spanR (Φ(Ej ))) ,

(5.8)

where (5.7) is by the rank–nullity theorem, and in (5.8), we used that for {Ej }j∈J ,(d-iii) holds. Note that the RHS in (5.8) does not depend on A. Thus, {Ej }j∈J also constitutes a valid e g . Application of Remark 4.9 decomposition in the sense of (d-i)–(d-iii) with respect to the map Φ s N N then establishes that for (H ) -a.e. N -tuple F ∈ E , Assumption 3.17 holds with respect to eg. the map Φ Proof of Proposition 5.3. From the derivation of (5.4), we know that C(N , ℓ, Φ, s) equals the e g -separable dichotomies of F . As F satisfies Assumption 3.17 with respect to the number of Φ e e g yields map Φg , application of Proposition 3.18 particularized to Φ N X X Y Nj C(N , ℓ, Φ, s) = 2 − 2 , νj t=s N

eg,t j∈J0 ∗ ν∈I

where we used that, by the rank–nullity theorem, e g (Ej ) = dimR (spanR (Φ(Ej ))) dimR spanR Φ − dimR (spanR ({Φ(g)}) ∩ spanR (Φ(Ej ))) ≥ s∗ − 1,

for all j ∈ J0 .

0 e Here, Ieg,t := {ν ∈ NJ 0 : |ν| = t, Υg (ν) ̸≡ t (mod 2)} and     X  [ e g (ν) := min e g (Ej ) . Υ νj + dimR spanR  Φ  s⊆supp(ν)  c

j∈s

(5.9)

Function-Counting Theory for Low-Dimensional Data Structures

Note that the constraint in the minimum s ⊆ supp(ν) can equivalently be replaced by s ⊆ J0 , where sc denotes the complement with respect to the indexing set appearing in the minimization (i.e., supp(ν) or J0 ). We next compute   e g (Ej )  e g (ν) = min Υ νj + dimR  spanR Φ  s⊆J0  c j∈s j∈s     X  X = min spanR (Φ(Ej )) νj + dimR P{Φ(g)}⊥   s⊆J0  j∈s j∈sc    X X = min νj + dimR  spanR (Φ(Ej )) − s⊆J0  c j∈s j∈s    X dimR spanR ({Φ(g)}) ∩ spanR (Φ(Ej ))  j∈sc      X X = min νj + dimR  spanR (Φ(Ej )) − 1{Φ(Eℓ )⊆P c span (Φ(Ej ))} R j∈s  s⊆J0   X



= min

s⊆J0 

(5.10)

(5.11)

(5.12)

j∈sc

j∈s

 X

 νj + dimR 

 X

spanR (Φ(Ej )) − 1{ℓ∈sc }

 

(5.13)

      X X   = min νj + dimR spanR (Φ(Ej )) + 1{ℓ∈s} − 1  s⊆J0  c j∈s

j∈sc

j∈s

= Υ(ν + eℓ ) − 1, where (5.10) holds as P{Φ(g)}⊥ is linear, (5.11) follows from the rank–nullity P theorem, and (5.12) c implies Φ(E ) ⊆ is by (5.6). Finally, (5.13) is valid because ℓ ∈ s ℓ j∈sc spanR (Φ(Ej )), and P because, conversely, whenever Φ(Eℓ ) ⊆ j∈sc spanR (Φ(Ej )), the minimization allows us to include ℓ ∈ sc . Thus, ν ∈ Ieg,t if and only if (ν + eℓ ) ∈ It+1 . Using (5.9), we therefore obtain N X Nℓ X C(N , ℓ, Φ, s) = 2 − 2 νℓ − 1 t=s∗ N

ν∈It+1

=2 −2

N +1 X

t=s∗ +1 ν∈It

Nℓ νℓ − 1

Y j∈J0 \{ℓ}

Nj νj Nj , νj

as desired. Combining Propositions 3.18 and 5.3, we have, by Remarks 4.9 and 5.4, for (Hs )N -a.e. N -tuple F ∈ E N and Hs -a.e. g ∈ E, P +1 P Nℓ Q Nj 2N − 2 N C(N , ℓ, Φ, s) t=s∗ +1 ν∈It νℓ −1 j∈J0 \{ℓ} νj = . P (Φ, F, g) = P +1 P Q Nj C(N , Φ, s) 2N − 2 N t=s∗ +1 ν∈It j∈J0 νj

(5.14)

In what follows, we will analyze the relation between P (Φ, F, g) and the s-separation capacity SC s (Φ) and particularize the RHS of (5.14) to two extreme cases. To this end, set sj ∗ :=

K. Häberle and H. Bölcskei

minj∈J sj . Then, C(N , Φ, s) ≥ C(N, sj ∗ ) by Theorem 2.1. For η ∈ (0, 1), compute lim ′

M →∞ sj ∗ /M ′ fixed N =⌊2sj ∗ (1−η)⌋

C(N , Φ, s) ≥ 2N

C(N, sj ∗ ) = 1, 2N

lim s ∗ →∞ j

N =⌊2sj ∗ (1−η)⌋

where the equality was shown in [1]. Thus, every dichotomy of a set of points in E of cardinality less than 2sj ∗ is asymptotically Φ-separability with probability one as M ′ → ∞ with sj ∗ /M ′ being fixed. But then g can be assigned to any F+ or F− to yield an asymptotic Φ-separable dichotomy if the cardinality of F satisfies N < 2sj ∗ . Indeed, in this case, we have N +1 N 1 = < 2, + sj ∗ sj ∗ sj ∗ |{z}

for sj ∗ large enough.

Hence, every dichotomy of F ∪{g} is asymptotically Φ-separable with probability one if N < 2sj ∗ . Recalling that SC s (Φ) = 2sj ∗ , we can infer that the s-separation capacity serves as bound to have ambiguous generalization with probability one for (Hs )N -a.e. N -tuple F and Hs -a.e. g in the regime M ′ → ∞ with fixed sj ∗ /M ′ . In particular, if N < 2sj ∗ , then unambiguous generalization is of probability zero for (Hs )-a.e. N -tuple F and Hs -a.e. g. Exemplifying this observation to the setting where E is countably Hs -rectifiable and Φ = Id, one can deduce that ambiguous generalization occurs with probability one if N < 2s, as sj ∗ ≥ s by Remark 3.13. Thus, the bound to have ambiguous generalization with probability one increases with the rectifiability parameter s. We further note that if F ⊆ Ej ∗ and g ∈ Ej ∗ , then C(N , Φ, s) = C(N, sj ∗ ) by Remark 3.4, and N +1 X X Nj ∗ N C(N , ℓ, Φ, s) = 2 − 2 νj ∗ − 1 t=sj ∗ +1 ν∈It

=2 −2

N +1 X

t=sj ∗ +1 (t−sj ∗ ) odd N

=2 −2

N t−1

N X t=(sj ∗ −1)+1 (t−(sj ∗ −1)) odd

N t

= C(N, sj ∗ − 1), using Remark 3.4 again in the last step. Thus, if F ⊆ Ej ∗ and g ∈ Ej ∗ , P (Φ, F, g) =

C(N, sj ∗ − 1) C(N , ℓ, Φ, s) = . C(N , Φ, s) C(N, sj ∗ )

Then, the asymptotic probability of ambiguous generalization takes the form (5.5), depicted in Fig. 5.2, and unambiguous generalization occurs with positive probability if N > 2sj ∗ . S Finally, let us emphasize that if g ∈ Eℓ with Φ(Eℓ ) ̸⊆ spanR ( j∈supp(N ) Φ(Ej )), then Nℓ = 0 0 and for all ν ∈ NJ 0 with νℓ = 0,

Υ(ν + eℓ ) = Υ(ν) + 1, by virtue of (5.12). Thus, ((ν + eℓ ) ∈ It ) ⇐⇒ (ν ∈ It−1 ) ,

(5.15)

Function-Counting Theory for Low-Dimensional Data Structures

0 whenever ν ∈ NJ 0 with νℓ = 0. We then obtain

C(N , ℓ, Φ, s) = 2 − 2

N +1 X

X Nℓ νℓ − 1

t=s∗ +1 ν∈It

= 2N − 2

N +1 X

t=s∗ +1 ν∈It j∈J0 \{ℓ} νℓ =1 N

=2 −2

N +1 X

=2 −2

N X X

t=s∗ +1 ν∈It j∈J0 \{ℓ}

j∈J0 \{ℓ}

Nj νj

t=s∗ +1 ν∈It−1 j∈J0 \{ℓ} νℓ =0 N

Nj νj

(5.16)

(5.17)

= C(N , Φ, s), where (5.16) is by (5.15), and in (5.17), we used that Is∗ = ∅, so that P (Φ, F, g) = 1. In other words, in this case, unambiguous generalization is not probable (i.e., occurs with probability zero) for every N ∈ N.

Notation

N, N0 , Z, R, and R+ 0 denote the sets of natural numbers, nonnegative integers, integers, real numbers, and nonnegative real numbers, respectively. For a, b ∈ Z and m ∈ N, we write n n! a ≡ b (mod m) whenever m divides (a − b). The binomial coefficient is defined as k := k!(n−k)! for all k, n ∈ N0 with 0 ≤ k ≤ n. Moreover, if n < k, we set nk := 0. For multi-indices Q N = (Nj )Jj=1 , ν = (νj )Jj=1 ∈ NJ0 with J ∈ N, we write Nν := Jj=1 Nνjj . Furthermore, the support and absolute value of ν = (νj )Jj=1 ∈ NJ0 is given by supp(ν) = {j ∈ {1, . . . , J} : νj ̸= 0} P and |ν| = Jj=1 νj , respectively. Let ⌊x⌋ denote the largest k ∈ Z such that k ≤ x, where x ∈ R. To represent the indicator of a statement S, we write 1{S} , which equals 1 if the statement S is true, and 0 if S is false. For a finite set X, let |X| denote its cardinality. We use xT to denote the transpose of x ∈ Rn , n ∈ N. The standard Euclideanpinner product of x, y ∈ Rn is ⟨x, y⟩ = y T x, and its induced norm on Rn is given by ∥x∥ := ⟨x, x⟩. For a set A ⊆ Rn , let spanR (A) stand for the set of all finite linear combinations of vectors in A with scalars in the field R. Given a linear space V over R, we write dimR (V ) for its dimension. Moreover, if {UkP }k∈K is a family P of linear subspaces of V , then the sum of these linear subspaces is denoted by k∈K Uk := { k∈K uk : uk ∈ Uk , k ∈ K}. For a finite set A ⊂ Rn , we denote by kr(A) the Kruskal rank of A, i.e., the largest integer k such that every subset of k elements of A is linearly independent. The n-dimensional Lebesgue measure on Rn is denoted by Ln . For s ≥ 0, Hs stands for the s-dimensional Hausdorff measure on some metric space (see Appendix C). A statement S is said to hold for µ-almost every x ∈ A (µ-a.e. x ∈ A for short) if there exists a set N ⊂ X with µ(N ) = 0 such that S is true for every x ∈ A \ N , where µ is a measure on some set X, and where A ⊆ X. The restriction of a measure µ to a subset A is denoted by µ⌞A.

Cover’s framework and fundamentals of function-counting theory

This section introduces Cover’s framework [1] and reviews some key results from functioncounting theory [1, 2, 3, 4, 6, 25, 26], using mostly the notation of [7]. A central ingredient in this framework is the pattern space, represented as the M -dimensional Euclidean space RM equipped with the standard inner product ⟨·, ·⟩. Let E ⊆ RM be an arbitrary subset of the

K. Häberle and H. Bölcskei

F+ F− E Figure B.1: Separation of points on a low-dimensional dataset E by a hyperplane (dashed line) through the origin. Specifically, the dichotomy {F+ , F− } is homogeneously linearly separable.

pattern space, and consider a set of N points (patterns) F := {f1 , . . . , fN } ⊆ E, where N ∈ N. We are concerned with the problem of binary classification of the points in F , i.e., assigning the elements of the set F to one of the two classes F+ and F− . Such a partition of F into F+ and F− is called a dichotomy. The simplest way to implement a dichotomy is by using a hyperplane as separating surface, see Fig. B.1. A dichotomy {F+ , F− } is said to be linearly separable if there exist w ∈ RM and t ∈ R such that ⟨f, w⟩ > t,

if f ∈ F+ ,

⟨f, w⟩ < t,

if f ∈ F− .

When t = 0, we speak of homogeneous linear separation. The surface {f ∈ RM : ⟨f, w⟩ = t} is called the separating hyperplane. In practice, however, most dichotomies we wish to realize are not linearly separable, i.e., they cannot be realized by separation through hyperplanes in the pattern space. Thus, more general nonlinear separating surfaces are required. To resolve this issue, one follows Cover’s idea [1] of first mapping the points in E ⊆ RM to another space, typically a higher-dimensional one, designated as feature space, by employing a nonlinear ′ transformation Φ : E → RM . The goal is to choose Φ such that the dichotomies become linearly separable in the feature space while keeping the dimension of the feature space, M ′ , as small as possible. The separating surface in the pattern space then becomes a nonlinear surface characterized by Φ, see Fig. B.2. Homogeneous linear separation in the feature space can always be achieved, provided that linear separation is possible in the feature space associated with Φ, by considering the transformation f 7→ (1, Φ(f ))T . Formally, the concept of obtaining homogeneous linear separation by employing a transformation Φ is captured by the notion of Φ-separability. Definition B.1 (Φ-separability). For M, M ′ , N ∈ N, let F := {f1 , . . . , fN } ⊆ E, where E ⊆ RM , ′ and let Φ : E → RM . A dichotomy F = {F+ , F− } is called Φ-separable if there exists a vector ′ w ∈ RM such that ⟨Φ(f ), w⟩ > 0,

if f ∈ F+ ,

⟨Φ(f ), w⟩ < 0,

if f ∈ F− .

We call {f ∈ E : ⟨Φ(f ), w⟩ = 0} the separating Φ-surface. The number of Φ-separable dichotomies depends in general on F and Φ. However, if F is “typical” with respect to Φ in the following sense, then the number of Φ-separable dichotomies depends on N and M ′ only.

Function-Counting Theory for Low-Dimensional Data Structures

F+

Φ: R → R 1 f 7→ (f )0 (f )1

F− F+

F+

F−

Φ(E)

Figure B.2: Mapping a linearly inseparable dichotomy in pattern space to a homogeneously linearly separable dichotomy in feature space. ′

Definition B.2 (Φ-general position). For M, M ′ , N ∈ N, let Φ : E → RM , where E ⊆ RM . The set F := {f1 , . . . , fN } ⊆ E is said to be in Φ-general position if every subset of k elements ′ of {Φ(f1 ), . . . , Φ(fN )} ⊆ RM is linearly independent for all k ≤ min{M ′ , N }. If this holds for Φ = Id : E → RM , f 7→ f , we simply say that F is in general position. We are now ready to state the central result in function-counting theory, which provides a closed-form solution for the number of Φ-separable dichotomies of F under the assumption that F is in Φ-general position. Note, however, that as E is an arbitrary subset of RM and Φ can ′ be any map E → RM , the Φ-general position assumption for F usually does not hold. For instance, if E is as in Fig. B.2, i.e., a union of two linear subspaces, and Φ = Id, every N -point set of E is not in Φ-general position. In Section 4, we extend the notion of Φ-general position to make it applicable in the general case where both E ⊆ RM and Φ are arbitrary. Theorem B.3 (Function-counting theorem, [1]). Fix M, M ′ , N ∈ N, and consider the set F := ′ {f1 , . . . , fN } ⊆ E, where E ⊆ RM . Furthermore, let Φ : E → RM . The number of Φ-separable dichotomies of N points in Φ-general position in RM is ′

C(N, M ) := 2

′ −1 M X

k=0

N −1 . k

(B.1)

If F is not in Φ-general position, there are fewer Φ-separable dichotomies of F (see, e.g., [27]), but determining the exact number becomes more challenging. To deal with this problem, consider a statement that is dual to Definition B.1. Concretely, we associate to each f ∈ F the (M ′ − 1)-dimensional hyperplane {Φ(f )}⊥ , with goal of determining the number of regions into ′ which these N hyperplanes divide the space RM . Fig. B.3 illustrates this for the case Φ = Id. Before the solution to this problem can be stated, let us introduce the following notion. Definition B.4 ([25]). Fix M ′ ∈ N, let K be a finite index set, and consider a set of (M ′ − ′ 1)-dimensional hyperplanes in RM , denoted by {Hk }k∈K , i.e., Hk := {φk }⊥ , k ∈ K, where ′ {φk }k∈K ⊆ RM \ {0}. The set {Hk }k∈K is said to be (i) even-degenerate if K = ∅ or ! dimR

\ k∈K

≡ M ′ − |K| (mod 2),

K. Häberle and H. Bölcskei

R2 3

f1 4 1

f3 5

Figure B.3: Regions into which the 1-dimensional hyperplanes H1 , H2 , and H3 divide R2 , where Hk = {fk }⊥ , k ∈ {1, 2, 3}. Since the set {f1 , f2 , f3 } is in general position, the number of such regions is given by C(3, 2) = 6.

(ii) odd-degenerate if K ̸= ∅ and ! dimR

̸≡ M ′ − |K| (mod 2).

k∈K

We are now ready to present the solution to the general problem of counting the number of Φ-separable dichotomies. We emphasize that here F need not be in Φ-general position. ′

Theorem B.5 ([25]). Fix M ′ , N ∈ N, and consider N hyperplanes in RM each of dimension M ′ \ {0}. ⊥ {φk }N M ′ − 1, denoted by {Hk }N k=1 ⊆ R k=1 , i.e., Hk := {φk } , k ∈ {1, . . . , N }, where ′ M is given by The number of regions into which the hyperplanes {Hk }N k=1 divide R |E| − |O|, where E := {{Hk }k∈K : K ⊆ {1, . . . , N } and {Hk }k∈K is even-degenerate} and O := {{Hk }k∈K : K ⊆ {1, . . . , N } and {Hk }k∈K is odd-degenerate} . N Remark B.6. Note that E ∪ O is the power set of {Hk }N k=1 , and hence |E| + |O| = 2 . In particular, ∅ ∈ E, i.e., the empty set is even-degenerate, see Definition B.4.

As already indicated above, the classical function-counting theorem (Theorem B.3) can be deduced from Theorem B.5. Indeed, we have the following remark. ′

Remark B.7. Let F := {f1 , . . . , fN } ⊆ E ⊆ RM be in Φ-general position, where Φ : E → RM . Consider the associated (M ′ − 1)-dimensional hyperplanes Hk := {Φ(fk )}⊥ , k ∈ {1, . . . , N }. To ′ determine the number of regions into which these hyperplanes divide RM using Theorem B.5, we need to count the sets of even- and odd-degenerate hyperplanes. By the assumption that F is in Φ-general position, all sets {Hk }k∈K with K ⊆ {1, . . . , N } and 0 ≤ |K| ≤ M ′ are even-degenerate. Indeed, we have !⊥ \ k∈K

Hk =

X k∈K

spanR ({Φ(fk )})

= (spanR ({Φ(fk )}k∈K ))⊥ ,

Function-Counting Theory for Low-Dimensional Data Structures

T and hence dimR k∈K Hk = M ′ −|K|, where we used that, by assumption, the set {Φ(f is T k )}k∈K linearly independent whenever |K| ≤ M ′ . For M ′ +1 ≤ |K| ≤ N , it holds that dimR k∈K Hk = M ′ . Consequently, the degeneracy of {Hk }k∈K alternates with increasing |K| whenever M ′ + 1 ≤ |K| ≤ N . Thus, by Theorem B.5, the number of regions is given by N N N N N N + + ··· + − + − ··· ± , (B.2) ′ ′ ′ 0 1 M M +1 M +2 N ′ where the last term is positive N is even and negative otherwise. As shown in [25], PN Nif M − ′ +1+t M one can use the identity t=0 t (−1) = 0, a consequence of the binomial theorem, and the recurrence relation of binomial coefficients (Pascal’s rule) to deduce that (B.2) is equal to C(N, M ′ ).

Hausdorff measure

In this section, we review the definition of the Hausdorff measure and recall some of its basic properties. Definition C.1 (Hausdorff measure, [23, 24]). Let (X, ρ) be a metric space, AS⊆ X, and 0 < δ ≤ ∞. A collection of subsets C = {Ci }i∈N of X is called a δ-cover of A if A ⊆ i∈N Ci and if diamρ (Ci ) ≤ δ, for all i ∈ N. Here, diamρ (Ci ) := sup{ρ(x, y) : x, y ∈ Ci } denotes the diameter of the set Ci . For s ≥ 0, 0 < δ ≤ ∞, and A ⊆ X, define ( ) s X 1 s αs Hδ (A) := inf diamρ (C) : C is a δ-cover of A , 2 C∈C

R∞ where αs := Γ(s/2+1) with Γ(t) := 0 xt−1 e−x dx, t > 0, being the gamma function. The s-dimensional Hausdorff measure of a set A ⊆ X is defined to be π s/2

Hs (A) := lim Hδs (A). δ→0+

Proposition C.2 (Properties of Hausdorff measure, [23, 24]). Let X be a metric space, and consider the s-dimensional Hausdorff measure Hs on X, where s ≥ 0. (i) For every s ≥ 0, Hs is a Borel-regular outer measure. (ii) On X = Rn , the n-dimensional Hausdorff measure Hn coincides with the n-dimensional Lebesgue measure Ln , n ∈ N, i.e., Hn = Ln . (iii) If U ⊆ Rn is an s-dimensional linear subspace s ∈ {0, . . . , n}, then Ht (U) = 0,

for all t > s.

(iv) Let A ⊆ X, and let Y be another metric space. If φ : A → Y is Lipschitz, then Hs (φ(A)) ≤ Lip(φ)s Hs (A). Moreover, if X = Rn , n ∈ N, and if A is Ln -measurable, then φ(A) is Hn -measurable. Proposition C.3 (Theorem 1.15 in [24]). Let X be a metric space. Suppose µ is an open σ-finite Borel-regular measure on X. Then µ(A) = inf{µ(U ) : U open, U ⊃ A}, for each subset A ⊂ X, and µ(A) = sup{µ(C) : C closed, C ⊂ A}, for each µ-measurable subset A ⊂ X.

K. Häberle and H. Bölcskei

References [1] 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. [2] L. Schläfli, “Theorie der vielfachen Kontinuität,” Gesammelte Mathematische Abhandlungen: Band I, pp. 167–387, 1950. [3] R. O. Winder, “Single stage threshold logic,” in 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961). IEEE, 1961, pp. 321–332. [4] J. G. Wendel, “A problem in geometric probability,” Mathematica Scandinavica, vol. 11, no. 1, pp. 109–111, 1962. [5] 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. [6] A. Kowalczyk, “Separating capacity of analytic neurons,” in Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN’94), vol. 5. IEEE, 1994, pp. 3038– 3043. [7] K. Häberle and H. Bölcskei, “Separation capacity of scattering networks,” arXiv preprint arXiv:2606.30822, 2026. [8] V. N. Vapnik and A. Y. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” Theory of Probability & Its Applications, vol. 16, no. 2, pp. 264–280, 1971. [9] Y. LeCun, “The mnist com/exdb/mnist/, 1998.

database

handwritten

digits,”

http://yann. lecun.

[10] H. Narayanan and S. Mitter, “Sample complexity of testing the manifold hypothesis,” Advances in neural information processing systems, vol. 23, 2010. [11] 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. [12] G. Carlsson, “Topology and data,” Bulletin of the American Mathematical Society, vol. 46, no. 2, pp. 255–308, 2009. [13] T. Zaslavsky, Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes: Face-count formulas for partitions of space by hyperplanes. American Mathematical Soc., 1975, vol. 154. [14] R. G. Baraniuk and M. B. Wakin, “Random projections of smooth manifolds,” Foundations of computational mathematics, vol. 9, no. 1, pp. 51–77, 2009. [15] O. Christensen, An introduction to frames and Riesz bases.

Springer, 2003, vol. 7.

[16] H. G. Feichtinger and T. Strohmer, Gabor analysis and algorithms: Theory and applications. Springer Science & Business Media, 2012. [17] R. A. Horn and C. R. Johnson, Matrix analysis.

Cambridge university press, 2012.

[18] D. L. Donoho and M. Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization,” Proceedings of the National Academy of Sciences, vol. 100, no. 5, pp. 2197–2202, 2003.

Function-Counting Theory for Low-Dimensional Data Structures

[19] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 489–509, 2006. [20] D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006. [21] S. Foucart and H. Rauhut, An invitation to compressive sensing.

Springer, 2013.

[22] L. Ambrosio and B. Kirchheim, “Currents in metric spaces,” Acta Mathematica, vol. 185, pp. 1–80, 2000. [23] H. Federer, Geometric measure theory.

Springer, 2014.

[24] L. Simon, “Introduction to geometric measure theory,” Tsinghua Lectures, 2014. [25] R. O. Winder, “Partitions of n-space by hyperplanes,” SIAM Journal on Applied Mathematics, vol. 14, no. 4, pp. 811–818, 1966. [26] E. F. Harding, “The number of partitions of a set of n points in k dimensions induced by hyperplanes,” Proceedings of the Edinburgh mathematical society, vol. 15, no. 4, pp. 285–289, 1967. [27] G. Mitchison and R. Durbin, “Bounds on the learning capacity of some multi-layer networks,” Biological Cybernetics, vol. 60, no. 5, pp. 345–365, 1989.

Record · ID 329094 · SHA-256 4776fbda64cfc3c8
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.