# Exact Non-Oblivious Performance of Rademacher Random Embeddings

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 38 references that are in the map.
- First posted on arXiv 21 Mar 2023.

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

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Understanding Sparse JL for Feature Hashing](https://mlsanity.com/paper/1903.03605/) (2019)
- [Simple Analysis of Sparse, Sign-Consistent JL](https://mlsanity.com/paper/1708.02966/) (2017)
- [Robust and Provable Guarantees for Sparse Random Embeddings](https://mlsanity.com/paper/2202.10815/) (2022)

## Abstract (arXiv)

This paper revisits the performance of Rademacher random projections, establishing novel statistical guarantees that are numerically sharp and non-oblivious with respect to the input data. More specifically, the central result is the Schur-concavity property of Rademacher random projections with respect to the inputs. This offers a novel geometric perspective on the performance of random projections, while improving quantitatively on bounds from previous works. As a corollary of this broader result, we obtained the improved performance on data which is sparse or is distributed with small spread. This non-oblivious analysis is a novelty compared to techniques from previous work, and bridges the frequently observed gap between theory and practise. The main result uses an algebraic framework for proving Schur-concavity properties, which is a contribution of independent interest and an elegant alternative to derivative-based criteria.