CS Paper Radar

Towards a mathematical theory of superposition

Michael I. Ivanitskiy, John Jasper, Emily J. King, Dustin G. Mixon

cs.IT stat.MLcs.LGmath.CO ·submitted 2026-08-27 16:08 UTC · v1
theory

Abstract

We develop a mathematical theory of superposition in neural networks using tools from frame theory and compressed sensing. In our model, a sparse binary vector \(x\) of active features is encoded through an overcomplete dictionary \(W\), and feature recovery is performed by applying \(\operatorname{ReLU}(W^\top W x+b)\) with an appropriate bias vector \(b\). We prove several recovery theorems for this model. In the random-support setting, we establish high-probability support recovery for nearly tight, low-coherence dictionaries, with guarantees when the expected sparsity is up to order \(d/\log n\). In the worst-case support setting, we give a sharp and computable criterion for which sparsity levels permit support recovery. We apply this criterion to Gaussian random matrices and equiangular tight frames. For real equiangular tight frames with \(n>d+1\), we determine the exact recovery threshold in terms of the coherence. The proof of this result for real equiangular tight frames relies on a novel characterization---which should be of independent interest to frame theorists---of the distribution of signs in the Gram matrix.

Closest papers

Nearest neighbours by meaning across the whole index.

High-probability guarantees for linear accessibility in feature superposition

cs.AI stat.MLcs.IRcs.LG+1 ·2026-09-09 ·Enrico Vompa
similarity 0.67
Abstract · preprint

Neural networks can leverage feature superposition to encode more concepts than dimensions, but cross-feature interference constrains the linear accessibility of simultaneously active features. By framing linear accessibility as a compressed sensing problem, we derive high-probability bounds for fixed supports under subgaussian noise, proving the sufficient dimension scales linearly ($d=O_{\varepsilon}(k \log m)$) rather than prior worst-case quadratic limits. We characterize the asymmetry between active and inactive interference and the trade-off between interference and observation-noise budgets. We then validate these bounds across system parameters through Gaussian-tail approximations. We also introduce IHT-SAE, which uses learned iterative refinement to improve feature recovery beyond the limits of linear availability. These results quantify the geometric constraints of the linear representation hypothesis, providing a framework for evaluating sparse autoencoders, compositional generalization, and neural interpretability.

0.18

Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

cs.LG cs.ITmath.NAmath.PR+1 ·2026-09-02 ·Piyush Sao
code/data similarity 0.65
Abstract · 41 pages, 6 figures, 4 tables. Reproducibility code: https://github.com/piyush314/random-projection-geometry (pinned as a submodule). Compan…

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to $m=O(\varepsilon^{-2}\log n)$ dimensions preserves pairwise squared distances within relative error $\varepsilon$ with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature $f(D)$ of a squared distance $D$ from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data ($Σ=σ^2 I_d$), we diagonalize this operator in closed form. For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(m/ d)^{k/2}$. This yields three sharp consequences. A rank-$m$ sketch retains at most an $m/d$ fraction of the variance of any feature of one squared distance. If $m\to\infty$ and $m/d\to0$, the expected Kendall correlation is $\frac{2}π\sqrt{m/d}(1+o(1))$; for fixed $q$, nearest- neighbor agreement tends to $1/q$. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when $\log n\ll m\ll d$. After removing scale, Haar-averaged retained covariance-shape information is $(m/d)^2$. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

0.38

Feature Superposition in Neural Networks: From Theory to Practice

cs.LG ·2026-09-06 ·Dai Shi, Xiaoyu Li, Andi Han, José Miguel Hernández-Lobato
code/data similarity 0.62
Abstract

Superposition refers to neural networks representing more features than they have dimensions. It was proposed to explain polysemantic neurons, which respond to several features, and also other phenomena, such as neural scaling laws and adversarial vulnerability. A feature stored in superposition is useful to the extent that its value can be read back despite interference from the other features. The theory of superposition mainly asks how wide a layer must be for the features to be read back, and by which decoder. In theoretical models, a single linear map that reads back every combination of nonzero features needs a width nearly quadratic in their number, while sparse optimization can succeed with a width linear in that number. In practice, one may hope to interpret a trained network by recovering its features in the same way. However, its features are usually unknown, and thus they are estimated from its activations or weights by recovery methods, such as sparse autoencoders and transcoders. In this work, we organize the theory of superposition by the decoder class and its practice by the strength of the claims about a feature supported by each method's results. On the theory side, we review the lower bounds on the overlap between feature directions, the conditions under which trained toy models share dimensions among features, and the separation between storing features and computing new features. On the practice side, we categorize recovery methods into four families, from probes for a named feature to decompositions of the trained weights. We then compare their evaluations, failure modes, and applications, and grade the evidence on one scale of claims about a feature. Finally, we assess previously stated open problems and identify remaining theoretical and empirical questions about superposition in trained networks. Project page: https://eethanshi.github.io/awesome-superposition/

