11institutetext: University of Luxembourg, 4365 Esch-sur-Alzette, Luxembourg
11email: @uni.lu

# Exact Non-Oblivious Performance of Rademacher Random Embeddings

Maciej Skorski  0000-0003-2997-7539 Alessandro Temperoni  0000-0003-0272-6596

###### Abstract

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.

###### Keywords:

Johnson-Lindenstrauss Lemma Rademacher Random Projections Schur-convexity

##  1 Introduction

###  1.1 Background and Related Work

The seminal result of Johnson and Lindenstrauss [25] quantifies the amazing
performance of _random linear maps as embeddings_ : they map input data into a
much smaller dimension (compression) while nearly maintaining the scalar
products (almost isometrically). The _strong quantitative guarantees_ , a
distinctive feature of this technique, enabled its application to a range of
problems and areas, including nearest-neighbour search [27], clustering [15,
12, 28], outlier detection [5], ensemble learning [10], adversarial machine
learning [35], feature hashing in machine learning [24], numerical linear
algebra [30, 12, 11], convex optimization [36], differential privacy [7],
neuroscience [21] and numerous others; for a comprehensive literature review
we refer the reader to the recent survey [20].

The focus of this work is on numerical guarantees for the _almost distance-
preserving_ property, which is formally stated as

$\displaystyle\|\Phi x\|^{2}\approx\|x\|^{2}\quad\textrm{with high
probability},$ (1)

where an appropriately sampled matrix $\Phi\in\mathbb{R}^{m\times n}$
represents the projection of an $n$-dimensional vector $x$ to $m$ dimensions
($m\ll n$ is desired), and the relative approximation error in (1) is referred
to as _distortion_.

The long-line of research [19, 22, 2, 3, 29, 14, 26, 24, 32, 33] has
incrementally established various guarantees for (1), in the form of
_distortion-confidence trade-offs_ : while a small distortion ensures that the
analytical task can be performed with a similar effect over the embedded data,
high confidence guarantees with what probability it will happen. Yet the
quantitative analysis of the property (1) has remained a difficult challenge,
resulting in complex proofs simplified many times [13, 23], crude statistical
bounds (for example, sparse variants have an exponential gap with respect to
the sharp no-go results [9]), and a lack of finite-dimensional insights
(bounds are input-oblivious which widens the gap between theory predictions
and empirical performance [34, 18]).

This work addresses the aforementioned gap by revisiting the most promising
construction of _Rademacher random projections_ , which uses the following
matrix

$\displaystyle\Phi_{k,j}=\frac{1}{\sqrt{m}}r_{k,i},\quad
r_{k,i}\sim^{IID}\\{-1,+1\\}.$ (2)

More specifically, this paper solves the following problem:

Give a precise, non-asymptotic, non-oblivious analysis of random projections
(2).

As recently [9] showed, Rademacher random projections are asymptotically
_dimension-optimal with exact constant_ ; this result improves upon a previous
suboptimal bound of Kane and Nelson [26]. The statistical performance of
Rademacher projections is superior to the sparse ones, as demonstrated
empirically in 1. Furthermore, the theoretical bounds for Rademacher random
projections are much better than those available for sparse analogues [13].
The best, prior to this paper, analysis of (2) is given by Achlioptas in [2].
It is worth noting that Rademacher projections are also superior to their
Gaussian counterparts; indeed, we know that they are dominated by the
gaussian-based projections [2]. The relation of statistical performance and
input structure has not been understood in-depth yet; as for conceptually
similar research, we note that recent results show that for sparse data one
can improve the sparsity of random projections, gaining in computing time [24,
33].

$-1$$0$$1$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$threshold
$\epsilon$$\mathbf{P}\\{distortion>\epsilon\\}$$p=0.10$$p=0.25$$p=1.00$

Figure 1: The distortion tail (empirical CCDF) w.r.t. the embedding density
parameter $p$ which equals the fraction of non-zero elements in the matrix.
Dense Rademacher projections ($p=1$) are numerically superior to their sparse
counterparts ($p<1$). The comparison was done on a toy dataset.

###  1.2 Our Contribution

Our study of the stochastic behavior of (1) offers the following novel
contributions:

(a)

non-oblivious insights, by quantifying the _dependency on input spreadness_.
Loosely speaking, we prove that more spread-out input data lead to heavier
tails in the distributed distortion. In particular111We can think of sparse
input as being the extreme opposite of the ”well-spread” property., we obtain
the _improved performance on sparse input data_.

(b)

Schur-concavity framework, used to provide the missing geometric intuitions
for the performance of random projections.

(c)

numerically optimal bounds, which precisely capture the extreme behavior and
cannot be improved by any constant.

(d)

benchmarking against previous bounds, both theoretically and empirically. By
means of distortion, we measured how high-dimensional vectors are projected
with different density to prove the strength of our bounds.

###  1.3 Organization

The remainder of the paper is organized as follows: Section 2 introduces
notation and technical notions used throughout the paper; then Section 3
discusses and benchmarks novel results of this paper, and Section 4 concludes
the work. Parts of the theoretical analysis appear in the Appendix 0.A.

$0.2$$0.4$$0.6$$0.8$$1$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$embedding density
$p$quadratic chaos
moment$sparsity=0$$sparsity=0.2$$sparsity=0.3$$sparsity=0.4$$sparsity=0.5$

Figure 2: Data-aware insights. We measured the theoretical moments against
_input data sparsity_. The plot shows that increased sparsity in the input
data leads to smaller values of the moments. This result becomes more evident
when related to the embeddings density parameter $p$.

##  2 Preliminaries

