[Paper] Linear Reservoir: A Diagonalization-Based Optimization

Source: arXiv - 2602.19802v1

Overview

The paper presents a clever way to speed up Linear Echo State Networks (ESNs)—a popular type of recurrent neural network used for time‑series forecasting and signal processing. By moving the reservoir dynamics into the eigenbasis of its recurrent weight matrix, the authors turn an expensive matrix‑multiply step ((O(N^2))) into a set of cheap element‑wise operations ((O(N))). The result is a drop‑in replacement for standard Linear ESNs that keeps accuracy while delivering substantial runtime gains.

Key Contributions

• Diagonalization‑based reservoir update: Reformulates the recurrent update in the eigenbasis, eliminating the dense matrix multiplication.
• Three practical variants:
  1. Eigenbasis Weight Transformation (EWT) – preserves the behavior of any already‑trained Linear ESN.
  2. End‑to‑End Eigenbasis Training (EET) – trains readout weights directly in the eigenbasis, simplifying the learning pipeline.
  3. Direct Parameter Generation (DPG) – bypasses diagonalization altogether by sampling eigenvalues/eigenvectors, enabling “design‑by‑choice” reservoirs.
• Theoretical analysis showing that the transformed dynamics are mathematically equivalent to the original linear system.
• Extensive empirical validation on benchmark time‑series tasks, demonstrating near‑identical prediction accuracy with up to 10×‑30× speedups depending on reservoir size.
• Open‑source implementation (released with the paper) that integrates seamlessly with existing ESN libraries.

Methodology

1. Linear ESN Recap

   • State update: (\mathbf{x}_{t+1}= \mathbf{W}\mathbf{x}t + \mathbf{U}\mathbf{u}{t+1}) where (\mathbf{W}) is the recurrent matrix ((N\times N)).
   • In a vanilla implementation each time step requires an (O(N^2)) matrix‑vector product.

2. Eigenbasis Reformulation

   • Compute the eigendecomposition (\mathbf{W}= \mathbf{V}\mathbf{\Lambda}\mathbf{V}^{-1}) once (offline).
   • Transform the state into the eigenbasis: (\tilde{\mathbf{x}}_t = \mathbf{V}^{-1}\mathbf{x}_t).
   • The update becomes (\tilde{\mathbf{x}}_{t+1}= \mathbf{\Lambda}\tilde{\mathbf{x}}t + \tilde{\mathbf{U}}\mathbf{u}{t+1}) where (\mathbf{\Lambda}) is diagonal and (\tilde{\mathbf{U}}=\mathbf{V}^{-1}\mathbf{U}).
   • Because (\mathbf{\Lambda}) is diagonal, the multiplication reduces to element‑wise scaling, i.e., (O(N)).

3. Three Deployment Strategies

   • EWT: After training a conventional ESN, simply apply (\mathbf{V}^{-1}) to the readout weights, preserving the original dynamics.
   • EET: Train the readout directly on (\tilde{\mathbf{x}}_t); the loss landscape is unchanged, but the forward pass is cheaper.
   • DPG: Randomly generate a set of eigenvalues (subject to the echo‑state condition) and orthogonal eigenvectors, constructing (\mathbf{W}) on the fly without ever performing a full eigendecomposition.

4. Complexity Discussion

   • One‑time cost: eigendecomposition (O(N^3)) (or (O(N^2)) for DPG).
   • Per‑step cost after that: (O(N)) for state update + (O(NM)) for input injection (where (M) is input dimension), which is the same order as the original input term.

Results & Findings

• Accuracy: Across all tasks, the optimized variants match or stay within 1‑2 % of the baseline error metrics.
• Stability: The echo‑state condition (spectral radius < 1) is naturally enforced by constraining eigenvalues during DPG, simplifying hyper‑parameter tuning.
• Scalability: Larger reservoirs (N ≥ 2000) benefit the most, as the quadratic term dominates the vanilla runtime.

Practical Implications

• Real‑time inference: Edge devices or low‑power micro‑controllers can now run Linear ESNs for streaming sensor data without hitting CPU bottlenecks.
• Faster hyper‑parameter sweeps: Since the per‑step cost drops dramatically, developers can explore larger reservoirs or longer training windows in the same wall‑clock time.
• Simplified model design: DPG encourages a “design‑by‑eigenvalues” mindset—pick a spectral shape (e.g., uniform, Gaussian) that matches the desired memory decay, generate orthogonal eigenvectors, and you have a ready‑to‑use reservoir.
• Compatibility: The methods are library‑agnostic; they can be wrapped around popular Python ESN packages (e.g., pyESN, reservoirpy) with a few lines of code.
• Potential for hybrid models: Because the transformation is linear, it can be combined with non‑linear readouts (e.g., kernel methods, shallow MLPs) to boost expressive power while retaining the speed advantage.

Limitations & Future Work

• One‑time diagonalization cost: For extremely large reservoirs (N > 10⁴) the initial eigendecomposition can become memory‑intensive; the authors suggest using iterative or randomized eigensolvers as a remedy.
• Linear dynamics only: The speedup applies to linear ESNs. Extending the diagonalization trick to non‑linear reservoirs (e.g., tanh activation) is non‑trivial and left for future research.
• Numerical stability: In finite‑precision arithmetic, repeated transformations between bases can accumulate rounding errors; careful conditioning of (\mathbf{V}) is required.
• Task diversity: Experiments focus on univariate time‑series; evaluating on high‑dimensional sequence tasks (e.g., video or language) would further validate the approach.

The authors plan to explore structured eigenvalue sampling (e.g., low‑rank or block‑diagonal spectra) and GPU‑friendly implementations that exploit the embarrassingly parallel element‑wise updates.

Authors

• Romain de Coudenhove
• Yannis Bendi-Ouis
• Anthony Strock
• Xavier Hinaut

Paper Information

• arXiv ID: 2602.19802v1
• Categories: cs.DC, cs.NE, math.CV, math.DS
• Published: February 23, 2026
• PDF: Download PDF