Multiplier-Free Hadamard Reservoirs for Time Series in Tight Settings

Recurrent models for time series are increasingly deployed under budgets fixed in advance, i.e., a memory footprint, a per-step latency target and, on neuromorphic substrates, a bounded number of values that can be programmed and kept calibrated. Reservoir Computing removes the cost of training the recurrence, which makes it a natural candidate for such substrates, but not that of applying it, since a dense recurrent matrix still requires $O(N^2)$ storage, operations and analog values. In this paper, we replace it with a structured orthogonal operator, built from two sign diagonals, a permutation and a fast Walsh-Hadamard transform, which is multiplier-free, stores $O(N)$ discrete parameters and is applied in $O(Nlog N)$ additions. We instantiate it in a standard and in a memristive-friendly Echo State Network, with one binary input connection per unit. Our analysis shows that it attains the memory of a dense orthogonal recurrence and the one-step mixing of a dense random one, with an echo state condition that is tight in the recurrent scaling. Experiments on twenty classification and seven regression benchmarks, up to N = 8192, show that the structured models match dense reservoirs, while the recurrent step is up to 50×faster than a dense product and 104×smaller in memory, and in-loop 8-bit state quantization is essentially free.