# Uniform Approximations for Randomized Hadamard Transforms with Applications

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 3 Mar 2022.

## Builds on (most cited first, 9 of 9)

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [On Adaptive Distance Estimation](https://mlsanity.com/paper/2010.11252/) (2020)
- [Separating Adaptive Streaming from Oblivious Streaming](https://mlsanity.com/paper/2101.10836/) (2021)

## Built on by (most cited first, 9 of 9)

- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Streaming Algorithms for Learning with Experts: Deterministic Versus Robust](https://mlsanity.com/paper/2303.01709/) (2023)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Structure of the Circular-Dyadic Convolution Error](https://mlsanity.com/paper/2607.15293/) (2026)
- [Random Fourier Features in Near-Linear Time](https://mlsanity.com/paper/2610.14751/) (2026)
- [Fast Quantized Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2610.16289/) (2026)

## Abstract (arXiv)

Randomized Hadamard Transforms (RHTs) have emerged as a computationally efficient alternative to the use of dense unstructured random matrices across a range of domains in computer science and machine learning. For several applications such as dimensionality reduction and compressed sensing, the theoretical guarantees for methods based on RHTs are comparable to approaches using dense random matrices with i.i.d. entries. However, several such applications are in the low-dimensional regime where the number of rows sampled from the matrix is rather small. Prior arguments are not applicable to the high-dimensional regime often found in machine learning applications like kernel approximation. Given an ensemble of RHTs with Gaussian diagonals, Mii = 1m, and any 1-Lipschitz function, f: ℝ → ℝ, we prove that the average of f over the entries of Mi vi = 1m converges to its expectation uniformly over | v | ≤ 1 at a rate comparable to that obtained from using truly Gaussian matrices. We use our inequality to then derive improved guarantees for two applications in the high-dimensional regime: 1) kernel approximation and 2) distance estimation. For kernel approximation, we prove the first uniform approximation guarantees for random features constructed through RHTs lending theoretical justification to their empirical success while for distance estimation, our convergence result implies data structures with improved runtime guarantees over previous work by the authors. We believe our general inequality is likely to find use in other applications.