Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
Authors: Simone Moretti
Paolo Pellizzoni
Francesco Silvestri
Venue: ICML 2025 poster (2025)
Keywords: dimensionality reduction
Johnson-Lindestrauss
complex space
Primary area: theory->everything_else
TL;DR: Dimensionality reduction for dynamically weighted Euclidean norm.

Abstract: The weighted Euclidean norm $||x||_w$ of a vector $x\in \mathbb{R}^d$ with weights  $w\in \mathbb{R}^d$ is the Euclidean norm where the contribution of each dimension is scaled by a given weight. Approaches to dimensionality reduction that satisfy the Johnson–Lindenstrauss (JL) lemma can be easily adapted to the weighted Euclidean distance if weights are known and fixed: it suffices to scale each dimension of the input vectors according to the weights, and then apply any standard approach. However, this is not the case when weights are unknown during the dimensionality reduction or might dynamically change. In this paper, we address this issue by providing a linear function that maps vectors into a smaller complex vector space and allows to retrieve a JL-like estimate for the weighted Euclidean distance once weights are revealed. Our results are based on the decomposition of the complex dimensionality reduction into several Rademacher chaos random variables, which are studied using novel concentration inequalities for sums of independent Rademacher chaoses.

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
Simone Moretti
Paolo Pellizzoni
21
Francesco Silvestri
Abstract
The weighted Euclidean distance a frequently used primi- tive in several learning tasks for improving output quality, as weights can capture the estimated relevance of a feature the output (Nifio-Adan et al., 2021). In the context of LLMs, attention scores are used to weight the relative importance of each component in a sequence relative to the other elements in that sequence (Vaswani et al., 2017), while weighted low- rank approximation used to compress models by taking into account the importance of parameters (Hsu et al., 2022; Woodruff & Yasuda, 2024). In recommendation systems, weights can improve the accuracy of prediction since it can enhance the role of relevant products while reducing the impacts of irrelevant products (Wang et al., 2015; Gu et al., 2016; Yu et al., 2003). Text k-NN classifiers use weights for taking into account the distribution of the terms across classes estimated from training data (Moreo et al., 2020; Bhattacharya et al., 2017). Most algorithmic methods sup- porting these applications assume that weights are known and fixed. However, weights might change over time or be not known at preprocessing time, a setting that we here- inafter refer to as "dynamic weights". Examples include nearest neighbor methods (Indyk & Motwani, 1998) for classification or recommender systems (Baumgärtner et al., 2022), where the relative importance of features might de- pend the type of query at hand. Weights might be esti- mated highly dynamic datasets that require frequent update of the parameters (e.g.. (Banihashem et al., 2024)). Moreover, weights might be user dependent and it might be too expensive to construct indexes for each possible set of weights, as in the aforementioned case of recommendation systems. For this reason, recent works have been addressing dynamic settings, such for weighted Euclidean distance for the near neighbor search problem (Lei et al., 2019; Hu & Li, 2021).
The weighted Euclidean norm | of vec- tor Ied with weights
Rd is the Eu- clidean norm where the contribution of each dimension is scaled by a given weight. Ap- proaches to dimensionality reduction that satisfy the Johnson- Johnson-Lindenseee Lindenstrauss (JL) lemma can be easily adapted to the weighted Euclidean distance if weights are known and fixed: it suffices to scale each dimension of the input vectors accord- ing the weights, and then apply any standard approach. However, this is not the case when weights are unknown during the dimensionality reduction or might dynamically change. In this paper, we address this issue by providing a linear function that maps vectors into smaller complex vector space and allows retrieve JL-like es- timate for the weighted Euclidean distance once weights are revealed. Our results are based on the decomposition of the complex dimensional- ity reduction into several Rademacher chaos ran- dom variables, which are studied using novel con- centration inequalities for sums of independent Rademacher chaoses.
1. Introduction
The weighted Euclidean distance between two vectors is a Euclidean distance where the contribution of each dimen- sion is scaled by given weight representing the relevance of the dimension. Specifically, given vector & gd and weight vector Rdd (with w, 2 0 for all i {1....dl .d),, the weighted norm of & with weights is defined as
The goal of this paper is to investigate the impact of dy- namically weighted distance in dimensionality reduction techniques. Dimensionality reduction methods map high- dimensional vectors into space with lower dimensionality, while keeping some information on the original vectors; the low-dimension vectors reduce communication and storage costs and mitigate the curse of dimensionality in the running time. A well-known result on dimensionality reduction is provided by the Johnson- Lindenstrauss (JL) lemma (John-
w x² The weighted Euclidean distance || E
between two vectors æ, is then defined as || yll
"Equal contribution 'University of Padova, Italy "Max Planck Institute Biochemistry, Germany, Correspondence to: Francesco Silvestri <francesco siranccsco.sslvestrieeee @ut.estrriiuniiiit..........
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Dimensionality Reduction on Complex Spaces with Dynamic Weights
son & Lindenstrauss, 1984): given set X' of vectors in Rd, there exists a linear map g()) that approximately main- tains pairwise squared Euclidean distances; that is, for any
of least square regression (Yang et al., 2015) and low-rank matrix approximation (Ghojogh al., 2021; Cunningham & Ghahramani, 2015).
I, E X, we have that || 2 (19(z) - 1 S e ||2 10-1 -vll.-
Dimensionality reduction under Euclidean distance with dynamic weights can be formalized by the following prob- lem: 1) each vector x E X is mapped into a smaller vector with a linear function g()), obliviously of weights: 2) when weights w are provided, a function p(g(z), w) is applied to compressed vector ((x) to obtain an unbiased estimate of | w. To solve the problem we have to provide function ((x) to map vectors into the smaller space, and function (1)()), w) to recover the weighted norm. To the best of our knowledge, no previous works have addressed this problem.
The JL lemma holds even with weighted Euclidean dis- tance if weights are known beforehand. Consider one of the several linear maps g(x) satisfying the JL lemma, for instance (xx) = Ar where A is the Achlioptas' ma- trix (Achlioptas, 2003) (i.e., each element is random value in (-1, If all input vectors in X' are scaled accord- ing to the given weights w as x' w O x, with @ denot- ing component-wise multiplication, the map g(x²) gives y - ll9(z²) 1l2 S e || - -il where x' is the scaled version of the input vector z E X. However, this method cannot be applied if weights are known only after the dimensionality reduction step, or if weights could dynamically change. Note that naively storing the origi- nal vectors and scaling them once weights are provided would defeat the purpose of using dimensionality reduc- tion. Therefore, one would need to find a dimensionality reduction technique that can reduce vectors obliviously to the weights, and then retrieve (an estimate of) the weighted norm once the weights are available based solely on the reduced vectors.
1.1. Our results
In this paper, we provide the first solution to dimensionality reduction with dynamic weights, We map vectors in X' into a low dimensional complex vector space with a linear map g(x) IRd + C+, for a suitable value k > 0. The map is done before the weights are revealed and it is hence indepne- dent of weights. More specifically, we let g(x) = Ax/// where matrix A is a complex h x d random matrix, where each entry is an independently and identically distributed random variable over (+1, -1, +i, -i], where i is the imag- inary unit (i.e., ;² = 1).. Once the weight vector w is known, we apply a suitable function to the low-dimensional vectors in {g(x)) : x E X} that allows us to estimate the squared weighted Fuclidean norms and the pairwise dis- tances for any pair of vectors in X. Let h(g(z)) w) ((x) @ g(x) @ ((A A) @ w)) with @ denoting the element-wise multiplication. Then, our unbiased estimate of | 1 is given by p(g(z), w) = Re (E Mg((z), w)i). where the subscript is denotes the i-th entry of a vector, and Re (-) is the real part. Note that computing p(:-)) does not require access to the original vector x.
In fact, we observe that there is a simple, but fundamentally flawed, solution to this problem. Indeed, it is enough to ob- serve that the weighted norm is the scalar product between the vector (#Ox)) and (wOw). Then, applying the JL dimen- sionality reduction to the vector (x @ x) yields the reduced vector g'(x) = A() where A is n x k random matrix with entries in 13. Then recalling the results of JL for scalar products, e.g. as shown in (Kaban, 2015), we have that g(()) g' (wv) is an estimator of ||al| that can be com- puted from the reduced vector gxxx) once the weights are revealed. In particular taking k- = D(e-21nn) In()-1)) yields, with probability at least -6, 8,
In the paper, we will show that the expected value of p(g(x), w) is || and provide upper bounds on the er- ror. The following theorem, which is the main result of our paper, states that p(g(z), w) provides a bounded additive error to the weighted norm, akin to the ones obtained for dot products under random projections (Kaban, 2015). More- over, when the vector and weights at hand are such that is bounded by some term A,
g'(x)- g'(w) - | < ||= lul
However, the function g(()) is not linear and it cannot be used for estimating pairwise weighted distances in set of vectors, severely limiting the applicability of the method.
the quantity | 2 || / || one can obtain a multiplicative approximation guarantee as in the JL lemma.
Indeed, the prime application of the linearity of JL maps reducing the time complexity of pairwise distance com- putations (Cunningham & Ghahramani, 2015), which has applications in clustering (Makarychev et al., 2019) and nearest neighbor search (Indyk& & Motwani, 1998; Ghalib et al., 2020), e.g. for recommender systems and classifica- tion. Other examples include compressed sensing (Upad- hyay, 2015), which relies on sparse linear measurements to recover an unknown signal. Finally, the lincarity of JL has been exploited to reduce the computational complexity
Theorem 1.1. Let e, 6 >>> O. Let A be suitable parameter and k 2 Ω (max { A 1311(8/))
Alm(s/b11) }). Then there exists linear function g(z) Rdd - C and an estimator plg(#), w) C* x Rd - IR such that for any given x. w. Rd, with probability at least 1 - 8,
2a
Ip(g(x), w) - ||~|| I < 11
2

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
In parficular, if ||: [| [/ / s A, we get, with prob-
In (Har-Peled & Mahabadi, 2017), the authors have pro- posed variant of the nearest neighhor search problem al- lowing for some coordinates of the dataset to be arbitrarily corrupted or unknown. The goal is to preprocess the in- put set such that, given a query point it is possible to efficiently find a point æ E S such that the distance of the query q to the point x is minimized when removing the noisiest & coordinates (i.e., coordinates are chosen so that deleting them from both vectors minimizes their distance). The paper provides a (1 + appproxximtao to the optimal solution. We observe that in this work the coordinates to be removed are selected by the maximization procedure, and not specified in input.
ability at least 6,
[p(g(z). - -11== < <<11 1|
We observe that the linearity of g(-) allows us to esti- mate pairwise weighted Euclidean distances using the com- pressed vectors, as p(g(2) g(y). w) p(g(x - w) is a unbiased estimator of || yll..
We then extend, in Section 4.4, the previous result by show- ing that when the vectors and w are near-uniformly dis- tributed, we can lower the dimensionality of the reduced vec- tors to θ max { ( In (8/5)
V2, ( In (8/0)"*)) and still obtain the same guarantees. The approach uses sparse block matrix consisting of L submatrices of size k x d/ L, where each submatrix is generated as the afore- mentioned complex matrix A, for a suitable value of L.
Complex numbers have been used for approximately com- puting the permanent of a matrix (Chien et al., 2003), and in data streams to approximately count the number of occur- rences of a given subgraph in graph (Kane et al., 2012). A use of complex numbers similar to our case can be found in (Kane et al., 1), where they estimate the norm in a streaming setting. with 0 < p 2.
The analysis of the aforementioned results leverages the decomposition of the complex dimensionality reduction into
several Rademacher chaos random variables, i.e., sums of products of Rademacher random variables (see Section 2.3 for formal definition). To do so, we develop novel upper bound to tail probabilities for sums of independent Rademacher chaoses, which can be of independent interest.
The JL. lemma has been proved to provide tight bounds (Larsen & Nelson, 2016; 2017), and has been used for sev- eral applications. including differential privacy (Blocki et al., 2012) and clustering (Makarychev et al., 2019).
Finally, Kaski et al. (2025) very recently addressed the prob- lem of developing a generalization of JL for multi-linear dot products, which encompasses weighted norms. Their approach relies on non- non-independent matrices rather than complex numbers to achieve unbiasedness and only consid- ers the case of general vectors. On the other hand, since we focus on the weighted norm, we develop an enhanced tech- nique for near-uniform vectors, which yields better results.
Specifically, we have the following concentration result, which builds on a novel application of Bonami's ' hyper- contractive inequality (Blei & Janson, 2004) to arbitrary Rademacher chaoses, and recent concentration result for sums of independent sub- Weibull random variables (Kuchib- hotla& & Chakrabortty, 2022).
Theorem 1.2. Let S and (5,)i= be k- + independent and identically distributed Rademacher chaoses of order n Let W (S) be the Fuclidean norm of the coefficients in S. Then Vt > 0, Vy 2 3 such that of S 7, there exist constants c1(7), c2()) depending only on y such that
1.3. Outline of the paper
In Section 2, we provide a formal background on the con- cepts we use throughout the paper. In Section 3, we derive the first tail bounds on sums of independent Rademacher chaoses. Our proof starts by generalizing the results of Bonami's hypercontractive inequality (Blei & Janson, 2004) to arbitrary Rademacher chaoses, which is then used to obtain expression for the Orlicz norm of Rademacher chaoses. Using recent results based on such Orlicz norms (Kuchibhotla & Chakrabortty, 2022), we then prove the con- centration result. In Section 4, we prove our main result (Theorem 1.1) and an improvement (Theorem 4.6) under the hypothesis of near-uniform vectors. Our proof is achieved by decomposing the estimator p(g(z), w) into Rademacher chaoses and applying our novel concentration bounds.
W(S) (abNMN++
Pr
S
< 2
1.2. Related work
Recently, (Lei et al., 2019; Hu & Li, 2021) have studied the r-near neighbor search problem under weighted distance with weights provided at query time: given a set S of n vectors, construct data structure that, for any query vector I and weight vector w, returns vector y S such that ||æ - -vllu The papers leverage asymmetrie Local- ity Sensitive Hashing approach that uses a dimensionality expansion (from dRd to 2d2 built with trigonometric func- tions. The result in (Lei et al., 2019) focuses on the weighted Euclidean distance. while the one in (Hu & Li, 2021) on the weighted Manhattan distance.
All the formal proofs of lemmas and theorems, if not present in the main paper, are reported in the appendix.
3

---

Dimensionality Reduction on Complex Spaces with Dynamic Weights
2. Preliminaries
cients (( E R. is defined as:
We now provide an overview of the concepts and techniques used prove our results.
Σ
a(taandg) X11 ... Xz,-
2.1. Basic concepts
The g-norm of the random variable S is defined as ||5||, E [|S| We define a function W on the set of all Rademacher chaoses as W(S) = VEier,.. af "immnny i.e. the Euclidean norm of the coefficients.
Given a value > 0, the p-norm of a vector x E Rdd
1/P Given weight is defined as ||>||p- (E=)
vector w in R4, the weighted p-norm of is |<]|b
Bonami's hypercontractive inequality (Blei & Janson, 2004) provides bound for ||S||l when the sum is taken over se- quences (i1...., 87) such that i1 < i2 <... < <.n, possibly after a renaming of the indexes.
(Ein uoll (1:1) norm and we simply denote the weighted norms of ||=|||.
1/p When p = 2. we get the Euclidean
Theorem 2.4 ((lli & Janson, 2004)). Let S be Rademacher chaos of the form S
We state some commonly known incqualities that will be used in the subsequent sections.
Σ Lish Eishe En (1 ... Then, ||5||, S
Lemma 2.1 CCauchy-Schward ineq.). For any x, 2.yC E Rdd (2 i-1 w²¹ ||x l/2 11v112.
(q 1)-1)//21)) = 11-1))/2
( 1 T:tss) S 1 u²
Note that in general, for Rademacher chaoses with sums over Ln Bonami's hypercontractive inequality does not hold. In Section 3.1 we show how to generalize the result to arbitrary Rademacher chaoses.
Lemma 2.2 (Monotonicity of p-norm). For any E Rd and any 0 p 9 < +oo, we have ||=||,, S ||=||p
Lemma 2.3. For any p, Q 2 1 and any y E Rd, we have D | Ply < > 12 12l12
2.4. Orlicz norms and sub-Weibuld random variables
2.2. Johnson--Lindenstrane (JI.) lemma
We introduce some results on the concentration of sums of independent heavy-tailed distributions. We recall the defini- tion of Orlicz norms for random variables (Kuchibhotla & Chakrabortty, 2022).
Let X' = (.I,... J be a set of n vectors in d > 0 dimensions. For any E > O, the lemma (Johnson & Lindenstrauss, 1984) claims that, if h = a (s-² log ni), there exists linear function g IR R* that maintains pairwise distances up to multiplicative emror e with high probability. That is, for any x, y E X, we have
Definition 2.5. Let g [0) + [0, oo) be a non- decreasing function with g(0) = O. The g-Orlicz norm of a real-valued random variable X is ||X|| = inf {1) > 0: IE [(((X(/))) s 11.
(1= v1l < [1((z) - 2()) < (1 + e) || vll-
Note that, despite the name, if g is not convex, the function II-I1, is not norm. However, the norm properties are not needed in the following derivations.
Equivalently, the JL lemma claims the existence of linear map that approximately maintains Euclidean norms. There are several constructions for s(-), for instance, those in (Achlioptas, 2003). Let g(x) = Ax for suitable k-d matrix: if k = θ (e (e-210pp log n)) and each entry of A is an independent and even distributed Rademacher random variable {-1, 1]. then satisfies the JI. lemma with high probability. The property holds even if an entry of A is O with probability 2/3 and in { (-1, 1} otherwise.
Two well-known spacial cases of g are 1/2 = exp(x²) - 1 and Φ = exp(x) - 1. When a random variable has finite Orlicz norm is called sub- Gaussian and when it has finite -Orlicz norm it is called sub-exponential. The following definition (Kuchibhotla & Chakrabortty, 2022) generalizes such random variables.
Definition 2.6. A random variable X is said to be sub- Weibull of order a > 0 if |[]]e < 0o where (x) = exp(x*)) 1
2.3. Rademacher chaos
We introduce here some results on Rademacher chaos. Let In,. C n).. and let In {(i1...., .,)) iz E fi....n..2 # in if F k- be set of ordered sequences of distinct values from [1....,n]: when is clear from the context, we drop the subscript n.
The following theorem, proved in (Kuchibhotla & Chakrabortty, 2022) (Theorem 3.1), states concentration result for sums of independent sub- Weibull random vari- ables. We report a bound for heavy-tailed (a < 1) variables.
Let XI....X, be n independent Rademacher random vari- ables. Then, a Rademacher chaos of order 7, with coeffi-
Theorem 2.7 (KKuchibholla & Chakrabortty, 2022)). Let X1y..., X2 be i.i.d. mean zero random variables with
4

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
[xill < 00 for some a (0,1). Then 1I
Finally, we can exploit the previous concentration result to provide an upper bound on the - norm for Rademacher chaos.
k
Pr Σ
Xi 1x220mm Ca
Ca 2 S 2
Lemma 3.3. Let S be Rademacher chaos of order y 2.
Let S 2/7 and Va exp(x=)) - 1. Then
with
C. = 8222
|| S ce(e² + 11 VSI((S).
3. Concentration of sums of Rademacher chaoses
Proof. From the definition of Orlicz norm we have || = inf (1 > 0: E [aa (IS1/n)] - 1}. Then, apply-
In this section, we provide the first concentration results for sums of independent Rademacher chaoses.
ing Lemma 3.2 with >' = 2/ox 2 7, we get
E [ ([S)))]
Pr [bb. (151/v) > a] de
3.1. Tail bounds and Orlicz norms of arbitrary Rademacher chaoses
1 Pr [is] > n(l((x + 1) 1)m de
We generalize the bound given by Bonami's inequality for arbitrary Rademacher chaoses. Let G. be the set of per- mutations over y elements, i.e. G. = Sym (9mm((1....,7)))) 7)). Then, Vo E Gzy let 17 = ((i,....,,,) (1....n) nJ, io(s) < <()(()) j < kj. Then we can express
s 6² / exp (-(eV//IW(S)) In(x)( de
= è² ( (or + 1) (oSsivie) dr
in E
e²
S=
Σ
al Xs, Xi,
(cVTir(S)) ) -1
(
Σ
Σ
" (i ......., ..,,,,, = Σ S
Then, if n 2 e(6² + 1)%av/s we have that E [[([(///)]] 1. Therefore, we have that || e(e² + 1))-v77W((S)
oEG, SET
IEG.
Intuitively, we can decompose the chaos S into a collection of chaoses St: in each 5a, tuples be sorted using per- mutation a and then Bonami's inequality can be applied. Indeed, Bonami's 's hypercontractive inequality (Blei & Jan- son, 2004) implies that, Vo Vig 2 2,
3.2. Proof of Theorem 1.2
Having obtained a bound on the Orlicz norm for a Rademacher chaos, we can now prove the first of our main results, a concentration inequality for sums of independent Rademacher chaoses.
|| 11, s (g- - 1) 12
1/2
= (g - 1)7/2
Σ (E1,
Theorem 1.2. Let S and {S:)i=1,....k be + independent and identically distributed Rademacher chaoses of order Y'. Then Vt > 0, Vy 2 3 such that 7' S % there exist constants ei c2))) depending only on 7 such that
Using this decomposition, we obtain a bound on the g-norm of a general Rademacher chaos.
Lemma 3.1. Let S = Eoeg, S be a Rademacher chaos of order 7 2. Then, ||S||, S (9-11)7 ()
Pr Σ S. > W(S) (a(t))VaV
$ <e
We then have the following concentration result.
Proof. By setting a = 2/7 S 2/7/ in Lemma 3.3, we get that || I e(c² + 1) VY!W(() < e(e² +
Lemma 3.2. Let S be Rademacher chaos of order y 2 2. Then for any 7 2 7 and > we have:
Then, by defining c1(7) e(e² +
Pr Pr||S| > 1 < a exp (-le 2//1
1) VrCyy, and (2(7) = c(e² + 1) 1/2 / we
get:
Proof sketch. We obtain the bound by applying Markov's inequality and Lemma 3.1 to obtain
h
> W(S) (o()))VTV+++aaa
Pr
S
l=1
Pr > 1 < E [| 4 = ||S||
$ Pr
Σ Sc
> C1411111l (V
and set 9 appropriately.
5

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Since E [S.] = 0 for any Rademacher chaos and by applying Theorem 2.7 with = 2/7, have that the right term of the previous inequality can be upper bounded as:
now the expectation of the term E Ais. Ai.jo As. for given value i. Since E [Ac,)] = E [A = E [ = for any i,j and the terms in A are independent, we have that E [A Ar.jo A =111 if ji j2 ja. and 0 otherwise.
Consider
Pr
Σ S. (=1
> C2t, |iS 2/
20
Then, we get:
The theorem then follows.
[h(g(z)),))))
Σ E [Aisr Alss A 23 "h
Jandana Is.d
The above theorem provides the first tail bound for sums of independent Rademacher chaoses. The following corollary rephrases the tail bound by splitting it into a sub-Gaussian tail for small deviations and a heavy tail for large deviations.
=
Σ 5 23 = || 1| /k.
The theorem then follows from the linearity of the sum and of the Re (-) function.
Corollary 3.4. Let (S:)i=1....k be sequence of k inde- pendent and identically distributed Rademacher chaoses of order y. Then by 2 3 such that o' S % there exist constants ei (2)) depending only on 7 such that
4.2. Results in high probability
We now prove, using as the main tool the newly developed Theorem 1.2, that the estimator for the weighted norm is concentrated around its mean with high probability. In particular, the concentration depends on k, the output space dimension. The concentration bounds then allow to choose k depending on the desired accuracy of the estimate.
2exp
401(7) ()5())((5))
e) ()
if(t) otherwise
Pr
S
> t
S
4/1
2exp
- W(S)
with (1) the event: 0 <<t<> 2
c1(7) c2(7)
Since the results of Theorem 1.2 apply only to pairwise distinct indices, we split p(g(z),
= Σ Re (h,(g(v)) w)?) into 4 sums, each over a set of pairwise distinct indices, and bound each term individu- ally. Here we recall that I = {l....,d} dd7 and L' = {Uh,...., ..)) Ind : ip F ig 4p,q E (1.....)) 7.P + g).
4. Complex dimensionality reduction
In this section, we analyze the properties of the dimension- ality reduction onto the complex vector space described in the introduction. We recall that A E Ckxd denotes a random matrix where each entry in an independent and identically distributed random variable in -1,-1,,, -i). and we define g(x) Ax/VR for any x E Rd. Let h(g(()) w) = g(x) @ g(z) O ((A O A) O w)) and p(g(z), w) = Re (Ein h(g(z), w): be our estimate of
k --p(((x), w) = =Σ Σ
Re (ris Aiiz æz 23,
i=1 indasaels,a
Σ
Σ
Re (Aud Anat Al.ss) In x.s w3,
|| where @ represents the element- wise multiplication. Although (I)())), w) is expressed as a function of x, it is computed from the reduced vector g(r)..
Σ
Σ
Re (A Alizz) az 22
21-22
4.1. Results in expectation
Σ
Σ
Re (A A2,))) و 3
We first show that the expected value of our estimator P(g(z), w) corresponds to the weighted norm.
1= 21
Theorem 4.1. For any x, w E Rdd, we have that Elo(g(x), w]] || 2 T...
1=1
= H1 + H + H + +
Proof. By the definition of h(g(z), w). for any e {1....k k}} we get:
Remark. might be tempting to simply use a Khintchine- like inequality (Haagerup & Musat, 2007), such as in Kane et al. (2011, Lemma 4), to directly estimate kt p((((z), w) using Aj, A,, A3, as the random variables and 2y Jiz " as their respective weights. This will however fail because the random variables are not independent. For this reason, we resort to Theorem 1.2 and Bonami's 's hypercontractive inequality to bound the tails of the Rademacher chaos.
2
d
h((()), w); = k1
Σ
Acjii
Σ
j=1
=
Σ
And 2 22
(l
6

---

Dimensionality Reduction on Complex Spaces with Dynamic Weights
Note that each A can be written s(1 (1--++ife (( +2) with and independent Rademacher random variables.
Instead, for the long tail part of the bound described by Lemma 4.3, we take ho = cA In(8/8)2 Both cases yield Pr [I((o(x), w)
We then bound the tail probabilities of the individual terms He, L = 1, 3 by expanding them into sums of Rademacher chaoses and using Theorem 1.2.
| 1 5.
As the failure probability decreases by k, taking k 2 max { {o78² A (n(8/5) proof.
d C28 In(8//) completes the
In particular, we decompose each Hy as a sum of & inde- pendent terms He and we show that W W(H,,)?? for any i E f1....k) k), can be upper bounded by [| |1=1
Finally, we restate the above theorem to prove that the pro- posed reduction maintains pairwise distances in a set S of n vectors and for a set of weights W with a bounded rel- ative error. We remark that, thanks to the linearity of g. p(g(1 y), w) can be computed from the reduced vector g(x) and g(y) as p(g(3 y), w) = p(g(x) g(v), w).
We report such bounds the Appendix, and provide here a bound on / H1 + H2 H3. which is obtained via union bound over the three terms. In what follows, let <1 and 02 be the constants of Theorem 1.2 for 4, and consequently (tt) = avviv + ogt
Lemma 4.2. We have that Pr 8c- 41 > 0.
[IFT]] > 4 | |1011 F(O) x
Corollary 4.4. Let = {.15..., Fn). 24 E TRd be a dataset of n vectors. Let W C Rd be the set of the weights of interest, with [W| O (n). For any given e O and k > cmmxx A e"
We can now use the previous concentration result for H to obtain a tail probability bound for the error lp(g(z). || incurred by the estimator.
where is uni- versal constant, we have with high probability that, for any N. y E &and
A2In(am)
A Aln(sn)] }
and w E W:
Lemma 4.3. For any given T, E Rd, we have
|0(((x - y), w) - || vll < (| x 01///4
Pr [IP(O()), w) - ||0| t)
Proof. suffices to apply Theorem 1.1 with x' = x and
8 8exp
-k (01)1111=113)
ift
8 = 1/ |[IW]n?). The claim follows by a union bound.
8 8exp
-V
otherwise
/ozil
4.3. Discussion of results
with (1) the event: 0 <t
< ci
2
1/88
| k-V
We briefly discuss our results. We note that obtaining mul- tiplicative error guarantee on the estimate of the weighted norm || using the dimensionality reduction given in Equation I, which does not maintain linearity and therefore cannot be used to estimate weighted distances, requires the quantity (||=) (|w/(/// ||=]| to be bounded. In particular, if k = @((A==)²) and max (I|= ||w /3)/ ||=||e < A, one obtains an e multiplicative error guarantee. This bound- edness requirement is intuitively required by the fact that the vectors @ x and O could be orthogonal, and ||=| could therefore be O. Similar results are obtained for estimating dot products under JL projections (Kaban, 2015).
We then prove our main result Theorem 1.1. In particular, we obtain an additive error bound akin to the ones obtained for dot products under random projections (Kaban, 2015), which can be then refined to multiplicative error by rescal- ing the accuracy parameter E.
Theorem 1.1. Let 0 >>>00000000 O. Lei A be suitable parameter A 1m18(8/6)
and k 2 22 ( maxx|
Alm(s/6[²] }). Then there exists linear function g(x)= Rd + Ck and an estimator p(g(x), w) : C**, x R2d - TK. such that for any given a, w E IRd with probability at least - 8,
According to Theorem 1.1, our novel complex dimen- sionality reduction technique, which instead guarantees linearity on x and can therefore be applied compute weighted distances (see Corollary 4.4), has a similar bound- edness requirement. Indeed, if k = (((A/))²) and max,. (1 ||w]l3// ||=|| < A, one obtains é multi- plicative error guarantee. The dependence on the 2-norm instead of the 4-norm of slightly weakens the results. Indeed, we note that || 2 || (Lemma 2.2), and there- fore our multiplicative error guarantee is worse than the non-linear method given by Equation 1. On one end of the spectrum, w has a single non-zero entry, and h: O(2?)
(p(g(x), | < E 2|lm| ||=12// /A.
In particular, if [|= 2/ || ||=|| < A. we get, with prob-
ability at least - 5.
(p(g()).w) - || < 1|
Proof sketch. We set t = e || ||=/1/// /A. For the Gaus- sian tail case of the bound described by Lemma 4.3, we take k - In(//5).
7

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
has to be (max, [| ming [m,]*)) to guarantee an e- approximation. At the other end of the spectrum, is near-uniform (e.g., all the entries are within factor Q and k = ) has to be ((max [|=) = ((d) to guarantee an e-approximation. Nonetheless, for sparse weights such that the weighted norm is nonzero, the method yields a valid dimensionality reduction technique.
We can then factorize H, which includes a sum over 7 into three sums of Rademacher chaoses H1, H2 and H3, as done in Section 4. Here, the main difference is that the sum that composes H1 is over k L independent chaoses H1,,, These are not all identically distributed, but rather divided into L blocks of k identically distributed chaoses each. The same holds for H2 and H3-
We observe that in the case where the weights w are close to 1 (i.e., a small re-weighting of all the dimensions), the results of Theorem 1.1 yield no dimensionality reduction. We address this particular case in the following section.
In particular, we obtain that for chaoses in the é-th block, they satisfy ((H1,,,)) I || |l /k I
<3/a I ||=/1// (k...1
Then, by following a derivation akin the one in the previ- ous section, which is reported in the appendix for the sake of brevity, we obtain the following result.
4.4. Improved results for near-uniform vectors
We now deal with the case where the entries of both the x's and w's are neaf-uniform
Lemma 4.5. For any given x, w E IRd, we have Vt > 0
Pr [I((())) w)
| > t]
A uniform vector is a vector where all entries are the same. We define a (block) near-uniform vector as a relaxation of this condition, where splitting the vector into contiguous parts results in sub-vectors with roughly the same norm. More formally, let S L < d, and let di,..., dz such that E d. Let then (f) E Rdd, f= 1...., L be such that == (x(")) ... [,x) with denoting concatenation. The same holds for w. We suppose that ||~(0 1|2 S < 1| /
8exp
-ci
S maxx
8 exx
(-Vkea
(1 Vt)
1.14
with 01 and 02 appropriate constants.
In turn, setting k and L carefully, we obtain result akin to Theorem 1.1.
and |0 = c [| /L. which holds, c.g., if all the entries are one within a factor ( from any other one.
Theorem 4.6. Let e, > O. Let e be a suitable universal
constant. Let L and be positive integers such that k Z 1m(8/8)) Aln(8/a1²
A Leea
We will apply the dimensionality reduction each of the sliced vectors individually, and then combine the estimates to obtain the final estimate for the weighted norm. We then have that our reduced vector is stored as g(z) = (zx))
L9 j Then there exists a linear function g(x) : Rdd + CC-L and an estimator p(g(z), w)
cmax
Cl Bdd + R such that for any given I, w E Rd, with probability at least 1- 5,
f = 1,...,,A L). with each (5) a function as in Section 4, defined with output dimension & and pairwise indepen-
(p(g()), w) - ||:|| [ << <<11<1 1 /A.
dent matrices A Each of such L matrices is a com- plex k x de random matrix, where each entry is an inde- pendently and identically distributed random variable over {+1,-1, +i, -i}. Therefore, we have that g(x) can be stored with k L complex numbers, i.c., g(x) E C We observe that g(x) consists of a matrix-vector multiplication with a sparse block matrix A, made of é submatrices of size k x d/E and where each submatrix is generated as the complex matrix described in the previous sections.
In particular, if ||11|| ||u / || S A we get, with prob- ability at least 1 - 8.
(1- |0 < p(g(z), w) < (1 + ||=|2
We remark that, when the partition dj, dr is fixed for all vectors x E X, the function I is still linear, the dimen- sionality reduction maintains pairwise distances in a set of vectors X.
Let p(o(z), w) = -k=r (x()), (f))), with p defined as in Section 4. We can rewrite 5 as follows:
4.5. Discussion of results for near-uniform vectors
In the case of near-uniform vectors, the results of Theo- rem 4.6 provide a significant improvement over the results of Theorem 1.1. Indeed, the balanced distribution across the entries of the vectors allows for more efficient dimensional- ity reduction via independent projections on the partitioned components of the vectors.
P(O()) w) = Σ (o (, (0)
1 4
29 12 (w0
1 00 2
Σ
Re (1 A/0 (4(00 (4
b
1=1 51.d2.3EE/9.d to
H
Σ
20000 1000
= 1|
In particular, the output dimension k L is decreasing in I. Therefore, if the vectors x and w are near-unifore for
8

---

Dimensionality Reduction on Complex Spaces with Dynamic Weights
large values of L, it is beneficial to set k to be as small as possible, i.e., setting k- 1, and
position into L sub-vectors almost closes the gap with the non-linear method, argued in Section 4.5.
L 2 emax (m (4/2)** In (8/0)
5. Discussion and Conclusions
In this paper, we provided the first dimensionality reduction techniques that are able to cope with dynamically-weightee Euclidean distances, as well as novel concentration inequal- ities for sums of independent Rademacher chaoses.
In this case, the dependency of the output dimension on A is lowered from up to (()²) of the original technique, as discussed in Section 4.3, to only ((A). In fact, we suppose that there exists some Ç >> such that all entries of w lie in the interval [1/VC. (i.e. no two entries of can be weighted arbitrarily differently), Then, we have <vd and ||= 2 1/c 1<12211. Thus, setting A A= ==²vd = (dd/2)) ensures that || ||0l22 /1==| < A. This means that to obtain multiplicative e-approximation to ||= the dimension k- = ((A) of the reduced vectors has to be only (dd+)).
An interesting open question for future work is to provide fast method for dimensionality reductions in the com- plex vector space similar to the Fast JL transform (Ailon & Chazelle, 2009). We furthermore conjecture that the com- plex map that we provide here admits a generalization to the estimation of arbitrary (weighted) Lp norms, Indeed, let h - Σn....,, II Aj. If A is a uniform on the p-th roots of 1, we have that E[L A = 1 if all the ji 's are the same, and O otherwise. Therefore, E(h] = =| However, the variance of the estimator grows with p. and novel approaches should be developed in order reduce this growth.
that || 1
However, the technique to partition the vectors into L smaller independent vectors guarantees a reduction in the dimensionality of the reduced vector only if the input vec- tors are guaranteed to be near-uniform. This is indeed reasonable assumption on the weight vectors w. as one can expect to rescale the importance of each dimension just by a constant factor. On the other hand, to guarantee the near- uniformity condition on the input vectors x'', one must have some prior knowledge on the data-generating distribution. We observe that, by bounding the maximum entry of the input and weight vectors, a random permutation of the di- mension can provide near-uniform distribution with high probability. Each entry is, e.g., uniformly distributed, one can get probabilistic guarantees via Bernstein's 's inequality.
We envision that an interesting research direction is the application of our techniques in downstream applications. For example, in machine learning, the weighted distance, phrased as the Mahalanobis distance with diagonal covari- ance matrix, is used as time-efficient alternative to dy- namic time warping (Prekopesák & Lemire, 2010), and as substitute for the Euclidean distance in RBF-like ker- nels (Abe, 2005; Kamada & Abe, 2006). These methods could then benefit from our techniques. We believe that our method might be of interest also in the weighted least squares problem (Golub & Van Loan, 2013, Chapter 5), which provides robust estimators in the presence of uneven reliability in the measurement (Fox, 2015). Here, given data matrix X Randd an observation vector y E T and weight vector E I (with w; 2 0 for all i), the goal is to find 0 E Idd that minimizes the weighted residual norm || |X yl = > wf
Finally, we observe that the sparse block structure of the linear map allows the use of hardware accelerators for matrix multiplication (e.g., Google TPU, Nvidia TC) for further speeding up the computation. We leave the development of improvements to the dimensionality of the reduced vectors via partitioning strategies under weaker guarantees on the r's to future work.
wxxTTT 0 - yr JI. maps have been used to reduce the complexity of ordinary least squares (Yang et al., 2015), and we envision that our technique could be used in a similar fashion for weighted least squares under dynamic weights. Finally, we believe that our constructions can be of interest for as it might allow the release of datasets that allow users to detect if there are near points within the desired weighted norms without releasing the details of the vector, similar to what done in Blocki et al. (2012) for JL..
i=1
4.6. Experimental evaluation
In Appendix B, we report the results of proof-of-concept experimental evaluation of our techniques. In particular, the experiments highlight the significant reduction of the variance of the estimator when using the sparse block ma- trices. Moreover, the experimental results showease the applicability of the method on sparse vectors, as discussed in Section 4.3, as well as the poor quality of the estimate for near-unifomm vectors for the method described in The- orem 1 1.2, suggesting that the probabilistic analysis of the method is tight. Finally, from the experiments, we indeed see a gap in the quality of the estimate between the lin- car and nonlinear method by Kaban (2015), as argued in Section 4.3. Interestingly, the sparse map with the decom-
similarity search,
Acknowledgments
This work was supported in part by MUR PRIN 20174LF3T8 AHeAD project, by MUR PNRR CN00000013 National Center for HPC, Big Data

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
and Quantum Computing, by Uni-Impresa Big-Mobility project, and by Marsden Fund (MFP-UOA2226)..
Fox, J. Applied Regression Analysis and Generalized Linear Models. SAGE Publications, 2015.
Ghalib, A., Jessup, T. D., Johnson, J., and Monemian, Clustering and classification to evaluate data reduction via johnson-lindenstrauss. transform. In Advances in In- formation and Communication, pp. 190-209, 2020.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Ghojogh, B., Ghodsi, A., Karray, F., and Crowley, M. Johnson-lindenstrauss lemma, linear and nonlinear ran- dom projections, random fourier features, and random kitchen sinks: Tutorial and survey, 2021.
References
Abe, S. Training of support vector machines with maha- lanobis kernels. In Lecture Notes in Computer Science, pp. 750-750, 08 2005.
Golub, G. and Van Loan, C. F. Matrix Computations 4th Edition. Johns Hopkins University Press, 2013.
Gu, Y., Zhao, B., Hardtke, D., and Sun, Y. Learning global term weights for content- recommender systems. In Proc. 25th ACM International Conference on World Wide Web (WWW), pp. 391-400, 2016.
Achlioptas, D. Database-frient ftiendll random projections: Johnson-lindenstraass with binary coins. Journal of Com- puter and System Sciences, 66(4):671-687, 2003.
Ailon, N. and Chazelle, B. The fast johnson lindenstin transform and approximate nearest neighbors. SIAM J. Comput., (9(1):302-322 2009.
Haagerup, U. and Musat, M. On the best constants in noncommutative khintchine-type inequalities. Journal of Functional Analysis, 250(2):588-66)) -224, 2007.
Banihashem, K., Hajiaghayi, M., Kowalski, D. R., Olkowski, J., and Springer, M. Dynamic metric em- bedding into ip space. In ICML, 2024.
Har-Peled. S. and Mahabadi, S. Proximity in the age of distraction: Robust approximate nearest neighbor search. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 1-15. Society for Industrial and Applied Mathematics, 2017.
Baumgärtner, T., Ribeiro, I.. R., Reimers, N., and Gurevych, I. Incorporating relevance feedback for information--eeeingg retrieval using few-shot document re-ranking- In Proceedings of the Conference Em- pirical Methods in Natural Language Processing, pp- 8988-9005, 2022.
Hsu, Y.C.., Hua, T., Chang, S., Lou, Q. Shen, Y., and Jin, H. Language model compression with weighted low-rank factorization. In ICLR, 2022.
Hu, H. and Li, J. Sublinear time nearest neighbor search over generalized weighted manhattan distance. CoRR, abs/2104.04902, 2021.
Bhattacharya, G., Ghosh, K., and Chowdhury, A. Granger causality driven AHP for feature weighted knn. Patlern Recognit., 06:425-4366 2017.
Indyk, P. and Motwani. R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Pro- ceedings of the ACM Symposium Theory of Computing (STOC), pp. 604-613, New York, NY, USA, 1998.
Blei, R. and Janson, S. Rademacher chaos: tail estimates versus limit theorems. Arkiv för Matematik, 42(1):13 29, 2004.
Blocki, J., Blum, A., Datta, A., and Sheffet, O. The johnson- lindenstrauss transform itself preserves differential pri- vacy. 2012 IEEE 53rd Annual Symposium on Founda- fions of Computer Science, pp. 410-419 2012.
Johnson, W. and Lindenstrauss, J. Extensions of lipschitz maps into hilbert space. Contemporary Mathematics, 26: 16:1892006, 01 1984.
Kaban, A. Improved bounds on the dot product under ran- dom projection and random sign projection. In Proceed- ings of the ACM International Conference on Knowledge Discovery and Data Mining (KDD), pp. 487-496, 2015.
Chien, S., Rasmussen, L., and Sinclair, A. Clifford algebras and approximating the permanent. Journal of Computer and System Sciences, 67(2):263-290, 2003.
Cunningham, J. P. and Ghahramani, Z. Linear dimensional- ity reduction: Survey, insights, and generalizations. Jour- nal of Machine Learning Research, 16(89):2859-290M 2015.
Kamada, Y. and Abe, Support vector regression using ma- halanobis kernels. In Lecture Notes in Computer Science, volume 4087, 08 2006.
10

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Kane, D. M., Nelson, J., Porat, E., and Woodruff, D. Fast moment estimation in data streams in optimal space. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 745-754, 2011.
ACM Symposium Theory of Computing (STOC), pp. 1027-1038, 2019.
Moreo, A., Esuli, A., and Sebastiani, F. Learning to weight for text classification. IEEE Trans. on Knowl. and Data Eng. 32(2):02-3116, 2020.
Kane, D. M., Mehlhorn, K., Sauerwald, T., and Sun, H. Counting arbitrary subgraphs in data streams. In Czumaj, A., Mchlhorn, K., Pitts, A., and Wattenhofer, R. (eds.), Automata, Languages, and Programming, pp. 598 609, 2012.
Ndn, I., Manjarres, D., Landa-Torres, I,, and Portillo, Feature weighting methods: A review. Expert Systems with Applications, 184:1 15424, 2021.
Prekopesák, 7. and Lemire, D. Time series classification by class-based mahalanobis distances. Computing Research Repository CORR, 01 2010.
Kaski, P., Mannila, H., and Matakos, A. A multilinear laanson-lindenstrausss transform. In Symposium Sim- plicity in Algorithms (SOSA), pp. 108-118, 2025.
Upadhyay, J.
Randomness efficient fast-johnson- lindenstrauss transform with applications in differential privacy and compressed sensing. 2015.
Kuchibhotla, A. K. and Chakrabortty, A. Moving beyond sub- Sub-Gaussianity in ligh-dimensional statistics: applica- tions in covariance estimation and linear regression. In- formation and Inference, (1(4): 1000::189-15559 1456, 2022.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In NeurlPS, pp. 6000-6010, 2017.
Larsen, K. G. and Nelson, J. The johnson- lindenstraus lemma is optimal for linear dimensionality reduction. In International Colloquium on Automata, Languages, and Programming (ICALP), volume 55, pp. 82:1-82:11 2016.
Wang, H., Wang, N., and Yeung, D. Collaborative deep learning for recommender systems. In Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1235-1244, 2015.
Larsen, K. G. and Nelson, J. Optimality of the johnson- lindenstrauss lemma. In Symposium Foundations of Computer Science (FOCS), pp. 633-638, 2017.
Woodruff, D. P. and Yasuda, T. Reweighted solutions for weighted low rank approximation. In JCML, 2024.
Lei, Y., Huang, Q., Kankanhalli, M. S., and Tung, A. K. H. Sublinear time nearest neighbor search over generalized weighted space. In /CML, volume 97, pp. 3773-3781, 2019.
Yang, T., Zhang, L., Lin, Q. and Jin, R. Fast sparse least- squares regression with non-asymptotic guarantees, 2015.
Yu, K., Xu, X., Ester, M., and Kriegel, H. Feature weight- ing and instance selection for collaborative filtering: An information-theoree approach. Knowl. Inf. Syst., 5(2): 201-224, 2003.
Makarychev, K., Makarychev, Y., and Razenshteyn, Performance of Maansson-lindestrannt transform for k- means and k-medians clustering. In Proceedings of the

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Appendix
A. Missing proofs
A.I. Section
Lemma 2.2. For any x E Rd and any 0 < < q < +00, we have ||>||, S ||>||
Proof. If x 0 the claim holds trivially. Else, yi = |z:1/ ||0||1 S Then we have
d
d
|<=1|p"
p
P
Ue
P |0
wil
|| = |1:11, Σ a
|
1|=1|²-
Lemma 2.3. For any p. 2 and any z, y E R., we have Σiz
lag11 S ||=|| 13
Proof. By applying Lemmas 2.1 and 2.2, we get:
d
1/2
d
1/2
9
<
Σ
Pp
Σ
1/
22
S |1:11 11v112, S ||0| 1vl1
1=1
1=1
A.2. Section 3
Lemma 3.1. Let S= =EEee S" be a Rademacher chaos of order 2 2. Then, ||5||, S (q (1))
Proof. Let S W2 = ||5 Yo and S = W(S)² = Eo S We have that:
5
VS- - -V80)² 2
Σ Σ
S -" - 27
52 Σ VS'S oEG, PEGn
GGG, PEG,
GG PEG,
oEG,
2
27 oEG,
Σ
5
Σ aEG,
S'
This implies that V 2 Eoec, V and thus VTI((S) 2 Eoec, ||8 Then we can use the triangular inequality and Bonami's hypercontractive inequalities to prove the lemma:
SS = Σ 5 GG
I Σ 15 I (q 1)7-2 oEG,
Σ ||S S (q - 1)7/2 ((W(())
oEC,
Lemma 3.2. Let be Rademacher chaos of order 7 2. Then for any 7' 2 7 and 0, we have:
Pr |r||S|
< d² exp (-(ev// 2/
Proof. When t S (S)2 the lemma trivially follows since e² exp (- > 1. Assume now that > (S)2'/ We apply Markov's 's inequality and lemma 3.1, obtaining
L (1) 9 < (?'AVAWW(S) 9
Pr[[S] > 4 < [|S| 1 = 1
Vq 2222 2.
12

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Then, by setting /7 (e)) 2 have Pr [[S] > 1 exp (-(ev) from which the Lemma follows.
Corollary 3.4. Let (Si..= be sequence of k independent and identically distributed Rademacher chaoses of order 7 Then vyy such that 7 7, there exist constants c1(7), c2(r) depending only y such that
k
2exp
"4c(())WW(S)
E R ((
if < c oz(7)
W(S)kai-a
Pr
S
t
2xxp
otherwise.
i=1
Proof. Let = (//022)/x
and let A' = 2
TI W(S) From Theorem 1.2 we have Vu > 0
Pr Σ S
W(S) (cVViv++ +
$ 2E
For u < A, we have that 6j Vk.u c2u'/2 201 Vkvu.. Then,
Pr
2c, Wc) S
Pr Σ S W(S) + 2e
i=1
By setting u = /2/ (4G we have a < A when / < inequality.
A. Then the above inequality gives the first part of the
For we have that ej /u Cz < 20 Then,
Pr
S
202W
Pr Σ S W(S) (avkkv++ oquih)
2u
By setting (t((22 we have inequality.
A when
A. Then the above inequality gives the second part of the
A.3. Section 4.2
We bound the tail probabilities of the individual terms He by expanding them into sums of Rademacher chaoses and using Theorem 1.2. In what follows, let F() ci vkvl + ezt2, with and c2 the constants of Theorem 1.2 for 7 = 4.
Lemma A.1. We have that Pr
H > | |0 F(t) < 4e
vt > 0
Proof. By setting Jaida.da
Ti J2 w we rewrite H1 as
H1
Re (Ar,, AP.5) Tridads
1= (2rdads)E
Σ
(8igh S1.j2 Pi.j + Siih Si Pe Jn
i=l (2
Σ
Σ
St.e Sta2 dadada /2
H1..1/2 /2 Σ
H12,122 H2,1/2 + H1./22
13

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Since H1 and H1 have the distribution, focus the first one. There are three indexes but four independent random variables in each term of the sum in H1,1, we perform index transformation to get chaos of order 4. Let f: 2d + R be
Ja.i -10 Ts Ja.bo
otherwise.
Let also X;, = (81,1,..
Si,d: -., ria). Note that the components of X are independent. Then, we can rewrite H1,
as
H1 U1
Σ
Xij. Xi. X In
We now upper bound W 1,) for any E (l....k}; standard arguments give
W(H.1))²
Σ
Σ (1))
Unntan Σ
(ndada)
wf S 11 ||
The final inequality holds as:
Σ
E
12), 2 wf
h1 jz
(n.ta.ta)EEaur
(I brna 12
(E Imsssl" JeEla
Σ
helaa
= =|lll| ||0|12-
We can then apply Theorem 1.2 with
= 4, from which follows that
Pr H1,1 || | r(O] Pr [|H W(H),,))(() s 2t
Since a similar bound holds for 22,2, and since 2//1 111,1 H1... an union bound gives
Pr [H ||ll| ||l F(t) Pr H H1 > 2 2| | F(t)
< 2Pr
|1 > || || F(O] = 4t
Lemma A.2. We have that H22 > 2 I |1r12 F(O]
S
1I 42
Proof. By setting Ji = I,j 2z 2 we rewrite H2 as
H3 H2=2 Σ
Σ
Re (Ai,s, Alsz) J3
2
Σ
Sj (1 )
1=1 (Jid2)eT2
Σ
$ Tridz +
Σ
8 8 Thita
I=1
(2)
14

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
where o/ = 8yyy and has the same distribution of a Rademacher random variable.
Let f: 12 RR be
Ji Tj dj-dd
if S d, d
To Ja
j1 > d, > otherwise.
Let also x;; = ($6,1 ................................ Si.d s
a,a) ). Note that the components of X are independent.
Then, we can rewrite H2
k
h
H2 Σ
Σ
Ni Snido
Σ
H2.
(2.d2)
Then, get that:
((H2))²
Σ
Σ
=2
Σ
3 " 4 11:11
Jidz
(1
(n,da)Ell
(
Since H2 is sum of independent Rademacher chaoses of order 2 S 4, from Theorem 1.2 we have that
Pr
H2l > 2 w| | F(t) S Pr H2 > (Hz)))F(() s 2e
and the claim follows.
Lemma A.3. We have that Pr [Ha] ||wll |0|1 F(t)
2e Vt 0
Proof. By setting Tisda = x), w we rewrite H3 as
k
H3 = Σ
Σ
Re (A Al.z)) Ta =
Σ
Σ
Th
H3.5
1=1 (2.22
== (15z)E11
1=1
Then we get:
#(Ha))²
Σ
||l|| |
(1
Since H3 is a sum of independent Rademacher chaoses of order S 4, from Theorem 1.2 we have that
|Hal || | F(t) Pr Hrs| > ((H).)F(t) < 2e
Pr
and the claim follows.
We then provide a bound on the quantity H H1 + H2 + H3.
Lemma 4.2. We have that Pr
[H]
|| 12 ||=113 F(t) s 88 v
Proof.
Pr H > 4 2 | P(O) = Pr Hi + H2 + Hal > >4 1|wر| || 11 F(t) <
< Pr [M > 1| F(1)
+ Pr
H22 > 2 || |F F(O] + Pr [49 > ||l|| | [(1)
< 4t + 2e T + 2c = -1
15

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Lemma 4.3. For any given 4, w IRd, have
Pr [ooo(()), w)
|10
8 exp
-k (11811011211211
if (t)
8 exp
/ Vi
otherwise
with (f) the event: 0 <<1< < c/"
1/8 12 |/ |,m1122 k-1/3
Proof. We have kp(g(x), w)
k || = 11 + H2 + H3 = H, which in turn implics that
Pr [o(a((), w) || > o = Pr [|]] > kd = Pr [|| > u].
From Lemma 4.2, we have that
Pr [1 > 4 // || ||
(1 (aV S88
Then, forv < //2/// we have that 201 aVVo and therefore Pr [ > 8 | | civoo
Se" Similarly for v 2 (c1//2) we have that Pr
|
8 |
|| c222 S Se.
Then, setting
8 || ||
ci v Vevo o for the first bound and 8 ||0l12 | cz for the second one yiclds
8xxp
if < c 1/8 | | k
B)
Pr Pr| > u| S
8exp
10 Vu
otherwise.
Finally, making the substitution u = kl, we obtain the claim.
A 1n(8//8) e²
Am((8/6) })
Theorem 1.1. Let E, 8 > 0. Let A be a suitable parameter and 2 S max
Then there exists
linear function g(x) R + C* and an estimator p(g(ar), w) C x Rd - R such that for any given v, w E Red. with
probability at least 1 - 8.
|p(g(z), w) - |ل < E || /1lm / /A.
In particular, if ||x12 2 || < A, we get, with probability at least - 5,
lp(g()), w) - 1|x11 < ||0.
Proof. Assume that In(8//)/A < c7c5 Rc-18. 8, and set is = c782 2
(n(8/6), and we get:
e 11 | A "
1/88 | || -///
We are thus the Gaussian tail case of the bound described by Lemma 4.3. Then we have
Pr [((o(t), w) | o]
< 8exp
(-ros))uuf || ||=
kt
s 8exp (-c782=-21)
2|
8
c²
6.
c7
Let now assume E (1(8//)/A 2/009/2cff// 8, and fix le C28A
In(8/8)2 this case,
= e | |
z
c
4/s
c2
4/8 | 112 || -/1
16

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
and we in the long tail part of the bound described by Lemma 4.3. Then,
- 8exp (- (-v Vo28 ||w/ll2 11x11
Pr (e(1o0(2)) w) || > $)
vkt
I 8exp
(-078% In
8 E²
G/82
=
8.
As the failure probability decreases by k, taking k 2 max (c782 1m(0//0)
C28 ln(
completes the proof.
8a
8
A.4. Section 4.4
We have that p(j(x),)) = E'e ((g10((0)(a()) wl0) decomposes as
p(O(x), w) = Σ
(z(() )))
1=1
(0)
)2
Re AA 1. (4
k
Ju Eda.de
Σ
Re
1 3,30
A0 (0) (49)
1
jn
(6) (2) (0 ///k
w
E Re
(A (4 )0)
18) /
iml fiideEli
Σ
Re
((4()))))))))) (1) (w)))))
k
ΣΣΣ w32}
H
H
H2
Ha, + ||=|
Am H1 + H
i=
Em1 1=1
H3
||
For ease of exposition, we only deal with the decomposition of H3, as the discussion for H1 and H2 is similar. We first bound some quantities related to the Orliz norms of the Rademacher chaoses H3,t,i- Lemma A.4. Let b- [lil..
L; i k)....k). We have that, for some constant C,
|bه| I e || |0 (VbIl)
and that
|b < ||01 (k
Proof. We have that
|b:12
Σ Σ
HHse P2 < 24e ee 1)2/a
W(Hg,
Eii=l
1=1
I k
||lllla |10 1 R. k2
$ (e (e + 1)2/a
ΣΣ
112 x- s c
Where we used Lemma 3.3 with the fact that x and w are near-uniform.
17

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Similarly,
w ||0|
| =
|H.e I S C max E= i=l.....
| |0oel
k= S c
max 6=1..... I.....
max
max
1-2 1,3
We then have the following result.
Lemma A.5. We have Pr Haal 2 || |10| F(t)) S 2e Vt O, with F(t) appropriate constants.
Ci VKL
Vt
and Ci and cz ea
Proof. Recall that H1 -E E.=1 H3,, with each summand mean-zero Rademacher chaos of order most 4. We then have (Kuchibhotla & Chakrabortty, 2022) for suitable constants čj and 02 that
Pr H3 2 |b1| Vt + 02 1b0l { 2c
Plugging in the result of the previous lemma, we have:
E| 11:12
č =1110| l2 || 2
2e 2 Pr [4 2 |bbl vt + c2 |b 1
2 Pr H3l 2
V2 + C2
VkL
kL
Choosing C = C and C2 = C2C gets the claim.
Similar results hold for H1 and H2. We then have the following.
Lemma A.6. We have that Pr [ 2 4 ||l]l || F()]
<
Se
Proof. We use union bound over H1, H2, and H3. similarly to what is done in Lemma 4.2.
We can then prove the lemma stated in the main paper.
Lemma 4.5. For any given æ, w IRd, we have
8 exp
Kci
(ww ir By) 12
Pr [p(g(r), - -|<01 >
max
8exp
-Vkez
Vt)
with or and 22 appropriate constants (different from the ones in Lemma A.5).
Proof.
We have
P [P(0(tt) w) - ||
Pr [ > fl
From Lemma A.6, we have that
1w0 11 ||x1
||
| 2
Pr
H
> 4c1
Vo + 402
< 88
Lvk
||101 110112
Then, for e such that the term with ve dominates, we have that P Pr H > 8c1
v
< 8
Lv
|
|
Otherwise, we have P < Pr H
802
2
<
1
Then, setting e accordingly yields the claim.
18

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Lemma 4.6. Let e > 0. Let e be suitable universal constant. Let L and k be positive integers such that 2 cmax (n(8/5) E
Then there exists a linear function g(x) Rd Cl and estimator p(g(xx, w) C.. x R + R such that for any given z, RR, with probability least 1 5, [ w) | m < | w / /A
Aln(s/8)" L
In particular, if | [ || S A, we get, with probability at least 1 - 8,
(1 =) ||=|| < p(g(z), w) (1 + ||
Proof. Let 1| Suppose we are in the Gaussian tail case of the bound. Then we have, taking ho =
Pr [p(((z). w) | > #) s 8 8exp (-ka
8. = S. (1110112 ||=:12)22
Let now assume we are in the long tail part of the bound. Then, taking k 02 2 ( 111(188)22L
ViL"
Pr p(((t)), | o) s 8 Bexp
(-o2VE
8.
(/wel1 || |=11))///
As the failure probability decreases by k by taking & 2 cmax completes the proof.
{
A 1m11686))
A1188/82² 1
with an appropriate constant e j.
L
B. Experiments
We perform here a proof-of-coneept experimental evaluation of our techniques. We generate a random vector æ E Rd by selecting uniformly at random each entry in [-1, 1] and then normalizing the resulting vector such that ||ж||, 1. The random weight vector Rd is also created by selecting uniformly at random each entry in [0.1, 1.2). We set - 10 Finally, we generate 1000 random matrices A and plot the empirical distribution of the estimator p()(
From the experiments, we see gap in the quality of the estimate between the linear (Figure 2) and nonlinear (Figure 1) method by Kaban (2015), as argued in Section 4.3. Moreover, the experimental results in Figure 5 showcase the applicability of the method on sparse vectors, as discussed in Section 4.3, as well as the poor quality of the estimate for near-uniform vectors for the method described in Theorem 1.2, suggesting that the probabilistic analysis of the method is tight. Finally, the experiments in Figures 4 and highlight the significant reduction the variance of the estimator when using the sparse block matrices. Interestingly, the sparse map with the decomposition into sub-vectors almost closes the gap with the non-linear method, as argued in Section 4.5.
Our code is publicly available at http://ssiiiiiiiiiaiololooooooom
14
P1e 2rl
Figure 1. Empirical distribution of the nonlinear estimator g' (अ) (())-g((v)) (ww) based on JI. deseribed in Equation I, over N 10 random matrices A. The vectors x and w are fixed throughout the experiment, and drawn from a uniform distribution on [-1, and on [1.0, 1.2] respectively. The dimensionality of the vectors is 2- 10 We report results for & {10?, 10 1043. 3. We remark that, due to its nonlinearity, this method does not allow to compute pairwise distances.
19

---

Dimensionality Reduction Complex Spaces with Dynamic Weights
Figure 2. Empirical distribution of the linear estimator p(z; w) described in Theorem 1.1, over N 10 complex random matrices A. The vectors x and w are fixed throughout the experiment, and drawn from uniform distribution on [-1, and on [1.0, 1.2)". respectively. The dimensionality of the vectors is df 2. 10 We report the results for & (10², 100, 100). We note that the choice of ar and w is the worst-case scenario discussed in Section 4.3, providing experimental evidence for the tightness of the analysis.
2014
Figure 3. Empirical distribution of the linear estimator p(z, w) described in Theorem 4.6, over N 10 complex random matrices A. The vectors x and w are fixed throughout the experiment, and drawn from uniform distribution on [-1, 1]" and on [1.0, 1.2)". respectively. The dimensionality of the vectors is d = 2 10 We report the results for E {10", 10 10") and k 1, which is the optimal parameter choice given the dumosttunffommityy of the vectors x and w. The results showcase the reduction of the estimator variance when using the vector partitioning technique, thereby closing the gap with the nonlinear method.
Figure 4. Empirical distribution of the linear estimator f(z, w²) described in Theorem 4.6, over N = 10 complex random matrices A. The vectors and are fixed throughout the experiment, and drawn from uniform distribution on [-1, and on [1.0, 1.2) respectively. The dimensionality of the vectors is d = 2 10 We report the results for L = 100 and k L E {100, 100, 10*), which ensures the uinoot-uniformity condition for wider range vectors x and w.
Figure 5. Empirical distribution of the linear estimator p(z, w) described in Theorem 1.1. over N = 10 complex random matrices A. The vector is sparse, with m 10 entries drawn from uniform distribution on 1-1, and the rest set to 0. Similarly, is sparse, with the same entries drawn from a uniform distribution on [1.0, 1.2 The dimensionality is d = 2 10 We report the results for E (10?, 103, 10"3. We note that the concentration depends on m. rather than d, as argued Section 4.3.
20


Reviews:
[{"review_id": "MU371a8sZh", "reviewer": "Reviewer_oog7", "summary": "The main result of the paper is the following (Theorem 1.1): \n\nLet $\\epsilon, \\delta  \\in (0,1)$ and $\\Delta \\ge 0$ be given parameters. There is a function $g : \\mathbb{R}^d \\rightarrow \\mathbb{R}^{O(\\Delta^2\\log(1/\\delta)/\\epsilon^2)}$ and an estimator $\\rho(g(x), w)$ such that for any vectors $x,w \\in \\mathbb{R}^d$, with prob. $1-\\delta$\n$$ \\left | \\left(\\sum_{i=1}^d x_i^2 w_i^2 \\right) - \\rho(g(x),w) \\right| \\le \\epsilon \\cdot \\|x\\|_2^2 \\cdot  \\|w\\|_4^2/\\Delta. $$\n\nThe authors seem to have missed the fact that the something similar to the main theorem easily follows from a one line calculation from the standard Johnson-Lindenstrauss lemma. Let me give the full proof below: \n\nLet $\\Pi: \\mathbb{R}^d\\rightarrow \\mathbb{R}^{O(\\log(1/\\delta)/\\epsilon^2)}$ be a JL map. It is well known that for any vectors $a,b$, with prob. $1-\\delta$, we have\n\n$$ | \\langle \\Pi a, \\Pi b \\rangle - \\langle a, b\\rangle  | \\le \\epsilon \\|a \\|_2 \\|b\\|_2.$$\n\n(This is a standard exercise, e.g. see hw 1 here:  https://rajeshjayaram.com/homeworks/hw2.pdf). \n\nNow apply this to the vectors $x' = [x_1^2, \\ldots, x_d^2]$ and $w' = [w_1^2, \\ldots, w_d^2]$. We have $\\sum_{i=1}^d x_i^2 w_i^2  = \\langle x', w' \\rangle$ so\n\n$$ \\left | \\left(\\sum_{i=1}^d x_i^2 w_i^2 \\right) - \\langle \\Pi x', \\Pi w' \\rangle \\right| \\le \\epsilon \\cdot \\|x'\\|_2  \\|w'\\|_2 \\le \\epsilon \\|x\\|_2^2 \\| w\\|_2^2. $$\nThen we can scale $\\epsilon$ by any $\\Delta \\ge 0$ to get an error guarantee of $\\epsilon \\|x\\|_2^2  \\|w\\|_2^2/\\Delta$ by projecting $x$ onto $O(\\log(1/\\delta) \\Delta^2 /\\epsilon^2)$ dimensions. This version is slightly weaker than the main theorem since we replace the $4$ norm with $2$, but better in the sense that we don't have to take the max over two dimensions that is done in Theorem 1.1. \n\nHowever, I can't imagine a situation where replacing the $4$ norm by $2$ would play a big role. This argument also has the benefit that it fits into a few lines with known tools rather than many pages with complicated analysis. Furthermore this construction seems easier to implement and is arguably much more practical than the \"radamacher chaos\" based construction of the paper.\n\nUpdate: After reading the rebuttal, I have updated the score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very confused by this review, and we believe that it might be due to a misunderstanding.\nThe summary that the reviewer provides is misleading and incomplete, as in his re-formulation of our main result, Theorem 1.1, they crucially omit that the function $g$ is linear. Because of this, the reviewer then describes the construction of a nonlinear function, which is a fundamentally different goal to the one we pose in this paper (e.g., because it does not allow to compute distances between vectors). In fact, we indeed explicitly address the proposed nonlinear construction in the Introduction section (lines 75-92 first column, e.g. Equation 1) of our submission.\n\n\nWe remark that linearity is a desiderable property also in practical scenarios. In order to make this even more clear to the reader, we will add the following sentences after line 92 in the introduction. \n\n> Indeed, the prime application of the linearity of JL maps is reducing the time complexity of pairwise distance computations [1], which has applications in clustering [2] and nearest neighbor search [3, 7], e.g. for recommender systems and classification. Other examples include compressed sensing [4], which relies on sparse linear measurements to recover an unknown signal. Finally, the linearity of JL has been exploited to speed up least square regression [5] and low-rank matrix approximation [6, 1]. \n\nWe also remark that in Section 4.4 we provide new results that did not appear in the previous version of the paper. We indeed show that by using a sparse blocked matrix multiplication it is possible to improve the quality of the results with some constraints on the input vectors.\n\nWe then kindly ask the reviewer to re-evaluate the paper, in light of this clarification of our results. \n\n -----\n References: \n - [1] Cunningham, John P., and Zoubin Ghahramani. \"Linear dimensionality reduction: Survey, insights, and generalizations.\" The Journal of Machine Learning Research 16.1 (2015): 2859-2900.\n - [2] Makarychev, Konstantin, Yury Makarychev, and Ilya Razenshteyn. \"Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering.\" Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019.\n - [3] Indyk, Piotr, and Rajeev Motwani. \"Approximate nearest neighbors: towards removing the curse of dimensionality.\" Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998.\n - [4] Upadhyay, Jalaj. \"Randomness efficient fast-johnson-lindenstrauss transform with applications in differential privacy and compressed sensing.\" arXiv preprint arXiv:1410.2470 (2014).\n - [5] Yang, Tianbao, et al. \"Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees.\" arXiv preprint arXiv:1507.05185 (2015).\n - [6] Ghojogh, Benyamin, et al. \"Johnson-Lindenstrauss lemma, linear and nonlinear random projections, random Fourier features, and random kitchen sinks: Tutorial and survey.\" arXiv preprint arXiv:2108.04172 (2021).\n - [7] Ghalib, Abdulaziz, et al. \"Clustering and classification to evaluate data reduction via Johnson-Lindenstrauss transform.\" Future of Information and Communication Conference. Cham: Springer International Publishing, 2020.", "claims_and_evidence": "Yes, the proofs seem correct although quite complicated.", "methods_and_evaluation_criteria": "No empirical results.", "theoretical_claims": "The proofs seem correct but the calculations are long so I was not able to follow them directly. However, the simpler argument I gave above is immediate.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "None.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Are there any realistic scenarios where the construction of the paper is to be preferred over the simpler construction outlined above?", "other_comments_or_suggestions": "None", "questions_for_authors": "None.", "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": "JfULNqRMdt", "reviewer": "Reviewer_pXLS", "summary": "This paper explores dimensionality reduction on complex vectors for Euclidean distances. The authors decompose the complex dimensionality reduction into several Rademacher chaos random variables, where novel concentration inequalities for sums of independent Rademacher chaoses are derived.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 2 for the useful feedback. We provide below detailed answers to comments.\n\n----\n\n**Few experiments should be provided.**\n\nThank you for the suggestion, we added some proof of concept experiments where we show the empirical distribution of the estimates $\\rho$ of the weighted norm. See comment of Reviewer 3 for details.\n\nLink: www.dropbox.com/scl/fo/lvallzefg646aayc826zv/ALbK6BOw0u5PANsePzCDGsM?rlkey=tns4b16zt86ce5tmjpdxdrbnh\n\n**The title contains dynamic weights but are not mentioned in detail**\n\nBased on your feedback, we will expand the introduction (e.g. lines 28-38, second column) with the following sentences and references to highlight the practical relevance of weighted norm queries where the weights can change dynamically from one query to another. \n\n> However, weights might change at each query, or they might not known at preproccessing time, a setting that we hereinafter refer to as “dynamic weights”. Examples include nearest neighbor methods [1] for classification or recommender systems [2], where the relative importance of features might depend on the type of query at hand.  Weights might be estimated on highly dynamic datasets which require a frequent update of the parameters (e.g., (Banihashem et al., 2024)). \n\n - [1] Indyk, Piotr, and Rajeev Motwani. \"Approximate nearest neighbors: towards removing the curse of dimensionality.\" STOC 1998.\n - [2] Baumgärtner, Tim, et al. \"Incorporating Relevance Feedback for Information-Seeking Retrieval using Few-Shot Document Re-Ranking.\" EMNLP 2022.\n\n**What is the effect of the complex vector spaces?**\n\nThe intuition on why a complex space is useful is that it allows to remove the bias in the estimator for $\\| x \\|^2_w$ when we have terms in it with three or more multiplicands. \nMore formally, the key observation, which can be found in Theorem 4.1, is that the contribution of $x_{j_1} x_{j_2} w^2_{j_3}$ in the estimator is multiplied by the random variable $A_{i, j_1} A_{i, j_2} A^2_{i, j_3}$. Since each entry of $A$ is iid in $\\{\\pm 1, \\pm i\\}$, we have that the r.v. is a uniform on either $\\{\\pm 1, \\pm i\\}$ or on $\\{\\pm 1\\}$ when any indices of $j_1, j_2, j_3$ are distinct (and thus it is $0$ in expectation), and the constant $1$ when $j_1, j_2, j_3$ are all the same, since $\\pm 1^4 = \\pm i^4 = 1$. Then, in expectation only the $x_{j} x_{j} w^2_{j}$'s contribute to the estimator. \n\n**It is meaningful to study the general norm.**\n\nThis is a very intriguing remark. We indeed agree that exploring norms beyond the $L_2$ would be of great interest, albeit not trivial: we believe that the approach can be generalized to $L_p$ by using roots of unit of higher order. Based on your comment, we will introduce the following remark to guide future work in this direction.\n\n>We conjecture that the map to the complex plane we provide here admits a generalization to the estimation of arbitrary (weighted) $L_p$ norms. Indeed, let $h = \\sum_{j_1, \\dots j_p}\\prod_{k=1}^p A_{j_k}x_{j_k}$. If $A$ is a uniform on the $p$-th roots of $1$, we have that $\\mathbb{E}[\\prod_{k=1}^p A_{j_k}] = 1$ if all the $j_k$'s are the same, and $0$ otherwise. Therefore, $\\mathbb{E}[ h ] = \\| x \\|_p^p$. However, the variance of the estimator grows with $p$, and novel approaches should be developed in order to reduce this growth. \n\n**Use toy examples to show the probability bound and the privacy-preserving similarity search**\n\nWe added some proof-of-concept experiments on some toy data to show the distribution of the estimator. See the reply to the first comment and Reviewer 3. \n\nAn example of privacy-preserving similarity search is the following: release a dataset, so that a user can detect if there exists a point $x$ within distance $r$ from a given query $q$, but no information on the exact values of $x$ are released. JL provides a solution under differential privacy (Blocki et al, FOCS 12). We believe that an interesting extension would be to release a dataset so that a user can detect if there are points within the desired weighted norm without revealing the exact point coordinates. Indeed, the variance of the estimates would avoid the reconstruction of the original vectors. \nWe plan to add the following sentence (at line 434, second column):\n\n>Finally, we believe that our constructions can be of interest for privacy preserving similarity search as it might allow the release of datasets that allow users to detect if there are near points within the desired weighted norms without releasing the details of the vector, similar to what done in  (Blocki et al, FOCS 12) for JL.\n\n**What is the near-uniform vector?**\nA uniform vector is a vector where all entries are the same. A near uniform vector is a relaxation of this condition, where splitting the vector into contiguous parts results in sub-vectors with roughly the same norm. We give a formal definition in the beginning of Section 4.4, and we will insert the informal description above in the paper to clarify it.", "claims_and_evidence": "The claims seem to be reasonable.", "methods_and_evaluation_criteria": "There are no experiments.", "theoretical_claims": "I checked the proofs of some theorems, and they sound correct.", "experimental_designs_or_analyses": "No experiments are provided.", "relation_to_broader_scientific_literature": "This paper provides a theoretical framework for finding linear functions in the case of weighted L2 norm.", "essential_references_not_discussed": "The references are sufficient.", "other_strengths_and_weaknesses": "This paper provides a theoretical framework for finding linear functions in the case of weighted L2 norm. For weaknesses, please refer to the problem below.", "other_comments_or_suggestions": "Few experiments should be provided.", "questions_for_authors": "1)The title contains dynamic weights. It seems that the authors do not mention them in detail in this paper.  \n\n2)The weighted L2  norm is explored. It is meaningful to study the general norm.\n\n3) Introducing complex vector spaces is interesting. What is the effect of the complex vector spaces when devising specific algorithms?\n\n4) It would be much better to use toy examples to show the probability bound. Maybe a specific example for the privacy-preserving similarity search should be given.\n\n5) What is the near-uniform vector?", "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": "kOHIwUtqdY", "reviewer": "Reviewer_xjUY", "summary": "This paper presents an embedding of a d-dimensional vector x into k dimension such that, for any d-dimensional weight vector w $\\sum_{i=1}^d w_i^2 x_i^2$ is preserved. Specifically, the authors give an additive error in terms of $\\varepsilon \\|x\\|_2^2 \\cdot \\|w\\|_4^2$. The classic Johnson-Lindenstrauss guarantee for unweighted vectors, that is, $w_i=1$ for all $i$, has an additive error of $\\varepsilon \\|x\\|_2^2$, which leads to a multiplicative $(1\\pm \\varepsilon)$ approximation.\n\nTraditionally, the entries matrices with Johnson-Lindenstrauss moments are subsampled Rademacher random variables. The authors extend this construction by choosing the embedding entries to be complex numbers, where the sign of the complex part is Rademacher distributed. This sketch is applied to input vectors $x$, and is then given to a decoding algorithm. The construction is novel and the use of complex numbers is clever. After this setup, the analysis is not too difficult, but requires controlling stochastic processes in ways that are not standard.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 3 for the useful feedback. We provide below answers to reviewer’s comments.\n\n---\n\n**There are no experiments. Comparing the performance with the result by Kaban would have been nice, if only to also see whether the theoretical bounds could be improved.**\n\nThank you for the suggestion. Based also on your comment, we added some proof of concept experiments where we show the empirical distribution of the estimates $\\rho$ of the weighted norm.\n\nLink: www.dropbox.com/scl/fo/lvallzefg646aayc826zv/ALbK6BOw0u5PANsePzCDGsM?rlkey=tns4b16zt86ce5tmjpdxdrbnh\n\nIn particular, the experiments highlight (Fig 3) the significant reduction of the variance of the estimator when using the technique described in Sect 4.4, which uses sparse block matrices. Notably, this technique introduces sparseness (via decomposing the vector into $L$ sub-vectors) to reduce the variance, and the trade-off lies in ensuring that the number of sub-vectors $L$ is small enough that the norm of each one is roughly $1/L$ of the total norm. We will highlight this tradeoff in the paper.  \nMoreover, the experimental results showcase the applicability of the sparse method (Fig 5), as discussed in Sect 4.3, as well as the poor quality of the estimate for near-uniform vectors for the method described in Thm 1.1 (Fig 2), suggesting that the probabilistic analysis of the method is tight.\nFinally, from the experiments we indeed see a gap in the quality of the estimate between the linear and nonlinear (Kaban, Fig 1) method, as argued in Sect 4.3. Interestingly, the sparse map with the decomposition into $L$ sub-vectors almost closes the gap with the non-linear method.\n\n**Why a linear method is important for applications still eludes me.**\n\nThank you for pointing out this lack of clarity. The main feature of linearity is the ability to compute distances between vectors by simply computing distances between reduced vectors, since $\\lVert x - y \\lVert \\simeq \\lVert g(x - y) \\lVert = \\lVert g(x) - g(y) \\lVert$. Based on your comment, we will include the following paragraph to make this clearer. \n\n> Indeed, the prime application of the linearity of JL maps is reducing the time complexity of pairwise distance computations [1], which has applications in clustering [2] and nearest neighbor search [3, 7], e.g. for recommender systems and classification. Other examples include compressed sensing [4], which relies on sparse linear measurements to recover an unknown signal. Finally, the linearity of JL has been exploited to speed up least square regression [5] and low-rank matrix approximation [6, 1]. \n\n(See answer to Reviewer 1 for the new references [1-7]).\n\n**A compelling use case that offers a real improvement over SOTA.**\n\nWe first observe that our approach represents the first linear dimensionality reduction supporting weighted case. Moreover, we partially address the sparse JL transformation by showing in Section 4.4 that a sparse block structure allows to reduce variance in case of almost uniform vectors.\n\n**Provide [...] a tight analysis of their method. I understand that it might be difficult to improve the paper...**\n\nThank you for your suggestion. We would indeed like to find a lower bound, but we were so far unable to obtain one. We conjecture there is some form of information-theoretic lower bound, as arbitrary approximations of the weighted norm would allow to reconstruct the vector at hand. \n\nWe can however provide a strong hint that our probabilistic analysis is indeed tight. Note that this is not a formal proof. \nWe have, by [1, Example 3.3] and  [2, Thm 1.1], that \n$\\lVert \\sum_{i=1}^k S_i \\rVert_q = \\Theta\\Big( \\big( \\sum_{i=1}^k \\lVert S_i \\lVert_q^q \\big)^{1/q} + \\big( \\sum_{i=1}^k q \\lVert S_i \\lVert_2^2 \\big)^{1/2}  \\Big) \\geq  C \\sqrt {kq} \\cdot W(S_1)$ for some universal constant $C$.  \n\nWe take $x = (1, \\dots, 1) \\in \\mathbb{R}^d$ and $w = (1, \\dots, 1) \\in \\mathbb{R}^d$. Note that $\\lVert x \\lVert^2_2 \\lVert w \\lVert^2_4 = d^{3/2}$. Then, in the proof of Lemma A.1, we have that $W(H_{1,1,i}) = |I'_{d,3}| \\geq d^{3/2} / 30$ if $d > 3$. This then implies that $\\lVert H_1 \\lVert_q \\geq C \\sqrt {kq} \\cdot  d^{3/2}$ for any $q > 2$, for some universal constant $C$.\n\nIf we suppose that we can obtain an upper bound on the tail probabilities of the type $\\mathbb{P}[|H_1| > t] \\leq \\exp( - c (t / f(d) )^{\\alpha} )$, with $\\alpha > 0$, we obtain that $\\lVert H_1 \\lVert_q \\leq C' f(d)$, for some universal constant $C'$ that depends on $q$ but not $d$. Therefore, if we take $f(d)\\in o(d^{3/2})$, for large enough $d$ it would violate the condition found above, and we have a contradiction. \nIn conclusion, the dependence of our bounds on $\\lVert x \\lVert^2_2 \\lVert w \\lVert^2_4 = d^{3/2}$ seems to be optimal.\n\n- [1] Latała. \"Estimation of moments of sums of independent real random variables\" The Annals of Probability.\n- [2] Hitczenko et al. \"Moment inequalities for sums of certain independent symmetric random variables.\" Studia Math.", "claims_and_evidence": "-", "methods_and_evaluation_criteria": "-", "theoretical_claims": "I have previously reviewed the paper. While there are some changes, the correctness proofs are the same and I still believe the results to be correct.", "experimental_designs_or_analyses": "There are no experiments. Comparing the performance between the author's embedding and the result by Kaban would have been nice, if only to also see whether the theoretical bounds could be improved or whether there is a gap between linear and non-linear methods. It would have also been nice to see if the performance is sensitive to the sparsity of the JL-matrix used (e.g. if the peformance is the same if a constant fraction of entries are set to 0).", "relation_to_broader_scientific_literature": "I believe that this result is a bit niche. Why a linear method is important for applications still eludes me. In addition, instead of developing a general framework for JL-transforms into a complex space with a range of sparsity/target dimension tradeoffs, the authors give one construction for which it is not clear that the presented analysis is tight.\n\nI think a compelling use case for which the authors offer a real improvement over the state of the art, a tight analysis of their method, or alternatively, but unlikely, a separation between linear and non-linear methods, or a general framework for sparse JL transforms into complex spaces would have increased my score substantially.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "I find the ideas quite clever and the technique engaging.\n\nNevertheless, it would have been nice if the result had achieved an optimal error, or if the analysis had been tight, or if the authors had presented a framework for generalizing general JL-embedding matrices, rather than only the complex analogue of dense Rademacher sketches. I understand that it might be difficult to improve the paper in the way that I am suggesting.\n\nAlternatively, some experimental focus would have been welcome for a conference like ICML.\n\nIn the end, I feel this paper barely gets a weak accept. For a higher rating, it would need to address one of the aforementioned points in a satisfactory way.", "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:

Meta-review: This paper presents an embedding of a d-dimensional vector x into k dimension such that, for any d-dimensional weight vector w 
 is preserved. Specifically, the authors give an additive error via the classic Johnson-Lindenstrauss guarantee for unweighted vectors, that is, which leads to a multiplicative approximation.

Traditionally, the entries matrices with Johnson-Lindenstrauss moments are subsampled Rademacher random variables. The authors extend this construction by choosing the embedding entries to be complex numbers, where the sign of the complex part is Rademacher distributed. This sketch is applied to input vectors , and is then given to a decoding algorithm. The construction is novel and the use of complex numbers is clever. After this setup, the analysis is not too difficult, but requires controlling stochastic processes in ways that are not standard.

Points to improve: (from the reviews):
it would have been nice if the result had achieved an optimal error, or if the analysis had been tight, or if the authors had presented a framework for generalizing general JL-embedding matrices, rather than only the complex analogue of dense Rademacher sketches. I understand that it might be difficult to improve the paper in the way that I am suggesting.

Alternatively, some experimental focus would have been welcome for a conference like ICML.
Decision: Accept (poster)