# Robust and Provable Guarantees for Sparse Random Embeddings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 68 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Fully Understanding the Hashing Trick](https://mlsanity.com/paper/1805.08539/) (2018)
- [Understanding Sparse JL for Feature Hashing](https://mlsanity.com/paper/1903.03605/) (2019)
- [Practical Hash Functions for Similarity Estimation and Dimensionality Reduction](https://mlsanity.com/paper/1711.08797/) (2017)
- [Gaussian Sketching yields a J-L Lemma in RKHS](https://mlsanity.com/paper/1908.05818/) (2019)
- [Approximation and Streaming Algorithms for Projective Clustering via Random Projections](https://mlsanity.com/paper/1407.2063/) (2014)
- [Comparison of Classification Methods for Very High-Dimensional Data in Sparse Random Projection Representation](https://mlsanity.com/paper/1912.08616/) (2019)

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

- [Exact Non-Oblivious Performance of Rademacher Random Embeddings](https://mlsanity.com/paper/2303.11774/) (2023)

## Abstract (arXiv)

In this work, we improve upon the guarantees for sparse random embeddings, as they were recently provided and analyzed by Freksen at al. (NIPS'18) and Jagadeesan (NIPS'19). Specifically, we show that (a) our bounds are explicit as opposed to the asymptotic guarantees provided previously, and (b) our bounds are guaranteed to be sharper by practically significant constants across a wide range of parameters, including the dimensionality, sparsity and dispersion of the data. Moreover, we empirically demonstrate that our bounds significantly outperform prior works on a wide range of real-world datasets, such as collections of images, text documents represented as bags-of-words, and text sequences vectorized by neural embeddings. Behind our numerical improvements are techniques of broader interest, which improve upon key steps of previous analyses in terms of (c) tighter estimates for certain types of quadratic chaos, (d) establishing extreme properties of sparse linear forms, and (e) improvements on bounds for the estimation of sums of independent random variables.