We start by recalling some basic concepts from probability theory, algebra,
combinatorics and optimization.

Throughout the paper we work basic probability distributions: normal,
binomial, and Rademacher. Given a vector $x$ we denote by $\|x\|$ its
euclidean norm and by $\|x\|_{0}$ the number of its non-zero components; we
also say that $x$ is $\ell$-sparse with $\ell=\|x\|_{0}$, for example
$x=\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},0\right)$ is $3$-sparse.

_Partitions_ represent a positive integer $q$ as a sum of positive integers. A
non-decreasing and non-negative sequence $\lambda$ is a partition of $q$,
denoted as $\lambda\vdash q$, when $\sum_{i}\lambda_{i}=q$; in the _frequency
notation_ distinct parts are assigned frequencies, so that
$\lambda=1^{f_{1}}\ldots q^{f_{q}}$ where $\sum_{i}if_{i}=q$. For example, we
have $\lambda=1^{2}2=(2,1,1)\vdash 4$.

_Monomial symmetric functions_ for a given partition
$\lambda=(\lambda_{1},\ldots,\lambda_{k})\vdash q$ are defined as the sum of
all distinct monomials with exponent $\lambda$, that is
$\mathbf{m}_{\lambda}(x)=\sum_{i_{1},\ldots,i_{k}}x_{i_{1}}^{\lambda_{1}}\cdots
x_{i_{k}}^{\lambda_{k}}$ where $i_{1},\ldots,i_{k}$ and monomials
$x_{i_{1}}^{\lambda_{1}}\cdots x_{i_{k}}^{\lambda_{k}}$ are distinct. For
example, we have
$\mathbf{m}_{(2,1,1,1)}(x_{1},x_{2},x_{3},x_{4})=x_{1}^{2}x_{2}x_{3}x_{4}+x_{1}x_{2}^{2}x_{3}x_{4}+x_{1}x_{2}x_{3}^{2}x_{4}+x_{1}x_{2}x_{3}x_{4}^{2}$.

_Elementary symmetric functions_ are defined as
$\mathbf{e}_{k}(x)=\sum_{i_{1}<\ldots<i_{k}}x_{i_{1}}x_{i_{2}}\cdots
x_{i_{k}}$. Both monomial and elementary polynomials are a base of symmetric
polynomials. For more details, we refer to the monographs [4].

The _majorization order_ on $n$-dimensional vectors is defined as follows: we
say that $x$ is dominated by $y$, denoted by $x\prec y$, if for their non-
decreasing rearrangements $(x_{i}^{\downarrow})$ and $(y_{i}^{\downarrow})$ we
have the inequality
$\sum_{i=1}^{k}x_{i}^{\downarrow}\geqslant\sum_{i=1}^{k}y_{i}^{\downarrow}$
for $k=1,\dots,n$ with equality when $k=n$; equivalently, $x$ can be produced
from $y$ by a sequence of _Robin-Hood operations_ which replace $x_{i}>x_{j}$
by $x_{i}\leftarrow x_{i}-\epsilon,x_{j}\leftarrow x_{j}+\epsilon$ for
$\epsilon\in\left(0,\frac{x_{i}-x_{j}}{2}\right)$. Intuitively, $x$ being
dominated by $y$ means that $x$ is more spread-out/dispersed than $y$. For
example, we have
$\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)\prec\left(\frac{1}{3},\frac{1}{3},0,\frac{1}{3}\right)$
(it takes 3 Robin-Hood transfers).

The _Schur-convexity_ of a function $f:\mathbb{R}^{n}\to\mathbb{R}$ is the
following property: $x\prec y$ implies $f(x)\leqslant f(y)$; we speak of
Schur-concavity when the inequality is reversed. Schur-convex or Schur-concave
functions are necessary symmetric; symmetric function is Schur-convex if
$\left(\frac{\partial f}{\partial x_{i}}-\frac{\partial f}{\partial
x_{j}}\right)\left(x_{i}-x_{j}\right)\geqslant 0$ (Schur-Ostrowski criterion).
For example, power sums $\sum_{i}x_{i}^{q}$ for $q\geqslant 1$ are Schur-
convex. For more on _majorization_ and _Schur-convexity_ we refer to [6, 31].

We define the _moment domination_ of a random variable $Y$ over $X$, denoted
as $X\prec_{m}Y$, by requiring $\mathbf{E}X^{q}\leqslant\mathbf{E}Y^{q}$ for
all positive integers $q$. In particular, it implies that MGF of $Y$ dominates
the MGF of $X$, the majorization in the Lorentz stochastic order [6].

##  3 Results

###  3.1 Main Result

In the following result, we provide the promised numerically sharp, non-
oblivious and geometrically insightful bounds for Rademacher random
projections. In the (particularly interesting) case of sparse input, we obtain
more explicit formulas involving binomial distributions.

######  Theorem 3.1 (Sharp Moment Bounds for Rademacher Random Projections)

Let $\Phi$ be sampled according to the Rademacher scheme (2), and define the
distortion as

$\displaystyle E(x)\triangleq\frac{\|\Phi x\|^{2}}{\|x\|^{2}}-1.$ (3)

Then the following holds true:

(a)

$E(x)$ has moments that are Schur-concave polynomials in $(x_{i}^{2})$

(b)

$E(x)$ is moment-dominated by $E_{*}$ defined as

$\displaystyle E_{*}$ $\displaystyle=\frac{1}{m}\sum_{i=1}^{m}(Z_{i}^{2}-1)$
(4)

where $Z_{i}$ are standardized binomial r.v.s.:

