PaperlayerView exact revision on arXiv

Source-linked AI summary

Dimension-Free Rank Lifting from Random Hyperplane Arrangements

Luca Becchetti, Matteo Russo, Ruben Skorupinski

arXiv:2609.39855v1cs.LGmath.PR

TL;DR

The paper asks how wide a frozen random hidden layer must be to lift the rank of features on separated data. It uses local hyperplane crossings to establish a dimension-free exact-rank width guarantee, while also studying quantitative stable rank.

  • Problem

    The paper asks when a frozen random feature matrix has full row rank, a certificate that arbitrary labels can be interpolated by training only the output layer.

    Source: §1 · pp. 1–2

  • Method

    For exact rank, the proof couples nearby Gaussian directions so a local crossing of an active hyperplane breaks a proposed linear relation.

    Source: §1.1 · p. 5

  • Results

    The exact-rank guarantee is dimension-free, replaces exponential dependence on m with linear dependence for fixed θ, and applies to positively homogeneous nonpolynomial activations.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    Full row rank means the same random representation can linearly realize every target on the dataset through an output-layer readout.

    Source: §1 · p. 2

    Pure monomial activations can fail to lift rank for some projectively separated datasets, regardless of the number of random features.

    Source: §2 · p. 8

Abstract

from arXiv · show

We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset $X \in \mathbb{R}^{m \times d}$ of $m$, $d$-dimensional input vectors separated by an angle of at least $\theta$, we consider the random feature matrix $\sigma(XR)$, where $R$ is standard Gaussian. For positively homogeneous nonpolynomial activations, which include sign, Heaviside, ReLU, and ReLU powers among others, we prove that $$n \gtrsim \frac{1}{\theta}\max\left\{m,\log\left(\frac{1}{\delta}\right)\right\}$$ neurons suffice for $\sigma(XR)$ to have full row rank $m$ with probability at least $1-\delta$. This dimension-free bound exponentially improves the previous general-dimensional guarantee for sign features (Drago et al., 2026) and is essentially tight. The proof shows that one random feature column escapes every proper subspace of $\mathbb{R}^m$ with probability $\Omega(\theta)$, using a coupling of nearby Gaussian directions and a local crossing of the induced hyperplane arrangement. We also study stable rank lifting, where the goal is to establish a quantitative analogue of exact rank lifting, i.e., a lower bound on the smallest eigenvalue of the empirical feature Gram matrix in high-probability. Our analysis unifies and generalizes stable rank guarantees for all $q$-homogeneous non-polynomial activations following prior work in Panigrahi et al. (2020) and Song (2026). In particular, we combine a diagonally dominant Taylor tail of the population kernel with truncation and matrix concentration, to show that for positively homogeneous nonpolynomial activations, stable rank lifting is achieved at width $$n \gtrsim C^q \frac{m}{\theta^{2q+1}} \log^{2q+\frac{1}{2}}\left(\frac{m}{\theta}\right) \log\left(\frac{m}{\delta}\right),$$ where $q$ is the degree of the activation and $C > 0$ is some universal constant.

1 Introduction

The paper studies when frozen Gaussian random features provide full row rank and when that rank is quantitatively stable. It develops exact- and stable-rank guarantees using hyperplane-arrangement geometry.

1 Introduction

  • Full row rank certifies that a frozen random representation can linearly realize arbitrary labels on the dataset.This separates representational capacity at initialization from the later question of optimizing the representation.Source: §1 · pp. 1–2

1.1 Our Contributions and Techniques

  • The paper establishes a dimension-free exact-rank width guarantee, replacing exponential dependence on m with linear dependence for fixed θ and removing dependence on ambient dimension d.The guarantee covers positively homogeneous nonpolynomial activations, including sign, ReLU, nonlinear leaky ReLU, and ReLU powers.Source: §1.1 · pp. 2–3
  • Stable rank lifting strengthens exact rank by quantitatively controlling the smallest eigenvalue of the empirical feature Gram matrix.The paper presents a unified, nonasymptotic treatment for positively homogeneous nonpolynomial activations of arbitrary nonnegative integer degree.Source: §1.1 · pp. 3–4
  • The paper combines Taylor-tail and Gershgorin arguments with Gaussian kernel expansions, truncation, and matrix concentration for stable-rank analysis.The proof uses the dual hyperplane-arrangement perspective: local chamber crossings support exact rank, while the correlation kernel controls stable rank.Source: §1.1 · pp. 3–4
  • A local crossing of one active hyperplane gives each next Gaussian feature column probability Ω(θ) of escaping any proposed proper subspace.A coupled Gaussian perturbation crosses exactly one active hyperplane with probability at least θ/2π; the two endpoints share the standard Gaussian distribution.Source: §1.1 · p. 5

1.2 Related Work

  • Unlike ’s global chamber-volume approach and proportional-asymptotic spectral analyses, this work gives nonasymptotic guarantees for fixed, projectively separated data.The related-work discussion contrasts its dimension-free results with bounds that depend on ambient dimension and with asymptotic regimes.Source: §1.2 · pp. 6–7

2 Setup and Assumptions

