# The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2017.

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

- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [Semi-orthogonal Embedding for Efficient Unsupervised Anomaly Segmentation](https://mlsanity.com/paper/2105.14737/) (2021)
- [Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimation](https://mlsanity.com/paper/2302.08923/) (2023)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Efficient Non-Local Contrastive Attention for Image Super-Resolution](https://mlsanity.com/paper/2201.03794/) (2022)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [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)
- [Efficient Online Bayesian Inference for Neural Bandits](https://mlsanity.com/paper/2112.00195/) (2021)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (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)
- [Dense Associative Memory Through the Lens of Random Features](https://mlsanity.com/paper/2410.24153/) (2024)
- [Repelling Random Walks](https://mlsanity.com/paper/2310.04854/) (2023)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts](https://mlsanity.com/paper/2510.04008/) (2025)
- [Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel](https://mlsanity.com/paper/2202.02031/) (2022)
- [Unlocking Pixels for Reinforcement Learning via Implicit Attention](https://mlsanity.com/paper/2102.04353/) (2021)
- [Implicit Two-Tower Policies](https://mlsanity.com/paper/2208.01191/) (2022)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [On the design of scalable, high-precision spherical-radial Fourier features](https://mlsanity.com/paper/2408.13231/) (2024)
- [EUGens: Efficient, Unified, and General Dense Layers](https://mlsanity.com/paper/2601.22563/) (2026)
- [Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions](https://mlsanity.com/paper/2604.23418/) (2026)

## Abstract (arXiv)

We examine a class of embeddings based on structured random matrices with orthogonal rows which can be applied in many machine learning applications including dimensionality reduction and kernel approximation. For both the Johnson-Lindenstrauss transform and the angular kernel, we show that we can select matrices yielding guaranteed improved performance in accuracy and/or speed compared to earlier methods. We introduce matrices with complex entries which give significant further accuracy improvement. We provide geometric and Markov chain-based perspectives to help understand the benefits, and empirical results which suggest that the approach is helpful in a wider range of applications.