mlsanityData to 14 Oct 2026

Random Fourier Signature Features

arXiv 2311.12214 ↗First posted 20 Nov 2023stat.ML cs.LG stat.MEcited by 9

Not on the map. Why?

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.

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

46 of 83 references.

References · 46

  1. 2020Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domainscited by 2,200
  2. 2018The UCR Time Series Archivecited by 431
  3. 2016Generalization Properties of Learning with Random Featurescited by 164
  4. 2021Neural SDEs as Infinite-Dimensional GANscited by 161
  5. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 109
  6. 2016A Primer on the Signature Method in Machine Learningcited by 104
  7. 2016Orthogonal Random Featurescited by 91
  8. 2016Kernels for sequentially ordered datacited by 84
  9. 2020Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligencecited by 82
  10. 2015On the Error of Random Fourier Featurescited by 76
  11. 2014Fastfood: Approximate Kernel Expansions in Loglinear Timecited by 74
  12. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
34 more
  1. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 70
  2. 2021Sig-Wasserstein GANs for Time Series Generationcited by 60
  3. 2020The Signature Kernel is the solution of a Goursat PDEcited by 58
  4. 2018Signature moments to characterize laws of stochastic processescited by 56
  5. 2020Signatory: differentiable computations of the signature and logsignature transforms, on both CPU and GPUcited by 46
  6. 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 45
  7. 2015Optimal Rates for Random Fourier Featurescited by 38
  8. 2023Non-adversarial training of Neural SDEs with signature kernel scorescited by 37
  9. 2018Learning with SGD and Random Featurescited by 33
  10. 2018But How Does It Work in Theory? Linear SVM with Random Featurescited by 28
  11. 2021Hybrid Random Featurescited by 25
  12. 2020Discrete-time signatures and randomness in reservoir computingcited by 23
  13. 2021Framing RNN as a kernel method: A neural ODE approachcited by 23
  14. 2023Error Bounds for Learning with Vector-Valued Random Featurescited by 23
  15. 2021SigGPDE: Scaling Sparse Gaussian Processes on Sequential Datacited by 22
  16. 2018Random Warping Series: A Random Features Method for Time-Series Embeddingcited by 12
  17. 2021Approximate Bayesian Computation with Path Signaturescited by 12
  18. 2022Improved Random Features for Dot Product Kernelscited by 12
  19. 2022Capturing Graphs with Hypo-Elliptic Diffusionscited by 12
  20. 2018Streaming Kernel PCA with tildeO(√n) Random Featurescited by 11
  21. 2020Tensorized Random Projectionscited by 11
  22. 2016Recycling Randomness with Structure for Sublinear time Kernel Expansionscited by 9
  23. 2017Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-offcited by 8
  24. 2022Amortised Likelihood-free Inference for Expensive Time-series Simulators with Signatured Ratio Estimationcited by 8
  25. 2021Tensor Random Projection for Low Memory Dimension Reductioncited by 7
  26. 2018On Kernel Derivative Approximation with Random Fourier Featurescited by 6
  27. 2019Gaussian Sketching yields a J-L Lemma in RKHScited by 6
  28. 2022Local Random Feature Approximations of the Gaussian Kernelcited by 6
  29. 2020Seq2Tens: An Efficient Representation of Sequences by Low-Rank Tensor Projectionscited by 5
  30. 2020Path Signatures on Lie Groupscited by 4
  31. 2022Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernelcited by 4
  32. 2020Generalized iterated-sums signaturescited by 3
  33. 2017Sketching the order of eventscited by 2
  34. 2023Non-parametric online market regime detection and regime clustering for multidimensional and path-dependent data structurescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 3.

9 papers.

  1. 2025Numerical Schemes for Signature Kernelscited by 3
  2. 2025Signature Maximum Mean Discrepancy Two-Sample Statistical Testscited by 3
  3. 2026Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSDcited by 2
  4. 2024Infinite-dimensional Mahalanobis Distance with Applications to Kernelized Novelty Detectioncited by 1
  5. 2025Local regression on path spaces with signature metricscited by 1
  6. 2025Scalable Signature Kernel Computations for Long Time Series via Local Neumann Series Expansionscited by 0
  7. 2025Random Controlled Differential Equationscited by 0
  8. 2026Lipschitz bounds for integral kernelscited by 0
  9. 2026Branched Signature Kernel Solvers for ODEs with rough Single-Trajectory signalscited by 0