$\displaystyle Z_{i}\sim^{IID}\frac{B-\mathbf{E}B}{\sqrt{\mathbf{Var}[B]}},\
B\sim\mathsf{Binom}\left(\|x\|_{0},\frac{1}{2}\right).$ (5)

Equivalently,

$\displaystyle\mathbf{E}E(x)^{q}\leqslant\mathbf{E}E_{*}^{q}$ (6)

holds for $q=2,3,\ldots$ with equality when all components of the input $x$
are equal.

We briefly overview the proof of Theorem 3.1 (see Figure 3): it starts by a
reduction to the dimension $m=1$, and writing the distortion as a Rademacher
chaos of order 2; we then find extreme values of its moments geometrically, by
means of _Schur optimization_. Finally, these extreme values can be found
explicitly and efficiently by linking them to binomial moments.

Distortion $E(x)=\|\Phi x\|_{2}^{2}-\|x\|_{2}^{2}$Distortion $E(x)=\|\Phi
x\|_{2}^{2}-\|x\|_{2}^{2}$ for $m=1$Rademacher chaos:
$E(x)=\sum_{i\not=j}x_{i}x_{j}r_{i}r_{j}$ for $m=1$Flat vectors $x$ yield
heaviest moments/tail boundsExplicit formula for Rademacher chaos on flat
vectorsaveraging IIDrewrittingRobin-Hood (Schur) optimizationcombinatorial
identities

Figure 3: The proof roadmap for Theorem 3.1.

###  3.2 Techniques: Proving Schur Convexity

We present a useful framework for proving Schur convexity properties. It makes
repeated use of few auxiliary facts to eventually reduce the task to a
2-dimensional problem. This is often easier than the classical approach of
evaluating derivative tests.

###### Lemma 1

The class of _non-negative_ Schur-convex (or concave) functions forms a semi-
ring.

###### Lemma 2

A multivariate function is Schur-convex (respectively, Schur-concave) if and
only if it is symmetric and Schur-convex (respectively, Schur-concave) with
respect to each pair of variables.

To demonstrate the usefulness of these facts, we sketch an alternative proof
of a refined version of celebrated Khintchine’s Inequality, due to Efron. This
refinement plays an important role in statistics, namely in proving properties
of popular Student-t tests.

######  Corollary 1 (Refined Khintchine Inequality [17])

The mapping

$\displaystyle x\rightarrow\mathbf{E}(\sum_{i}x_{i}r_{i})^{q}$

is a Schur-concave function of $(x_{i}^{2})$. As a consequence for
$\sigma=\|x\|_{2}$ we have

$\displaystyle\mathbf{E}(\sum_{i=1}^{n}x_{i}r_{i})^{q}\leqslant\mathbf{E}\left(\frac{\sigma}{\sqrt{n}}\sum_{i=1}^{n}r_{i}\right)^{q}\leqslant\mathbf{E}\mathsf{Norm}(0,\sigma^{2})^{q}.$

###### Proof

The symmetry with respect to $(x_{i})$ is obvious. Applying the multinomial
expansion to $(\sum_{i}x_{i}r_{i})^{q}$, taking the expectation and using the
symmetry of Rademacher random variables, we conclude that
$\mathbf{E}(\sum_{i}x_{i}r_{i})^{q}$ is polynomial in variables $(x_{i}^{2})$.
By Lemma 2, it suffices to prove the Schur-concavity property for
$x_{1}^{2},x_{2}^{2}$. By the binomial formula and the independence of
$r_{1},r_{2}$ from $(r_{i})_{i>2}$, we see that
$\mathbf{E}(\sum_{i}x_{i}r_{i})^{q}=\sum_{k}\binom{q}{k}\mathbf{E}(\sum_{i>2}x_{i}r_{i})^{q-k}\cdot\mathbf{E}(x_{1}r_{1}+x_{2}r_{2})^{k}$
is a combination of expressions $\mathbf{E}(x_{1}r_{1}+x_{2}r_{2})^{k}$ with
coefficients $c_{k}=\binom{q}{k}\mathbf{E}(\sum_{i>2}x_{i}r_{i})^{q-k}$ that
are independent of $x_{1},x_{2}$ and non-negative due to the symmetry of
$r_{i}$. By Lemma 1, it suffices to prove that
$F_{k}\triangleq\mathbf{E}(x_{1}r_{1}+x_{2}r_{2})^{k}$ is a Schur-concave
function of $x_{1}^{2},x_{2}^{2}$. Define
$G_{k}\triangleq\mathbf{E}(x_{1}r_{1}+x_{2}r_{2})^{k}x_{1}x_{2}r_{1}r_{2}$. By
$(x_{1}r_{1}+x_{2}r_{2})^{k}=(x_{1}r_{1}+x_{2}r_{2})^{k-2}(x_{1}^{2}+x_{2}^{2}+2x_{1}x_{2}r_{1}r_{2})$
we have $F_{k}=(x_{1}^{2}+x_{2}^{2})F_{k-2}+2G_{k-2}$ and
$G_{k}=(x_{1}^{2}+x_{2}^{2})G_{k-2}+2x_{1}^{2}x_{2}^{2}F_{k-2}$. Since
$x_{1}^{2}+x_{2}^{2}$ and $x_{1}^{2}x_{2}^{2}$ are both Schur-concave in
$x_{1}^{2},x_{2}^{2}$, the Schur-concavity property of $F_{k},G_{k}$ is proven
when it is proven for $k:=k-2$. By mathematical induction, it suffices to
realize that $F_{0}=1,F_{1}=0,G_{1}=1,G_{2}=x_{1}^{2}x_{2}^{2}$ are Schur-
concave in $x_{1}^{2},x_{2}^{2}$.

