mlsanityData to 7 Oct 2026

Orthogonal Random Features

arXiv 1610.09072 ↗First posted 28 Oct 2016cs.LG stat.MLcited by 89

Not on the map. Why?

Abstract (arXiv)

We present an intriguing discovery related to Random Fourier Features: in Gaussian kernel approximation, replacing the random Gaussian matrix by a properly scaled random orthogonal matrix significantly decreases kernel approximation error. We call this technique Orthogonal Random Features (ORF), and provide theoretical and empirical justification for this behavior. Motivated by this discovery, we further propose Structured Orthogonal Random Features (SORF), which uses a class of structured discrete orthogonal matrices to speed up the computation. The method reduces the time cost from O(d2) to O(d log d), where d is the data dimensionality, with almost no compromise in kernel approximation quality compared to ORF. Experiments on several datasets verify the effectiveness of ORF and SORF over the existing methods. We also provide discussions on using the same type of discrete orthogonal structure for a broader range of applications.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 15; 2023: 14; 2024: 11; 2025: 15; 2026: 18.

89 papers.

Sort:

By area:

  1. 2021Random Feature Attentioncited by 350
  2. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  3. 2022Monarch: Expressive Structured Matrices for Efficient and Accurate Trainingcited by 100
  4. 2021Finetuning Pretrained Transformers into RNNscited by 94
  5. 2022Deep End-to-end Causal Inferencecited by 93
  6. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
  7. 2022A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awarenesscited by 49
  8. 2024QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overheadcited by 47
  9. 2022Accelerated Linearized Laplace Approximation for Bayesian Deep Learningcited by 27
  10. 2022NeuralEF: Deconstructing Kernels by Deep Neural Networkscited by 26
  11. 2021Hybrid Random Featurescited by 25
  12. 2021Learning with Density Matrices and Random Featurescited by 17
38 more
  1. 2023Taming graph kernels with random featurescited by 17
  2. 2023Towards Understanding How Transformers Learn In-context Through a Representation Learning Lenscited by 15
  3. 2025ProKeR: A Kernel Perspective on Few-Shot Adaptation of Large Vision-Language Modelscited by 15
  4. 2021On Learning the Transformer Kernelcited by 14
  5. 2022Improved Random Features for Dot Product Kernelscited by 11
  6. 2022A Call for Clarity in Beam Search: How It Works and When It Stopscited by 10
  7. 2022Localized Contrastive Learning on Graphscited by 10
  8. 2023General Graph Random Featurescited by 10
  9. 2023Simplex Random Featurescited by 9
  10. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  11. 2023Random Fourier Signature Featurescited by 9
  12. 2025Streaming Attention Approximation via Discrepancy Theorycited by 9
  13. 2021Scalable Variational Gaussian Processes via Harmonic Kernel Decompositioncited by 8
  14. 2022Learning Self-Modulating Attention in Continuous Time Space with Applications to Sequential Recommendationcited by 8
  15. 2023Scalable Neural Network Kernelscited by 8
  16. 2025SDTagNet: Leveraging Text-Annotated Navigation Maps for Online HD Map Constructioncited by 8
  17. 2021Random matrices in service of ML footprint: ternary random features with no performance losscited by 7
  18. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  19. 2022QUIC-FL: Quick Unbiased Compression for Federated Learningcited by 7
  20. 2024Fast Summation of Radial Kernels via QMC Slicingcited by 7
  21. 2023Repelling Random Walkscited by 6
  22. 2022Local Random Feature Approximations of the Gaussian Kernelcited by 5
  23. 2023Uni-Fusion: Universal Continuous Mappingcited by 5
  24. 2022Linearizing Transformer with Key-Value Memorycited by 4
  25. 2024High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularizationcited by 4
  26. 2025Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encodingcited by 4
  27. 2025Graph Random Features for Scalable Gaussian Processescited by 4
  28. 2021Unlocking Pixels for Reinforcement Learning via Implicit Attentioncited by 3
  29. 2024Comparison of Reservoir Computing topologies using the Recurrent Kernel approachcited by 3
  30. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 3
  31. 2024The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machinescited by 3
  32. 2021MetaKernel: Learning Variational Random Features with Limited Labelscited by 2
  33. 2023Linear-scaling kernels for protein sequences and small molecules outperform deep learning while providing uncertainty quantitation and improved interpretabilitycited by 2
  34. 2024Variance-Reducing Couplings for Random Featurescited by 2
  35. 2024On the design of scalable, high-precision spherical-radial Fourier featurescited by 2
  36. 2025Adaptive Local Clustering over Attributed Graphscited by 2
  37. 2025Learning collision risk proactively from naturalistic driving data at scalecited by 2
  38. 2025Revisiting Deep Information Propagation: Fractal Frontier and Finite-size Effectscited by 2

50 most cited of 89 All 89 (JSON)