Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
Authors: Sandeep Silwal
David Woodruff
Qiuyi Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: dimensionality reduction
sparsity
johnson lindenstrauss
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We study beyond worst-case dimensionality reduction for sparse vectors

Abstract: We study beyond worst-case dimensionality reduction for $s$-sparse vectors (vectors with at most $s$ non-zero coordinates). Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis:

\noindent (a)  We first consider average-case guarantees for embedding $s$-sparse vectors. Here, a well-known folklore upper bound based on the birthday-paradox states: For any collection $X$ of $s$-sparse vectors in $\mathbb{R}^d$, there exists a linear map $A: \mathbb{R}^d \rightarrow \mathbb{R}^{O(s^2)}$ which \emph{exactly} preserves the norm of $99\%$ of the vectors in $X$ in any $\ell_p$ norm (as opposed to the usual setting where guarantees hold for all vectors). We provide novel lower bounds showing that this is indeed optimal in many settings. Specifically, any oblivious linear map satisfying similar average-case guarantees must map to $\Omega(s^2)$ dimensions. The same lower bound also holds for a wider class of sufficiently smooth maps, including `encoder-decoder schemes', where we compare the norm of the original vector to that of a smooth function of the embedding. These lower bounds reveal a surprising separation result for smooth embeddings of sparse vectors, as an upper bound of $O(s \log(d))$ is possible if we instead use arbitrary functions, e.g., via compressed sensing algorithms.


 (b) Given these lower bounds, we specialize to sparse \emph{non-negative} vectors to hopes of improved upper bounds. For a dataset $X$ of non-negative $s$-sparse vectors and any $p \ge 1$, we can non-linearly embed $X$ to $O(s\log(|X|s)/\varepsilon^2)$ dimensions while preserving all pairwise distances in $\ell_p$ norm up to $1\pm \varepsilon$, with no dependence on $p$. Surprisingly, the non-negativity assumption enables much smaller embeddings than arbitrary sparse vectors, where the best known bound suffers an exponential $(\log |X|)^{O(p)}$ dependence. Our map also guarantees \emph{exact} dimensionality reduction for the $\ell_{\infty}$ norm by embedding $X$ into $O(s\log |X|)$ dimensions, which is tight. We further give separation results showing that both the non-linearity of $f$ and the non-negativity of $X$ are necessary, and provide downstream algorithmic improvements using our embedding.

Published as a conference paper at ICLR 2025
BEYOND WORST-CASE DIMENSIONALITY REDUC- TION FOR SPARSE VECTORS
Sandeep Silwal
David P. Woodruff
Qiuyi Zhang Google DeepMind
UW-Madison
CMU and Google
si 1 ww (écs. wiscc edu
dwoodru feaddrer cmu edu
giuyizegoog com
ABSTRACT
We study beyond worst-case dimensionality reduction for s-sparse vectors (vectors with at most non-zero coordinates). Our work first presents pessimistic lower bounds and then bypasses them by introducing a non-negative assumption:
(a) We first consider average-case guarantees for embedding s-sparse vectors. Here, a well-known folklore upper bound based on the birthday-paradox states: For any collection X of s-sparse vectors Rd, there exists a linear map A Rd + (O())) which exactly preserves the norm of 99% of the vectors in in any lp norm (as opposed to the usual setting where guarantees hold for all vectors). We provide novel lower bounds showing that this is indeed optimal in many settings. Specifically, any oblivious linear map satisfying similar average- case guarantees must map to (2(=²) dimensions. The same lower bound also holds for wider class of sufficiently smooth maps, including 'encoder-decoder schemes', where compare the norm of the original vector to that of smooth function of the embedding. These lower bounds reveal a surprising separation result for smooth embeddings of sparse vectors, upper bound of O(s log(d)) is possible we instead use arbitrary functions, e.g., via compressed sensing algorithms.
(b) Given these lower bounds, we specialize to sparse non-negative vectors with hopes of improved upper bounds. For dataset of non-negative s s-sparse vectors and any 2 1, we show that we can non-lincarly embed X to O(s (og((X|s)//s dimensions while preserving all pairwise distances in lp norm up to + &, with no dependence on p. Surprisingly, the non-negativity assumption enables much smaller embeddings than arbitrary sparse vectors, bypassing our previous quadratic lower bounds and improving on previous best known upper bounds that suffer an exponential (log (()) dependence. Our map also guarantees exact dimensionality reduction for the lo norm by embedding X into O(s log (X]) di- mensions, which is tight. We further give separation results showing that both the non-lineant con-lincarity of ff and the non nogaaiiayyy X are necessary, and provide down- stream algorithmic improvements using our embedding.
INTRODUCTION
Many popular algorithms for data processing in machine learning suffer from large running times on high-dimensional datasets. To alleviate this curse of dimensionality, a common paradigm is first embed the data into lower dimension and then run any desired algorithm in the embedded space. Arguably the most fundamental result in this area is the the Lindonnnindessrruuss (JL.) lemma. states that any set of high-dimensional data X with X dimensional space while approximately preserving all pairwise l2 distances up to relative error Johnson & Lindenstrauss (1984). While very versatile, the JL lemma is still a pessimistic worst case bound. This has led to a proliferation of works studying better trade-offs in more constrained settings, with the goal of exploiting intrinsic structure within the problem or in the dataset to obtain smaller embedding dimensions beyond JL. This 'fine-gre -origrrannne approach has found success in many domains including nearest neighbor search Indyk & Naor (200)) Andoni et al. (008)), clustering
can be embedded into an Ollog Ollogn/e²)

---

Published as a conference paper at ICLR 2025
Boutsidis et al. 2010); Makarychev al. (2019); Becchetti et al. (2019); Narayanan et al. (022 Izzo et al. (2021) Jiang et al. (2024), and numerical linear algebra Woodruff et al. (2014); Cohen
al. (2015).
In this paper, we consider data sparsity as the structure to exploit to obtain better dimensionality reduction. Sparsity is an ubiquitous property of datasets and plays crucial role in many tasks across machine learning, statistics, and hignal-processen dimensionality reduction upper bounds for sparse vectors in general Ep norms. In contrast, virtually all the aforementioned progress improve beyond JI. has been limited to the &2 norm[]] However, all known embedding" results for sparse vectors rapidly degrade as p increases. For E norms, known that any linear dimensionality reduction for sparse vectors must suffer an exponential dependence on on the embedding dimension Zhu et al. (2015). In particular for the important Lo0 case, all known bounds become vacuous.
Theoretically, sparsity assumptions allow for
However, if we relax to average-case guarantees and only require 99% of the pairs of distances in dataset of sparse vectors to be preserved, then well known folklore dimensionality reduction map is known to give excellent dimensionality reduction. It is based on the birthday birthday-paradox map:
Definition 1.1 (Birthday Paradox Map). Consider the linear map f R + En where every coordinate in {1...., d} = [d] is mapped uniformly at random to one of m coordinates. The coordinates in [d] that are mapped to the same 'bucket' in [m] are summed.
For any fixed s-sparse vector x E Rd, the birthday paradox implies that if constant C, then with probability at least 99%, all the support elements of xr do not collide. Thus with probability least 99%, [z))) = || holds for any fixed sparse x 3 Since I is linear, this also implies the same statement for pairwise distances. Interestingly, this map guarantees exact dimensionality reduction (for most pairs), the embedding dimension does not depend on p. and the guarantees hold for arbitrary sparse vectors. The natural question following from this discussion if we can improve upon the (ss²) upper bound of the birthday paradox map, under the same average-case guarantees. This is the first question we address.
Cs² for a large
(Q1) Is the birthday paradox map optimal for 'average-case" dimensionality re- duction of general sparse vectors?
In contributions detailed in Section 2 prove novel lower bounds demonstrating that the birthday paradox map is optimal in many natural settings. This prompts us to ask conditions in addition sparsity enable improved dimensionality reduction upper bounds. Towards this end, analyze the novel setting of sparse non-negative vectors, i.e., sparse vectors whose non-zero coor- dinates positive, go beyond existing lower bounds. This additional constraint is motivated in two ways. Practically in many applications, many sparse vector datasets are naturally non-negative, such one-hot vectors in recommendation datasets or ReLU activations in deep learning He al. (2024). Theoretically, there exists other fundamental problems demonstrating separations between non-negative sparse vectors and arbitrary sparse vectors |Bringmann et al. (2021) 2022); Jin & Xu (224)). Note that one cannot assume non-negativity by simply shifting the dataset, as shifting can destroy sparsity. Thus the second question we ask is:
(Q2) Can obtain improved dimensionality reduction for non-negative sparse vectors in general Ep norms, such as loc?
2
OUR CONTRIBUTIONS
We detail our contributions to each question (Question in Section 2. and Question 2 in Section 2.2 Table summariiess our lower bound results, Table I our upper bound results, and
Table 3 lists applications of our upper bounds. Additional related works discussed in Section A.
"This is not for the lack of trying: there exist fundamental limits disallowing for dimensionality reduction for general Ep norms Brinkman & Charikar (2005) for dense vectors.
in this paper, we use the terms dimensionality reduction and emhedding interchangeably.
ttis hashing idea is ubiquitous, e.g. see CountMin and its variants Cormode & Muthukrishnan 2005
2

---

Published as a conference paper at ICLR 2025
2.1 QUESTION I: AVERAGE CASE LOWER BOUNDS FOR GENERAL SPARSE VECTORS
Our main contribution towards (Q1) is to demonstrate that the average-case guarnntees of the folk- lore birthday paradox upper bound of Definition I.1 is optimal in many natural settings. First recall that the folklore upper bound guarantees that for any and for any point set of 8-Sparse vectors, there exists an embedding into O(s²) dimensions which preserves the ly norm exactly for 99% of the vectors (this is weaker hypothesis than requiring pairwise distances to preserved as long as the all zeros vector is also mapped to the all zeros vector).
Arbitrary linear maps. Our first result states that any linear map with arbitrary real entries which satisfies the properties of the folklore upper bound must embed to at least m = (ss²) di- mensions. Our lower bound holds for any even integer p. More precisely, we construct a set of s-sparse vectors in d-dimensions, where we show that any linear map A which guarantees exact norm-preservation for more than 99% of this set (i.e., randomly chosen vector in the set has > 99% chance of their lp norm being preserved under the map) must map to 22()2) dimensions. Note that the lower bound below for d = s² automatically implies the same lower bound for all higher d by padding zeros in the 'hard' instance.
Theorem 2.1 (Informal, see Theorem B.Ij. Letp 2 2 be an even integer. There exists a point set S C. R of s-sparse vectors such that any linear map A : R²* + R satisffyng || = | for 99% of vectors x E S must map to m = (2s²)) dimensions.
We note that our lower bound, even for the p case, is not implied by the known lower bounds for the JL. lemma Alon (2003): Larsen & Nelson (014 (017). even if some of the hard point sets in prior works are sparse. This because the hypotheses of the lower bounds are different. We prove a lower bound against only preserving 99% of distances, rather than all of them. Our lower bound also has no term that depends on the size of the point set (matching the folklore upper bound).
There is also a known lower bound for the JL lemma (again 2) where only one distance must be preserved with high probability (similar the setting of the above theorem) Jayram & Woodruff] (203). However, this lower bound is only against dense vectors, and so it cannot imply Theorem 2.1 Prior lower bounds for the JL. lemma are discussed in detail in Section
Beyond Exact Preservation. Our lower bound for linear maps extends to a stronger statement for the &g case. We show that mn (s))) even if we only require the weaker guarantee of |x|
|| S (lll)))) This is optimal as any larger relative error of E >> 1/s s can be accomplished with the standard linear JL map with ( = o(s²) dimensions. This reveals an interesting phase transition: any larger error than 1/s enables o(s²) dimensional embeddings but any smaller error requires 2(s²) dimensional embeddings (1/s error is no easier than O error!).
s
Theorem 2.2 (Informal, see Theorem 3.1/. There exists a point set S C R=* of s-sparse vectors
such that any linear map A : R=a + 1.m satisfying |||A=|| || [[[=][//s) for 99% of vectors x E S must map to m = ())²) dimensions.
We also extend this lower bound for linear maps the case where we require inner-products to be preserved, rather than & norms (Theorem B.4).
Arbitrary smooth embeddings. For the l case, we consider a more general class of embed- dings/ f: R' + Rm where f(x) = (fi (z)...., .. fm (x)) and each f: : R + R is twice differen- tiable with continuous second partial derivatives. We prove that this large richer class of mappings still requires m = R()2) to satisfy the guarantees of the folklore upper bound for the E2 case.
Theorem 2.3 (Informal, see Theorem B.2).. The lower bound statement of Theorem 2.2 extends to the general class of mappings defined above.
Beyond Embeddings. Our &g lower bounds hold even when we are not restricted to computing the norm on the embeddings produced by a mapping f and can use another function (on top of the output of f) to compute the norm. Formally, we define an mecodnng-ecodiing scheme using an encoding function of which maps an s-sparse vector in R to a dimension m. A decoding function g then takes the output of f and maps it potentially much larger dimension k. Our goal is to
3

---

Published as a conference paper at ICLR 2025
show that even if l is large, long is substantially less than the initial sparsity squared, cannot have (f())))) = ||0||2-
Definition 2.1. We suppose the encoder and decoder finctiions satisfy the following.
(Encoder function) f RR" - Ihm where
f(z)
and euch Ji IR= - IR is twice differentiable with continuous second partial derivatives.
(Decoder (uncctoon g Rm - IR* where
g(x) = (2),
and each 9: T + R. is twice differentiable with continuous second partial derivatives.
The lower bound statement of Theorem 2.2 extends the case of encoder/decoder schemes of Definition 2.1 and shows that f (the encoder) must map to (2)) dimensions.
Theorem 2.4 (Informal, see Theorem B.3
Perhaps surprisingly, the theorem above states that if f and are both sufficiently smooth, then f still must map to !2(=²) dimensions (matching the folklore upper bound). That is, the whole procedure still "bottle-necked" by the dimension of f.
One reason for why this lower bound is surprising is that the hypothesis that f and are smooth is quite crucial. In fact, the lower bound cannot hold if g is arbitrary, even if f is constrained to a linear map. Indeed, compressed sensing algorithms tells us that there exists suitable linear map A [R + g0(ss log(4)) (the called RIP matrices Candes & Tao (005)) and decoding function such that g(Ar) = x for any s-sparse z. However, g is usually a complicated optimization step. For example in the popular Lasso algorithm for exact recovery, 9 amounts to solving linear program Foucart Rauhut (2013). and the optimal solutions to such optimization programs can be highly discontinuous. If we also for arbitrary encoding functions f, then f also just be list of the non- coordinates of x along with their values, thereby also mapping into Ö(s) dimensions. Clearly this f is also highly discontinuous.
Thus, results reveal an interesting separation result in the context of compressed sensing and sketching in general: if we let the encoding and decoding functions be arbitrary, then we can map to Ō(x) dimensions. On the other hand, imposing even mild smoothness assumptions on f and implies much larger (?s²) lower bound. See Section for more details.
2.2 QUESTION 2: UPPER BOUNDS FOR EMBEDDING NON-NEGATIVE SPARSE VECTORS
We begin with our upper bound theorem for embedding non non-angative sparse-vectors.
Theorem 2.5 (Informal, see Theorem C.2 Let X be set of non-negative s-sparse vectors. For
every p 2 1, there exists a non-linear map f Rd + R" for = OOlo((ns) -sse" which satisfies
[f(x)) f()) y- = (1 [ vllp for all x. X. For the fox case, we can instead guarantee [f(xx) f(v)](())))))))))) < = | ylloo for all y E X with = O(s log
We note that for every p, it is the same map (up to scaling by known factor) that gives the guarantees of the above theorem. There are three interesting aspects of Theorem 2.5 we want to highlight:
1. The map f is non-lineat and non-smooth.
2. X needs to be point sets of non-negative sparse vectors.
3. Our embedding gives a non-trivial embedding for foc.
Given these points, we additionally show that our upper bound for embedding non-negative sparse vectors presented in Theorem 2.5 is optimal in many ways.
4

---

Published as a conference paper at ICLR 2025
Our Lower
Point Set
Guarantee
Thm.
Bound
Sspasse
||||
S 11f(2))loo I 31
Q(d)
2.6
non-negative vectors
Linear f
(spasree
|| yl10o 1 [lf(z) + f(y)ll (2 (2- || + ullæ
(2dd)
2.8
non-negative vectors
Arbitrary f. any E 0
(1p-spee
Vr > 0, 0,0.99|/rzlll> & ll S 1.01/|rzr]le
s2(d)
2.7
non-negative vectors
Arbitrary with continuous second-order derivatives
0.9 || - u & llf(x) - f(y)ll v 1.1 || yll || + ull & llf()) + f( _ C vlo
Opp)-se
2(d)
2.9
vectors
Arbitrary /, any C >
[](x)) - fly)ll S || p---ypl. yll
s-sparse
C| v/1 S (z) - f(y
((Cs))
D.1
vectors
Arbitrary f, any C
8-Sparse
I1(()) = ||>|| for 99% of the points
!(s²))
B.1
vectors
Linear f. even p
s-sparse
[I] | s O l1//) for 99% of points
92(5²)
B.2
vectors
Arbitrary f with continuous second-order derivatives ||/0/
s-sparse
[Il)([<=))] ||=1| O /)) for 99% of the points Arbitrary f, with continuous second-order derivatives
!2s²2)
B.3
vectors
Our lower bound results. d is the ambient dimension. The first five guarantees hold for every pair of vectors z, y in the point set specified in the respective theorems. The second to last column is the dimension that f must map to. In the last row, g is allowed to map to arbitrary dimension.
Table 1:
Non-linearity is necessary. We give an example of an ((1)-sparse and non-negative point set in HE where any linear map requires 52(d) dimensions to preserve the foo norm up to relative error 0.5. This is particularly interesting as many prior oblivious dimensionality reduction maps, i.e. maps which do not depend on the input dataset such as JL or RIP matrices, are linear. However in natural case of non-negative sparse vectors, linear maps are provably insufficient.
Theorem 2.6. Let S be the set of all 10-sparse vectors in Rd with all non-zero coordinates equal to 1. Lei A Rd + I.mh be a matrix such that z =|<=||oo < |x/ 0o S
| Vr E S. Then m = ((d).
'Non-smoothness' necessary. Our upper bound of Theorem 2.5
continuous but differ-
entiable. Motivated by this phenomenon, we show that any upper bound satisfying Theorem 2.5 cannot be 'very smooth': any twice differentiable map (satisfying the same hypothesis) must embed into (dd) dimensions.
Theorem 2.7. Suppose f :d R.m is such that f(x) twice differentiable with continuous second partial derivatives. Let S be the set of all 10-sparse vectors in Rd with all non-zero coordinates being equal to 1. Suppose f satisfies
where each fi is
0.99 |r]| S [r S |1001||rz]|> Vr > V. S.
Then (dd).
Sums of non-negative sparse vectors cannot be preserved. It is natural to ask if the map f of Theorem 2.5 can also preserve sums of non-negative sparse vectors: [I](x) + (w)ll,, || + vll,?
5

---

Published as a conference paper at ICLR 2025
Indeed, upper bound of Theorem 2.5 has the additional property that it preserves the norms of sums in &o norm up to a multiplicative factor of 2, even we embed into one dimension (see the formal Theorem C.2p. We show that the approximation factor 2 is tight in very strong sense.
Theorem 2.8. Let ei be the ith basis vector in RRd, Consider the set S [e)) of d vectors. Suppose f > Ih be an arbitrary mapping which satisfies
|1 + xl [lf(x)) f(u)llo S (0)=)]la + olloo
Vr,y ES
for any > 0. Then m 2 d.
General sparse vectors are hard to embed. We also consider dropping the non-negative hy- pothesis. We again show that for the &oo case, upper bounds in the non-negative case cannot exist for general sparse vectors. Note that prior lower bounds studied in Zhu et al. (2015) are restricted to linear maps. In contrast, we show in the following theorem that any map which satisfies the same hypothesis as Theorem 2.5 but which holds for general sparse vectors with possibly negative entries, must embed into [(d) dimensions.
Theorem 2.9. Let be the ith basis vector in Rd. Consider the set S = } U {0} of 2d vectors. Suppose f S + Ih be an arbitrary mapping which satisfies
0.9|| vll S 11f(2) f())ll 1.1 || ul
Vr,yES E.S
| + yll < [ /w S ClI== + al V
for any C 2 Then m 2 d.
The final lower bound implies that (2(s) embedding dimension is necessary in Theorem C.2
Theorem 2.10 (Informal, see Theorem D.I.. Any map f satisfying similar guarantees to that of Theorem C.2 with e (1) must map to S2(s log(n)) dimensions.
Our embedding
Prior embedding
Prior
Approx.
lp norm
dimension
dimension
Reference
(p (p))(())))())
2 p < x
Zhu et al. (2015)
Linear Map
1 =
(lg) 22
s log(d)
4-2/p-- Pog(d)
1<p<2 <
Non-linear Map
62/(p-1)
Zhu et al. (2015)
Linear Map
O log(d/e) 2²
p E [1,2]
Candes & Tao 2005): : Berinde 2008
Linear Map
(sslo((n)
1
p = oc
Non-linear Map
Table 2: Our upper bound results. The ambient dimension is Our upper bounds are Theorem
C.2 and hold for set of non-negative s-sparse vectors. The first row is not explicitly given in Zhu et al. (2013), but can be derived from their argument. However, their result also holds for n arbitrary s-sparse vectors. The 1 I 2 cases of prior work also handle all s-sparse vectors simultaneously.
2.3 APPLICATIONS OF OUR NON-NEGATIVE EMBEDDING
Our dimensionality reduction upper bound for non-negative sparse vectors, just as the JL lemma, has slew of downstream algorithmic applications. We present small subset of some of the new applications here, with a focus on more fundamental geometric optimization problems that have been well studied. At high level, dimensionality reduction allows to make black-box of any

---

Published as a conference paper at ICLR 2025
existing algorithm for geometric task in low-dimensions. If the dimensionality reduction step is sufficiently powerful, we can hope to get faster runtimes at the cost of a small approximation factor loss; Table B for summary of our downstream algorithmic applications (diameter, max-cut, k-clustering, and more).
Embedding
Problem
Definition
Distortion
Reference
Dimension
Diameter
E.1
O(s2) O O(s (()))/())/
Lemma E.1
and Theorem E.3
Max-Cut
E.2
1
Theorem E.4
k-median/k-center
E.3
4
Theorem E.5
k-means
E.3
O ((g))
16
Theorem E.5
Distance Estimation
E.4
O(s/e2)
1
Theorem E.6
Applications of our dimensionality reduction upper bound. The input is always dataset of n s-sparse non non-negative vectors and the underlying norm is lp for an arbitrary p 2 1. The distortion bounds hold with probability at least 99%. See the theorem statements for full details.
Table 3:
TECHNICAL OVERVIEW
We give on overview of our average-case lower bounds for embedding arbitrary sparse vectors and upper bound for embedding non-negative sparse vectors.
3.1 OVERVIEW: AVERAGE-CASE LOWER BOUNDS
In this section, we provide insights to our lower bound result of Theorem 3.1 Similar ideas are used in all of average-case lower bounds, so foeus this case which is the most instructive.
First we briefly outline how a known lower bounds for the JL lemma is proven. We state the proof of Alon (2003 where slightly suboptimal lower bound is given (the result is tight up to log(1/s) factors), but is perhaps more pedagogically useful in relation to our approach.
Alon (0033 construct specific set of unit vectors and consider embedding of these points into m dimensions which preserves all pairwise distances up to + E multiplicative factor, or the inner product up additive fe. Letting X e gnxm denote the matrix of embeddings, they consider the gram matrix X X The key point is that they have precise control on all the entries of XXT due to the JL. assumption. This allows them argue that the rank of X must be sufficiently large, implying lower bound for m, the embedding dimension.
For us, we cannot directly employ this approach. Our lower bound hypothesis is weaker since we only guarantee that the norm is preserved say 99% of the time. This means that we have no control over a constant fraction of the entries XXT, which can wildly influence the rank. However, this approach suggests that rank is useful parameter and this observation is the starting point of our lower bound.
We now outline lower bound approach for the case of linear map A given in Theorem 3.1 We first construct a suitable 'hard' input. We remark that showing a lower bound under this specific hard example extends to lower bound for general point sets, the former is special case of the latter. The hard input we use can be represented as a distribution over sparse vectors. Our distribution first randomly samples the support elements and then puts random Gaussian values in the sampled support. The distribution we use, Unify,r, is defined below.
Definition 3.1. To generate x Unifa,r,
1. First pick coordinates uniformly at random to be the support.
2. The non-zero coordinates of x are mean zero i.i.d. Gaussians with variance r.

---

Published as a conference paper at ICLR 2025
I = 1, we also denote the distribution as Unif,. Theorem 3.1 states the following.
Theorem 3.1. Let A R= R be linear map and y S C/s for a sufficiently small constant
C O. If A is such that for any 1 1 8,
Pr (III wed W--inif
|| S > 1/1l| 2 0.99,
then m 2 s21100
Note that as stated above, we are assuming the ambient dimension s². This easily generalizes to any larger dimension by padding zeros.
To begin the proof, we first assume for contradiction that m E 8². Now note that
| 2 1|==112 = Σ n. (A,, - Σ x Tr(mx" A) Σ 2
where A; are the columns of A. For simplicity, let's ignore the E, x. portion for the rest of the discussion. We also assume the sum Σvs (A, A2) is over i # j. (In the formal proof,
show that the Σ, 2² portion and the Σ. A, "roughly cancel'.) We view this expression as a polynomial P(x) of degree in the variables z;- Then the condition ||| 12 - ||=|||| I <>1a implies that with large probability, P(x) lies in fixed interval / of size O11) (as typically, y||==112 O()). Our goal now is to show that P(x) has variance (11) (under the randomness of x), implying it does not lie in any fixed / with large constant probability, violating the hypothesis of the theorem.
Now would be very bad for us if P takes on 'very small' values over typical choice of x. This means that cannot rule out P I. For example, P could even be equal to 0 if the non-zero entries of x" I only collide with the zero entries of A" A. To avoid this possibility, we first demonstrate that large fraction of the columns of A have norms very close to 1. However, there are s² columns, which are all in RT. Since we assumed m to be very small, this means that we have > m almost- unit vectors in m dimensions. We show that this implies there are at least S?(*²) pairs of A; and Aj that have non-zero inner products (note that there are ((s*) total pairs). This bound crucially relies on the fact that m < s² and can be thought of as a 'generalized' version of the rank argument used in Alon 2003). Since any pair (i.j) is non-zero in x. x with probability approximately 1/s², this means x x and A A 'collide' on a non-zero entry with a large constant probability.
However, this is not quite strong enough for our purposes since the coefficient of P, which exactly (As, Ay). can be very close to 0 and unluckily, x x could only collide on such small entries. Thus, our refined aim is to show that the coefficients of P that collide with the non-zero entries of x² x are 'large' in the sense that the sum of these coefficient squared is ((11). It can be checked that this is sufficient to show the variance of P(x) (1).
Then in the formal proof, we show that the sum of non-zero coefficient squared is 22(1), via a "fine-grained" exploitation of the fact that < 52 (i.e. another appearance of rank). Now to argue anti ooteiionnenttttoon of P(z), we invoke the following classical inequality which states that the random variable P(z) cannot be concentrated in an interval that is much smaller than the variance (which is directly related to the sum of non-zero coefficients squared).
Lemma 3.2 (Theorem 8 in Carbery & Wright (2001)). Let P: R" + R be a degree d polynomial and Z denote the random variable where P is evaluated on standard Gaussian vector in R". Then
Pr([Z| S ///r(Za)))))))))//))))>>)))))/ S Odd)
An application of Lemma 3.2 then implies that with sufficiently large constant probability, P(x) does not lie in the interval 7 defined above, contradicting the theorem hypothesis that | ap-
proximately preserves the norm of with large probability. Hence, our assumption that m < s2 is not valid, finishing the proof. The formal details are given in the proof of Theorem 3.1
3.2 OVERVIEW: EMBEDDING NON-NEGATIVE SPARSE VECTORS
The goal of this section is to motivate our upper bound result of Theorem C.2 only focus on the lo norm case of the theorem in the overview, but the ideas generalize to any fp.
For simplicity, we
The main idea is first construct a map with slightly weaker guarantees. We initially give a con-
struction of (randomized) map ʃ RRd + RO()) such that
8

---

Published as a conference paper at ICLR 2025
1. f preserves the lx norm of any pair in X with probability 99%.
2. f is never expanding deterministically; [I[(x)) - 2( S | ulloo always.
Before discussing the construction of f. let's quickly see why the two points are beneficial towards the final construction. The final construction simply concatenates (log () independent copies of f. Due to independence, with high probability, every pair xr will have at least one copy of f which "certifies" the &o norm between them least || yll (due to property (1)). Furthermore, since we know every copy of f is non-expanding, we will never overestimate the distance (due property (2)). Putting together these two statements implies the guarantees of our main theorem (for the &oo case).
Now we describe the construction for f which satisfies the two properties listed above. Property (1) actually holds for the birthday paradox map. However, this will not ultimately work since it cannot guarantee property (2). (And more directly, our lower bound in Theorem [2.6] rules out all linear maps). Instead, we use highly non-linear map f- Similar to the birthday paradox map, we start by hashing all coordinates of the ambient dimension, d, to a set of O(s) buckets. These buckets are the coordinates of the embedding. The crucial difference is that instead of summing the coordinates that land in a bucket, we take the maximum, a very unintuitive operation. More precisely, for a sparse vector 2,, we look the buckets where the support elements of x land. Then for all buckets which are non-empty, we take the maximum of the support elements of z that land in the bucket, while all empty buckets get O.
The hashing step already guarantees property (1), similar to the birthday paradox upper bound. So remains to check property (2). This reduces to checking the following: suppose coordinates 1,...,k map to the same bucket under f. Let x and y be two non-negative sparse vectors. Then we want m x&) max (yi. y/)] S max; la, Vil. where x; and yi are the ith entries of x and y (they may be 0). We can check that this is sufficient to imply property (2), To show this claim, imagine all the coordinates 2, and yi together on the real line. They must all be to the right of the origin due to the non-negativity constraint. The right most coordinate, say 21 without loss of generality, is always closer to the rightmost coordinate among the y's, than it is to y1. So the claim follows.
This construction crucially relies on the non-negativity of the vectors. An explicit example where our proposed map fails for arbitrary sparse vectors is as follows: consider two sparse vectors x = 0, O] and y [0, 1, o..... Oj. Clearly, || y|l = 1. Now suppose the first two coordinates hash to the same bucket under f. Then the first coordinate of f(x) will have coordinate -1, since we take the maximum of all the support elements of z that land in the first bucket. In this trivial case, the bucket is a singleton. Similarly, the first coordinate of the embedding of y will be 1, so (z) ((v) > = 2. Thus, property (2) does not hold as the distance expands. One could try to massage the map f to fix this particular issue, but our Theorem 2.9 rules out the existence of any map which preserves the distances between arbitrary sparse vectors in foo norm.
3.3 OPEN PROBLEMS
We note some interesting questions that follow naturally from our work.
1. What is the right & and s dependency for sparse non-negative dimension reduction (The-
orem C.2 ? Can we improve upon the 22(s) lower bound of Theorem D.I to also include 8 factors? For example, for every p 2 1, can we construct set of n non-negative 8- sparse vectors such that any embedding f to m dimensions which preserves all pairwise lp distances up to distortion 1 + ε requires m = [ ([ssoo(n))=²)) Interestingly. such a lower bound cannot be true for the = 2 case since JL already gives us an upper bound of Oloog n/e²) (regardless if the vectors are sparse or dense), so we must look at other p's. On the other hand, for the p 2 case, the JL lower bound of Alon (2003) implies a ((og(n)) log(1/))) lower bound for arbitrary mappings (for a + E approximation) since their hard point set consists of basis vectors (i.e. 1-sparse). Thus, we know some- thing about the E dependency for the p= 2 case. Can we extend this lower bound to other lp norms? Note that our 'average-cass lower bounds discussed in Section 3.1 are not di- rectly applicable since they rule out exact (not approximate) dimensionality reduction for a constant fraction of (not all) pairs of vectors.

---

Published as a conference paper at ICLR 2025
2.00
Embedding L norm
1.75-
1.50-
1.25-
1.00
0.75
ZGR15
0.50
Our Map
0.25
y
0.00
0.5
0.6
0.7
0.8
0.9
1.0
True la norm
Figure 1: simple plot demonstrating the performance our non-negative embedding (Theorem
C.2 versus the map of /hu et al. (2015). The dots represent 10-sparse vectors in R200 with
non-zero entries chosen uniformly in 0, 1]. The z-axis the true &oo norm and the y axis is the approximated norm using the two different maps. Every vector has two dots (one for each map). We adapt both maps to embed to IR T000 but the performance qualitatively similar for other m. We see line).
that the performance of our map is demonstrably superior (it hugs the
2. Our "average-case" lower bound of Theorem B.1 states that the folklore parthday-paradon mapping of Definition 1.1 is optimal for linear maps well sufficientlyssmoood maps. It is an interesting question to prove a similar bound for arbitrary maps for the question of preserving 99% of distances between sparse vectors. Note that for linear maps, preserving distances is equivalent to preserving norms (on the set differences of vectors), but this is not the case for arbitrary maps. The question of only preserving norms is easy for arbitrary maps: there exists an upper bound dimensions by just writing down the norm exactly, the question of preserving distances is the natural one.
3. What is the power of non-lineat embeddings dimensionality reduction? Many oblivious dimensionality reduction upper bounds in literature linear maps. Our results demon- strate a separation between linear and non-linear maps in the natural case non-negative sparse vectors, and it is intriguing ask if such separations exist in other settings.
4. general, are there other natural dataset assumptions or relaxations that enable beyond worst case dimensionality reduction?
4 OUTLINE OF THE APPENDIX
Full details can be found in the appendix, which is organized follows. Section contains discussion on related works. Section gives full proofs for lower bounds for Question (1). Section gives the full proofs for our upper bounds for Question (2). Section D proves that all of the hypothesis in our upper bound for embedding for non-negative sparse vectors are necessary. Lastly, Section gives novel algorithmic applications based embedding for non-negative sparse
G
vectors.
ACKNOWLEDGEMEETS
D. Woodruff worked on this in part at Google and while visiting the Simons Institute for the Theory of Computing. He also acknowledges support from Simons Investigator Award.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Noga Alon. Problems and results in extremal combinatorics--3 Discrete Mathematics, 273(1-3): 31-53, 2003.
Alexandr Andoni, Piotr Indyk, and llya Razenshteyn. Approximate nearest neighbor search high dimensions. In Proceedings the International Congress of Mathematicians: Rio de Janeiro 2018, pp. 3287-3318. World Scientific, 2018
Yair Bartal, Ben Recht, and Leonard J Schulman. Dimensionality reduction: beyond the johnson- lindenstrauss bound. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 568-887. SIAM, 2011.
Luca Becchetti, Mare Bury. Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the lemma. In Proceedings of the 51 annual ACM SIGACT symposium on theory of computing, pp- 1039-1050, 2019.
Radu Berinde, Anna C Gilbert, Piotr Indyk, Howard Karloff, and Martin Strauss. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In 2008 46th Anmual Allerton Conference on Communication, Control, and Computing, pp. 798-805. IEEE, 2008
Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. Random projections for k-means clus- tering. Advances neural information processing systems, 23, 2010.
Karl Bringmann, Nick Fischer, and Vasileios Nakos. Sparse nonnegative convolution is equivalent to dense nonnegative convolution. In Samir Khuller and Virginia Vassilevska Williams (eds.), STOC 21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 1711-1724, ACM, 2021. doi: 10.14553406325.35550000 URL https: 3451090
e/doi.org//
Karl Bringmann, Nick Fischer, and Vasileios Nakos. Deterministic and las vegas algorithms for sparse nonnegative convolution. In Joseph (Seffi) Naor and Niv Buchbinder (eds.), Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithmss, SODA 2022, Virtual Conference Alexandria, VA, USA, January 12, 2022, pp. 3069-3090. SIAM, 2022. doi: 10.1137/1.
9781611977073.1 19, URL/https: / /oi ww.//o............... 1137/1 9781 07778161110 77779737
Bo Brinkman and Moses Charikar. On the impossibility of dimension reduction 1, J. ACM, 52 59:766-788, 2005. doi: 10.1145/109003310890666 URL
1089023. 1089026
Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, 51(12):420-44215 2005.
Anthony Carbery and James Wright. Distributional and norm inequalities for polynomials over convex bodies in _ Mathematical research letters, 8(3):233-248, 2001.
Timothy M Chan. Applications of chebyshev polynomials to low-dimensional computational ge- ometry. Journal of Computational Geometry, 9(2):3-20, 2018.
Moses Charikar, Kevin Chen, and Martin Farach-Coltor Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Xiaoyu Chen, Shaofeng H-C Jiang, and Robert Krauthgamer. Streaming euclidean max-cut: Di- mension vs data reduction. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 170-182, 2023.
Yichen Chen. Yinyu Ye, and Mengdi Wang. Approximation hardness for A class of sparse opti- mization problems. Mach. Learn. Res., 20:38:1-38:27, 2019.
Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal embeddings in sublinear time. TheoretiCS, 3, 2024.
11

---

Published as a conference paper at ICLR 2025
Rewon Child, Scott Gray, Alec Radford, and llya Sutskever. Generating long sequences with sparse transformers. arXiv preprint vrXiv:194..05000 2019.
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation. In Proceedings of the sorty-seventh annual ACM symposium on Theory of computing, pp. 163-172, 2015.
Graham Cormode and S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications. J. Algorithms, 55(1):38-75, 2005, doi:
2003. 12.001
Geoff Davis, Stephane Mallat, and Marco Avellaneda. Adaptive greedy approximations. Construc- tive approximation, 13(1):57-96 1997.
David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1228- 1306, 2006.
Michael Elkin, Arnold Filtser, and Ofer Neiman. arXiv:1603.02321, 2016.
Terminal embeddings.
arXiv preprint
Dean P. Foster, Howard J. Karloff, and Justin Thaler. Variable selection hard. In Proceedings of The 28th Conference on Learning Theory, COLT, volume 40, pp. 696-709, 2015.
Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, 2013. ISBN 978-00-8176-4947--0 doi: 10.1007/ 17880-8176-4948-77 htt.stts: http://.....00000000000000000-10
Lee-Ad Gottlieb and Robert Krauthgamer. A nonlinear approach to dimension reduction. Discrete & Computational Geometry, 14:2 2015.
Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinato- rial optimization, volume 2. Springer Science & Business Media, 2012.
Aparna Gupte and Vinod Vaikuntanathan. The fine-grained hardness of sparse linear regression, 2021.
Sariel Har-Peled, Piotr Indyk, and Sepideh Mahabadi. Approximate sparse linear regression. 45th International Colloquium on Automata, Languages, and Programming, ICALP, volume 107, pp. 77:1-77:14, 2018
Zihao He, Qianyu Shu, Yinghua Wang, and Jinming Wen. A relu-based hard-thresholding algorithm for non-negative sparse signal recovery. Signal Processing, 105:0,, 2024.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruming and growth for efficient inference and training in neural networks. The Journal of Machine Learning Research, 22(1): 10182-105,,, 2021.
Nate Eldredge http:////wwsstacceccccaaeee/////
eldredge). The lebesgue measure of zero set of a polynomial function is zero. Mathematics Stack Exchange. sstackexchange. wtt.://cc./////// URL:httss//math..oo htw.:h//w/mmattt.soooxxx...ooo//
(ver-
sion: 2021-07-22).
Piotr Indyk and Assaf Naor. Nearest-neigbbor-rrseeee embeddings. ACM Transactions on Algo- rithms (TALG), 3(3):11es, 2007.
Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for wasserstein
barycenter. Advances neural information processing systems, 34: 10:11582-1555 15594, 2021.
Thathachar S Jayram and David P Woodruff. Optimal bounds for and streaming problems with subconstant error. ACM Transactions on Algorithms (TALG), 9()): 1-17, 2013.
transforms
12

---

Published as a conference paper at ICLR 2025
Shaofeng H.-C. Jiang, Robert Krauthgamer, and Shay Sapir. Moderate dimension reduction for k- center clustering. Wolfgang Mulzer and Jeff M. Phillips (eds.). 40th International Symposium Computational Geometry, SoCG 2024, Jume 11-14, 2024, Athens, Greece, volume 293 of L.Plcs, pp. 64:1 14:1-644 164116. Schloss Dagstuhl Lww.-iii--eeenrrum für Informatik, 2024. doi: 10,4230/ SoCG. 2024 64
LIPICS.SOCC..0024.
URRhhttps://dba
Ce Jin and Yinzhan Xu. Shaving logs via large sieve inequality: Faster algorithms for sparse convolution and more. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell (eds.), Proceed- ings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pp. 1573 1584. ACM, 2024. doi:
URL
https: /ttps://doi.. org/ 1w.............. T1A111////111000..
William Johnson and Joram Lindenstrauss. Extensions of Lipschitz maps into Hilbert space. Contemporary Mathematics, 26:189-206, 01 1984. doi: 10. 10.0000/oom/022577770000
Daniel M Kane and Jelani Nelson. Sparser johnson-lindenstraae transforms. Journal of the ACM
(JACM), 11(1):1-23, 2014.
Christiane Lammersen, Anastasios Sidiropoulos, and Christian Sohler. Streaming embeddings with slack. In Frank K. H. A. Dehne, Marina L. Gavrilova, Güdg-Rüdiger Sack, and Csaba D. Tóth (eds.), Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 2 21-23, 2009. Proceedings, volume 5664 of Lecture Notes in Computer Sci- doi:
ence, pp. 483 494. Springer, 2009.
011177997883-42-333333- 42. URL https: //doi. 10. 1.00..00000 1007/978 3- 03367-2337-4-444
Kasper Green Larsen and Jelani Nelson. The johnson-lindenstrauss lemma is optimal for linear dimensionality reduction. arXiv preprint 1rXiv:1411.24000 2014.
Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstraus lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 633-638. IEEE, 2017.
Gen Li, Xingyu Xu, and Yuantao Gu. Lower bound for rip constants and concentration of sum of top order statistics. IEEE Transactions on Signal Processing, 18:3119-3178,, 2020.
Sepideh Mahabadi. Approximate nearest line search in high dimensions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM SIAM Symposium on Discrete Algorithms, SODA, pp. 337-354, 2015.
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Nonlinear dimension reduction via outer bi-lipschitz extensions. In Proceedings of the 50th Annual ACM SIGACT Symposiun on Theory of Computing, pp. 1088-1 1101, 2018
Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, and David Woodruff. Optimal sketching bounds for sparse linear regression. In International Conference on Artificial Intelligence and Statistics, pp. 11288-111 11316. PMLR, 2023.
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Moses Charikar and Edith Cohen (eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Com- puting, STOC 2019, Phoenix, AZ, USA. June 23-26, 2019, pp. 1027-1038. ACM, 2019, doi: 10.1145//313376.331666 URL bsttps://dot UBL_Lttte///eo...rg..000111///22 33163557333330
Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in euclidean space. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1064- 1069, 2019.
Shyam Narayanan, Sandeep Silwal, Piotr Indyk, and Or Zamir. Randomized dimensionality reduc- tion for facility location and single-linkage clustering. In International Conference on Machine Learning. pp. 7948-7957. PMLR, 2021.
Balas K. Natarajan. Sparse approximate solutions to linear systems. SIAM J. Comput., 24(2):227- 234, 1995.
13

---

Published as a conference paper at ICLR 2025
Eric Price and David P Woodruff. (1+ approxiit sparse recovery. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 295-304. IEEE, 2011.
Eric Price, Sandeep Silwal, and Samson Zhou. Hardness and algorithms for robust and sparse optimization. In International Conference Machine Learning, pp. 71926-17944 PMLR, 2022.
David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-157 2014.
Zeyuan Allen Zhu, Rati Gelashvili, and Ilya P. Razenshteyn. Restricted isometry property for general p-norms. In Lars Arge and János Pach (eds.), 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPlcs, pp. 451-460. Schloss Dagstuhl- Leibniz--Zentrum für Informatik, 2015. doi: 10.4230/LIPICS. SOCG,2015.451 URL /230 www.ssoo..ooo 2015.4511.451
A RELATED WORKS
Lower-bounds for the JL Lemma Lower bounds for dimensionality reduction were intro- duced for understanding the minimum embedding dimension for n vectors with at most +
multiplicative distortion. By using rank arguments of perturbed identity matrices, as outlined
in Section 3.1. the first such lower bounds showed that the embedding dimension must satisfy
(log((n)/ ( [o)(]/s))), even when the embedded vectors are simple basis vectors Alon 2003 Furthermore, these bounds hold even when a non-linear or adaptive embedding function is applied: however they crucially depend on the maximum distortion being smaller than E. These lower bounds were improved to an optimal ((log(n)/=²) bound for an oblivious or fixed linear map Larsen & Nelson (2014), and then finally improved to any non-oblivious, non-linear embedding function by Larsen & Nelson (2017). It is worth noting that the final construction is significantly different that that of previous works and does not use nearly orthogonal sparse vectors. Note that these lower bounds inherently rely on the assumption that the dot product of the embedding must approximately preserve the dot product, without any post-procsssing or decoding.
Speeding up JL for Sparse Vectors There have been a number of works speeding up the runtime for embedding a collection of n sparse vectors using a JL. map (while still embedding (log(n))==) dimensions). Kane & Nelson (2014) demonstrates a distribution over sparse JL embedding matrices II such that II takes (([==|o/E=) time compute, where ||=/||o denotes the number of non-zero entries of vector x.
Distributional Embedding Lower Bounds and JL Recall that the standard JL lemma states that
for any vectors in R&, one can use random Gaussian embedding to (llgg())ee)) dimensions to guarantee the following maximum distortion bound with high probability: (1 - 1|= - y/|² S ||Ar Ayll² < (1 + =)|l - y/l² for all x. y E V, where [V|
Furthermore, this embedding also oblivious. While is also known that the JL lemma is tight in the worst case, we emphasize that even average-case lower bounds towards Question (2) (see Section 2.1 not implied by the existing JL lower bounds, even for the p = 2 case of Theorem 2.1 At high level, this is because our hypothesis is much weaker (we only require a large fraction of the norm to be preserved, rather than all pairs). We elaborate below.
JL embedding lower bounds state that for large enough n, there exists specific point set on n points such that any map / which preserves all pairwise distances must map to Q[log(n)/e dimensions Larsen & Nelson (2017). The main difference between this lower bound and our lower bounds of Section 2.1 are that the hypotheses assumed are different. The JL upper bound guarantee implies approximate norm preservation for every pair of differences of points in collection of n points, simultaneously and with high probability. Similarly, the JL. lower bound assumes approximate norm preservation for every pair in a collection of n vectors. On the other hand, the folklore birthday paradox upper bound assumes a fixed sparse vector as input, whose norm it preserves with constant probability. Similarly, our lower bounds of Section 2.1 only assume approximate norm preservation only a constant fraction of the time across uniform distribution of suitably chosen sparse vector inputs. Consequently, we have no term depending on the number of input vectors in the statement (both in the folklore upper bound and the lower bounds).
14

---

Published as a conference paper at ICLR 2025
There is also the distributional JL lemma which is random map from R + RO(1/²)) preserving the norm of any fixed vector in IR up to a multiplicative 1 1= with probability at least 99% Johnson & Lindenstrauss (1984). It is shown in Jayram & Woodruff (2013) that the projection dimension of the distributional JI. lemma is tight information theoretically. This ostensibly seems to imply our lower bounds (e.g. the p 2 case of Theorem 2. for example if we parameterize the sparsity as = 1/e, seemingly rendering our lower bounds obsolete. But this is not the case! The information- theoretic lower bound proved in Jayram & Woodruff (013)) relies on dense vectors in IRd, This is not an artifact of the proof, but an inherent requirement to prove their information -itiiootttttttttccce lower bound: any such lower bound cannor use sparse vectors. This because information enfornation-theorttiaalll theoretically, there is already smaller projection dimension from compressed sensing: we can encode any sparse vector in (s)) dimensions. Parameterizing the sparsity by 1/e, this implies an information- theoretic upper bound of Ó(1/e), demonstrating that the lower bound Jayram & WWoodrffi (0133) is not applicable to sparse vectors.
Compressed Sensing The field of compressed sensing studies decoding to recover encoded or compressed sparse vectors Donoho (2006). The restricted isometry property (RIP), introduced in Candes & Tao 2005), is way recover sparse vectors and focuses on bounding the RIP constant:
the maximum distortion D of a linear map A E Rm on all s-sparse vectors: (||=:| I ||Ax=|e | I
DI[æe|ip for all x with x E Rd and s-sparse. The mappings under matrices with good RIP constants can serve as the compressed representation. Furthermore, matrices with such properties automat- ically give dimensionality reduction for s-sparse vectors. The prior known bounds for m for RIP matrices with distortion + ε are (s log (d) for the p 1 and 2 case Candes & Tao (200);; case/Candes
Berinde al. 22008.. For other values of p. Zhu al., (2015) gave bounds of the form (ss²), If we only require to embed n many s-sparse vectors, then one can calculate that [Zuu et al. (2015) 's bound can be converted to (l))()))))(()) ignoring E factors (see Table 2 Thus, both bounds suffer an exponential dependence on p. Zhu et al. (2015) further showed that m = (2())) if A has a bounded RIP constant.
We note that if the RIP constant is small enough, then applying a linear programming decoding via & minimization recovers the sparse vectors when compressed to the ceommattonal-theoretinn optimal ((s lo)( dimensions, with matching lower bound Li al. (2020); Mai et al. (202)). There are other alternatives, e.g. based on CountSketch Charikar et al. (2002); Price & Woodrufi (2011), but all these decoders solve a complex optimization problem. Moreover, these mappings do not serve as embeddings//imeeniinn
reduction (e.g. the Ep of the original vector is not approximated by the lp norm of the mapping).
Role of Sparsity in Machine Learning Primitives for sparse vectors, such as sparse matrix mul- tiplication, is fundamental in a wide range of domains, such as graph analytics and scientific com- puting, and is used as iterative algorithms for sparse matrix facttoriaaton. Moreover, the field of deep learning often relies on faster sparse kernels to demonstrate speedups in practice, as it is a core operation in graph neural networks, transformers, and other architectures Child et al. (2019); Hoefler et al. (202T). On the theoretical side, there are also many works which seek to understand the role of sparsity in computational hardness for optimization problems such as sparse regression Natarajan (1995); ; Davis et al. (1997); Mahabadi (2015); Foster et al. )): Har-Peled et al. (2018): Chen
al. 2019); Gupte & Vaikuntanathan (2021) Price et al. (2022).
Non-linear dimensionality reduction One particularly interesting facet of our upper bound for embedding non- negative sparse vectors that the mapping we give is non-linear. This is an example of an oblivious dimensionality reduction map (a mapping that does not depend on the input dataset) with this property. Oblivious maps include for instance JI. matrices and RIP matrices, which are linear maps. We would like to highlight that non-linear dimensionality reduction results have found many applications, such as modifications of the JL lemma to E2 distances raised to fractional powers Gottlieb & Krauthgamer (2nrhiggmeer(((11115 (2015); Bartal et al. 12.11), terminal embeddings for &g Cherapanamjeri & Nelson (2024): Narayanan & Nelson (2019); Mahabadi et al. (2018) ; Elkin et al. (0066), and finding the optimal way to embed given set of vectors in euclidean space Grötschel et al. (2012). The last two of the aforementioned applications crucially adapt the mapping to a given input point set and
not oblivious.
15

---

Published as a conference paper at ICLR 2025
B AVERAGE-CASE LOWER BOUNDS FOR EMBEDDING GENERAL SPARSE VECTORS
The goal of this section is prove lower bounds showing that the birthday paradox map of Definition is optimal in many settings. The point set we use are generated randomly from the following distribution discussed in Section
Definition 3.1. To generate x ~ Unife,r.
1. First pick coordinates uniformly random be the support.
2. The non-zero coordinates of x are mean zero i.i.d. Gaussians with variance r.
Our first result is to show that any linear map with the same average-case guarantees as the birthday paradox map must map ((52) dimensions. Note that the birthday paradox map satisfies the hypothesis of the theorem statement below up to constant factors (by mapping to C's² dimensions for a sufficiently large constant C). This is because any fixed set of coordinates of size most s hashes to unique buckets under the map with probability say at least 99% (by picking large enough C). If this the case, then does not matter what entries we put in this set of coordinates.
Theorem B.1. Let A TR R.m be linear map and 2 2 be an even integer. If A is such that for any 1 S 1 8,
Pr UniUnif
(IIAullp = ||ullp) p 2 0.99,
then m 2 12/1000.
Proof. Suppose for the sake of contradiction that < 8² /10000. The proof is roughly divided into three parts. The first part shows that A A has many 'non-zero coordinates. The second part shows that a random sparse vector u (as chosen in the hypothesis of the theorem statement) has 'many' pairs of coordinates u, and ūj such that the corresponding (i, entry in A is also non-zero. The last part then shows that the prior result implies that A does not (approximately) preserve the norm of u with a large constant probability, contradicting the assumption of the theorem. The last part relies on the fact that the zero set of a non-zero polynomial has measure 0.
Part #1. Let AI,..., A,a denote the columns of A. Let be random vector chosen from Unif,, and let i be its support with 22 the corresponding non-zero entry. Then | = ||A: uf and ||ulB = of" Then the hypothesis implies that
Pr(11 1 S 0.00001) 2 0.99.
(1)
(Note that we deliberately work with a weaker hypothesis since it will be more useful to us later on). Thus, 0.99 fraction of the columns of A have Fuclidean norm in the range (0.9999, 1.0001]. Let Ax be the restriction to such columns. Note that all diagonal entries of A& are at in the range [0.999, 1.001] and all entries are bounded by 1.001 absolute value (via Cauchy-Schwarl on the columns of Ax). For 2 1, we let E, denote the number of non-diagonal entries of A Ax whose absolute values are in (2-1, 2 2-(+1] and to denote the rest of the non-diagonal entries (with absolute values (1, 1.001)). We show the following claims hold.
a) |xx P (0.99)3$². 2
b)
1 Ax
('99)'s'
c) Σ 422 21+2
(-99)*a*
s.
Claim (a) readily follows from inequality equation 1 To show (b), note that singular values of AT Ax are the squared singular values of Ax so Ax Dne (;(AA)) (since the rank of A is at most m). By Cauchy-Schwarz,
m || = m -o((Ax)*
Σ [a(AAx]]
= =1Ax 2 44.
16

---

(.99)1s1 Published as a conference paper at ICLR 2025
To show (c), note that all diagonal entries of Ax at in the range [0.999, 1.001]. Claim (c) then follows from using the lower bound of Claim (b) since there are at most s² diagonal entries.
Part #2. Now let u be a vector drawn from Unifg and let T be its support. The hypothesis of the theorem states that
Pr( = [|=]]p]) 2 0.99.
Our goal is to demonstrate a contradiction by showing Pr(I|Au||p * 11((р)) 2 0.02, which contra- dicts equation 2
Let ux be the restriction of the coordinates in X (i.e., only keep the coordinates in X). Consider x- By our choice of the non-zero entries of uxxx lie a random principal submatrix of size [T TXX x JI n X We show that with a sufficiently large constant probability, both uxu E R X and A Ax XXX have a non-zero value in 'many' shared entries.
Towards this end, let Vis be the indicator variable for the entry (i, in uxux being non-zero and let Sty denote the squared (i. entry A AxAx We know
1) B|Y,] (52 s(s
Finally, let 7 = Ens 86g Yig. Recalling our partitions lg that defined earlier and Claim (c), have
2
Σ (
Sig
Ee
42-22 2k
1.001s²)
200.
s(s +
4s(s +
m
We want to show Z concentrates well around its mean. Towards this end, we bound E[Z²], We have
2
z² Σ
siyKis
Σ
S Yu
Σ
sysiy
Σ
stySyy Yey.
Since 8 1.001, the first term can be bounded as
E
Σ
S
Vis
1.001 1) i.
Σ
Sij 000 E[2].
s(s+1)
Similarly, the third term can be bounded as
2
E
Σ
Σ
811881
8(88 + 1)
2
Sij
(B[2))²
8(8 +
It remains to bound the second term. We know E[, Yipl S 1/53. For a row i of A3 Ax. let (x) denote the number entries in that row which are in level lg. Then the second sum is
E
Σ i
Stg YogKi
StySij' $
34
(z
Z
4s
122k222
k.k'
(+
48
2222
17

---

Published as a conference paper at ICLR 2025
Let = Zx)2 Zx)2 2k: We now consider the following two cases.
Case 1: At least half of the t, 'ss are at least s. In this case, we note that
(i)
[X]
2 0.495s.
22 g2
28
We have
(i)
(A(i)
48
< 48
S 48
E[Z]
$2225
2222
where we have used the fact that
Σ k (1) 2 5² So altogether.
E| S 5s E| + B|ZJ² S 12
Thus the Paley Haley-Zygmunt Zygmund inequality implies that
E| E 72|
Pr(Z 2 1) (1 (1- (1-0013
20
Case 2: At least half of the it's are at most In this case, let Ax be A3xAx restricted to the rows where S We know |X|] 2 0.5 Our goal is to show that A Ax still has at least 'many' non-zero off-diagonal entries.
The proof is identical to the proof of the three claims (a). (6), (c) above. All sums below only pertain to the matrix Ax'. Indeed, we know |Ax 1|2 2 0.495s² so
2 > Σ Eoi(Ax)8))
||4 Ax 11: Eoi(Ax))
|Ax: (-495)3s4.
Combining with the fact that all non-diagonal entries are bounded by 1.001 in absolute value, the above inequality implies that Σ1z0 6, 2i+2 (.495)²s* //10001mmm) s 50ss. Furthermore,
for row of Ax',
Σ
(1) 2222h
t
5
82 8
so we can bound
(i)
Zz(i)
4s
Σ
Σ
< 4 ΣΣ Σ
222h
$222K
4 Σ
4
44E/21
8
Thus,
E <6 + 2
So by Payely-Zygmund,
2
2r -1-1100 -101-2
Z N 20"
Thus we see that Z 2 with probability least .05 in both cases.
Part #3. Recalling that T' is the support set of u, we have Au Ever U,A and thus,
Σ U, KET
Σ k1....pp
26, ... Uip
Σ A..0) .. A4,
Σ
uf = P(u),
(3)
[E(m]
TE
p
18

---

Published as a conference paper at ICLR 2025
where the outer sum is over all p-sized tuples of indices (with repeats allowed), the notation A,, (1) denotes the jth entry of the column A,, and the inner sum is over all the entries of the column.
We claim that if is even integer, then P(u) is non-zero polynomial. To do so, we demonstrate a monomial U; ... us with a non-zero coefficient. Now if we assume Z 2 1, then this implics there exists two columns say A1 and A₂ of A such that (A1, A2) is non-zero and both and are in the support set of u. We consider the following different cases for p.
If p 2, consider the monomial ū U2. It's coefficient in P is Σ, A,())42)) = (A), * 0, so we are done. Now if p > 2 and even, instead consider the monomial up zug. We claim that this is non-zero. Indeed, since p 2 is also even, Σj (G) ( A1) must be non-zero since is sum of non-negative terms, onc of which is non-zero (since at least one j satisfies A Az()) * 0). So are also done.
Now finally, we note that since the entries of u in its support are picked from a continuous distribu- tion and P is non-zero, the probability of the event P(u) 0 is also O However, ||Aul|p || lp implies Au - ||u|ا = P(u)= = 0. Overall, with probability at least 0.05 (the event that Z 2 1), we have Puu) # 0, contradicting the hypothesis equation 2
Thus, m 2 / /2/1000, as desired.
We extend the previous theorem to the case of approximate norm preservation for the le case.
Theorem 3.1. Let A : R² + R. be a linear map and y S C/s for a sufficiently small constant
C> 0. If A is such that for any 1 < S
Pr uniUnif
(II)
|| S >>||u| 2 0.99,
then m 2 2/1000.
Proof. Suppose for the sake of contradiction that < s² /1000. The proof is roughly divided into three parts as in Theorem B.1 The first part shows that A has many 'non-zero' coordinates. The second part shows that random sparse vector (as chosen in the hypothesis of the theorem state- ment) has 'many' pairs of coordinates u, and Uj such that the corresponding (i.j) entry in AT A is also non-zero. The last part then shows that the prior result implies that A does not (approxi- mately) preserve the norm of u with a large constant probability, contradicting the assumption of the theorem. The last part relies on bounding the probability that a random polynomial lies in an uncxpectedly small interval. Since the first two parts are identical, we just present the last part.
Recall the random variable Z defined in the proof of Theorem B.I with probability at least 0.05.
There we showed that Z 2
Part #3. Recalling that T is the support set of u, we have ||Aull ||uu|3
|EtEr
ue 1|2
1/1112-
Σ uy A
Σ
uuu u.u (Ar,
>'EEef := P(u)
(4)
LAVET
tET
where |cel S 0.001. If we pick the entries of u to be standard Gaussians, have
E(P(w)) = Σ
Recalling that Yıj is the indicator for ub ux having non-zero entry at (i,j), we have
E[P(())] > Σ Sig Vi + Σ CeG + Σ 3
IET
SO
Var -(w)
Σ
813 Yo =2
1.3
Thus, we assume that Z 2 1, then Lemma 3.2 implies that if the variables of u the support are picked from the standard Gaussian distribution, then the probability that P(u) E [-e,e] = (vv)) for any sufficiently small e > O. Now consider the following three events.
see www/////w//iaaan..cccccccccco/// eldredge
19

---

Published as a conference paper at ICLR 2025
E event that ||u/12 100s.
2 event that Z 1.
E3 = event that P(u) & [-c,d] cf for a sufficiently small constant c.
By picking e to be a small enough constant, we know that all the events hold with probability least 0.02. Let's condition all of these events holding. If so, we show that the condition Au| - || S 7/|u cannot hold. Indeed, the condition directly implies that || ||u| =
P(u) lies an interval strictly contained in [-c, cj. Thus altogether, with probability at least 0.02, we have Au| || lul22 contradicting inequality equation This finishes the proof. D
We now extend the result of the prior theorem to a more general class of mappings. We recall the general class that we consider, as described in Section 2
We let f IR + 12' where f(x) =
(fi(z)..... fm))) and assume each fi R - R is twice differentiable with continuous second partial derivatives.
At high level, the level of smoothness assumed allows us to consider taylor expansion, where we approximate each fa using linear function up to some quadratic error. By taking the expansion sufficiently close to the origin, the quadratic error becomes negligible, thereby reducing the problem to the linear case. Crucially, we use the fact that our sparse vectors are drawn from 'scale invariant' distribution, in the sense that scaling vector sampled from Unife,- is equivalent to sampling from r for an appropriate r'. The full details are given in the proof below.
Theorem B.2. Suppose 7 S C|s for a sufficiently small constant C defined above is such that for any 1 S t S and any r > O,
Iff Rd
R
as
Pr Uniuiiler
(111/(=))12 | < x 2 0.999,
then m 2 2/10000.
Proof. Note that we may assume that f:(0) O: otherwise our guarantees would trivially fail when r -> O. Since the second partial derivatives of all fa which comprise f are continuous, they are bounded in magnitude in [-1, 1]s² a compact set. Let L be such an upper bound which holds for all i (note that L may depend on s). Now let e < be sufficiently small value which will be determined shortly. For any fixed St. Taylor's theorem for multivariate function 5 implies that for any E c]c
-f(()) - (V) 2) S L (x1 +... +... +x,)²² Ls²c²
for every i. Let A R= R be the matrix with a, it's rows. The above inequality implies that
ll(()) Axlloo S L
Thus Lemma F3
implies that
[11f()) || S d² poly(s, L.
(5)
for all x I-c, satisfying [=) 2| By picking sufficiently small, we can say the following:
For any E [-c, cje² such that [x) || S >| we also have Ax | S
|||=|| + 2² poly(s, I.).
For any x where Ax| - |
x holds for some scalar 7' > 0, then for any 21 where y ...
scalar > O, we also have Ay
s Tayl schorrm_foor
20

---

Published as a conference paper at ICLR 2025
The first claim follows from inequality equation 5 and the second claim follows from the fact that is a linear map. Now note that by picking large enough constant / > 1, we know that sampling from any L, x ~ Unift,c/se satisfies ||>:1 2 2 / (for some other constant 3 > 0) with probability 0.999. Thus sufficiently small choice of and large enough /3 implies the following:
For any x E [-c, cf* such that [1) -
< 21/=
we also have || 1 S
2y 1
For any x sampled from offa in (-c, c)p² with probability least 0.999.
Now note that uniformly chosen vector in Unif,, for any is just scaled uniformly chosen
vector Unif,,1 Due to our hypothesis on f. it then follows that A such that for any S t S
Pr U-iuni
(11
|
< 2) N 0.99.
The theorem then follows from Theorem 3.1 (note that 2ny is smaller than the tolerance required in that proof).
As discussed in Section 2 further extend prior result to encoder decoder schemes (recalled below), where another 'decoder' function can be applied on top of the embeddings to compute the l2 norm. Our lower bound shows that as long as both the encoder and decoder functions are suffi- ciently smooth, the encoder function is required to map to ((s ) dimensions. We do not restrict the embedding dimension of the decoder function. In other words, the whole process is 'bottle necked'
by the inner dimension. We recall the definition of encoder decoder schemes for convenience.
Definition 2.1. We suppose the encoder and decoder functions satisfy the following.
(Encoder ) f TR55 TRe where
f(x) =
and each fi R - R. is twice differentiable with continuous second partial derivatives. (Decoder, function) R + IR where
g(x) = (2)
and each 9i : 1R + R is twice differentiable with continuous second partial derivatives.
Theorem B.3 (Encoder/Decoder Schemes). Let S C/s for sufficiently small constani C' > 0. h(()) = s(f(x)) = R for k 5² (as defined above) is such that for any 1 S t S and
any r 0,
Pr Uniff
(I))())) | I < 2 0.999,
then m 2 32/1000.
Proof. Similar the proof of Theorem B.2 let A be the matrix where the ith row is equal to (h,
Note that 2 + R² We first claim that has rank at most m. To see this, note that
h(x) = (f()))....... g,a (f
For S j s², let (z) 9, (x)).. Denoting the input variables of gj as 9j (311.... Fm)), the chain rule tells us that for any j and i,
ah dx;
m Σ 1m1
Ögg 0f:
(g.pp)
Oye
Ox:
where
0f
0.
=
E m
Or,
Dx:
21

---

However, note that the proof of Theorem 3.1 only relies on the rank of the matrix A A, which is at most m (also true here). Thus, the rest of the proof is Published as a conference paper at ICLR 2025
and
0gi 0y1
ogi
Pj
I
yym
(For simplicity, we are omitting the fact that all the parital derivatives of ft are being evaluated at and the parital derivatives of 9j are being evaluated f(0)). Letting
of
B
42
E
R xm C=
P2
RRoxxm
RR*
122
p/
we see that
p B"
p1 BT
CBB E =
:
p B
Thus, has rank at most m. Now the rest of the proof proceeds by combining elements of Theorem and B.2 which only briefly sketch for simplicity.
First, identical to the proof of Theorem B.2 a second-order varialle talyor expansion around 0 implies that A is such that for any 1 S
Pr U-iff.
() |1|
|| S r||2|12 2 0.99.
Now we cannot directly invoke Theorem 3.1 since the matrix A the statement Theorem 3.1
maps R=" to R",, but A is R= + RR
identical to the proof of Theorem 3.1
Finally, we extend the lower bound of Theorem 3.1 to the case of approximately preserving inner products.
Theorem B.4. Let A: B + Rh be non-zero linear map and I C/s for a sufficiently small
constant C > 0. If A is such that for any S 1, S 8. (KAx, Ay) - (,, S (||0|||||v|||2 2 0.99
Pr y--
and
Pr Unifi
(1I
Ilvll21 < >a11 (2) 2 0.99,
then m 2 s//100..
Proof. The proof is almost identical to that of Theorem 3.1 but we present the full details for completeness, since we are working with two vectors instead of one. Suppose for the sake of contradiction that shows that A A has many 'non-zero' coordinates. The second part shows that a pair of random sparse vector and (as chosen in the hypothesis of the theorem statement) have 'many" pairs of coordinates u, and by such that the corresponding (i.j) entry in AT AA also non-zero. The last part then shows that the prior result implies that A does not (approximately) preserve the inner product with a large constant probability, contradicting the assumption of the theorem. The last part relies on bounding the probability that random polynomial lies an unusually small interval.
s2/103.. The proof is again roughly divided into three parts. The first part
Part #1
Let Ai..... A. denote the columns of A. Let be a random vector chosen from Unif,, and let be its support with the corresponding non-zero entry. Then || = |A..1 of and || = of. Then the hypothesis implies that
Pr A.112 1 s 0.0001) 0.99.
22

---

the Published as a conference paper at ICLR 2025
Thus, 0.99 fraction of the columns of A have Euclidean norm in the range (0.9999, 1.0001]. Let Ax be the restriction to such columns. Note that all diagonal entries of A are at in the range [0.999, 1.001] and all entries columns of xx). For 2 1, we let & denote the number of non-diagonal entries A Ax whose absolute values are in (2-i, 2 2- and to denote the rest of the non-diagonal entries (with absolute values in (1, 1.001)). We show the following claims hold.
bounded by 1.001 in absolute value (via Cauchy-Schwart
a) |Ax P (0.99)33².
b) |x (.90)4.4
c) E9 22 21+2
21+2
(.99)'s²
1.001s².
m
Claim (a) readily follows from inequality equation 6 To show (b), note that singular values of AxAx are the squared singular values of Ax so Ax Ei= ox(x))' (since the rank of A at most m). By Sauchy-Schwar
1x
|1 Ax m Eo((A))²
[
|Ax11 2 (.99)'84.
To show (c), note that all diagonal entries of Ax are at in the range [0.999, 1.001]. Claim (c) then follows from using the lower bound of Claim (b) since there are at most s² diagonal entries.
Part #2.
Now let u and be a vector drawn from Unif, and Unif, respectively and let T, and T, be their corresponding support sets. The hypothesis of the theorem states that
Pr([(Au, Au) (u, wY) s >/|u||2||o|12) 2 0.99.
Our goal is to demonstrate a contradiction by showing Pr( (Au, Ac) + ?|1u||2/||122) 2 0.02, which
contradicts equation 7
Let ux be the restriction of u to the coordinates in X (i.e., only keep the coordinates in X) and similarly define ux- Consider ux".. The non-zero entries of uxex lie on a random principal submatrix. We show that with a sufficiently large constant probability, both wxux e [ and Ax E [ have non-zero value in 'many" shared entries.
Towards this end, let Yij be the indicator variable for the entry (i.j) uxux being non-zero and let Sty denote the squared (i.j) entry Ax. We know
E|
$
Finally, let % = Ei, 8ig Yij. Recalling our partitions Ea that we defined earlier and Claim (c), have
((99))s*
E
Sty
E
42 2h
1.001s?)
200.
4s2
m
The same proof in Theorem 3.1 shows that Z with probability least .05.
Part #3.
Recalling that T, and T. are the support sets of and v, we have
(Au, Au) (u,v) Σ uwy (Ai, Ag) Σ iin P(u,)) v).
23

---

Published as a conference paper at ICLR 2025
If we pick the entries of u and to be standard Gaussians, have E[P] 0. Recalling that Yıg is the indicator for ux ux having non-zero entry at (i,j), we have
E
Sig Yi Z.
Thus, if we assume that Z 2 1, then Lemma 3.2 implies that if the variables of and v in their support are picked from the standard Gaussian distribution, then the probability that P e [-E,a] ((VE) for any sufficiently small E > 0. Now consider the following three events.
ε event that ||u|||||||| - 100s.
Σ event that Z 1.
Eg = event that P & [-c, c] for a sufficiently small constant C.
By picking to be a small enough constant, we know that all the events hold with probability at least 0.02. Let's condition on all of these events holding. If so, we show that the condition [Au, Au) (u, e}} S > a||v||22 cannot hold. Indeed, the condition directly implies that (Au, Av) - (u, v) = P lies in an interval strictly contained in |-c, c). Thus altogether, with probability least 0.02, we have (Au, Au) (u, e) > //|/||2/||/1 contradicting inequality equation 7
This finishes the proof. C
C UPPER BOUNDS FOR EMBEDDING FOR NON-NEGATIVE SPARSE VECTORS
In this section we present our embeddings for non-negative sparse vectors and prove Theorem See section 3 for overview.
Our embedding is constructed two parts. In the first part, we introduce a "base" mapping / Rd m It will be random mapping which preserves all lg norms of fixed pair of non- negative sparse vectors with constant probability. Crucially, it will be non-expanding. Our final embedding formed by stacking many independent copies of our base mapping.
The base mapping maps every coordinate into one of m buckets and takes the max of all non-zero coordinate elements that map any bucket. The max pooling operation makes this map non-linear.
Definition C.1 (Base mapping). We define mapping f Rd + R Pick a uniformly random
function from h : [d] + [m]. For every i [ml, let S. { E [d] h()) i). We define f(z) E R as follows. For every i E [ml)
[max ((z, lie E S.)) ifS, #0, otherwise.
f(x); = {0,
Our final embedding is the following. It stacks many copies of the base mapping. Note Q denotes vector concatenation.
Definition C.2 (Final Embedding). non-negative (d, m, m) embedding F :Rd R is defined as follows. For every 1 < i & T, let fa: TRd - RR be independent copy of the random mapping of Definition C. Then any x E Rdd
T
F(r) = θ fl(x).
The key properties of the base mapping are proved below. As discussed in Section 3 the non- expansion property is crucial and is only guaranteed for non-negative vectors due to the max opera- tion.
Theorem C.1. Let f Rd m be a random mapping of Definition C.1 It satisfies the following:
1. f(0) 0 deterministically for all values 2 1.
2. For any pair of non-negative s-sparse vectors x, y E Rd (both independent of f), if we take
m = (6))
Pr(vp, (15(x) f())lzz = || -y11)) 1
24

---

Published as a conference paper at ICLR 2025
3. For every pair non-ngative vectors and (not necessarily sparse) and any embedding dimension m, lf(x)) f(y)llp I || - ylpp deterministically for all 2 1.
Proof. The first property follow from the definition of f. Let m = 100s²/o /6 and h be the uniformly random function from [d] + [mm] that constitutes f.
Let and y be two fixed s-sparse vectors R4, Proving the second condition relies solely on fact that h is likely separate all the non-zero coordinates of and y- Indeed, the union of their supports is of size at most 2s. Under h, the probability that some two domain elements their union collide is at most
(100>2/8)
This event means that very coordinate in the union of the supports of and is mapped to unique coordinate in [m]. and thus for every p.
2/2
D4 P
Σ (((x),-(w))) -1f(())) f(y)lpp
3=1
proving the second condition.
The third condition crucially relies the fact that are using the 'max' operation to define f. For any pair of non-negative vectors x and y, we have
m
m
(1 - sw)) Σ -
- 1())p Σ max ((a) h()) = -]) - max((u MM) = i.
suffices to prove the following: if a1,..., ag and bi,.... by are non-negative real numbers then
max(a1, .2k) max(b).......... (b.x...,,bb))))) & max lor bel-
This is because assuming the claim, we have
m
d |os - 19 S Σ 1 - Vill. j1b()=+*
Σ max MG) i}) max ((us (M)) = i))1 R S max
1=1
since h maps every coordinate [d] to only one coordinate in [m].
Now to prove the claim, assume without loss of generality that ay = max(a:) 2 max, (bx). Then
Joe- - max; (b:) s lar bbl
bel since in the real line, have the ordering by max, (br) S ag.
we give an embedding which approximately preserves all pairwise distances between points a dataset of non-negative sparse vectors.
Building upon Theorem C.1
Theorem C.2 (Embedding for non-negative sparse vectors). Let F IRd - R be a non-negative (d, m, T) embedding for Oss/e) and T Ollog(ss)/e) stated in Definition C.2 Let
X Rd be a dataset of n non-negative s-sparse vectors (which independent of F). We have
1.
Pr Vpp 12 [F(z) - F(yIITTT
E $1#E) 1
xx- 411
2. For the lxx. norm, suffices to take m O(s) and T O(log n) and guarantee that
Pr Pravaye X, - = ||0- 2 1/n)
3. Additionally for the too norm, it suffices to take m and T 1 and guarantee that
Pr Vr,y E X, [F(x) + F(2) E [1,2] =
I + alloo
25

---

Published as a conference paper at ICLR 2025
Proof. We first prove part (1). Note that
T
F fu
1=1
where each f& Rd + go(s/e) is the mapping of Definition C.1 and T (llg(ns))EE) Now consider an arbitrary fixed pair z,y E X. First by the non-expanding property of each fE, we always have
- fu(0) ST. T vlß.
Now we show that the sum is also sufficiently large. Consider any fixed coordinate in the union of the support of and y. For any fk. the probability that does not collide with any other support element is at least 1 - e/100 since there are only O(s) total coordinates ports of and y. and fa maps (s/EE) dimensions. Since the fx's 's' are independent, this means that é will not collide with any other support elements for at least 1 1 & fraction of the fa's 's with most exp(-9((T)) (Lemma F.T By union bounding,
the union of the sup-
failure probability statement to all the coordinates in the support of x and except with failure probability at most exxp <exp(=((T=)) < 1/poly(nz). by our choice of T. Now if coordinate i does not collide with any others in some fu. then we know that fx) (u) 2 (z; - y:)". We can sum this relation over all coordinates and all fx. Thus, except with failure probability at most 1 1/poly(n), we have
extend this
Illf(()) fa 2 (1 - =)T 1| vIp.
as desired.
The foo case can be handled as follows. For a fixed pair x, y, suppose that the first coordinate witnesses their l norm. If we take Oss,, then the first coordinate does not collide with any other coordinate with probability at least 99% (there maybe collisions among other coordinates). Thus with large constant probability, fixed base mapping f of Definitionn
that [If()x) fly) 2 || - ylloo- But we always have [ı((z) [w)ll I || y deterministically. Thus with (log n) repetitions, every pair x, y will have at least copy of the base mapping which ensures that the Eoo distance is exactly preserved.
For the third part of the theorem, note that since the coordinates are non-negative and F(x) R is just the maximum coordinate, we trivially have [F)) + Fov 2 || + yllso- In the other direction, we claim that [=) f(y) so I 2||xx + yoloo always holds deterministically where
is our base mapping of Definition C.I Indeed, it suffices to show that for any non-negative real
numbers 01,- 01,...,0, ar and b,, .i,.... by we always have
max + max(b,,............... ...t, br) S max + b.).
(10)
xE(r]
This is seen to be true by just taking I = arg max de (w.loo.g. max(ar) 2 max(b:)). This completes the proof.
The additive guarantees of our mapping F also extends to general Ep norms, with an overhead of 20(p)
Corollary C.3. Let 2 1 and F Rd - R 220r) lon(n)/6 be a non-negative (d, s2.22000) /e, T) embedding for T = 20(r) log(n)/E as stated in Definition C.2 Let X C Id be dataset of non-negative s-sparse vectors (which independent of F). We have
Pr Vz, Vx,yEX [F(x) F(EIE/TT + V
c1+E
2 1 2 111oopo))(
Proof. The proof is very similar to that of Theorem C.2 so we only highlight the differences. For the parameters, we take independent base embeddings fs Rd + Imm for m $220(p) /s (of
Theorem C.1) and T 1og(n)20(v)) (0p)). /e. Let s²/m. First, for any fixed pair x, y E X we have
26

---

Published as a conference paper at ICLR 2025
[f)(
fa(1)1 v holds for at least - fraction of k's (due property (2) in Theorem with failure probability at most 1/poly(n). Thus we have
C.1
Σ [llf(())+ fu 2 2 (1->)'' ||a + 2/13
To bound the other direction, we also always have (x) fu - 2 U y for every from This means that
Eq. TO
Σlnoo+ S (1 -) vlß 7T2 | y
Recalling the value of finishes the proof as in Theorem C.2
If we limit the entries of the sparse vectors to be from discrete set, then we can extend our non linear map to sparse vectors with arbitrary entries as well. Contrasting it with the known (ss)) lower bounds for embedding arbitrary s-sparse vectors (using linear maps) from Zhu et al. (2015) hints that the 'hardness' for embedding arbitrary sparse vectors maybe due to entries with a large range.
Theorem C.A. Letp and F IR +R = Oir) log(n)/s" be (d, A /e), T) embedding for Let X C. Wd be dataset of n s-sparse vectors We have
T log(n) A Alrl / stated in Definition
C.2
with entries in the discrete set (-A, (-A...., }}.
[F(x) F
Pr yx
E [(1 - =)T,T]]
21 11-11polt 11/polly(n).
| u11
Proof. We again consider
T F D fx
where each fk Rdd + R.h for ((1))())(22))ee) We can check that the first two properties in Theorem C.1 hold for arbitrary s-sparse vectors. However, the third property crucially relies on non-negative entries. Nevertheless, we can obtain the following variant, assuming the entries are in a discrete set: for every pair of vectors y E {-A.... A) d we have (lfx(()) fa(y)) S A | yllp- Indeed, as in the proof of Theorem C.I it suffices to prove the following: if @i. and bj..... by are all in (-A...., A). then
(2A)%/ is the mapping of Definition C.1 and T
Imax(a)...... ax) max(b, ... bR) < 2A max la, - bel-
And this holds because if the RHS is 0, then so is the LHS. Otherwise, the RHS is at least 2A 1 and the LHS is always bounded by 24.
Equipped with this, similarly have that with failure probability most exp(-I((>)) 1/poly(n), [x) fu(i))
= || vlpp for at least (1 - 7/2)T fraction of the indices & where
= =/AA)).. If this is the case, then again
(1-7/2)T -|x Σ - (1-
and by the bounded-expea bounded-expanding property of fk. we also have
(1-
vllk + + vll.
Putting everything together, we have En [1 ff E =1 || vllp. And the final result follows from union bounding over all (nn²) pairs, desired.
(w)ll
27

---

Published as a conference paper at ICLR 2025
D LOWER BOUNDS FOR EMBEDDING NON-NEGATIVE SPARSE VECTORS
In this section, we provide lower bounds for dimensionality reduction for sparse vectors under var- ious hypotheses. As stated in Section 2
together they demonstrate that our non- non-negative sparse embedding of Theorem C.2 is optimal in many natural ways. See Section for an overview.
We begin by showing that linear map cannot have the same guarantees as Theorem C.2
Theorem 2.6. Let S be the set of all 10-sparse vectors in F2 with all non-zero coordinates equal to 1. Let A : R + I. be a matrix such that 2 |1121100 I || S 3 || Vr E S. Then m = Q((d).
d/100. By considering the basis vectors, every column of A must have an entry with absolute value at least 1/2. Then there must exist a row r of A which has at least d/m 2 100 such entries. At least 50 of such entries in row r must be of the same sign. Let x be an indicator vector for the column of 10 these entries in row r. Note that E and (Ax)r] 2 which implies ||AAz|loc z 5, contradicting our assumption on A. Thus, m 2 d/ d/100- = (d)) desired.
Proof. Suppose for the sake of contradiction that
The following theorem states that preserving the norms of the sum of vectors is impossible factor of 2 - E for any ε > O in &cc, even if we only restrict to non-negative sparse vectors. Note that Theorem C.2 preserves the norms of the sums up to factor of 2.
Theorem 2.8. Let e, be the ith basis vector in Rd. Consider the set S {e;] (0) of d vectors. Suppose f S + IRm be an arbitrary mapping which satisfies
| + vllxe S [1f(x)) f(u)ll S (2- + vllso VK
for any & > O. Then m 2 d.
Proof. Suppose for the sake of contradiction that m d. First note that f(0) must be the all 0's vector by taking = = 0. Then taking x = e; and y = 0 implies that (es E [1. =] for all i. Again label such coordinates of (e:) that lie in this range as 'large.' If m < d, then there exists and such that f(e)) and f(e) have the same large index by Pigeonhole. We know that Ilf(e;) + fle))]lo E [1, - =] by our hypothesis. Now the large entries of (e:: and f(ez) have the same sign, then their sum in absolute value is at least 2, which cannot happen from the above observation. On the other hand, if they have different signs, then the largest sum (in absolute value)
that these entries can add to is at most - (either from 2 - + (-1) or -(2 =)+ + 1), which also cannot happen. These cases are exhaustive which means our assumption m < d cannot hold, and must have 2 d.
The following theorem shows that any mapping f also cannot be 'too smooth'. Note that in our mapping, we use the maximum function, which is not differentiable.
Theorem 2.7. Suppose f _dd + R. is such that f(x) (2)....., where each fo is twice differentiable with continuous second partial derivatives. Let be the set of all 10-sparse vectors in Rdd with all non-zero coordinates being equal to 1. Suppose f satisfies
0.99 |xel < [rf(rr)]oc s 1001||rz11xx
Vr> 0, S.
Then m (dd).
Proof. Note that [o( = by taking r - 0. Since the second partial derivatives of all fi are continuous, they are bounded in magnitude in the compact set [0, 1ja Let T be such an upper bound which holds for all Now we let r < 1 be a sufficiently small value which will be determined shortly. For any fixed ft. Taylor's theorem for multivariate function limplies that for any y [0, r]d which is O(1) -Ssa-se,
1f(()) / (V.(0.)) (M +... va)² < O(Tr2)
http://.....aaaaa////oooooooaarr s_thssset_hhhhteee for_________
s_thhoremmtaaylrr
28

---

Published as a conference paper at ICLR 2025
for every i. Let A Fd - I= be the matrix with a, it's rows. The above inequality implies that Il(()) Ayllo S )(T))).
Thus if r > 0 sufficiently small, z is any vector such that ||2||00 = 1, and
0.99 |r=]| = (1=(c2) 1 1.01 |==|
then we must also have
|>>|b> < [|A(r=)]loo S ||=1|000
2
But since A is linear, this actually implies that
3
1//2 I (A(r'2))l< S 221 |1''slle
for all r' >>>0 0. Putting everything together, (letting z be the vectors in the hypothesis of the theorem statement), implies that
3 221llloo Vz E.S.
b ||=1100 S |o S
Then Theorem 2.6 that m = S2(d), as desired.
The next lower bound of this section demonstrates that the non-negative hypothesis is crucial. If we drop the non-negativity constraint, then any map cannot satisfy the guarantees promised by Theorem
Theorem 2.9. Let e; be the ith basis vector in Rd. Consider the set S = { U {0} of 2d + 1
vectors. Suppose f S:S S + m be an arbitrary mapping which satisfies
0.9||z vl - ll)(()) - f( S 1.1 olloo Vx, E S,
| + y|l - [1((x)) + f()ll== s C||== ulloo VE
for any C 2 1. Then 2 d
Proof. Suppose for the sake of contradiction that m < d
1. We first show that ((e) = - (-(s)
for all i. Indeed, e; + (-e;) 0 we must have [[f(e)) + f(-e)) = =0 = f(e)) = (--ee)... We also have f() = 0 E I also using the second relation. This means that [[( E [0.9, 1.1] for all by using the first relation with r =e; and y =
For vector v E S, call the indices where I E [0.9, large entries. Our goal is to show that most vectors in need have distinct large entries. This will imply that must be large since [S] is large.
Indeed, if m S d 1, then there must exists some * such that f(e)) and fee) share the same large entry index by Pigeonhole. Then either f(e,) or f(-ez) ffe) also has the opposite sign as the large entry of f(;) So at least in one case, we can find two vectors x, y E such that [I - |l > 2- 0.9 1.8. However, since i + j. we know that || yll = 1, contradicting the first relation. Hence, m 2 d, as desired.
Finally, the last lower bound demonstrates that any map with weaker guarantees than that of The- orem C.2 must map to Ω(s)) dimensions. Note that Theorem C.2 satisfies the hypothesis of the theorem bellow with C = O(1/ log n) for a dataset of n non-negative 8-sparse vectors
Eii en Eie 0, Suppose f S + R. be
Theorem D.I. Suppose 2s and let S an arbitrary mapping which satisfies
(x(()) - f(w)l S || - vlloo Yr S, C| f/11 S llf(x) - f(y)lla Vx
for any C' > Then m 2 Cs..
Proof. By shifting, we can assume f(0) = 0. Let = Ei & and 02 = Ei.+t 6. Then the first relation implies that all coordinates of 01 and v22 are bounded by 1 in absolute value. The second relation them implies that
2Cs < (1)())) f12) < +1/02))) S 2m,
yielding m 2 Cs.
29

---

Published as a conference paper at ICLR 2025
E APPLICATIONS OF OUR NON-NEGATIVE EMBEDDING
We now present applications of our embeddings for sparse vectors for many problems in geometric optimization. We always assume input is dataset X of n non-negative s-sparse vectors in Rd.
E.1 COMPUTING DIAMETER
Our goal is to compute the diameter of the dataset X in Ep norm (see Definition E.1 lemma shows that the diameter is preserved when projecting onto very low dimensions. Vllp
The first
Definition E.1. diameterp maX ||
Lemma E.1. Let f : Rd + p((") mapping given in Definition C.I. Ler X = (f(x) RO(2)) We have
1 x
Pr
Vp, diameter, diameter, (X))
> 0.99.
For the 1x case, we can instead embed to Oss) dimensions.
Proof. Let (z. y) be pair in X that witnesses the diameter. Theorem C.1 implies that for any p. the distance between and y preserved under with probability at least 99%. The proof of the Lo case is the same as Theorem|C.2 the coordinate which witnesses the distance between x and y does not collide with any of the other support elements with constant probability. Furthermore, Theorem also implies that all other distances do not expand under f. This completes the proof.
This implies the following corollary stating that any 'low dimensional' algorithm for computing diameter can used to compute the diameter of after composing with our dimensionality reduction.
Corollary E.2. Given 2 1, consider an algorithm which computes a C-factor approximation of the diameter of any n point dataset in d-dimensions in Q(n, d)C) time. Then there exists an algorithu which computes a C approximation of the diameter correctly with 99% probability of our dataset X in time Q(n, (() + O(ns). For the too case, the corresponding bound Qn, (s), C) + Ons))
Proof. We simply project our dataset X using f as stated Lemma E.1 and apply the algorithm Q in the projected space.
Appealing to existing algorithms on diameter computation implies the following results.
Theorem E.3. Let X be dataset of non-negative s-sparse vectors. We have the following algo- rithms:
1. Using Chan 2018), for any constant integer p. we can compute a 1 + approximation to diameter, of X in time Ó(n/VE ns 2015* (og(1/e))) which is correct with probability 99%.
2. We can exactly compute the diameter of X in to norm in time O(ns). This algorithm can be implemented in stream using O(s) words of memory.
3. We can exactly compute the diameter of X E norm in time (())s, This algorithm can be implemented in stream using (0))) words of memory.
Proof. The first result just follows from appealing to Corollary 4.1 in Chan 2018 which gives an algorithm for computing the diameter in L, low-dimensional spaces, and appropriately plugging in the bounds as specified in Corollary E.2
For the second result, recall folklore streaming algorithm for computing diameter in Ex norm. We have
diameter,,
max dimension
max [Ts X
Di
max dimcnsion
max Ty min 9/: #EX
yEX
30

---

Published as a conference paper at ICLR 2025
Thus, it just suffices to only keep track the maximum and the minimum coordinate along every dimension. Via Lemma E.1 suffices to assume the dimension is only O(s). The non-streaming algorithm simply scans the points along every dimension well.
Finally for the third result, we recall a well known isometric embedding of Ef into lxt for any l 2 1: simply map any x E Rd to Ar E IR2 where A has all possible +1 vectors as rows. Applying this embedding reduces the l case to the loo case addressed above.
E.2 DIMENSIONALITY REDUCTION FOR MAX CUT
We consider the max cut problem defined as follows. Definition E.2. MaxCut, maxsçx ExsSweesss || ylp-
To the best of our knowledge, dimensionality reduction for max cut has been only studied in the & case where its known that (11/²2) dimensions suffice to estimate max cut of an arbitrary sized dataset up to 1 + (only for f2) Lammersen et al. 20099;; Chen et al. (2023).
We show the following dimensionality reduction for max cut the general lp case, where the point set consists of non-negative sparse vectors.
Theorem E.4. Let f: R2 + (((//(()) be the mapping given in Theorem C.1 Let X (f(x) J
}]. For every p 2 1, we have
EE
(X)- Max (M)xC)))X))])) S ((s)
MaxXutt(X)..
Proof. We drop the dependence p for the sake of clarity. Let E be the set of edges that participate in fixed optimal max cut for X. Let MaxCut(X) be the value of the cut given by E in the projected dimension (note that E is deterministic but the value is random since the projection random).
Fix any pair x, y and consider the random variable [lf(z) - fg) We know deterministically [If(x) - fi (v) I < || yyl For non-zero coordinate z; of == y. let t, denote the indicator random variable for the event that does not collide with any of the other non-zero coordinates of By choice of m, know that E[t.] 2 E² since the sparsity of is O(s), as it is the difference two s-sparse vectors. Thus,
(x) f())l 2 (1 - y1
so by Markov's inequality,
0 0 | 011. llf(x)) f()) s =||0 y/1
with probability at least - We have
MaxCut(X) MaxCut(
Σ
[[ll((z) - f(y)llB - -1x-~y10 -
(x.))EE
Σ (x:))ER
O(E) -|x yllp
= 0(E) MaxCut(X),
Now we make two simple observations. First, we always have
MaxCut(X) 2 MaxCut(X),
since MaxCut(X* X) the best cut in the projected space. Secondly, since the value of every cut never expands in the projected dimension due property (3) in Theorem C.I we also have that the value of every cut in the projected space is at most MaxCut(X)) deterministically. In particular, it must also be true that
MaxCut X) 2 MaxCut( X).
In particular, this means that we have
0 < MaxCu((X) - MaxCut(X)) < MaxCut(X) - MaxCut(X),
so the random variable
MaxCut(XX) - MaxCut(X)
is always bounded
by
MaxCut(X) MaxCu((X) which finishes the proof.
31

---

Published as a conference paper at ICLR 2025
E.3 CLUSTERING APPLICATIONS
We consider the (arguably) most well-studied formulations of clustering: k-median, k-means, and k-center. Dimensionality reduction for these problems have been well studied in the E2 case Makarychev et al. (2019). Here we consider dimensionality reduction for general Ep norms, but with restricted set of vectors (non-negative sparse).
We recall their definitions below.
Definition E.3. We are interested in general ly norm formulations of the k-median/centeermeeams. clustering objectives.
Given a dataset X f Ind of n points W.,, the goal is to find partition C = {C1, Co...., Cx} of [n] into k non-empty parts (clusters) to minimize the following:
k-median:
cost(C(x))
E min Σl
us uellp-
u JEC,
k-center: Same k-median, but define the cost
cost(C(X))
min max ||a uz
u, u,ERd jEC:
k-mmaas: Same as k-median, but we instead use the squared distances || uzllz
Note that for these clustering problems, the centers u; do not have to be in X and can be arbitrary points space. That is, once the points are partitioned, we optimize for the choice of centers. Note that even though our initial dataset may satisfy structural properties as sparsity, is it likely that the optimal centers chosen will not. Thus, while our embedding of Theorem C.2 guarantees that & distances between dataset is preserved, there is meaningful notion of what the center is under the embedding. Nevertheless, our embedding implies that the cost of every clustering is preserved up small multiplicative factor.
Theorem E.S. Consider the k-median or k-center problem. Let X be a set of n non-negative 8- sparse vectors in Rdd Let F Rd - O log(n)/e)" be the mapping given in Theorem C.2 and X = (F(x) x DE X). We have
Pr (ost(oss(C(()) (4 =))os(((())) 2 2 2111/polymn).
For k-means, an identical statement as above holds, except we replace 4 with 16.
Proof. Fix a clustering C (partition of the datapoints). The complication arises due the fact that (XX) optimizes for (non-necessarily sparse) centers in IR whereas C(X)) optimizes for cen- ters in the projected space. There may not be an analogue of center chosen in Rd the projected space. To get around this, we show we can simply move the centers to their closest data point in X with small multiplicative loss. The proof proceeds formally as follows.
We first only consider the case of k-median and k-center. Assume that F preserves all pairwise distances between points in X, which holds with probability least - 1/poly(n) and condition on this event. Take any one of the k partitions C of C and consider the best center for this partition in Rdd Now let w' be the closest center to u in its partition C. Moving u to u' will never decrease the cost (by the optimality of u). We claim that it will also never increase the cost by more than factor of 2. Indeed for k-median, the cost increases by a factor of |C] ||u u'Ilp by triangle inequality, which is less than Ejec ||= ullp by the minimiality of u'. Now the sum just the original cost. For k-center similar reasoning holds.
Call such clusterings where the centers are restricted to the dataset points in as basic. The above reasoning implies that given partition C, the cost of the optimum clusterings and the optimum basic clusterings only differ by a multiplicative factor of Of course the same reasoning is also true in the projected dimension. But note that the costs of all basic clusterings are preserved under F, since all pairwise distances are preserved. Thus we have the following chain of inequalities:
co)t(C(X)) basic) s (c)))(((X)) < (()), basic) 2(1 + ))oost(C(XX, basic),
32

---

Published as a conference paper at ICLR 2025
and similarly
2(1 + e)))st(C(XX, basic) Σ 4(1 + =))ott((())) & 4(1 coott(((()) basic).
Adjusting e, altogether, this shows that cost(C((X)) and cost(C(X)) are within a factor of = E of each other. The argument does depend on the choice of C (once we condition on the event that all pairwise distances are preserved). The proof also easily extends to k-means, where the basic clusterings now increase the cost by at most factor of due to the squared triangle inequality.
L
E.4 DISTANCE ESTIMATION
We first define the distance estimation problem.
Definition E.4. In the distance estimation problem. we want to preprocess a dataset X and output a data structure D. Then on any query y, outputs an approximation Exex -
We have the following result.
Theorem E.6. Given dataset X R& of non-negative s-sparse vectors and even integer p. we can compute a data structure D using O(n log(n)ps/E") preprocessing time. For any fixed non-negative s-sparse query y, D(y) computes value satisfying
SE
Σ DEX
1
xEX
with probability 1/poly(n) with query time (log(n))ps/E))
Proof. We will have Ollog n) independent d-variate polynomials Pi... Pollggn). Each P; will output an estimate 4 with the guarantee that
E
4
Σ =
SE
Σ 1
ylp
xEX
which extends to the high-probability guarantee by just taking medians of all the independent esti- mates.
Pi will be constructed by using the 'base' mapping Rdd Rm for (ss/c²) of Theorem
C.I We set Xi (f) x X}, and let Pi()) Exes, || =|lp. Then is simply
(y)).
- Note that each æ E X satisfies - || - yill < e||K vlly (see the proof of Theorem B.4
Finally, repeat this independently for all P. The construction and query times are only dependent on the polynomial evaluation.
Note that each ((mpp) time to construct P and given z, we can compute P(z) in time ((m)) as well. Theorem guarantees the quality of the approximation.
polynomial with the number of monomials bounded by O(mp). takes
F USEFUL INEQUALITIES
Lemma F.1. If X XI...., X, are ii.d. Bernoulli(p) for p 2 E/100 then
Pr Σ
X; tp 2 et < exp (-S((tt))
Proof Sketch. Consider the complement random variables Y, 1 X₁. These are Bernoulli(1 (1-p) and so by standard Chermoff bound,
Pr
Σ Y t(1 - p) 2 Et s exp (-x(())())).
33

---

Published as a conference paper at ICLR 2025
as desired.
Lemma F2. Let 2 E 12 p 2 10 log((d))/, and = E (0,1/10). Then ||=||p E (1==))l21
Proof. Without loss generality, suppose || = | = maxie[d] /z//. We have
d 2 | 2 aa...
Taking 1/p-th powers gives us
d' ///1 ||=|| 2 |21|,
and the lemma follows by noting that d=/r exp (d) /1)p)/ exp(e/10) 1 + O(e).
Lemma F.3. If a, b Rd satisfy la bllco S 8, then ||||| - || - 25 @ovdl|a|22 + 5d.
Proof. Let = b, - aj We know that le S Then b, = a; + c and a - b3 a² (a. + +c)² =
& 20,0 so (a) bit z do + 25 >. |a.| - 20vd|lalla + 5dd
34


Reviews:
[{"review_id": "WeoYLwfFhs", "reviewer": "Reviewer_e6vD", "summary": "The paper studies dimensionality reduction for sparse vectors. Suppose we have a set of s-sparse vectors X in \\R^d (i.e., each vector has s non-zero entries), the goal of dimension reduction is to find a transformation f : \\R^d -> \\R^k, such that k is as small as possible, and || f(x) || \\approx ||x|| for \"most\" x \\in X.\n\nDifferent variants of this basic question are considered:\n- if the norm is \\ell_p and the goal is to exactly preserve the norms of 99% of the vectors, the authors show a lower bound k = \\Omega(s^2). The nice thing here is that it matches the \"trivial\" birthday paradox based embedding. \n- when the norm is \\ell_2 and the goal is approximate preservation but to a \"small enough\" error factor, the authors show that the same lower bound holds.\n- the above two lower bounds are for the case when the embedding function f() is assumed to be linear. The authors extend this result to more general non-linear embeddings (assuming smoothness of derivatives), and then argue that a similar lower bound holds on the embedding dimension.\n\nOn the upper bound side, the authors consider a set of n vectors, each s-sparse, with _non-negative_ entries. Here, they argue that in order to maintain pairwise distances between these vectors, k = O(s \\log n) suffices (with an extra dependence on \\epsilon, which is the parameter measuring the approximation error). The statement is interesting, because (a) it overcomes the upper bound shown in the earlier results, and (b) such embeddings are typically difficult for general \\ell_p norms (e.g., p=1).\n\nThe lower bounds are shown via a nice use of anti-concentration properties of the Gaussian distribution. While not too surprising, it's nice that a simple construction works out. It is nice to see that the lower bound also holds for general smooth embeddings (not just linear). The upper bound is via a non-linear embedding that builds on the birthday construction but with more tricks.", "questions": "- Can the authors say more about whether the known non-linear embeddings (eg., compressed sensing) work for the non-negative vector setting considered in the paper? (will it be that most pairs of distances will be preserved but not all?)\n\n- Please comment on the second point in the weakness above, in case I missed something in the paper.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and the authors do a thorough study of dimension reduction for sparse and non-negative sparse vectors.\n\n- While the proof is not hard, the fact that the lower bound matches the birthday embedding is interesting. It is also interesting that the lower bounds extend to non-linear but smooth embeddings.\n\n- The upper bound also felt interesting, but perhaps the authors can clarify things a bit more (see questions below).", "weaknesses": "- The results are nice, but it does feel like a pure theory paper, raising the question of whether ICLR is the right venue. That said, dimension reduction is ubiquitous in ML, and so I feel it is justified.\n\n- The setting considered in the lower bounds and upper bounds are quite different -- lower bounds work only for linear and smooth embeddings while the upper bound uses a non-linear embedding. So stating the results as a \"separation\" between general and non-negative results does not seem convincing to me. (Of course, there is also the bigger difference that one case considers distances between the vectors, while the other case considers the vectors themselves.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "UhrnUin7uc", "reviewer": "Reviewer_ASUj", "summary": "This paper studies the problem of dimensionality reduction for sparse vectors.\n\nSuppose $x\\in \\mathbb{R}^d$ is an $s$-sparse vector.\nWe would like to map $x$ to an $m$-dimensional vector $f(x)$ such that $\\lVert f(x) - x \\rVert$ is preserved.\nNote that this map can be a nonlinear map.\nOur goal is to minimize $m$.\n\nThis paper provides two main results.\nThe first one is for the general setting.\nThe authors show that $m$ needs to be at least $s^2$ for a class of smooth maps $f$.\n\nThe second result is for vectors with non-negative entries.\nNamely, we further assume that the entries of $x$ are all non-negative.\nThe authors construct a novel map and show that $s$ is at most $s\\log n$ to preserve the pairwise distance among $n$ points.\nAlso, the authors prove the lower bounds in this setting.", "questions": "Line 431: \"... a map (randomized) ...\" $\\to$ \"... a (randomized) map ...\"?\n\nLine 456: \"... (they maybe $0$).\" $\\to$ \"... (they may be $0$).\"\n\n\nLine 842: \"... let $i$ be it's ...\" $\\to$ \"... let $i$ be its ...\"\n\nLine 908: Should it be the second sum (in the expression for $Z^2$ in line 891)?\n\nTheorem E.6: \"datastructure\" $\\to$ \"data structure\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The presentation of this paper is generally clear. \nReaders from different backgrounds should be able to follow the main idea of this paper.\n\n\nFor the second result, the map constructed by the authors seems to be novel and interesting.\nResearchers who work on this area may be able to learn the insight from this construction.", "weaknesses": "Regarding the first result, it seems to be natural that one should expect a lower bound of $s^2$ because of the birthday paradox.\nIndeed, the main analysis of the lower bound is mostly a probability calculation and the construction is based on uniform sampling which is not particularly surprising.\nI am not quite able to see new techniques introduced in this part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "o4UnKhhqfL", "reviewer": "Reviewer_Mwp7", "summary": "The authors focus on the problem of sparse dimensionality reduction in the average case $\\ell_p$ norms, where, instead of preserving distances across a high percentage of problem instances, the goal is to preserve distances for a high percentage of pairs of vectors within each instance.\n\nThey present a bunch of results for this problem, mainly some are:\n\n1. They show that any linear map, resembling the so called Birthday Paradox map if optimal for the case where $p$ is even. They provide lower bounds to match existing $O(s^2)$ upper bounds on the embedding dimension for $s$-sparse vectors. Their hard cases involves distributions where one first samples co ordinates uniformly at random, and then assigns mean 0 i.i.d. Gaussian value to the non zero co ordinates. \n2. They extend this lower bound for weaker guarantees for the case of $\\ell_2$ norms, providing stronger results. These extend to continuous, twice differentiable maps, and compositions of such maps that can be interpreted as an encoder-decoder scheme. \n3. For the case where the entries could be non negative, they show improved upper bounds by showing the existence of a nonlinear map that achieves a reduced embedding dimension. These results are also paired with lower bounds.", "questions": "Have the authors explored separation results between non-i.i.d. maps and linear i.i.d. maps for this problem?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Apart from the interesting hard cases, their results on nonlinear mappings for non negative vectors, which provide guarantees for preserving $\\ell_\\infty$ distances, highlight the importance of moving beyond linear i.i.d. mappings for certain problems. \n\nTheir overall theory results are good and I recommend an accept for this venue.", "weaknesses": "I don't recommend a strong accept mainly because of lack of a cohesive insight across the two main research questions they address -- average case lower bounds for general sparse vectors and improved upper bounds for non negative sparse vectors. \n\nThe paper's array of results could also be supplemented with more insight into the hard distributions (of the type $Unif_{t,r}$) that they constructed. They also mention that Birthday Paradox like maps are folklore, but it would provide more completeness if they referenced mentions or proof of the upper bound. Moreover, their proof techniques might not be highly novel -- for instance the authors ultimately leverage a linear structure of the nonlinear mapping through a Taylor expansion, which is fairly standard. \n\nAs a result, while the overall contributions are good, if there were an option for giving a 7, I would give that. However, I do not consider this work sufficiently non trivial to warrant a strong accept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "k28yohcy4r", "reviewer": "Reviewer_HFgV", "summary": "The paper investigates dimensionality reduction techniques for sparse vectors by addressing two central research questions. It explores average-case guarantees, presenting lower bounds that show that essentially the \"birthday paradox map\" (simply randomly map into the lower dim space with very low chance of coordinate collision) which uses O(s^2) dimension is optimal in many relevant scenarios. In particular, any linear map with similar average-case properties must use Omega(s^2) dimensions; this is then also extended to the case where the map is potentially non-linear but smooth. The authors also propose improved dimensionality reduction for *non-negative* sparse vectors, showing that they can be embedded into fewer dimensions, i.e., O(s log (#vectors) / eps^2) than arbitrary sparse vectors. This shows that non-negativity enables more efficient embeddings, especially in high-dimensional spaces; this is also necessary for smaller embeddings as also shown by the authors. The papers also includes several interesting down-stream applications from optimization.", "questions": "see above", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I really like the paper, although I have to admit not being an expert in the field, so I might over-/underestimate the relevance and the first 9 pages only include high-level exposition with no proofs and I did not have the time to check the proofs in details in the appendix. The results seems to be quite \"complete\" and \"complementary\" in the sense that basically for each relevant case and bound the corresponding lower bound or construction is presented. The results regarding the additional dimension-reduction in the case of non-negative vectors were somewhat surprising. \n\nIt would be great if the paper could give a little bit more intuition why the non-negativity makes such as significant difference. In particular, the authors write that simple translation is not good enough as it might affect sparsity. Intuitively I tend to agree (as this happens to be the case in many similar scenarios). \n\nI think the paper, assuming everything is correct etc, can have quite a few downstream application as dimensionality reduction is at the core of many ML and optimization algorithms.", "weaknesses": "Not much to complain about - my only concern or comment is that the first 9 pages only contain high-level summaries. A little bit more detail and intuition, e.g., for the non-negativity induced improvement would have been nice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)