Let $\mathbf{1}_{n}$ be the vector of $n$ ones. The first inequality follows
then by
$\frac{\sum_{i=1}^{n}x_{i}^{2}}{n}\cdot\mathbf{1}_{n}\prec(x_{1}^{2},\ldots,x_{n}^{2})$,
and is clearly sharp. Since
$\frac{1}{n+1}\mathbf{1}_{n+1}\prec\frac{1}{n}\mathbf{1}_{n}$ and the Schur-
concavity implies that $\mathbf{E}(\sum_{i=1}^{n}r_{i}/\sqrt{n})^{q}$
increases with $n$, the second inequality follows by the CLT.

###  3.3 Techniques: Rademacher Chaoses

Of independent interests are the techniques used in this work. The first
result analyzes the quadratic Rademacher chaos geometrically. It is similar in
the spirit of the results of Efron [17] and Eaton [16], which however concern
only a first-order Rademacher chaos.

######  Theorem 3.2 (Schur-concavity of Rademacher chaoses)

Let $(r_{i})$ be a sequence of independent Rademacher random variables. Then
the Rademacher chaos moment

$\displaystyle\mathbf{R}_{q}(x)\triangleq\mathbf{E}\left(\sum_{i\not=j}x_{i}x_{j}r_{i}r_{j}\right)^{q}$
(7)

is a Schur-concave function of $(x_{i}^{2})$ for every positive integer $q$.

The second result is a recipe for explicitly computing the extreme moment
values:

######  Theorem 3.3 (Extreme moments of Rademacher Chaos)

For any $x$ and $K=\|x\|_{0}$ the following holds:

$\displaystyle\mathbf{R}_{q}(x)\leqslant\mathbf{R}_{q}(x^{*}),\quad
x^{*}=\underbrace{\left(\frac{\|x\|_{2}}{\sqrt{K}},\ldots,\frac{\|x\|_{2}}{\sqrt{K}}\right)}_{K\text{
times}},$ (8)

and furthermore the explicit value of this bound equals

$\displaystyle\mathbf{R}_{q}(x^{*})=\|x\|_{2}^{2q}\cdot\mathbf{E}_{\bar{B}}({\bar{B}}^{2}-1)^{q},$
(9)

where $\bar{B}=\frac{B-K/2}{\sqrt{K/4}}$ standardizes the symmetric binomial
distribution with $K$ trials $B$.

###  3.4 Numerical Comparison

The presented result is _numerically optimal_ and _captures input sparsity_.
It should be compared against the bounds from [1] and the no-go result from
[9], as illustrated in Table 1. To see that our bounds are better than those
in [1], it suffices to use the Gaussian majorization argument to obtain a
weaker bound $E(x)\prec_{m}\frac{\sum_{i=1}^{m}(N_{i}^{2}-1)}{m}$ where
$N_{i}$ are independent standard normal random variables, and use known sub-
gamma tail bounds for chi-square distributions (for example, those developed
in the monograph on concentration inequalities [8]).

To validate our findings, we performed the following experiments on both
synthetic and real-world datasets.

