# Random Fourier Signature Features

arXiv: https://arxiv.org/abs/2311.12214 · HTML: https://mlsanity.com/paper/2311.12214/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 83 references that are in the map.
- First posted on arXiv 20 Nov 2023.

## Builds on (most cited first, 30 of 46)

- [Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains](https://mlsanity.com/paper/2006.10739/) (2020)
- [The UCR Time Series Archive](https://mlsanity.com/paper/1810.07758/) (2018)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Neural SDEs as Infinite-Dimensional GANs](https://mlsanity.com/paper/2102.03657/) (2021)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [A Primer on the Signature Method in Machine Learning](https://mlsanity.com/paper/1603.03788/) (2016)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Kernels for sequentially ordered data](https://mlsanity.com/paper/1601.08169/) (2016)
- [Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligence](https://mlsanity.com/paper/2002.04803/) (2020)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent](https://mlsanity.com/paper/2006.05013/) (2020)
- [Sig-Wasserstein GANs for Time Series Generation](https://mlsanity.com/paper/2111.01207/) (2021)
- [The Signature Kernel is the solution of a Goursat PDE](https://mlsanity.com/paper/2006.14794/) (2020)
- [Signature moments to characterize laws of stochastic processes](https://mlsanity.com/paper/1810.10971/) (2018)
- [Signatory: differentiable computations of the signature and logsignature transforms, on both CPU and GPU](https://mlsanity.com/paper/2001.00706/) (2020)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Non-adversarial training of Neural SDEs with signature kernel scores](https://mlsanity.com/paper/2305.16274/) (2023)
- [Learning with SGD and Random Features](https://mlsanity.com/paper/1807.06343/) (2018)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Discrete-time signatures and randomness in reservoir computing](https://mlsanity.com/paper/2010.14615/) (2020)
- [Framing RNN as a kernel method: A neural ODE approach](https://mlsanity.com/paper/2106.01202/) (2021)
- [Error Bounds for Learning with Vector-Valued Random Features](https://mlsanity.com/paper/2305.17170/) (2023)
- [SigGPDE: Scaling Sparse Gaussian Processes on Sequential Data](https://mlsanity.com/paper/2105.04211/) (2021)
- [Random Warping Series: A Random Features Method for Time-Series Embedding](https://mlsanity.com/paper/1809.05259/) (2018)
- [Approximate Bayesian Computation with Path Signatures](https://mlsanity.com/paper/2106.12555/) (2021)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)

## Built on by (most cited first, 9 of 9)

- [Numerical Schemes for Signature Kernels](https://mlsanity.com/paper/2502.08470/) (2025)
- [Signature Maximum Mean Discrepancy Two-Sample Statistical Tests](https://mlsanity.com/paper/2506.01718/) (2025)
- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)
- [Infinite-dimensional Mahalanobis Distance with Applications to Kernelized Novelty Detection](https://mlsanity.com/paper/2407.11873/) (2024)
- [Local regression on path spaces with signature metrics](https://mlsanity.com/paper/2510.16728/) (2025)
- [Scalable Signature Kernel Computations for Long Time Series via Local Neumann Series Expansions](https://mlsanity.com/paper/2502.20392/) (2025)
- [Random Controlled Differential Equations](https://mlsanity.com/paper/2512.23670/) (2025)
- [Lipschitz bounds for integral kernels](https://mlsanity.com/paper/2604.02887/) (2026)
- [Branched Signature Kernel Solvers for ODEs with rough Single-Trajectory signals](https://mlsanity.com/paper/2605.25826/) (2026)

## Abstract (arXiv)

Tensor algebras give rise to one of the most powerful measures of similarity for sequences of arbitrary length called the signature kernel accompanied with attractive theoretical guarantees from stochastic analysis. Previous algorithms to compute the signature kernel scale quadratically in terms of the length and the number of the sequences. To mitigate this severe computational bottleneck, we develop a random Fourier feature-based acceleration of the signature kernel acting on the inherently non-Euclidean domain of sequences. We show uniform approximation guarantees for the proposed unbiased estimator of the signature kernel, while keeping its computation linear in the sequence length and number. In addition, combined with recent advances on tensor projections, we derive two even more scalable time series features with favourable concentration properties and computational complexity both in time and memory. Our empirical results show that the reduction in computational cost comes at a negligible price in terms of accuracy on moderate-sized datasets, and it enables one to scale to large datasets up to a million time series.