The setup represents the inputs with Gaussian random features and assumes pairwise projective separation. It specifies positively homogeneous activations, explains how input norms affect exact and stable rank, and identifies a polynomial obstruction to dimension-independent rank lifting.

2 Setup and Assumptions

  • Z = σ(XR) has one row per input representation and one column per random neuron’s responses across the dataset.The Gaussian columns of R are independent, and σ is applied entrywise.Source: §2 · p. 7
  • Projective separation requires pairwise angles to lie in [θ, π − θ], excluding nearly parallel and nearly antiparallel input directions.This two-sided separation is necessary for a theorem covering sign features, which coincide or oppose for parallel or antiparallel inputs.Source: §2 · p. 7
  • The activation class is positively homogeneous of a nonnegative integer degree q, including sign, Heaviside, ReLU, leaky ReLU, and ReLU powers.For Gaussian preactivations, the value of σ(0) is irrelevant because preactivations are nonzero almost surely.Source: §2 · pp. 7–8
  • For exact rank, normalizing each input to a unit direction preserves rank; for stable rank, the corresponding eigenvalue bound scales by min_i ||x_i||_2^(2q).The stable-rank scaling follows from the diagonal rescaling by the input norms.Source: §2 · p. 8
  • Monomial activations can obstruct dimension-independent rank lifting: some projectively separated datasets cannot yield full row rank at any width.The setup identifies pure polynomials, up to their value at zero, as the obstruction subclass.Source: §2 · p. 8
  • A central hyperplane arrangement partitions weight space into open, full-dimensional chambers, and adjacent chambers share a codimension-one face.The closures of the chambers and their faces form a polyhedral fan.Source: §2 · p. 8

3 Exact Rank Lifting

The section proves exact rank lifting by showing that each new random feature column escapes any proper subspace with probability proportional to the input separation. Sequential sampling turns this local guarantee into full row rank, without a dependence on ambient dimension.

3 Exact Rank Lifting

  • Positive homogeneity makes row normalization rank-preserving, so the exact-rank argument can work with normalized inputs.The argument concerns exact rank only and does not establish a quantitative lower bound on the smallest eigenvalue.Source: §3 · p. 9
  • A local crossing of one hyperplane gives adjacent chambers, where the activation-weighted function cannot vanish on both sides.The coupling uses nearby correlated Gaussian directions; the probability of exactly one sign change is at least θ/(2π).Source: §3 · p. 10
  • Monomials are excluded because rank-deficient inputs can keep their feature distribution inside a proper subspace.For σ(t)=t and rank(U)<m, the image lies in a hyperplane orthogonal to a nonzero vector in ker(U⊤).Source: §3 · p. 11
  • Every proper subspace is escaped by one random feature column with probability at least θ/(4π), enabling full rank through sequentially revealed columns.The proof lower-bounds the probability of reaching full rank by revealing independent columns and bounding each conditional escape probability.Source: §3 · pp. 9, 11
  • A dimension-free width bound gives exact rank lifting for positively homogeneous nonpolynomial activations, with width linear in the number of points for fixed separation.The result covers sign, ReLU, nonlinear leaky ReLU, and ReLU powers; the theorem’s confidence requirement is chosen to meet the target failure probability.Source: §3 · pp. 9, 11, 12

4 Stable Rank Lifting

Stable rank lifting strengthens exact rank by requiring a quantitative lower bound on the empirical feature Gram matrix’s smallest eigenvalue. The section combines a population-kernel eigenvalue bound with truncation and matrix concentration to obtain finite-width guarantees.

4 Stable Rank Lifting

  • Theorem 4.1 establishes finite-width stable rank lifting for projectively separated data and positively homogeneous nonpolynomial activations.By positive homogeneity, bounds for the original data follow by diagonal rescaling from bounds for the row-normalized matrix.Source: §4 · p. 12
  • Truncation and matrix Chernoff transfer a positive population-kernel eigenvalue lower bound to a high-probability lower bound for the empirical Gram matrix.The truncation threshold is chosen so the expected truncated kernel retains at least κσ/2 of the population minimum eigenvalue.Source: §4 · pp. 12–13
  • A Taylor-tail and Gershgorin argument lower-bounds the population kernel’s minimum eigenvalue using projective separation.The Taylor expansion has nonnegative positive-semidefinite terms, and a sufficiently high-degree tail is diagonally dominant.Source: §4 · pp. 13–14
  • The sign-activation analysis avoids truncation because the feature-column squared norm equals m almost surely.The remark also gives corresponding stable-rank implications for Heaviside and ReLU activations.Source: §4 · p. 15
  • For plain ReLU covariance, the derived θ^3/log^(3/2)(m) rate is not shown to be worst-case tight.A matching upper bound requires a separate construction; the matching construction cited for the ReLU derivative Gram matrix does not establish one for plain ReLU covariance.Source: §4 · p. 15

A.1 Minimum-Norm Interpolant

For a full-row-rank feature matrix, the minimum-norm interpolant is given explicitly and is unique. The proof uses orthogonality between the row space and the null space, with the Gram matrix’s smallest eigenvalue controlling the inverse.