Author | Result
---|---
[9] |  $\max_{x}\mathbf{P}[|E(x)|>\epsilon]\geqslant 2\exp\left(-\frac{m\epsilon^{2}(1+o(1))}{4})\right)$ when $m\gg\epsilon^{-2},n\gg 1$
[1] | $\mathbf{P}[|E(x)|>\epsilon]\leqslant 2\exp\left(-\frac{m\epsilon^{2}}{4}\left(1-\frac{2}{3}\epsilon\right)\right)$
this paper |  $E(x)\prec_{m}\frac{\sum_{i=1}^{m}Z_{i}^{2}-1}{m}$, $Z_{i}\sim^{IID}\frac{B-\mathbf{E}B}{\sqrt{\mathbf{Var}[B}},\ B\sim\mathsf{Binom}\left(\|x\|_{0},\frac{1}{2}\right)$

Table 1: Bounds from this work (Theorem 3.1) compared with the best prior
bounds [1] and the sharp no-go results [9]. Our bounds imply those from prior
work by ”normal majorization” arguments (see the supplementary material).

####  3.4.1 Synthetic dataset

Figure 4 and Figure 5 demonstrate numerical improvements. The input sparsity
is the key: random projections are seen _less distorted when input data is
sparse_.

$2$$5$$10$$15$$20$$10^{0}$$10^{2}$$10^{4}$$10^{6}$$10^{8}$$\|x\|_{0}$$\max_{x}\mathbf{R}_{q}(x)$$q=4$$q=6$$q=8$$q=10$

Figure 4: The more spread-out the input (controlled by sparsity $\|x\|_{0}$),
the more distorted the projected output (captured by $\mathbf{R}_{q}(x)$, the
Rademacher chaos moment). Utilizing the input dispersion improves probability
bounds by orders of magnitude. Note: for normalization purposes, we assume
$\|x\|_{2}=1$.

$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$$10^{-7}$$10^{-5}$$10^{-3}$$10^{-1}$$\epsilon$bound
on $\mathbf{P}[|E(x)|>\epsilon]$new($\ell=10$)new($\ell=20$)new($\ell=50$)old
bounds

Figure 5: Capturing input-sparsity ($\ell=\|x\|_{0}$) improves the bounds on
Rademacher random projections, as demonstrated by distortion probability
tails.

$0.1$$0.2$$0.4$$0.6$$0.8$$1$$10^{-0.1}$$10^{0}$$10^{0.1}$embedding density
$p$$distortion$$mnist$$optdigits$$semeion$$usps$

Figure 6: The distortion measured w.r.t. the density of the embeddings shows
that sparse data result in better bounds and proves that Rademacher
projections are superior to sparse ones.

$0$$2$$4$$6$$8$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$$\epsilon$bound on
$\mathbf{P}[|E(x)|>\epsilon]$$mnist$$plantstexture$$micromass$$Ecoli$$Glass$

Figure 7: Measuring the distortion tail probability on real-world datasets
confirms our theoretical findings: capturing the input-sparsity improves the
bounds on Rademacher random projections. The datasets, from left to right, are
displayed from the most sparse (mnist) to the least one (Glass).

####  3.4.2 Real-world datasets

Figure 6 and Figure 7 show our findings. The results are validated with
experiments performed on datasets from the SuiteSparse Matrix Collection
(formerly the University of Florida Sparse Matrix Collection) available at
https://sparse.tamu.edu/. For these experiments, we selected matrices from
machine learning datasets.

##  4 Conclusions

We revisited the performance of Rademacher random projections, connecting the
statistical guarantees with the input structure: for spreadness and, a special
case, sparsity. The main result of this paper proves Schur-concavity
properties, which makes the bounds numerically sharp and data aware (non-
obliviuos) while giving a geometric perspective to the performance of the
projections. We benchmarked our bounds both theoretically and empirically by
measuring the distortion of the projected vectors against the original input
data. As a result, dense projections are preferred, and they work incredibly
well with sparse input data. We believe that our findings are of broader
interest for a variety of statistical-inference applications.

## References

  * [1] Achlioptas, D.: Database-friendly random projections. In: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 274–281 (2001)
  * [2] Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. Journal of computer and System Sciences 66(4), 671–687 (2003)
  * [3] Ailon, N., Chazelle, B.: Approximate nearest neighbors and the fast johnson-lindenstrauss transform. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. pp. 557–563 (2006)
  * [4] Alexandersson, P.: The symmetric functions catalog (2020), https://www.symmetricfunctions.com
  * [5] Aouf, M., Park, L.A.: Approximate document outlier detection using random spectral projection. In: Australasian Joint Conference on Artificial Intelligence. pp. 579–590. Springer (2012)
  * [6] Arnold, B., Sarabia, J.: Majorization and the Lorenz Order with Applications in Applied Mathematics and Economics. Statistics for Social and Behavioral Sciences, Springer International Publishing (2018), https://books.google.pl/books?id=ibhmDwAAQBAJ
  * [7] Blocki, J., Blum, A., Datta, A., Sheffet, O.: The johnson-lindenstrauss transform itself preserves differential privacy. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 410–419. IEEE (2012)
  * [8] Boucheron, S., Lugosi, G., Bousquet, O.: Concentration inequalities. In: Summer school on machine learning. pp. 208–240. Springer (2003)
  * [9] Burr, M., Gao, S., Knoll, F.: Optimal bounds for johnson-lindenstrauss transformations. The Journal of Machine Learning Research 19(1), 2920–2941 (2018)
  * [10] Cannings, T.I., Samworth, R.J.: Random-projection ensemble classification. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79(4), 959–1035 (2017)
  * [11] Clarkson, K.L., Woodruff, D.P.: Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM) 63(6), 1–45 (2017)
  * [12] Cohen, M.B., Elder, S., Musco, C., Musco, C., Persu, M.: Dimensionality reduction for k-means clustering and low rank approximation. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pp. 163–172 (2015)
  * [13] Cohen, M.B., Jayram, T., Nelson, J.: Simple analyses of the sparse johnson-lindenstrauss transform. In: 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
  * [14] Dasgupta, A., Kumar, R., Sarlós, T.: A sparse johnson: Lindenstrauss transform. In: Proceedings of the forty-second ACM symposium on Theory of computing. pp. 341–350 (2010)
  * [15] Dasgupta, S.: Learning mixtures of gaussians. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039). pp. 634–644. IEEE (1999)
  * [16] Eaton, M.L.: A note on symmetric bernoulli random variables. The annals of mathematical statistics 41(4), 1223–1226 (1970)
  * [17] Efron, B.: Student’s t-test under non-normal conditions. Tech. rep., HARVARD UNIV CAMBRIDGE MA DEPT OF STATISTICS (1968)
  * [18] Fedoruk, J., Schmuland, B., Johnson, J., Heo, G.: Dimensionality reduction via the johnson–lindenstrauss lemma: theoretical and empirical bounds on embedding dimension. The Journal of Supercomputing 74(8), 3933–3949 (2018)
  * [19] Frankl, P., Maehara, H.: The johnson-lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory, Series B 44(3), 355–362 (1988)
  * [20] Freksen, C.B.: An introduction to johnson-lindenstrauss transforms. arXiv preprint arXiv:2103.00564 (2021)
  * [21] Ganguli, S., Sompolinsky, H.: Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis. Annual review of neuroscience 35, 485–508 (2012)
  * [22] Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. pp. 604–613 (1998)
  * [23] Jagadeesan, M.: Simple analysis of sparse, sign-consistent jl. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
  * [24] Jagadeesan, M.: Understanding sparse JL for feature hashing. In: NeurIPS. pp. 15177–15187 (2019), (Full version: https://arxiv.org/pdf/1903.03605.pdf)
  * [25] Johnson, W.B., Lindenstrauss, J.: Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics 26(189-206), 1 (1984)
  * [26] Kane, D.M., Nelson, J.: Sparser johnson-lindenstrauss transforms. Journal of the ACM (JACM) 61(1), 1–23 (2014)
  * [27] Kleinberg, J.M.: Two algorithms for nearest-neighbor search in high dimensions. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. pp. 599–608 (1997)
  * [28] Makarychev, K., Makarychev, Y., Razenshteyn, I.: Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. pp. 1027–1038 (2019)
  * [29] Matoušek, J.: On variants of the johnson–lindenstrauss lemma. Random Structures & Algorithms 33(2), 142–156 (2008)
  * [30] Sarlos, T.: Improved approximation algorithms for large matrices via random projections. In: 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06). pp. 143–152. IEEE (2006)
  * [31] Shi, H., Technology, H.: Schur-Convex Functions and Inequalities: Volume 1: Concepts, Properties, and Applications in Symmetric Function Inequalities. De Gruyter (2019), https://books.google.at/books?id=VrztDwAAQBAJ
  * [32] Skorski, M.: Johnson-lindenstrauss transforms with best confidence. In: Conference on Learning Theory. pp. 3989–4007. PMLR (2021)
  * [33] Skorski, M., Alessandro, T., Martin, T.: Robust and provable guarantees for sparse random embeddings. In: Advances in Knowledge Discovery and Data Mining. pp. 211–223 (2022)
  * [34] Venkatasubramanian, S., Wang, Q.: The johnson-lindenstrauss transform: an empirical study. In: 2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX). pp. 164–173. SIAM (2011)
  * [35] Vinh, N.X., Erfani, S., Paisitkriangkrai, S., Bailey, J., Leckie, C., Ramamohanarao, K.: Training robust models using random projection. In: 2016 23rd International Conference on Pattern Recognition (ICPR). pp. 531–536. IEEE (2016)
  * [36] Zhang, L., Mahdavi, M., Jin, R., Yang, T., Zhu, S.: Recovering the optimal solution by dual random projection. In: Conference on Learning Theory. pp. 135–157. PMLR (2013)

