On Sparsity and Sub-Gaussianity in the Johnson- Lindenstrauss Lemma
Authors: Aurélien Garivier
Emmanuel Pilliat
Venue: Accepted by TMLR ()

Abstract: We provide a simple proof of the Johnson-Lindenstrauss lemma for sub-Gaussian variables. We extend the analysis to identify how sparse projections can be, and what the cost of sparsity is on the target dimension.
The Johnson-Lindenstrauss lemma is the theoretical core of the dimensionality reduction methods based on random projections. While its original formulation involves matrices with Gaussian entries, the computational cost of random projections can be drastically reduced by the use of simpler variables, especially if they vanish with a high probability. In this paper, we propose a simple and elementary analysis of random projections under classical assumptions that emphasizes the key role of sub-Gaussianity. Furthermore, we show how to extend it to sparse projections, emphasizing the limits induced by the sparsity of the data itself.

Published in Transactions on Machine Learning Research (10/2025)
On Sparsity and Lindenstrauss Lemma
Sub-Gaussianity in the Johnson-
Aurélien Garivier ENS de Lyon UMPA UMR 5669 / UMR 5668 46 allée d'Itake F-69364 Lyon cedex 07 and Emmanuel Pilliat ENSAI Rennes
curelien.prrioorreens--p...
emmanuullyplllaateenaattt Oensaai
Reviewed on OpenReview: https: // openreview. //perrvveeeeeeveeee.e. net/ ott.::/wiiizztooooooeeeeeeeeeeee
Abstract
We provide a simple proof of the Joinson-Linneeustrauss lemma for sub-Gaussian variables. We extend the analysis to identify how sparse projections can be, and what the cost of sparsity is the target dimension. The Johnson-Tinndenstrauss lemma is the theoretical core of the dimensionality reduction methods based random projections. While its original formulation involves matrices with Gaussian entries, the computational cost of random projections can be drastically reduced by the use of simpler variables, especially if they vanish with a high probability. this paper, we propose a simple and elementary analysis of random projections under classical assumptions that emphasizes the key role of sub- Gaussianity. Furthermore, we show how to extend it sparse projections, emphasizing the limits induced by the sparsity of the data itself.
1 Introduction
The celebrated Loinson-Linddesttruus lemma Johnson & Lindenstrauss (1984] ensures the existence low- distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. If .1,...; In E RP, where p is a (large) integer, and > a tolerance parameter, then there exists matrix in the set Ma (TR) of real matrices with d rows and p columns such that
V1 Misijsn
(1 (1-e) c)]lAr, Ax 112 < Ix, - =,,1²² s (1 +e]lAr; - Ar,112
(1)
SOOn
8 8l((n) d
2
The classical proof of this result is an elegant illustration the Probabilistic Method Alon & Spencer 2004 when drawing the entries of at random from independent Gaussian distributions, Property q11 is satisfied with positive probability as soon as the output space is large enough. It results from a simple deviation bound for the chi-square distribution, and hence builds on the specificity of the Gaussian distribution. This proof is not only mathematically remarkable, but it also gives mathematical foundations for random projections, simple and computationally efficient dimensionality reduction technique in unsupervised machine learning
(see e.g. Bingham & Mannila (2001): Indyk 20001
Vempala 2004); Sarlos (2006); Clarkson & Woodruli
2009hh and references therein).
In 2001, Achlioptas (2001) showed that random projections can casily be extended non-Gaussian ma- trices. In particular, Rademacher, {-1,0, 0, 1]-valudd entries can just as well be chosen, leading to even simpler algorithms suitable for database applications. The proof provided in Achlioptas (2001) relies

---

