Dimension-Free Rank Lifting from Random Hyperplane Arrangements

arXiv:2609.39855v1 Announce Type: new 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 in R^{m imes d} of m, d-dimensional input vectors separated by an angle of at least heta, 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}{heta}maxleft{m,logleft(frac{1}{elta}right)right} neurons suffice for sigma(XR) to have full row rank m with probability at least 1-elta. 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 R^m with probability Omega(heta), 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}{heta^{2q+1}} log^{2q+frac{1}{2}}left(frac{m}{heta}right) logleft(frac{m}{elta}right), where q is the degree of the activation and C > 0$ is some universal constant.

Source: arXiv cs.LG | 2026-10-01

Related