Research map / Architectures and efficiency / RNNs and normalization
Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvalues
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that a single diagonal linear RNN (real or complex) followed by a position-wise MLP can approximate arbitrary regular causal sequence-to-sequence maps, and that complex eigenvalues near the unit circle improve conditioning of input reconstruction from the hidden state.
Problem
Expressive power of architectures that interleave linear diagonal RNNs (SSMs such as S4, LRU) with position-wise MLPs, especially the role of initialization and complex eigenvalues, is poorly understood.
Approach
Separation of concerns: the linear RNN provides a (near-)lossless encoding of the input sequence in its hidden state via a Vandermonde-based linear reconstruction map, and a time-independent 1-hidden-layer MLP performs non-linear processing; Barron-theory extended to sequences of functions gives width bounds. Complex eigenvalues on the unit ring yield well-conditioned reconstruction, while real ei
Key results
- Theorem: a diagonal real or complex linear RNN of width N >= dim(V) followed by a 1-hidden-layer MLP of width O(L/eps^2) approximates any regular causal sequence-to-sequence map to error eps.
- With eigenvalues near the unit circle (r_min=0.99), the Vandermonde reconstruction of MNIST digits from the final hidden state is near perfect; with r_min=0 only recent tokens are recovered.
- A trained LRU (N=128) plus 1-layer MLP (D=256) learns the protein transduction ODE map with low out-of-sample test loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the trained RNN hidden dimension | LRU reconstruction model · Sequential MNIST and PathFinder | reconstruction error | Helped |
| Use a linear rather than nonlinear reconstruction decoder at N=1024 | LRU reconstruction model · Sequential MNIST and PathFinder | reconstruction error | Helped |
| Use a nonlinear reconstruction decoder at small hidden dimensions | LRU reconstruction model · Sequential MNIST and PathFinder | reconstruction error | Helped |
| Train the linear RNN and reconstruction map jointly | LRU reconstruction model · Sequential MNIST and PathFinder | reconstruction error | Helped |
| Use a linear RNN with N=128 followed by a 1-HL MLP with D=256 | Protein transduction model · Protein transduction (L=2048) | test loss | Helped |
| Initialize complex eigenvalues closer to the unit circle | Random complex diagonal RNN with Vandermonde pseudoinverse · MNIST (784 tokens) | reconstruction error | Helped |
| Initialize eigenvalues with r_min=0 | Random complex diagonal RNN with Vandermonde pseudoinverse · MNIST (784 tokens) | reconstruction error | Hurt |
| Set eigenvalues to the N-th complex roots of 1 | Complex diagonal RNN with Vandermonde pseudoinverse · MNIST (784 tokens) | reconstruction error | Mixed |
| Increase hidden state size | Random complex diagonal RNN with Vandermonde pseudoinverse · MNIST (784 tokens) | reconstruction error | Helped |
| Increase r_min toward 1 | Random complex diagonal RNN with Vandermonde pseudoinverse · MNIST (784 tokens) | reconstruction error | Helped |
| Initialize eigenvalues in T(0.99,1) rather than T(0.95,1) | Complex diagonal RNN with learned reconstruction map · Sparse random inputs (L=4096, P=32 Haar wavelets) | minimum hidden dimension for perfect reconstruction: N=256 -> N=64 | Helped |
| Reduce the number of basis functions P | Sparse-input reconstruction · Sparse random inputs | condition number of Ω^TΩ | Helped |
Surprising findings
- Real diagonal recurrences are already sufficient for universality, but their Vandermonde condition number grows exponentially with N, causing information loss in practice.
- For learned reconstruction, a linear decoder beats a non-linear one at N=1024, which the authors attribute to optimization of wide MLPs.
Limitations
- Approximation guarantees require the MLP width to scale as O(L) and hidden state to be at least the input dimension, which is large in the worst case.
- Reconstruction errors at moderate hidden-state dimensions are not modeled by the theory.
- Finite-alphabet tokens and finite-precision settings are not covered.
Experimental setup
Datasets: MNIST PathFinder Long-range Arena protein transduction ODE simulations
Benchmarks: MNIST reconstruction PathFinder reconstruction protein transduction ODE
Metrics: reconstruction L2 error condition number test loss
Baselines: S4D-Lin LRU non-linear RNN
Builds on: S4 LRU Barron's theorem HiPPO
Closest papers by meaning
- Bridging Expressivity and Scalability with Adaptive Unitary SSMs (NeurIPS 2025 · similarity 0.87)
- DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products (NeurIPS 2025 · similarity 0.87)
- Linear Attention for Efficient Bidirectional Sequence Modeling (NeurIPS 2025 · similarity 0.87)
- Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models (NeurIPS 2025 · similarity 0.86)
- Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues (ICLR 2025 · similarity 0.86)
- Explaining Modern Gated-Linear RNNs via a Unified Implicit Attention Formulation (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.