0.28

Compressed sensing matrices from orthogonal spaces over finite fields of odd characteristic

cs.IT math.RA ·2026-08-24 ·Kanittakorn Moonchaisook, Poom Kumam, Songpon Sriwongsa
published similarity 0.61
Abstract · 23 pages. The paper has been accepted by JAA

In this paper, we construct deterministic matrices from subspaces of orthogonal spaces over finite fields of odd characteristic and investigate their applicability to compressed sensing. The construction is based on incidence relations among three types of subspaces, yielding families of matrices with explicitly computable dimensions and coherence. Using coherence-based estimates, we establish sufficient conditions under which these matrices satisfy the Restricted Isometry Property for prescribed sparsity levels. We also provide numerical comparisons with DeVore's deterministic construction to illustrate the trade-off between the number of measurements, coherence, and sparse recovery guarantees.

0.32

Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements

cs.LG cs.DScs.IT ·2026-09-26 ·Xiaxin Li, Arya Mazumdar
similarity 0.59
Abstract

The support recovery problem in mixture of linear classifiers aims to identify the features relevant to the underlying decision rules when data is generated by a mixture of several linear decision rules. In particular, the goal is to recover the support (nonzero coordinates) of $l$ unknown $k$-sparse vectors from sign measurements. Each measurement is generated by selecting one of the $l$ vectors uniformly at random, and returning the sign of its inner product with a chosen measurement vector. In this paper, we propose adaptive and non-adaptive schemes that significantly improve upon prior results by simultaneously reducing the number of measurements and achieving sublinear decoding time. In particular, our adaptive constructions substantially reduce measurements compared to existing approaches, while also lowering decoding complexity from super-quadratic to sublinear in the ambient dimension. We further provide a non-adaptive scheme that improves previous measurement bounds while maintaining efficient decoding. Overall, our approach yields a more efficient trade-off between sample complexity and decoding time for support recovery in mixture models compared to previously known methods.

0.21

Compressive Sensing - Introduction and Relations to Deep Learning

cs.IT ·2026-08-25 ·Hung-Hsu Chou, Johannes Maly, Holger Rauhut
similarity 0.59
Abstract

Compressive sensing predicts that sparse vectors (signals) can be recovered from a small number of linear measurements via efficient algorithms. This finding, which dates back two decades, has triggered a paradigm shift in signal processing and initiated many developments both in practical signal-processing applications, such as medical imaging, radar, and astronomy, and on the theoretical side. More recently, seminal connections to the field of deep learning have led to further advances in the field, such as the use of unrolled neural networks for sparse recovery and the discovery that common training algorithms (variants of gradient descent) favor sparsity in overparameterized scenarios -- the so-called implicit bias phenomenon. This article gives an introduction to compressive sensing and outlines connections to deep learning. In particular, we will discuss generalization for neural networks generated by unrolling sparse recovery algorithms and implicit regularization for gradient descent applied to learning simplified linear neural networks.

0.06

Recovering linear images of sparse signals from indirect observations

cs.IT stat.MLcs.LGmath.OC ·2026-09-05 ·Anatoli Juditsky, Arkadi Nemirovski
hot direction similarity 0.59
Abstract

In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $ω=Ax+ξ$. It is {\em a priori} known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse---has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.

0.26

Learning the Mathematical Property for Designing Low Mutual Coherence Binary Sensing Matrices

cs.LG ·2026-08-13 ·Rekha, Santosh Singh, S. K. Neogy
similarity 0.59
Abstract · 25 pages, 18 figures

In this research work, we are constructing the sensing matrix, which is essential for the success of the compressive sensing technique. We have chosen a learning-based technique for the construction of the sensing matrix. The novelty and uniqueness of the proposed technique is that it does not use any data set and also does not use a specific application. It uses the mathematical property/constraint for the construction of the sensing matrix for the perfect recovery of the signal. The perfect recovery of signals is an old and still very challenging problem in real-world applications. In late 2000, compressive sensing became a popular mathematical tool for the perfect recovery of sparse signals. The core of the compressive technique is the construction of the sensing matrix, which satisfies certain special properties such as restricted isometry property (RIP), null space property (NSP), and spark property (SP). All these properties are NP-hard problems and hence computationally challenging to solve. For all practical purposes, the construction of the sensing matrix needs to achieve low mutual coherence to achieve the perfect recovery of the signals. We have used a neural network for the construction of the sensing matrix, and this framework constructs a binary sensing matrix with low mutual coherence. The entries in the matrix are generated through a shared underlying rule. The proposed architecture is simple and does not use large-scale training data sets. Such uniqueness and novelty bring a drastic reduction in computational cost, and also, for the first time in literature, the use of a mathematical property for defining the loss function. In this proposed research work, the mutual coherence property has been used in the neural network framework. Such a neural network framework brings generality, robustness, and reduces storage requirements.

0.10