A.1 Minimum-Norm Interpolant

  • For full-row-rank Z, the unique minimum-Euclidean-norm solution to Zw = y is w⋆ = Z⊤(ZZ⊤)−1y.Full row rank makes ZZ⊤ positive definite and invertible.Source: §A.1 · p. 20
  • The interpolant is orthogonal to every difference between it and another solution, because those differences lie in ker(Z).The interpolant lies in range(Z⊤), which is the orthogonal complement of ker(Z).Source: §A.1 · p. 20
  • The largest eigenvalue of (ZZ⊤)−1 is 1/λmin(ZZ⊤), linking inverse-Gram control to the smallest Gram eigenvalue.Source: §A.1 · p. 20

A.2 Pure Polynomial Activations

Pure monomial activations confine random features to a finite-dimensional polynomial space, so full row rank is impossible when the dataset exceeds that space's dimension.

  • When m exceeds that feature-space dimension, full row rank is impossible for every realization of R.Source: §A.2 · pp. 20–21
  • For σ(t)=ct^q with c≠0 and integer q≥0, the case q=0 is the constant activation.Source: §A.2 · p. 20
  • Each feature column lies in the space of homogeneous degree-q polynomials in d variables, whose dimension caps the feature matrix rank.Source: §A.2 · pp. 20–21

A.3 Lower Bounds on the Necessary Width

The section gives exact-rank width lower-bound examples for sign and ReLU features. Their failures arise when random feature columns obey linear dependencies across the selected inputs.

  • Proposition A.3 establishes confidence lower bounds on the width required for exact rank lifting.Source: §A.3 · p. 21
  • For two inputs at projective separation θ, sign features collapse into a one-dimensional subspace when their Gaussian projections agree, with probability 1 − θ/π per column.Source: §A.3 · p. 21
  • For three θ-separated ReLU inputs, a feature column obeys a fixed linear relation when the two outer projections share a sign, giving rank at most 2 if this holds across all columns.Source: §A.3 · pp. 21–22

A.4 Exact versus Stable Rank Lifting: Dependence on the Degree

For one-dimensional inputs with σ(t)=t^q, exact rank lifting has a probability independent of q, while stable rank lifting becomes increasingly demanding as q grows.

A.4 Exact versus Stable Rank Lifting: Dependence on the Degree

  • Exact rank occurs if and only if some Gaussian variable is positive, so its probability is independent of q.Source: §A.4 · p. 22
  • Stable rank lifting depends strongly on the homogeneity degree q, and its necessary width is exponential in q.Source: §A.4 · p. 22
  • The stable-rank calculation requires at least one preactivation larger than q/(2e), connecting the width requirement to a Gaussian-tail event.Source: §A.4 · p. 22

B.1 Computation of the Sign-difference Bound

The sign-difference bound uses a small rotation coupling of Gaussian directions to estimate the chance of exactly one hyperplane crossing. Angular separation controls the intersections that could produce multiple sign changes.

  • The coupling rotates g to a nearby Gaussian direction ˜g, and sign differences count hyperplanes crossed along the segment between them.Source: §B.1 · p. 23
  • For each input direction, the probability of a sign change under the rotation is φ/π.Source: §B.1 · p. 23
  • Pairwise sign-change events correspond to a rectangle of preactivation values, and separation controls these intersections to bound the chance of exactly one change.Source: §B.1 · pp. 23–24

B.2 Concentration of the Empirical Kernel

Proposition 4.2 establishes concentration of the empirical kernel when the population kernel has positive minimum eigenvalue, with failure probability at most δ.

  • With κσ = λmin(K) > 0, Proposition 4.2 bounds empirical-kernel concentration so the failure probability is at most δ.Source: §B.2 · pp. 24–25
  • Truncating columns and applying matrix Chernoff to independent truncated positive-semidefinite rank-one matrices yields a lower-tail bound for the empirical Gram matrix.Source: §B.2 · p. 24
  • The truncated population kernel is compared with K using an eigenvalue perturbation bound based on ∥K − KL∥.Source: §B.2 · p. 25
  • Cauchy–Schwarz and Gaussian tail bounds control truncation error without requiring the two preactivations to be independent.Source: §B.2 · p. 25

B.3 Taylor Coefficients of q-Homogeneous Activations and Their Tail

This section derives Taylor coefficients for the population kernel of q-homogeneous activations, establishes their nonnegativity, and bounds the high-degree tail.

  • The population kernel ψσ(t) = E[σ(ζ1)σ(ζ2)] has a Taylor expansion whose coefficients are nonnegative.Source: §B.3 · p. 26
  • The coefficient calculation uses Gaussian integrals and extends an integral identity analytically to every q ≥ 0.Source: §B.3 · pp. 26–27
  • For k > q, the tail analysis uses Gamma-ratio bounds and shows that one parity class has numerator at least Δq/2.Source: §B.3 · p. 27
  • The Taylor series converges absolutely at t = 1 and t = −1, with endpoint values established by dominated and monotone convergence.Source: §B.3 · pp. 27–28
  • Lemma B.2 bounds its stated expression for integer q, with the proof treating q ≥ 1 and q = 0 separately.Source: §B.3 · pp. 28–29
Loading 2609.39855v1…