# Dimension-Free Rank Lifting from Random Hyperplane Arrangements

arXiv: https://arxiv.org/abs/2609.39855 · HTML: https://mlsanity.com/paper/2609.39855/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 62 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 30 of 36)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020)
- [A Random Matrix Approach to Neural Networks](https://mlsanity.com/paper/1702.05419/) (2017)
- [Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks](https://mlsanity.com/paper/2005.11879/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Neural Networks Learning and Memorization with (almost) no Over-Parameterization](https://mlsanity.com/paper/1911.09873/) (2019)
- [Characterizing the Spectrum of the NTK via a Power Series Expansion](https://mlsanity.com/paper/2211.07844/) (2022)
- [Randomized Nonlinear Component Analysis](https://mlsanity.com/paper/1402.0119/) (2014)
- [Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape](https://mlsanity.com/paper/2305.19510/) (2023)
- [A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilities](https://mlsanity.com/paper/2410.18938/) (2024)
- [The capacity of feedforward neural networks](https://mlsanity.com/paper/1901.00434/) (2019)
- [Effect of Activation Functions on the Training of Overparametrized Neural Nets](https://mlsanity.com/paper/1908.05660/) (2019)
- [The Separation Capacity of Random Neural Networks](https://mlsanity.com/paper/2108.00207/) (2021)

## Abstract (arXiv)

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 gtrsim frac1θmaxleftm,logleft(frac1δright)right 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 Omega(θ), 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 Cq fracmθ2q+1 log^2q+frac12left(fracmθright) logleft(fracmδright), where q is the degree of the activation and C > 0 is some universal constant.