##  Appendix 0.A Proofs

###  0.A.1 Proof of Lemma 1

Consider two non-negative functions $f,g$ and inputs $x\prec y$. Consider the
identity

$f(y)g(y)-f(x)g(x)=(f(y)-f(x))\cdot g(y)+f(x)\cdot(g(y)-g(x)).$ (10)

If $f,g$ are Schur-convex then $f(y)-g(x)\geqslant 0$ and $g(y)-g(x)\geqslant
0$ and the whole expression is non-negative when $f,g$ are non-negative. This
shows that $f\cdot g$ is also Schur-convex. The claim for Schur-concave
functions follows analogously (the expression is then non-positive).

###  0.A.2 Proof of Lemma 2

The proof follows from the fact that $x$ is dominated by $y$ if and only if
$x$ can be produced from $y$ by a sequence of _Robin-Hood operations_ , and
the fact that Robin-Hood operations change only two fixed components of
vectors.

###  0.A.3 Proof of Theorem 2

###### Proof

Note that $\mathbf{R}_{q}$ is a polynomial in $x_{i}^{2}$ with integer
coefficients, and thus a well-defined function of $(x_{i}^{2})$. This follows
by applying the multinomial expansion and noticing that monomials with odd
exponents have expectation zero due to the symmetry of Rademacher
distribution. $\mathbf{R}_{q}$ is obviously symmetric. By Lemma 2 it now
suffices to validate the Schur-concativity for $x_{1}^{2},x_{2}^{2}$ and any
fixed choice of $(x_{i})_{j>2}$. Define the following expressions

$\displaystyle\begin{aligned} P&=\sum_{i\not\in\\{1,2\\}}x_{i}r_{i}\\\
R&=\sum_{i,j\not\in\\{1,2\\}}x_{i}x_{j}r_{i}r_{j},\end{aligned}$ (11)

then our task is to prove the Schur-concativity of the function

$\displaystyle\mathbf{R}_{q}\triangleq\mathbf{E}\left(P(x_{1}r_{1}+x_{2}r_{2})+x_{1}x_{2}r_{1}r_{2}+R\right)^{q},$
(12)

with respect to $x_{1}^{2},x_{2}^{2}$.

By the multinomial expansion we find that

$\displaystyle\begin{split}\mathbf{R}_{q}\triangleq\sum_{q_{1}+q_{2}+q_{3}=q}\binom{q}{q_{1},q_{2},q_{3}}\bigg{[}\mathbf{E}\left[P^{q_{1}}R^{q_{3}}\right]\quad\mathbf{E}\left[(x_{1}r_{1}+x_{2}r_{2})^{q_{1}}(x_{1}x_{2}r_{1}r_{2})^{q_{2}}\right]\bigg{]},\end{split}$
(13)

where we used the independence of $r_{1},r_{2}$ on $(r_{i})_{i>2}$ and thus
also on $P,R$. Observe that $P^{q_{1}}R^{q_{3}}$ is, by definition and our
assumption $x_{i}\geqslant 0$, a polynomial in symmetric random variables
$r_{i}$ with non-negative coefficients. This observation shows that

$\displaystyle\mathbf{E}\left[P^{q_{1}}R^{q_{3}}\right]\geqslant 0,$ (14)

and by Lemma 1 it suffices to prove that

$\displaystyle
F\triangleq\mathbf{E}\left[(x_{1}r_{1}+x_{2}r_{2})^{q_{1}}(x_{1}x_{2}r_{1}r_{2})^{q_{2}}\right]$
(15)

is Schur-concave as a function of $x_{1}^{2},x_{2}^{2}$ for any non-negative
integers $q_{1},q_{2}$.