Published in Transactions on Machine Learning Research (10/2025)
moment bounds and is somewhat specific to those two families of distributions. It was improved in Ma-
toušek in Matoušek (2008) with more general arguments. It is generally considered Li et al. (2006) that
'a uniform distribution is easier to generate than normals, but the analysis is more difficult'. Even faster
methods for sparse data on streams were then devised Ailon & Chazelle (2009): : Charikar et al. (2004) : Kane
& Nelson (0144) using random hashing constructions and more involved moment bounds. Very recently y and
concurrently to our work, Li (024)) has proposed unified analysis of sparse Johnson-Linndenstrauss methods
based on the Hanson- Wright inequality, while Høgsgaard al. (2024) tries to identify the optimal sparsity rate in the data
function of the dimension d, the mumber of points n and the tolerance parameter e.
Our goal is to make the analysis of sparse random projections accessible to wider audience, and the main contribution of this paper is two-fold. The first purpose is to highlight that sub- mub-Gausiianity is in fact an elementary property of random matrix entries that suffices to ensure the success of random projections. The possibility of using sub-Gaussian entries was (to the best of our knowledge) first mentioned in Matoušsk (2008). Unlike Li (2024), our analysis is cntirely clementary: exploiting sub-Gaussianity in an original way, it does not require the Hanson-Wright. inequality and relies solely on Chernofl and Bernstein bounds. Compared to Matoušek (200S); Chafai et al. (2012). the central argument is simplified, the approach is new, and we pay special attention to the constant in the exponential deviation bound. The folk theorem (stated entries instead of normal laws is possible at the price of "just a multiplicative constant'' in the target dimension. Focusing on this multiplicative constant, we show what distributions can be used to obtain ezactly the same guarantees as with Gaussian entries. Trying to provide an optimal compromise between tightness and clarity, we also give intuitions and intermediate products that may be overseen with the general point of view of Orlicz norms. We give a simple proof that any L-sub-Gaussian law with variance 1 offers the same guarantees as the Gaussian law. We provide simple and critical analysis for Achlioplas' limit of 1/3 of non-zero coefficients, and under what conditions it is possible to go further in the understanding of much sparser random projections. Interestingly, our treatment of the lower and upper bound of 11 is not totally symmetric. While the upper deviations of sub-Gaussian variables can be handled by Chernoff's bound just as those of the Gaussian law, the lower deviations can obviously be much smaller (after all, constant variables are sub-Gaussian) and hence require a different argument. To highlight the connection to the Hanson- Wright inequality, we propose in the final section an clementary proof of this incquality for aub-Gaussian vectors when the quadratic form is positive definite. It relies on the same tools as the other proofs of this paper, and it can be read independently.
for example in Boucheron et al. (2013)) is that using
The second purpose of this paper is to build on this analysis to clearly emphasize the conditions on the data under which much sparser random projection matrices can be considered. Our approach provides a clear decomposition of noise into a sparse component Ç and a sub-Gaussian component U. The (pretty intuitive) take-home message is that the distances are preserved if and only if the proportion of non-zero entries the projection matrix A multiplied by the number of significant coefficients in each vector x; is sufficiently large: we propose quantitative and mathematically rigorous formulation of this intuition. An analysis of the same flavor was established by Matoušek| (2008) for a specific distribution on the sparse projection A, in the case n = 2. While the arguments in [atoušck (2008) could be generalized to larger values of n and other iostributions, we present a new perspective through detailed proofs in the sparse and dense cases, with careful attention to constants in the dense case. Furthermore, we fully elaborate on the lower bound argument outlined in that article. Specifically, we establish that the condition on the proportion of non-zero coefficients of A in our main result is essentially not improvable.
The paper is organized as follows. The pedagogical Section 2 includes our analysis of random projections without assumptions on the data: Section 2.1 includes deviation bound for the averages of squared sub- lemma for sub-Gaussian random matrices. We discuss in Section 2.3 a few examples of choices of the distribution P for random projections. Section 3 investigates the possibility of much sparser projection matrices and of the theoretical limit to the minimal sparsity. Theorem 2 with its rather simple proof in Section A extends the previous analysis with minimal changes to sparse matrices. Theorem 3 gives the order of magnitude of the minimal allowed sparsity to obtain a quasi-isometry with high probability, at the price of poly-logarithmic terms. The optinality of this result. is discussed in Section 3.3 A connection to the Hansonn-rrigh inequality is proposed in Section before the full proofs of the main theorems in the appendix (Section
Gaussian variables which is applied Section 2.2 to derive the classical
2

---

Published in Transactions on Machine Learning Research (10/2025)
2 Data- mata-agnostic random projections
We recall in this section known but fundamental results that are of constant use in the sequel. The originality lies in the fact that the Johnson-Lindenstraan lemma is stated from the start for sub Gaussian variables. Furthermore, we were not able to find anywhere else the elegant derivation of 3 written like this. Section contains a simpler derivation results published Achlioptas (2001), with a discussion on their optimality.
2.1 Chernoff's method for squared sub-Gaussian variables
Let X be a random variable assumed to be I-sub- Gaub-Ganssian, which means that AA E R, EE 1 S ex This implies in particular that E[x] and that Var[X] I We derive in this section a deviation bound for the empirical mean of independent copies of X2:
Proposition 1 If X1,..., X are idd 1-sub- Gaussian random variables with variance then
(1 1- X² +
X s 51+c S 2e a( (
d
For Gaussian variables, this is well-known application of Chernoff's method that is to be found in many probability lextbooks. Inspired in particular by Theorem 2.6 of WWinwright (2019), we propose an extension to nub-Gaussian variable with an argument that is (as far as we know) original. The proof requires to treat the upper- and the lower bound separately, which is done in the two following subsections.
2.1.1 Proof of the upper bound
Chernoff's method requires to bound the exponential moments [exx] of X² with & 0 for the right deviations and with < 0 for the left. deviations. We start with the right deviations, for which we will see right away that reduction to the Gaussian case is possible without further assumption. Following Wainwright 2019) (Theorem 2.6), and remarking that for all x E IR, and E> 0,
dx E x²
dd,
2V
if X is 1-sub-Gaussial Gaussian we obtain by Fubini's theorem that for every E (0, 1/2)
12
a2
E ex27
e AX
47
00
e 4
=E
dd
E
dd
2/
2 ml
P0-20
dd
1
dx
2L ml
2/
V1 - 28
which holds with equality if and only if X ~ 1). A slightly more elegant approach to establishing the above equality is to observe that for G ~ No0, 1), Fubini's theorem implies that
Txx2
EG e [2vex [] EG Fx [2 x Ex
Ex
c
22T / clu e- 4 du J2
1
Eg
(3)
/1 2
with equality and only if X ~ 10)
Hence, all sub-Gaussian variables have exponential moments bounded by those of Gaussian law, which permits the right-deviations to be handled the usual way. If Zi,..., Za are independent random variables with the same distribution X2, then for every positive e, Markov's inequality implies that
Zi ......+ Zu 2 +c) =P =P(c(2attm22))) > (((1tc)
Bidd di(1+e] = (u((
TP
d
3

---

Published in Transactions on Machine Learning Research (10/2025)
The concave function + {(1 + c) + 2 In(11 26) v {(1 + c) - In B[ is maximized at e such that
1+ 1- that is at 8x 2 [ r+te) -2íTTp- Hence, P(Z) +.... + Za 2 (1 + +)dd S se-d(() with
((c) = 8 (1 (1) -n c- 1-In1++]
2
This expression can be slightly simplified in many different ways. Let us illustrate the very useful 'Pollard trick": taking g(e) = e - In(1 + +), since g(0) = g (0) = 0 and since ge(e) = 1/(1 + e)² is convex, by Jemsen's 's inequality
c-1n(1 +
S g"(sc)2(1 - s)ds 2 9" ( (cf/-- 2(1 syds) 9"" (()
2/2
and hence I(e) 6 1n(1 +e)
6
é²
2
In summary,
2
4 (1
+ 3
4
71 +...+
Zdd
1+ se (e-((()))
IP
(4)
2.1.2 Proof of the lower bound
There is no hope to prove that E [(x²] < V1+2 for any f > 0 for all l-sub-Gaussian distributions, since it for example not the case if X 0 almost surely. In the context of the Johmson-Lindenstrauss lemma, very natural to assume that the entries of the random matrix have variance 1, so that at least | - A2y |2] = ||æ; - 2yyl?. Under this assumption,
maybe possible to bound the negative exponential moments bounded by those of the standard Gaussian and conclude (as in the Gaussian case) by remarking that I(-e)= 2 I(c), ie. that the left-deviations of the Chi-square are lighter than the right deviations. But we do unfortunately not have proof for that.
Instead, we remark that if Var[X] = 1, the sub-Gaussianity inequality E[cAx] S e2 implies by Taylor
expansion around À = 0 that E[X*] < 3. Using that - S - u- 2 and hence
2²
obtain that IE [e-ex²] S 1- 11-e+ 36
+ .... Z1
+ Za
s <1 11-c S -d( (1-e+
P
d
Since -In(1 (((1-u) 2 u w²/2,
((-1+()- In (1 (1-2+
362
322
(1 -
22)2
36
2
3ea
f.
2 le
+
2 lt 6
2
2
2
2
4
16
for l e/2. It follows that
P
7n + +....
Zz
< 1 11
Se
16
<
d
(5)
d
2.2 Application to the Johnson-Lindenntrrasss lemma
Now that we have proved that squares of sub-Gaussian variables concentrate as well as squares of Gaussian variables, we recall for the sake of self-containment the argument that permits to obtain the Johnson- Lindenstrauss lemma with no assumption on the data:
Lemma) Let F1,..., In RP and c > 0. For every d 2 there exists a matrix A E Ma, (R) such that
Theorem 1 Loohsson-Lindenstraan
8ln(n)
2-
11 < i,j n,
(1- e)) An, < 1 2zll (1 e)) Ax
(6)
4

---

Published in Transactions on Machine Learning Research (10/2025)
In the sequel, we assume that A., = i standard independent variables of 1-sub-Gaussian distribution P:
Proof:
.1 d, d S p, where the (Tiz) are centered,
E B = 0, Var[T,p]= =1
E [ S
12
For vector E Rº of norm llll2 = 1, define Y = Ay and for all iE {I....,d) d}
Z: VaY = Σ
yJTis
==1
Then, as for all LER IR
p II
x2>²
E [[>22]] II E P.3
2
j=1
Ze is 1-sub--Saaae Gaussian Since
d
d Σ
||Ay|| = d Σ
Vay.)
d 1=1
Equations and yield:
P (I|AAl2 & [1-6,1+ +e]) =
Σ
1 d +P
< 1- (
23
(1
S
2 n1
soon as d 2 8la(n)
2-2 By the union bound and the above incquality applied to y
84 a- |
for all i < j
such that v, # Ty:
P U
[1A4(1 21)] & [[1- e)(l=; - 22112. (1 +c]l=;; -2,1111] 20111]] S n²
n(n-1)
<1,
ISidjSa
hence giving the desired conclusion.
Observe that the constant 8 in Condition is the best that can be obtained from this proof. The dependency in 1/e² also appears to be necessary, but the second-order term d is slightly improvable. In the Gaussian case, the proof above allows to use
4m((n) d = c c1
8ln(n) (1+
as we saw in Scction 2.1.1 For sub-Gaussian variables, the simple expression 2 covers at the same time left- and right-deviations. Also observe that choosing d 2 1ln(n²/88 /8) permits Property to hold with probability at least 1-d. d.
2.3
What distribution should we use in random projections?
We have seen that any
distribution of variance presents just the same guarantecs as the standard Gaussian for random projections. This is for example the case of p= 5-1 + 01 or of P =
2
([-v3..33) which are very simple laws that are fast to sample from. Indeed, their exponential moment functions are cosh(A) and sinh( /3x) (V /3X) respectively, which are upper- upper-bounded bounded by x²²/2 One may wonder, after Achlioptas in Achlioptas 2001 how sporse a random projection matrix can be (sparse matrices require fewer computations).
Proposition 2 If 1-sub- Gaussinn random variable of variance 1, then P(X 0) s 2/3, with equality if and only P(X - -33) P(X v3) = P(X 0)/2.
5

---

Published in Transactions on Machine Learning Research (10/2025)
Proof: Let write X = (U, where Ç ~ (q) and U is an independent centered random variable. The
requirement Var[X] = =1 implies that B[U 1/g. Tf X is Ssub-GGussian, then [[[*1] gR S 3, and since B|U 2 2| = 1/q² this implies that 2 1/3. Moreover, the choice q = 1/3 is possible only if B[U*] = E that if U² = 1/g almost surcly. The choice
P P= 8_ + (1 g)0o + 2 w
(7)
2 v
with q == 1/3 is indeed the suggestion of Achlioptas, and it is 1-sub-Gaussial The justification of this choice in Achlioptas (2001) involves pretly involved moment computations, while we here only need to check that for all x E IR,
E E AX = 1-11--0 q + q cosh A =
=
2k (2k)
S
2/2
2k
2 k!
k=1
k=1
whenever q 221/3. A sufficient condition for the inequality that for all k: 2 1,
1 g² (2k]!
2 k! (2k))
9th
(8)
2 k!
4 2
1
For k: = 1 this is always true, for h: = 2 it requires that q
24 3 A simple induction shows that if
2 1/3, the condition is also satisfied for all k 2 3. Reciprocally, if 1/3 then B[eAx] - e 222 ~ - cx for positive constant and P is not
This shows that Achlioptas' suggestion is the only 'optimal" choice in terms of sparsity for a variance and A-sub-Gaussial distribution. Nevertheless, many other choices are possible, such as for example +
P - + - 2 + t + 02.
3 Very Sparse Random projections
We say that random matrix with independent entries is g-sparse if each coefficient has probability at least
- q to be equal to zero. In the previous section, showed that the minimal probability q for the non-zeros
values of a suitable 1-sub-Gaussian distribution P is 1/3. In fact, this result was proven in Li et al. (2006)
with more complicated moment arguments. It allows to take target dimension d 2 8 (n(nn) -e") see
2 to get a c-quasi-isometry with non-zero probability, whatever the data x.
This does not exclude the possibility of using g-sparse projection matrices with q < 1/3, however. Technically speaking, the previous analysis remains quite conservative in that the sub-Gaussianise of Z4 is deduced from
the sub- sub-Gaussianity of each of its summands. We may expect to gain lot of sparsity by using the fact that
can be lot more concentrated than each of its components. Figure I suggests that, at least under certain conditions on the data, much sparser matrices may be considered.
In this section, we present two results aimed at quantifying the minimum sparsity necessary to maintain the quasi-isometry condition with a dimension d on the order of In(n)/e. In particular, Theorem shows ||,-=,1| that q can be as small as max ||x.-2,1 To finish, we establish that this is in fact theoretical limit and that must be at least of this magnitude.
3.1 Towards maximal sparsity
Let U E Bd be a matrix of iid 1-sub-Gaussian entries with variance 1, and ç E Rdxp be matrix of iid Bernoulli variables of parameter independent from U that is used to mask a proportion 1- of the coefficients. We assume that for all i,
1
A.k
(9)
Vdq
For the coefficients of U, one can take Achlioptas' choice _ + 36u + 6665 to gain yet another fraction of sparsity on top of the mask. We apply the matrix A to n points 31 Fn in high-dimensional space

---

Published in Transactions on Machine Learning Research (10/2025)
1.3
1.2
1.1
1
1.0
0.9
0.8
1/3
Figure 1: Admissible value e, in function of the sparsity parameter q of the random projection entrics. Each data point 2, E RR 10000 has independent Gaussian entries. The projection matrix has independent entries
with distribution 36 vág + (1 9 + 25 V/m. The target dimension is 500. The blue line shows
||A[;; 12 while the red line shows maxi, || min,j || =a,
[|(x===5)]1*
The value = 1/3 seems to play no special role, much sparser matrices seem to respect pairwise distances just well.

---

Published in Transactions on Machine Learning Research (10/2025)
R", and we look for the minimal conditions under which the quasi-isometry property 11 still holds with positive probability. We propose first result in that direction.
36 (2n²)
Theorem 2 Let æı,... .1....,. E Rp and > 0. For every d 22
and every
2² 2- c3
18 24 - x3 + 2/ - 2
222 x3
max ()
In (ndnn))
(10)
2,,0;; Izy
it holds with positive probability that
LA visissn, (1=,)]lAx; Axy1l S | - | s (1 + Anyl1
(11)
In particular, Theorem 2 establishes that there cxists q-sparse matrix in (a. satisfying the quasi- ||ا-
isometry condition if d ž In(n)/e² and ž maxişj -1 In(nd) up to a constant factor. Hence, if the coefficients of the differences I2 Iy for i i j are of the same order of magnitude 1/VP, then is allowed to be of order In(nd)/(=*p) which much smaller than 1/3 p > 1/e². The cost in terms of target dimension is only a multiplicative constant (that is not optimized in the previous reasoning). The proof of Theorem 2 relies similar ideas in the preceding section, and will be provided in Section A
In Theorems and 2 the target dimension is of order In(n)/e². The interest of Theorem is mostly theoretical, as the constants can become pretty large. It turns out that if we allow slightly larger target dimensions of order polylog(n)/e², then we can decrease even further the sparsity parameter q. For the sake of completeness, we state this version of the quasi-isometry property (11b in high-probability instead of just with positive probability.
Theorem Let -....., Fn be arbilrary vector in TRP and let A E Rdxp be random matric with independent entries Ask _ SuUix with
ddg
| x3 1/
2 max
(12)
(F
I3: F 2
Then for any 5 E (0, and any d such that
d z ln33/0) (1+ (ln(nd/6) + 21n(nd/8))
12
(13)
the e-quasi-isometry property
11 holds with probability at least 8. 8.
Up to poly-logarithmic factor in n and 6, the minimal dimension do satisfying Condition 13 is still of order 1/e2. The parameter can be chosen as small as max1ą5 ||;:-,,10
|| while keeping the original guarantee of
Johnson Lindenstrauss (11 with non-zero probability under the same condition 2 up to poly-logarithmic
factor: we require d 2 dn, L,e) instead of d 2 8 In(n)/(e² - e²). In comparison to Theorem
2 removed factor of order 1/e" in the minimal allowed sparsity g, at the cost of poly-lggarithmic factor in the target dimension.
3.2 About the sparsity conditions 12 and 10
Condition 12) can be understood as hot-too-high-spaae formalize as follows. For any constants k < w' E (0, 1) and integer any 8 E {1....,p), we say that a vector v is (N,,'', (o,,k's))) sfullll if ||ollce I Vk'/s and if it has at least s coordinates whose absolute value are at least equal to v 8/8, that is
condition on the differences -zj, which we
|101 S
V VR/S and l[
Ioa 2 vk/s) 2s
(14)
This implies in particular that ||/||2 2 x 2 x $ Hence, if a set vectors (II,...,,,)) is such that all the differences x, - 2j are (K, n', f-ll for + j, then a sufficient condition implying 12 is
1
N
(15)
K
8

---

Published in Transactions on Machine Learning Research (10/2025)
1-30
14
S+20 5-30
S-230
2-2000
2=2000
Figure 2: Admissible value e in function of the sparsity parameter q of the random projection entries (logarithmic scale), for different values of the sparsity of the data. Each data point I; E R 10000 has exactly non-zero components, which are independent Gaussian entries. The coefficients of the projection matrix
A are independent and have distribution _ v4d
+ (1 g)oo + $6_ The target dimension is = 500.
Vaa
The blue line shows miney of the ordinates are different between the plots.
a. -u |(,11 while the red line shows max,,
[|A(+)=))1 Observe that the scales | ---0,
It can be observed that quasi- ionseers is ensured whenever q x s is sufficiently large.
In other words, we can take a matrix A which has only a proportion q 2 1/s of non-zero coefficients. This condition is for instance very weak in the dense case where the differences xęç - Iz are (x, K', p)-full for all * j, since it only requires A to have proportion non-zero coefficients of order q ž l/p. In that case, all the coefficients of each difference I; Zj uniformly spread over the p dimensions, in the sense that up to constants K, k', |aak Iys| x 1/v/ for any k.
Condition 12 becomes however much stronger when there exists a difference x; - Iz which is s-sparse for a small s, that is [[ : Za * xzHH- S s. Indeed, in such a sparse case, ||,, - x, 2/112//1zz - 23 11 z 1/s, and the condition q 2 1/s is necessary to satisfy [12].
3.3 Theoretical limit to the sparsity
It turns out that the condition q Σ 1/s in some sense optimal if we impose the dimension d be order 1/e² up to a poly-logarithm. This observation was already highlighted in Matoušek (2008). and we establish result in this section that aligns with this perspective. Experimentally, Figures 2 and dually confirm that random projections remain equally efficient as long as the proportion of non-zero coefficients is clearly above the minimum between 1/s and 1/3. Our lower bound is based on the following intuition: let be (1, 1, sfffull vector, that is ||v| and yı E {-1/v², 1/V8, 0}, and let S = [k E [p] yA a 0). If A E Raxp is any random matrix with independent coefficients such that IAA, # 0) I q for all (i, k), then,
P(Ay = 0) > P V(i, k) E [4] x S, A,s 0) = a)- do in(1-4) 4) > ds 1-9
Hence, if q S 1/(2ds), then P(Ay 0) > 1/c. In other words, there is no hope to satisfy the quasi- isometry property 11 with high probability if g S 1/(2ds). This argument misses however the regime
9

---

Published in Transactions on Machine Learning Research (10/2025)
4-0.00 1-001
q-0.226 0:0000
-4
3:4
Figure 3: Admissible value e, in function on the sparsity parameter of the data (logarithmic scale), for different values of the sparsity of the projection matrix. Each data point of the n = 100 data point 24 E IR 10000 has independent coefficients that are non-zero with probability s/p; the non-zero coefficients are independent and uniformly distributed on {11,+1}. The projection matrix A has independent entries _ + (1 4) + gō سيرة The targel dimension is = 500. The blue line shows Vag
with distribution 5
Vgd
mina, [[A(=:-=:)I while the red line shows maxi. - 1-
|A(=:22)1
|,.-2,11
We observe that the values 2 1/3 ensure the quasi-isometry property whatever the data. For smaller values of g, the number of non-zero coefficients needs to be larger than 1/g.
10

---

Published in Transactions on Machine Learning Research (10/2025)
where 2// 5 9 1/s if d 1/e2. The following theorem provides a general optimality result for all < 1/(200s)) and hence fills the gap between 2²/8 and 1/8 when d x 1/6² up to poly-logarithmic factor.
Theorem 4 Assume that A E TR has iid coefficients distributed according to Achlioptas' distribution with parameter see Eq. 7 Let y E Re be unit vector with coordinates in 1/11/,,1//8,,0 If dqse² S 1/2, qs < 1/240, then
E11 $
5000
In other words, if dd = 1/c² up to a polylog, then Theorem 4 only requires that q 1/s up to polylog. We take probability - -5000 that is very close to 1 in the theorem to match the two regimess where dqs 2 1 and dgs $ 1. In the proof of Theorem | we also show that in the sub-case where dgs 2 1/2048, the probability of success Ay|l E [1
c, 1 + <)) is smaller than 1/2. The proof, which is given at the end of section A relics on the Tchebychev's inequality and on control of the moments of order 2, 4, and 8 of the random variable ||Ay||-
4 En passant: concentration of non-negative quadratic forms
As conclusion to this contribution, we highlight that the upper bound given in Section 3.1 is in fact strongly connected to the Hanson- Wright inequality for nub-Gaussian random variables see e.g. Rudelson & Vershynin (2013), and Li 20244) for an application to the Baahnson-Linddestraaut lemma.. This inequality is known with precise constants for quadratic form of Gaussian vectors see Example 2.12 in Boucheron ct al. (013)) - and it has been generalized with non-explicit constants to sub-Gaussian vectors, e.g. in Theorem 6.2.1 of |Vrshynnn (2019). In the case where the quadratic form assumndd to non-negative, the constants were established to be the same as in the Gaussian case Hsu al. (2012). For completeness, we propose succinct proof of the Manson-Wright inequality for uub-Gaussian vectors when the quadratic form is assumed to be non-negative.
if, for any u Rd, E[e""x] S exp (luul/2). In particular, if ZI....,Z4 Za are independent real random variable and Gaussian that is Ble>Z, < ex² then for any orthogonal matrix P, PZ is a 1-sub-Gaussian vector. In contrast to Rudelson & Vershynin 2013), we do not require in the following proposition the coordinates of X to be independent.
A random vector X E R" is said to be
Proposition 3 (See also Theorem 2.1 of Hsu et al. (2012) Let S be any d d symmetric matrix with mon-negative eigenvalues, and X be a 1-sub- Gaussian vector. Then, for any E [0, / (0)11/(()))))))
Ex eexp (eIr(S) + T- 2f
As a consequence of Proposition 3 and following the same computations as in Theorem 10 of Boucheron et al. 2013), it holds that with probability at least 1-8, 8,
XTSX S Tr(S) 11
for any 8 E 1). In comparison to Theorem 6.2.1 of Vershynin (2019), the constants are explicit they are indeed the same in the Gaussian case. The argument applies however apply only to non-negative matrices. Propasition can be deduced from the proof of Thereom 2.1 in Hsu et al. (2012) in the case μ 0 and o 1, but we still provide our own short proof as the underlying ideas are at the core of the upper bounds of this paper.
Proof: Proof of Proposition 3 Let us write S Diag(( pn) pT where μr 2 ... 2 p4 2 and P. is orthogonal matrix. Let also Y be the sub-Gaussian vector equal to PX, and 0. By Fubini's thcorem,
Ex [XTTx]] =Ex [oCin ENYY?] euY??
Eg Ex Ein V2e.x.a. < EG
Dn
11

---

Published in Transactions on Machine Learning Research (10/2025)
where Gl...., Gn are independent standard and centered Gaussian random variables. Then,
Ea Cinn femot
1
(T)( exp (- In(1 - 2bpu)) - -pps) S exp (Tr(S) +
M
2pp4
1 2sjt;
1=1
where the first inequality comes from the inequality
- 1n(1 20pu)) luu f¹
2sps 1-2pp
ds
f 1-2
We
Exp
conclude the proof by remarking that Ei=1 1-2spi
1-2s||3||p-
Acknowledgments
Aurélien Garivier thank Chaire SeqALO (AN--20-CHLA-0000000) and PEPR IA project FOUNDRY (ANR- 23-PF1A-0003) for their support. The authors are thankful to Pierre Bellec, Nicolas Verzelen and the anonymous reviewers for their precious feedback.
References
Dimitris Achlioptas. Databaso-friendly random projections. In Proceedings of the Twentieth ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Dalabase Systems, PODS '01, pp. 274 281, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581133618. doi: https://doi.oom http://ooooorg/////// 1145/37555111 011/.//////01111//55555/1111 375608
URL
Nir Ailon and Bernard Chazelle. The fast johnson lindess-ind transform and approximate nearest neighbors. SIAM Journal on Computing, (9(1)3302 322, 2009. doi: 10.1137/06067309.. URL https:
Addii.or/11) 10. 1011111700000 1187/060673096
Noga Alon and Joel H. Spencer. The Probabilistic Method, Wiley, New York, second edition, 2004. ISBN 0471370460 9780471370468 0471722154 9780471722151 0471653985 9780471653981.
Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '01, pp. 245 250, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 158113391X. doi: 00.1145/005512.525555 URL http:///oo...og/111114//////1211 1145/502512, 502546
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalilies. Oxford University Press, Oxford, 2013. ISBN
/0..0093//ppp0icor07779999955555 doi: 10. /0.1093//cproofsss /978019953355500000 000022555.0000000000 001.0001. URL http://
dx.doi.cm org/ 10. 10930099/9g0 acproff 0000/9700019633555000000 With a foreword by Michel Ledoux.
A nonasymptotic theory of independence,
Djalil Chafai, Olivier Guédon, Guillaume Lecué, and Alain Pajor. Interactions belween compressed sensing, random matrices, and high dimensional geometry. Société Mathématique de France, December 2012. URL
Moses Charikar, Kevin Chen, and Martin Farach-Coltor Finding frequent items in data streams. Theoret- ical Computer Science, 312(1):3-15, 2004. ISSN 0304-3975. doi: http:///bba.err//00000/888444443 00400-6. URL httpp://www.cccccccccc.ccccc/crp tomata, Languages and Programming.
Au-
Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the First Annual ACM Symposium on Theory of Computing, STOC '09, pp. 205-214, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585062. doi: 10.1145/1536414. 1536445. URL https://doi. http://ddiooggg/.../// 1145/1536414, 1536445
Mikael Moller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn. Sparse dimensionality reduction revisited. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian
12

---

Published in Transactions on Machine Learning Research (10/2025)
Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Procecdings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp- 18454- 18469. PMLR, 21 27 Jul 2024. URL https://proceeddngs mlr. wwt.:/mwww.......eeeeeeeeeeeeeee presss/2235hogggaaaaaea
htmml
Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Commanications in Probability, 17(nonc):1 - 6, 2012. doi: M01214/ECP.w17-2000
URL ftctpe://doi.orgg// 1214/ECP.
P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 10 (3-33, 2001. doi: N0.1109/SFCS.2001.9555
William Johnson and Joram Lindenstrauss. Extensions of lipschitz maps into a hilbert space. Contemporury Mathematics, 26:189 206, 01 1984. doi: 00.1090/conm//266, 7734400
Daniel M. Kane and Jelani Nelson. Sparser Johnson- Transforms. J. ACM, 61(1), jan 2014. ISSN 0004-5411. doi: 10.1145/2559002, 25599002 URL https://doi. 111111..1115/55590010
Ping Li, Trevor J. Hastie, and Kenneth W. Church. Very sparse random projections. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '06, рp. 287-296, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933395. doi: 111115000111044444 1150436. URL
http:///o....rr10..1114//////5.. 1150436
Yingru Li. Simple, unified analysis of Johnson-Iindeeustrauss with applications. 2024.
Jifí Matoušek. On variants of the johnson- -indesr-indd lemma. Random Struct. Algorithms, 33(2):142-1566 September 2008. ISSN 1042-9832.
Mark Rudelson and Roman Vershynin. Hanson-wright, inequality and sub-gaussian concentration. 2013.
Tamas Sarlos. 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, 2006, doi: 10.1109/FOCS.2000 2006.37..
Santosh Vempala. The random projection method. 01 2004. doi: 10.1077/9761-4011--1111111 16.
Roman Vershynin. High-dimensional probability. 2019. URL https://www.math uci. wwt..ccn/r/ereeerhyyll
Haopss/DDD-oooooo bobk pdf
Martin J. Wainwright.
Statistics: Non-Asymptotic Vieupoint. Cambridge Scries in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/9781108627777.
A Proofs of Theorems 2 and
While the proof Theorem for the proof of Theorem
reraain as close as possible to that Theorem 1 it provides some intuitions
A.1 Proof of Theorem
Let U E Rd be a matrix of iid L-sub-Gaussian entries with variance 1, and ( E Rddp be a matrix of iid Bernoulli variables of parameter q independent from U that used to mask a proportion 1 q of the coefficients. We assume that for all i,
1 GRUEe Au Vdq
(16)
and for any vector E R of norm ||y||2 = write as before Y = Ay and Z, = VdY,
Following the previous analysis, we need to bound IE[ exp()))) and we know how to do it from IE[ [exp(AZ))]
when Zi is Sub-Gaussian thanks to the argument of Inequality 3 Since Z, Ed
Su is sum of /
13

---

Published in Transactions on Machine Learning Research (10/2025)
many small contributions, for any fixed À we can bound In E[ exp(XZ,)] using only the local behavior of (A)) In E exp(AUA..)] around O, which is of order X2/2 even when & is not upper-bounded by that quantity. But using Inoquality would require a uniform control of Φ which we cannot provide. We are hence obliged to take another path, by conditioning on the mask variables (Gx) and locusing on the "typical" behavior. Namely,
VdGaUaa ddq
unsinlli
E fexp (AZ+))
I
exp
AyI
E
E
exp
A V9
-. Sede
k=1
k=1
p
X2 Sike
X²
P
yi
IE
exp
E
exp
Cik
2g
2
To upper bound this term, let. for each i EE (1.....d) d) and for 0 S 1
(
t) 5}} yk Cak - (1 + 5)
G
By Bernstein's inequality applied on the 0. 2 valued independent variables
(1)))) 1skSP
which have
variance f 9) s y²_ 9
2//18
qe²
P(G.)) S exp
exp
18111/11 (-18||y/l + 2
Ek=
Mi +
9g
which is smaller than 1/(dn?) as soon
18 + 211y112 In(dn?).
q 2
(17)
e²
On the event G3, the behaviour of Y; is expected:
eexp eexp (AZ,) La S exp
( 12_
(1+
9)
2
and 2//1 + e/3 is I-sub-Gausiian. By Equation
3
12?
1
E exp
Lo,
<
1+
vI 28
Left deviations may be treated similarly. Hence, the event in the non-sparse case: for all < 1, by Equations and 5
G N N Gi, the behaviour of |Y| is just
z
1+c
))
d
z
((G) & [1- - 11, SP
Gn
1+
1+3
+ Gn
1
<
1- 3
1=1
1=1
< Gn
1
Σ
z
>
11 3
3) ))
+ P
Gn
1
Z
<
1+
d
1
3
1=1
< 2 d( (22))
Consoquently, denoting by Giu the set G corrosponding to y æ;-0
||m;-æy |
U ISi<ján
[|A(T, - -z)11 &
- [(1-))
- 2, 1,11, (1 + e)]l - 2 1121
<
Σ
P
P(G
Gbi + Gn { ||(e;; 11;))=);;)1" $ [1- | (1-c.1+0]))
<
< + n²
1
1(
|
ISikjšn
14

---

Published in Transactions on Machine Learning Research (10/2025)
s6 (2n²)
88 soon as q satisfies Eq and d 2
A.2 Proof of Theorem 3
Let @ be the Hadamard product, so that A = SOU We assume that is unit vector of R2 representing
Vdg
one of the unit vector 2,-2, | and write before Y Ay. The coefficients of w; Vdy J O equal
to wik = 1 Gi and
day
Y
1 dq
+
4CCa CaGuuUU (U w;)²
k.k
The upper bound
w/:l is 1-sub- Gaussia conditionally to Ç. Hence, if G is standard Gaussian random variable, it holds conditionally to Ç that for any in [0, 1/(22 max ||uz;l?)),
Ey e r2?
Ea Eu ( @e
s Eg
flw P
1
exp (Allws|1
111)
V1 2 ww//w
where the last inequality comes from the fact that - In(1 - Hence, conditionally to S, we have that
Só
2-2
20llur
ds S
1 11
de max; || |wwl ||
{(1 (((+0))
Ayl 2 1+ SASEA
cxp
(18)
1 28 max; ||
Let now integrate according to Ç. The won's 's independent, identically distributed random variables with law =h Moreover, Var(w))) S 2 Bl s ,, Bernstein's inequality together with a union vdg bound over the d possible indices i = 1,...,d gives that with probability at least - 8/(3")),
max 1| - 1 + 2 I In(3ndd/8) + 2y 1lvl In (3n²dd/))
The assumption 12 implies that q Z 11 Since ||v| 1, 11 ll and the following event G holds with probability at least 8/(3n?):
V
G = max || 1| S (1 / 44ln(3d/8) + 2ln(3dd/5)) Vi, [ii.[wall || S
(19)
d
where for simplicity we write v= 1 / 4/44nnndd 8) + 22 Using the inequality e" < 1 + (e for any [0, 1], we have that for any e e [0, T )
2)n²²
dg
wwall !1?
II (exp(
+1 1-9) 11 (
exp
i.k
< II exp (g(exp( 2 - 1))
1,k
< <exp(e (e 2) _ (Ivlld)
exp(e (c 2)
Let integrate the conditional probability Po Ay 2 2 1 +)) over Ç. For any E ())d(4 have
15

---

Published in Transactions on Machine Learning Research (10/2025)
al² max; |wml|+
Ay| 2 1 e) S
E
exp
[ | 1| + - 2l max; ||w;|12
E(1
+
16
+
3n
luul1 1| + 28 f(1 ((1+c) }
8
E2
exp
3n2
6
exp
(e (e-2)
2) L
262 02
3n2
The second inequality comes from Equation which holds true under the event G defined in (19). The third incquality comes from the fact that l d/(4w²) I d s dg/llyll and the above upper bound on Elexp(( Ei= ||w;||3]]- Choosing de/(2(e 2) 4 S d/(4v/2), we get
de²
8
|1 21 1 S exp
+
2(e 2) + 41/2
3n2
Hence, if ifd dg 1121n(3n66)22/2 we obtain that
3n
5
28
P(]AA|] 1 2 1)+c) - exp
- In
+
-
8
3n2
3n
A union bound all the n(n 1)/2 S n² pairs gives that
IP
U
{|| 2;)11 2 (1 [1] - =2]11]]
s 25/33
(20)
Isicisn
The lower bound
For the lower bound, we use the same arguments as in section 2.1.2 We still have that E[ = 1/d for any E {I....,d} d}, but we since the variables (Ay); are not sub-Gaussians, do not have the bound B[(Ay),) s 3. Instead, we bound the fourth moment as follows:
B((Ay)
3
Σ9
dd Σ qu (UA
dºq
3
3 3 22
6
<
d
d29
d
Hence,
22
+ f(1 - .)
PP (11 < - é) exp
dln
1
+
exxp exp
3 -le) le
d
d
Choosing f - c/6, we obtain that
de2
22 < - c) < exp(
12
If d 2 do 2 lnnn/o)) then we obtain
Ay 51 t) 6/(3n?)
16

---

Published in Transactions on Machine Learning Research (10/2025)
Hence, from union bound over the at most n² possible pairs 24, 2,, obtain that
P
U Isi<jón
(aM(:;-2)]10 s (1 -)||=:=,,)1 - 25123
s 8/3.
(21)
We conclude from the upper bound 20 and the lower bound (11 that if 2 maxiyj
|
and if
1
d do(n, 6, c), the c-quasi isometry property 11 holds with probabiliyy at least 8, that is
P
U SSicjsn
( [1|A(E - m1)l x1,11 $ [[1- e)} - xyl1?, (1 e) 231 x0131]] = 2 6/3
A.3 Proof of Theorem
Let be unit vector of RP. If dgs S 1/2244,, then we have that
P(I [1 c, <)) 2 P(a 0) de 2
which proves the result in that case. In what follows, we assume that dgs 2 1/2048. Chebychev's inequality implies that
P(IlAy| E - 11-,,1++lll P([IIAy|| - 1)² - 2²)
War [1I - 1)
[(] Ayl 1) -
Subsequently, give lower bound of B[[[))|]=-1)] and upper bound of Var (||Ay|l= We denote by X a random variable following the distribution of one coefficients of A. X can be written V S UÜ where
{ ~~ Bern(q) an U (((-1,11))) are independent. holds in particular that for any 2 1, E[x = 0
and [[[X* /ل/.
Lower bound of |||| 1)
)
27
E [114Ay12 - 1)?] E [1-A111]] - -1 E
A Au
1=1 Am 1=1
Σ
Ai,k, Ai.. (uE(1.)
II
-1
ka
where the final sum is over all (2,,2) E [d] and all (ka, A2, 1 12) E [p] Let us fix in such that i2. Since [[Aa]] = B[A%,] 0 for any i, k; either kn = l2 = 4 = L2 there is exactly two pairs of equal indices
among (k1, k2, 41, l2). Since there are exactly 3 possible ways of matching 2 pairs among the four indices, we have that
Σ E k2,
II (1,2)
Ai yku Vi.. - E
| + 3 (Ievll 11v112))
1
3 de
1-
1
dass
If i * i2, then necessarily have that An l and ly = la for non-zero contributions. Hence, in that case,
Σ E
II
Ai,k, A, V1, 1 E|x
1
d
ky dz
NE (1.2)
17

---

Published in Transactions on Machine Learning Research (10/2025)
Combining the two cases, obtain that
d
3d
d(d -
E [[I 1)9]
1 (1-5)
-1
(22)
d'qs
d²
d2
dqs
Upper bound of Var [||Ay| 1)²].
Var [(IIAu11 1) - E Ayl 11)² = ==[[=]]4- [1yl
4E Ayll
+ 6TE [6E[||
Ay|l
4E ||
18
- || 4E Ayl
+ dgs +
3
+
d
The inequality comes from the above computation of Ay] In what follows, first upper-bound [|[| Ayll* and then we lower-bound E. Ayl]) For the latter, the idea is to cancel out the terms of constant order or of order 1/(dqs). Following the same lines as in the computation of B[]lAy]]*), we observe that
E Alyls
E
II
(23)
(1.2,34)
where the sum is over all ((wu)==1..... (kw)) (lu)==t....)) sets for the indices (fu):
E [d] [p] Let us consider the following
1. (in) E l1 if the i, 's are pairwise distinct. in that case, //| d(d 1)(d (d 3) S d=
2. (t.) E Ig if there exactly two equal indices among the i, 'ss In other words, (fu) is permutation of ",,"""""") where i, i', 1" are pairwise distinct. Here, |T2 = 6d(d 1) 2) S 6d
3. (i.) E Ig if there are exactly three equal indices among the i, ss i. (f.) is permutation of (i,
where + i' Here, /sl = 4d(d - 1) S 4d
4. (tx) E I if all the in's are equal. Here, |4 = d
5. (ia) E Is if there are exactly two pairs of equal indices among the i, t.'s. Here, [ss = 3d(d - 1) S 3d
The sets (4v) are disjoint, and the reader can check that the sum of their sizes is equal to dt. Let us fix (iw) e [d],, and consider the five following cases, cach corresponding to one of the sets (I.).
1. If (1.) E 4, then the expectation of the product over E 31,2,3,4) is non-zero only if k, ly for all a E 31,2,3.4) Hence,
Σ
E II
A Vk..
1 da
11ull
d4
(k
(1,2,333
2. If (in) E 12, assume that without loss of generality that (in, i2, is) are pairwise distinct and
that ig is. In that case, we have non-zero contribution only if k = h, b2 = la and if either
(hg = lg = his = 44) or there are two matching pairs among the indices (ks, l, k4, 14) (3 possible matching). Hence, using the fact that ||vl|2 = 1 and ||yll = 1/s:
3
Σ (Bw).
E II
Ar.... A. Bl...
- d#g
+ da
11 = d +
(E(1,233,4)
18

---

Published in Transactions on Machine Learning Research (10/2025)
3. If (t.) I3, assume that 81, 12 are distinct and that i2 -t 14. In that case, have non-zero contribution if A h and if either (N/2 = l2 h3 l/ = k4 = (4) or if there are 3 matching pairs among (k1, (2, k3, 13, k4. (4) (5-3 3 = 15 possible matchings). Hence, using also that qs S 1,
15 l
16 d' q²
Σ
E
II
As.h. Ai. yk. Mr.
S d 1
-
(Ra)
MHE (1:2,344)
II (b.) E la, Chen there is non-zero contribution in one of the three following cases. Either the k 's and ln's all equal, there are groups among the ky 's and ly 8, each made of indices that are all equal (5 ( 35 possibilities), there are 4 matching pairs (7.5 5 3 105 possible matching). Hence,
35 +
105 de llyll
141 da d'
Σ (Au).(tu)
E
II (E(1,23344)
|1yl
llvll
d'
d²
If (fa) E Ta, assume without loss of generality that in i2; is is and i2 # iz. Then there two possibilities for each pairs (2) and (ia, i4). Either k1 = 11 = h2 l2 (resp. K3 = 13 K4 4)
there are three pairs of equal indices among k1, h h2 l2 (resp. ka, la. ka) This gives
3 ] s (+t lulli + de 11v1lb
Σ
E
II
Ar.. A 3h
2
S
16
da
(kw (1.)
(E(1,,3344)
Decomposing the equation
23 into these five above cases and using the assumption dgs 2 1, we obtain that
6
18
16
141
16
253
S
1+
+
S1+
+
+
dqs
d
dqp
d'gpzz
dqs
d
d²aq²
which implies that
6
12
Var
<
B||| Ay|l 4E
Ayil
+ 3
dgs
d
12
253
30
4EI|
Ay
|
dgs
d2
We now show that the term 4 + write
12 is smaller than |. Doing the same reasoning as above, dgs
E
Σ
E
II
Ai,t
(24)
[E
where the sum over all (jw), (kw), (Lw) in [d] [p].. The product is always non-negative, and we consider the sets
J1 ((i.1.)): [d]} and J2 ((11.22. fs): two of the ju are equal and distinct from the other one}
We have that |J = d and |Jل| = 3d - 1), so that
[||l|]]] z
Σ E
A A An 3h
+
Σ
E
II
A A Dk. 3i.
uE (1,233
uu (1,233))3)
141l2 + 3d(dd
1)
d3
3
3
3
3
=1+
dqs
d'gs
dqs
do
19

---

Published in Transactions on Machine Learning Research (10/2025)
To conclude, obtain
12
253
30
Var [[]|Ay| - 1)) S 4
4E Ay|l +
+
dqs
d2
d
256
30
+
p2
d
Combining this latter upper bound with 22
we conclude that
256
256
+ 30qs
22 q2
2
dgs
S 1/2,
2
1 dqse?
dgs
where we used in the last inequality the assumption that dase? S 1/2, q8 S 1/240 and dgs 2 2048. This
concludes the proof of Theorem
20


Reviews:
[{"review_id": "clLeOGSip5", "reviewer": "Reviewer_AFa3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In Prop 1, the proof is elementary yet tight to third order in \\varepsilon^3; no Orlicz norms or Hanson-Wright are needed here. Then using a combinatorial uniion bound along with Prop 1, Theorem 1 is shown. Then Theorem 2 shows that quasi‑isometry holds as soon as q ⁣\\geq ⁣max⁡ ∥xi​−xj​∥_\\infty/∥xi​−xj​∥_2 times a poly-log(nd) and poly epsilon. This technique is neat and provides additional geometric insight about the (2,\\infty)-norm used in high-dimensional statistics literature. Although these techniques are not new, the way they are organized in the current paper is indeed a nice technical piece to the community. I think the paper is quite well written, I only have a few comments/questions:\n\n(1)The authors admit that upper deviations follow directly from Chernoff, whereas lower deviations need ad‑hoc manipulation, is it possible to provide some discussion on the limitation of this kind of manipualtion, specifically extensions to heavy‑tailed, dependent, or merely bounded‑moment distributions?\n(2)The impossibility result is proved for a specific Bernoulli-Rademacher scheme; it is unclear whether other zero‑mean, sub‑Gaussian sparsification rules could circumvent the bound. WHen considering the equivalence of Bernoulli width and Gaussian widths (e.g., https://arxiv.org/abs/1305.4292), does it mean that the impossibility result also extends to other sub-Gaussian sparsifications?\n(3)I like the connection to HW inequality which turns the JL error into a quadratic‑form deviation where nothing stronger can work because the lower‑bound in Theorem 4 shows the inequality reverses when q<1/s. Can the authors comment on whether/how this can be extended into matrix case (e.g., following J.Tropp's series of work extending the HW into matrix case)?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper revisits the JL lemma-based dimensionality reduction and asks two intertwined questions:\nHow general can the distribution of the projection entries be while keeping the classical JL dimension bound? and how sparse can we make those projection matrices—without paying too high a price in target dimension?\nTheir main contribution is the new Chernoff‑style bound for the mean of squared sub‑Gaussian variables (Proposition 1), that underpins the proof and may be reused beyond this context. Extending the analysis, the authors characterise when a projection matrix with only a fraction q of non‑zeros preserves pairwise distances: essentially, the product qs (matrix sparsity times data sparsity) must be large enough. They provide matching upper (Theorems 2, 3) and lower (Theorem 4) bounds, showing the condition is “essentially not improvable.”", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above points (1) to (3), but these are mostly discussion points.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WFzW5VkKdX", "reviewer": "Reviewer_nbQE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The result of the paper is a progress in the theory of random projections. Sparse matrices are appealing for dimensionality reduction as they impose remarkably lower computational effort. The paper is well-written and easy to understand.\n\nDespite mathematical contributions, the connection of the paper to ML is not well justified. More examples from ML can be helpful to make this connection.\n\nA limitation of theorem 4, if I understood it correctly, is that it does not rule out existence of a suitable projection for sparse matrices, which would be a proper converse theorem to JL. At best, the result shows that finding such a matrix is not an easy task anymore.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents mathematical theorems improving the classical JL theorem. JL is a fundamental result that justifies dimensionality reduction methods using linear projections (a.k.a linear sketching). In particular, this paper predicts existence of sparser projection matrices than the ones the original theorem predicts, provided that the data is not too sparse. The paper also provides a lower bound on sparsity in the sense that too sparse random projection matrices, being at the core of the JL argument, have a non-vanishing probability of failure.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The contributions of the paper in the introduction remain ambiguous. It is good to list the contributions in the introduction.\n\nI am not sure why the authors decide to present proofs of standard results (propositions) in the body,  while Theorem 2-4 are the actual contributions. It makes more sense to me to have a sketch of the proofs for these results in the body.\n\nThe relation of Section 4 to the rest of the paper is not clear to me. Please clarify.", "broader_impact_concerns": "No ethical implications, the contribution is completely mathematical.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PoajlZKwDc", "reviewer": "Reviewer_J33z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert on the latest and greatest on Johnson-Lindenstrauss or sub-Gaussian concentration, but I've been a user of both and I understand standard proof arguments.\n\nWith this background stated, I think this is a very nice paper: \n\n- it clearly states its contribution\n- it clearly delineates what is known, without overselling or underselling, pleasure to read in 2025\n- the arguments are clear\n- I checked the math somewhat carefully and derivations and proofs seem correct\n\nI'm putting here a mixed list of comments and suggestions. There is nothing weak about the paper. The main suggestion for improvement is to do more signposting and explain (for non-experts) _how_ the proof mechanics are different from earlier approaches (and thus put 2-3 sentence about these earlier proofs), or at least what is the key new idea / trick / insight.\n\n- When you write things like \"the central argument is simplified with a new approach\" it would be nice to state the gist of the new approach and how it's different from the old approach. This could be done here or elsewhere, but the same comment applies to most of the manuscript. Rather than learning that some earlier argument (e.g. Achlioptas) is \"pretty involved\", I'd prefer to get some quick understanding of the mechanics of difference between the two arguments.\n\n- (3) is exactly the same as the previous display. I've no problem with that but I was wondering if it's just for didactic purposes or there's something we should note. If I were to keep one, it'd be the second one for its elegance.\n\n- on page 3, \"the concave function l \\mapsto l(1+eps) - ln E[e^{lX}] = l(1+eps)...\": should X be squared in the exponent? (I understand that it is meant as a dummy rv but it may be simpler to follow if you put Z here.) Should = be an inequality (from (3))?\n\n- btw, here you use both ln and log to refer to the same function\n- proof of Proposition 2: mention that \\zeta is independent of U \n\n- I understand the theoretical value of Theorem 2, but I'll point out that the dimension can get quite huge. E.g. for n = 10000, eps = 0.1, one gets that d should be at least ~75000. With eps = 0.1 to get d = n/100 one needs n about 1.3e7.\n\n- About Figure 1: I'm wondering about quantifiers. All statements of J-L lemma work for any set of points. If we look at a \"universal\" random A that works with prob at least 1-delta (rather than saying, for a set of points, there is a matrix), then one could wonder about \"adversarial\" point sets when q gets very small, which would be impossible to discover by generating random points.\n\n- Second display on p11 (in Theorem 4): is the inequality pointing in the wrong direction? \n\n### Typos and typesetting\n\n- page 1: \"Property equation 11 is satisfied\" - better to refer to eq (1) on the same page\n- the macro you use to reference equations results in repetition (Equation equation (x)); same for \"Property equation 11\" which sounds weird (there's also Eq. equation 7, etc)\n- a similar comment for citation (\"... e.g. was established by Matousek Matousek (2008)\")\n- \"on streams where then devised\"; where -> were\n- \"which is done is the two following\" -> in the two following\n- \"... bounded by those of the standard Gaussian. and to ...\": remove full stop\n- proof of Theorem 1: \"where the (T_{i,j}) centered\" -> are centered\n- page 2: mutliplicative constant -> multiplicative constant\n- several places, Archlioptas -> Achlioptas\n- why is there an inline QED sign in the first paragraph of page 6? It would be nicer to open a new paragraph.\n- first display on p11: \"(i, k) \\in d \\times S\" - it's clear what you mean but please use precise notation (e.g. [d] \\times [S], with proper definitions)\n- p11: Gaussian chaos -> Gaussian case?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors improve, simplify, and consolidate some of the proofs of the Johnson-Lindenstrauss lemma, and show that the statements which were made for the Gaussian case extend to sub-Gaussian entries effectively without modification, with matching constants. Along the way they propose several new proof techniques which simplify derivations, while always referring to primary references for ideas and bits and pieces. In the first part they explain the mechanics behind standard proofs and introduce their techniques; in the second part they zoom in on sparse random projections and the interplay between maximum sparsity of data / matrices, generalizing and improving the results of Achlioptas and others.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- please address my suggestions about improving comparisons with background / making it explicit how and why the new arguments simplify things\n- please correct the numerous typos", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)