Dimension-Free Rank Lifting from Random Hyperplane Arrangements
Abstract
We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset X ∈ ℝm × d of m, d-dimensional input vectors separated by an angle of at least θ, we consider the random feature matrix σ(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 ≳ 1/θmax{m,log(1/δ)} neurons suffice for σ(XR) to have full row rank m with probability at least 1−δ. 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 ℝm with probability Ω(θ), 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 ≳ Cq m/(θ2q+1) log2q+1/2(m/θ) log(m/δ), where q is the degree of the activation and C > 0 is some universal constant.
Related
- Bernstein-Sato ideals for free hyperplane arrangements
- On the proof of multi-variable n/d-conjecture for hyperplane arrangements
- Suciu's Conjecture on hyperplane arrangements
- The strong monodromy conjecture for hyperplane arrangements
- Equivalence of freeness and higher order freeness of hyperplane arrangements
BibTeX
@misc{becchetti2026dimensionfree,
title = {{Dimension-Free Rank Lifting from Random Hyperplane Arrangements}},
author = {Luca Becchetti and Matteo Russo and Ruben Skorupinski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39855},
eprint = {2609.39855},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39855},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dimension-Free Rank Lifting from Random Hyperplane Arrangements
AU - Luca Becchetti
AU - Matteo Russo
AU - Ruben Skorupinski
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39855
UR - https://arxiv.org/abs/2609.39855
AB - We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset X ∈ ℝ^m × d of m, d-dimensional input vectors separated by an angle of at least θ, we consider the random feature matrix σ(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 ≳ 1/θmax{m,log(1/δ)} neurons suffice for σ(XR) to have full row rank m with probability at least 1−δ. 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 ℝ^m with probability Ω(θ), 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 ≳ C^q m/(θ^2q+1) log^2q+1/2(m/θ) log(m/δ), where q is the degree of the activation and C > 0 is some universal constant.
ER -