To see that $F$ is indeed a well-defined function of $x_{1}^{2},x_{2}^{2}$,
note that it equals the expectation of a polynomial in the symmetric random
variables $y_{i}=x_{i}r_{i}$; thus only monomials with even-degrees
contribute, and the result is a polynomial in $y_{i}^{2}=x_{i}^{2}$. In fact,
$F$ equals the sum of even-degree monomials in the expanded polynomial
$(x_{1}+x_{2})^{q_{1}}(x_{1}x_{2})^{q_{2}}$.

We next observe that

$\displaystyle
F=\begin{cases}(x_{1}x_{2})^{q_{2}}\mathbf{E}\left[(x_{1}r_{1}+x_{2}r_{2})^{q_{1}}\right]&q_{2}\text{
even}\\\
(x_{1}x_{2})^{q_{2}-1}\mathbf{E}\left[(x_{1}r_{1}+x_{2}r_{2})^{q_{1}}x_{1}x_{2}r_{1}r_{2}\right]&q_{2}\text{
odd}\end{cases}.$ (16)

Note that $x_{1}x_{2}$ is Schur-concave in non-negative $x_{1},x_{2}$; indeed,
the identity
$(x_{1}+\epsilon)(x_{2}-\epsilon)=x_{1}x_{2}+\epsilon(x_{2}-x_{1}-\epsilon)$
shows that Robin-Hood transfers increase the value. By Lemma 1 we conclude
that $(x_{1}x_{2})^{k}$ is Schur concave in $x_{1}^{2},x_{2}^{2}$ for non-
negative even $k$. Thus, by Equation 16 and Lemma 1 we conclude that it
suffices to consider the case $q_{2}=1$, that is, to prove the Schur-concavity
of the following two functions:

$\displaystyle G_{k}$
$\displaystyle\triangleq\mathbf{E}\left[(x_{1}r_{1}+x_{2}r_{2})^{k}\right]$
(17) $\displaystyle H_{k}$
$\displaystyle\triangleq\mathbf{E}\left[(x_{1}r_{1}+x_{2}r_{2})^{k}x_{1}x_{2}r_{1}r_{2}\right].$
(18)

with respect to $x_{1}^{2},x_{2}^{2}$ for any non-negative integer $k$.

Using the identity
$(x_{1}r_{1}+x_{2}r_{2})^{k}=(x_{1}r_{1}+x_{2}r_{2})^{k-2}(x_{1}^{2}+x_{2}^{2}+2x_{1}x_{2}r_{1}r_{2})$,
we find the following recurrence relation

$\displaystyle G_{k}$ $\displaystyle=(x_{1}^{2}+x_{2}^{2})G_{k-2}+2H_{k-2}$
(19) $\displaystyle H_{k}$
$\displaystyle=2x_{1}^{2}x_{2}^{2}G_{k-2}+(x_{1}^{2}+x_{2}^{2})H_{k-1},$ (20)

valid for $k\geqslant 2$. Since $x_{1}^{2}+x_{2}^{2}$ and $x_{1}^{2}x_{2}^{2}$
are Schur-concave as functions of $x_{1}^{2},x_{2}^{2}$, by Lemma 1 the
concavity property proven for $k-2$ implies that it is valid also for $k$. By
induction, it suffices to verify the case $k=0$ and $k=1$. But we see that

$\displaystyle\begin{aligned} G_{0}&=1\\\ G_{1}&=0\\\ H_{0}&=1\\\
H_{1}&=2x_{1}^{2}x_{2}^{2}\\\ \end{aligned}$ (21)

are all Schur-concave as functions of $x_{1}^{2},x_{2}^{2}$. This completes
the proof.

###  0.A.4 Proof of Theorem 3

Without loss of generality, we assume that $\|x\|_{2}=1$. From Theorem 2 and
the fact that $(x^{2}_{i})$ majorizes $({x^{*}_{i}}^{2})$ we obtain

$\displaystyle\begin{aligned} \max_{\|x\|_{0}\leqslant
K}\mathbf{E}\left(\sum_{i<j}x_{i}x_{i}r_{i}r_{j}\right)^{q}&=\mathbf{E}\left(\sum_{i<j}x^{*}_{i}x^{*}_{i}r_{i}r_{j}\right)^{q}&=\mathbf{E}\left(\frac{1}{K}\sum_{1\leqslant
i<j\leqslant K}r_{i}r_{j}\right)^{q},\end{aligned}$ (22)

Observe that $r_{i}=1-2b_{i}$ where $(b_{i})$ is a sequence of independent
Bernoulli random variables with parameter $\frac{1}{2}$. Therefore,

$\mathbf{E}\left(\sum_{i=1}^{K}r_{i}\right)^{q}=\\\ \begin{aligned}
&=^{(a)}\sum_{k\in\mathbb{Z}}k^{q}\cdot\mathbf{P}\left\\{\sum_{i=1}^{K}r_{i}=k\right\\}\\\
&=^{(b)}\sum_{k}k^{q}\cdot\mathbf{P}\left\\{\sum_{i=1}^{K}b_{i}=\frac{K-k}{2}\right\\}\\\
&=^{(c)}\sum_{i=0}^{K}(K-2i)^{q}\cdot\mathbf{P}\left\\{\mathsf{Binom}\left(K,\frac{1}{2}\right)=i\right\\}\\\
&=^{(d)}\frac{1}{2^{K}}\sum_{i=0}^{K}\binom{K}{i}(K-2i)^{q}\\\
&=^{(e)}\frac{1}{2^{K}}\sum_{i}\binom{K}{i}(-K+2i)^{q},\end{aligned}$ (23)

