# Orthogonal Random Features

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

## Key facts

- Cited by 91 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2016.

## Built on by (most cited first, 30 of 91)

- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [Finetuning Pretrained Transformers into RNNs](https://mlsanity.com/paper/2103.13076/) (2021)
- [Deep End-to-end Causal Inference](https://mlsanity.com/paper/2202.02195/) (2022)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead](https://mlsanity.com/paper/2406.03482/) (2024)
- [A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness](https://mlsanity.com/paper/2205.00403/) (2022)
- [Accelerated Linearized Laplace Approximation for Bayesian Deep Learning](https://mlsanity.com/paper/2210.12642/) (2022)
- [NeuralEF: Deconstructing Kernels by Deep Neural Networks](https://mlsanity.com/paper/2205.00165/) (2022)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Towards Understanding How Transformers Learn In-context Through a Representation Learning Lens](https://mlsanity.com/paper/2310.13220/) (2023)
- [ProKeR: A Kernel Perspective on Few-Shot Adaptation of Large Vision-Language Models](https://mlsanity.com/paper/2501.11175/) (2025)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Localized Contrastive Learning on Graphs](https://mlsanity.com/paper/2212.04604/) (2022)
- [General Graph Random Features](https://mlsanity.com/paper/2310.04859/) (2023)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Scalable Neural Network Kernels](https://mlsanity.com/paper/2310.13225/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition](https://mlsanity.com/paper/2106.05992/) (2021)
- [Learning Self-Modulating Attention in Continuous Time Space with Applications to Sequential Recommendation](https://mlsanity.com/paper/2204.06517/) (2022)
- [SDTagNet: Leveraging Text-Annotated Navigation Maps for Online HD Map Construction](https://mlsanity.com/paper/2506.08997/) (2025)
- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)

## 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.