--- kind: concept slug: linear-separability title: Linear separability summary: >- Whether one point, or a small group, of a set can be cut from the rest by a linear functional and a threshold. In high dimension, random samples from a ball, a cube or a product distribution are separable with high probability, with explicit bounds. Trade-off: the bounds assume i.i.d. points from those distributions, and the paper reports no experiments beyond a qualitative figure. tags: [high-dimensional-data, measure-concentration, linear-classifier, error-correction, knowledge-transfer] papers: ["1801.03421"] related: [concentration-of-measure, intrinsic-dimension, support-vector-machine, linear-probing, knowledge-distillation, feature-whitening] status: draft updated_at: 2026-11-09 --- ## Overview A set is linearly separable when each of its points can be scored by one linear functional so that it beats every other point, which is a one-versus-rest test. Two sets X and Y are separated when a single threshold puts all of X above and all of Y below the same functional [arxiv:1801.03421 §2]. The shared invariant across the variants below is that the separating rule is a dot product with one vector plus a scalar threshold. What differs is how the vector is chosen and how likely the separation is. In the card on this page, the authors ask how often random samples in high dimension have this property. Their answer is a set of probability lower bounds, for three sampling models, and a procedure that uses the same geometry to correct a deployed system [arxiv:1801.03421 §3.1] [§3.2]. ## Variants ### Uniform ball: one point against the rest Draw M points i.i.d. uniformly from the unit ball in R^n, and fix a radius ratio 0 < r < 1 with ρ = sqrt(1 − r²) [arxiv:1801.03421 §3.1, Thm. 3.1]. The direction of the last point itself is the separating functional, with threshold r. The probability that this works for that one point is at least 1 − r^n − 0.5(M − 1)ρ^n [arxiv:1801.03421 §3.1, Thm. 3.1(a)]. Requiring it for every point, or for every pair, gives weaker bounds with more terms [arxiv:1801.03421 §3.1, Thm. 3.1(b–c)]. The paper's corollary turns these into an upper limit on M for a chosen failure level; the paper says this limit grows at least exponentially with n [arxiv:1801.03421 §3.1, Cor. 3.1]. Card: [Blessing of dimensionality](/papers/1801.03421). ### Product distribution in a cube Here the coordinates are independent, each in [0, 1], with variances bounded below by σ_0² > 0. Let R_0² be the sum of the coordinate variances and fix 0 < δ < 2/3 [arxiv:1801.03421 §3.1, Thm. 3.2]. The paper bounds the chance that centred norms concentrate within a factor (1 ± δ), and that each centred point has small inner product with the direction of the last one. The bound has two exponential terms, one per point and one per pair [arxiv:1801.03421 §3.1]. The paper says the results extend to ellipsoids, Gaussians and weakly dependent variables, but gives no proof for those extensions [arxiv:1801.03421 §3.1]. ### Tuples of m points The question changes: can a group of m points from one set be separated from another set X by one functional? The paper takes the functional to be the normalised mean of the tuple [arxiv:1801.03421 §3.1, Thm. 3.3]. The bound depends on two correlation parameters, β1 and β2, that describe the pairwise inner products inside the tuple. The paper notes two regimes. If the tuple points are uncorrelated, the bound falls as m grows. If they are positively correlated, the bound does not depend on m [arxiv:1801.03421 §3.1]. How to choose β1 and β2 for real data is not stated. ### Corrector and knowledge transfer This variant is a procedure rather than a bound. Each recorded input becomes a vector, and inputs where a student system disagrees with a teacher, or with external checks, form the error set Y [arxiv:1801.03421 §3.2] [§3.3] [alg. 1]. The error points are centred, whitened and split into positively correlated clusters. For each cluster, the functional is a Fisher-type direction, computed against the rest of the set, and its threshold is the smallest score the cluster receives [arxiv:1801.03421 alg. 1, step 2b]. The paper reports that such correctors can be cascaded [arxiv:1801.03421 §3.2] [fig. 2]. The only empirical result is a qualitative plot for a pedestrian detector with dimension 2000, taken from earlier work [arxiv:1801.03421 §3.2] [fig. 3]. Compare [Linear probing](/concepts/linear-probing), which fits a linear head on a frozen network but does not use these bounds. ## When to use which | Situation | Use | Why | |---|---|---| | You want to know how many random points a single linear cut can handle in high dimension | Ball or cube bounds | They give explicit probabilities for the stated distributions [arxiv:1801.03421 §3.1] | | The data is not i.i.d. from a ball or cube, or you cannot check that | Do not rely on the bounds; test on held-out data | The paper says the real distributions cannot be checked in advance, so validation has to be done after the fact [arxiv:1801.03421 §4] | | A deployed system makes errors, retraining is costly, and old behaviour must stay | The corrector in alg. 1 | It is non-iterative and built from closed-form Fisher-type directions, and the paper says new corrections do not destroy old ones [arxiv:1801.03421 §3.2] | | You can afford a standard classifier and need a margin-based separator | [Support vector machine](/concepts/support-vector-machine) | The paper cites a worst-case cost of order N³ for SVM training with quadratic loss, but says practical runs are cheaper [arxiv:1801.03421 §3.1] | | Points in a group are positively correlated | Tuple functional, positively correlated case | The paper's bound does not decay with the tuple size m [arxiv:1801.03421 §3.1] | | You need a bound for a specific n | Check the sign and size first | The corollary limit is negative unless the failure level exceeds r^n, so the bound can be vacuous for small n [arxiv:1801.03421 §3.1, Cor. 3.1] | Dimension rule of thumb: the paper's conclusion suggests that after whitening, dimensions of about 100 or more, with up to about 10^6 points, give more than 99% probability for the separation results. The paper calls this a rule of thumb, not a theorem [arxiv:1801.03421 §4]. ## Implementation sketch The common core is a dot product with a unit vector and a threshold. The sketch below is the exact one-versus-rest test on a given sample, using the ball functional. The probability statements are separate and are not computed here. ```pseudocode # Exact test: is point i cut from the others by the ball functional? # [arxiv:1801.03421 §3.1, Thm. 3.1(a)] # Input: points (M, n) inside the unit ball; index i; ratio r in (0, 1) # Output: True if x -> (x, unit_i) > r holds for x_i and < r for all others def separates_point(points, i, r): # Direction of the point itself; no fitting is needed [§3.1] x_i = points[i] norm_i = norm(x_i) if norm_i <= r: return False unit_i = x_i / norm_i # Every other point must score below the threshold [§3.1, Thm. 3.1(a)] for j in range(len(points)): if j != i and dot(points[j], unit_i) >= r: return False return True ``` For the corrector variant, the core step is the Fisher-type direction w = (Cov(rest) + Cov(cluster))^(−1) (mean(cluster) − mean(rest)), with threshold equal to the smallest score in the cluster [arxiv:1801.03421 alg. 1, step 2b]. The paper gives no ridge term for the matrix inversion, so a singular sum has to be handled by the implementer. ## Contradictions None known across papers, because this page uses one source. Within the source, the card's compile check found that its hand calculations of the union bound in Proposition 2.1 and of the second bound in Corollary 3.1 did not reproduce the stated limits. Treat the theorem statements as the reference and derive any limit you use [arxiv:1801.03421 §2] [§3.1, Cor. 3.1]. ## Papers - [Blessing of dimensionality](/papers/1801.03421): stochastic separation theorems for uniform ball, cube and tuple samples, and a non-iterative corrector for AI systems. No new experiments.