mlsanityData to 7 Oct 2026

The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

arXiv 1703.00864 ↗First posted 2 Mar 2017stat.ML stat.COcited by 43

Not on the map. Why?

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.

Key facts. Cited by 43 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 11; 2024: 7; 2025: 5; 2026: 5.

43 papers.

Sort:

  1. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  2. 2023Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Surveycited by 71
  3. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
  4. 2021On the Expressive Power of Self-Attention Matricescited by 44
  5. 2021Semi-orthogonal Embedding for Efficient Unsupervised Anomaly Segmentationcited by 26
  6. 2021Hybrid Random Featurescited by 25
  7. 2022Efficient Non-Local Contrastive Attention for Image Super-Resolutioncited by 25
  8. 2023Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimationcited by 25
  9. 2022Chefs' Random Tables: Non-Trigonometric Random Featurescited by 20
  10. 2023Taming graph kernels with random featurescited by 17
  11. 2021Efficient Online Bayesian Inference for Neural Banditscited by 15
  12. 2021On Learning the Transformer Kernelcited by 14
31 more
  1. 2022Improved Random Features for Dot Product Kernelscited by 11
  2. 2023General Graph Random Featurescited by 10
  3. 2023Simplex Random Featurescited by 9
  4. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  5. 2023Random Fourier Signature Featurescited by 9
  6. 2023Scalable Neural Network Kernelscited by 8
  7. 2024Dense Associative Memory Through the Lens of Random Featurescited by 8
  8. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  9. 2023Repelling Random Walkscited by 6
  10. 2025RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contextscited by 4
  11. 2021Unlocking Pixels for Reinforcement Learning via Implicit Attentioncited by 3
  12. 2022Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernelcited by 3
  13. 2022Implicit Two-Tower Policiescited by 3
  14. 2024Spectraformer: A Unified Random Feature Framework for Transformercited by 3
  15. 2024Variance-Reducing Couplings for Random Featurescited by 2
  16. 2024On the design of scalable, high-precision spherical-radial Fourier featurescited by 2
  17. 2026Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensionscited by 2
  18. 2021Denoising Score Matching with Random Fourier Featurescited by 1
  19. 2023Error Estimation for Random Fourier Featurescited by 1
  20. 2023Orthogonal Random Features: Explicit Forms and Sharp Inequalitiescited by 1
  21. 2025Feature maps for the Laplacian kernel and its generalizationscited by 1
  22. 2025Quality Measures for Dynamic Graph Generative Modelscited by 1
  23. 2025Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networkscited by 1
  24. 2026Manifold Random Featurescited by 1
  25. 2024UIO-LLMs: Unbiased Incremental Optimization for Long-Context LLMscited by 0
  26. 2024EUGens: Efficient, Unified, and General Dense Layerscited by 0
  27. 2024Kernel Approximation using Analog In-Memory Computingcited by 0
  28. 2025Random Projection Flows for Efficient Manifold Density Estimationcited by 0
  29. 2026EUGens: Efficient, Unified, and General Dense Layerscited by 0
  30. 2026Data-Aware Random Feature Kernel for Transformerscited by 0
  31. 2026New Bounds for Kernel Sums via Fast Spherical Embeddingscited by 0