where in (a) we use the fact that $\sum_{i}r_{i}$ takes integer values, (b)
follows by the identity $r_{i}=1-2b_{i}$, (c) follows by
$\mathsf{Binom}(K,1/2)\sim\sum_{i=1}^{K}b_{i}$, (d) uses the explicit formula
on the binomial probability mass function, and finally in (e) we substitute
$i:=K-i$ and use the symmetry of binomial coefficients
$\binom{K}{i}=\binom{K}{K-i}$.

Using the above formula, we further calculate

$\mathbf{E}\left(\sum_{1\leqslant i\not=j\leqslant K}r_{i}r_{j}\right)^{q}=\\\
\begin{aligned}
&=^{(a)}\mathbf{E}\left(\left(\sum_{i=1}^{K}r_{i}\right)^{2}-\sum_{i=1}^{K}r_{i}^{2}\right)^{q}\\\
&=^{(b)}\sum_{j}\binom{q}{j}(-K)^{q-j}\mathbf{E}\left(\sum_{i=1}^{K}r_{i}\right)^{2j}\\\
&=^{(c)}\frac{1}{2^{K}}\sum_{i,j}\binom{q}{j}\binom{K}{i}(-K+2i)^{2j}(-K)^{q-j}\\\
&=^{(d)}\frac{(-K)^{q}}{2^{K}}\sum_{i}\binom{K}{i}\left(1-\frac{(-K+2i)^{2}}{K}\right)^{q},\end{aligned}$
(24)

where (a) follows by the square sum completion, (b) follows by the binomial
formula and $r_{i}^{2}=1$, (c) follows directly by Equation 23, and (d) is
obtained by algebraic rearrangements.

Inserting Equation 23 into Equation 22, we arrive at

$\max_{x:\|x\|_{0}\leqslant K}\mathbf{E}\left(\sum_{1\leqslant
i\not=j\leqslant
K}x_{i}x_{j}r_{i}r_{j}\right)^{q}=\frac{1}{2^{K}}\sum_{i=0}^{K}\binom{K}{i}\left(\frac{(-K+2i)^{2}}{K}-1\right)^{q}.$
(25)

To simplify further, let
$Z\sim\frac{\mathsf{Binom}\left(K,\frac{1}{2}\right)-\frac{K}{2}}{\sqrt{\frac{K}{4}}}$
be the standardization of the symmetric binomial distribution. Denoting
$i\sim\mathsf{Binom}\left(K,\frac{1}{2}\right)$ we have
$Z^{2}\sim\frac{\left(i-\frac{K}{2}\right)^{2}}{{\frac{K}{4}}}=\frac{(-K+2i)^{2}}{K}$,
and we can rewrite Equation 25 as follows:

$\displaystyle\max_{x:\|x\|_{0}\leqslant K}\mathbf{E}\left(\sum_{1\leqslant
i\not=j\leqslant
K}x_{i}x_{j}r_{i}r_{j}\right)^{q}=\mathbf{E}_{Z}\left(Z^{2}-1\right)^{q},$
(26)

which finishes the proof.

###  0.A.5 Proof of Theorem 1

We have to prove that for the distortion $E(\cdot)$ defined as in

$\displaystyle E(x)\triangleq\frac{\|\Phi x\|^{2}}{\|x\|^{2}}-1.$ (27)

the following inequality holds true:

$\displaystyle E(x)\leqslant E(y),\quad(y_{i}^{2})\prec(x_{i}^{2}).$ (28)

The proof goes through several reduction steps until Schur-concavity of few
simple functions.

We first observe that it suffices to prove that the moments of the expression

$\displaystyle x\rightarrow\|\Phi x\|^{2}-\|x\|^{2},$ (29)

are Schur-concavity with respect to $(x_{i}^{2})$. Indeed, since
$(y_{i}^{2})\prec(x_{i}^{2})$ implies
$\|x\|^{2}=\sum_{i}x_{i}^{2}=\sum_{i}y_{i}^{2}=\|y\|^{2}$ we have
$\mathbf{E}E(x)^{q}\leqslant\mathbf{E}E(y)^{q}$ if and only if
$\mathbf{E}(\|\Phi x\|^{2}-\|x\|^{2})^{q}\leqslant\mathbf{E}(\|\Phi
y\|^{2}-\|y\|^{2})^{q}$, by the definition of $E$.

We first prove that the distortion of $m$-dimensional projections is the
average of $m$ IID distortions of $1$-D projections. Observe that

$\displaystyle\|\Phi
x\|^{2}-\|x\|^{2}=\sum_{k=1}^{m}\left((\Phi_{k}x)^{2}-\mathbf{E}(\Phi_{k}x)^{2}\right),$
(30)

where $\Phi_{k}$ is the $k$-th row of $\Phi$; this follows by
$\mathbf{E}(\Phi_{k}x)^{2}=\sum_{i}x_{i}^{2}\mathbf{Var}[\Phi_{k,i}]=\frac{1}{m}\|x\|^{2}$.
Furthermore, the summands in (30) are independent and identically distributed:

$\displaystyle(\Phi_{k}x)^{2}-\mathbf{E}(\Phi_{k}x)^{2}\sim\frac{1}{m}\sum_{i\not=j}x_{i}x_{j}r_{i}r_{j}.$
(31)

Then we note that the Schur-concativity test can be done on the 1-D case. This
follows because, due to the multinomial expansion applied to Equation 31, the
$q$-th moment of $m$-dimensional distortion is a multivariate polynomial in
1-D distortion moments of order $k\leqslant q$, with non-negative
coefficients; the distortion moments are themselves non-negative, and by Lemma
1 and Theorem 2 we obtain the first part of the theorem.

Finally, applying Theorem 3 proves the second part.