Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights

We thank Reviewer 3 for the useful feedback. We provide below answers to reviewer’s comments.

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.

Thank 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.

Link: www.dropbox.com/scl/fo/lvallzefg646aayc826zv/ALbK6BOw0u5PANsePzCDGsM?rlkey=tns4b16zt86ce5tmjpdxdrbnh

In 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.
Moreover, 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. Finally, 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.

Why a linear method is important for applications still eludes me.

Thank 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.

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].

(See answer to Reviewer 1 for the new references [1-7]).

A compelling use case that offers a real improvement over SOTA.

We 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.

Provide [...] a tight analysis of their method. I understand that it might be difficult to improve the paper...

Thank 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.

We can however provide a strong hint that our probabilistic analysis is indeed tight. Note that this is not a formal proof. We have, by [1, Example 3.3] and [2, Thm 1.1], that $\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$.

We 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$.

If 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. In conclusion, the dependence of our bounds on $\lVert x \lVert^2_2 \lVert w \lVert^2_4 = d^{3/2}$ seems to be optimal.

• [1] Latała. "Estimation of moments of sums of independent real random variables" The Annals of Probability.
• [2] Hitczenko et al. "Moment inequalities for sums of certain independent symmetric random variables." Studia Math.

We thank Reviewer 2 for the useful feedback. We provide below detailed answers to comments.

Few experiments should be provided.

Thank 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.

Link: www.dropbox.com/scl/fo/lvallzefg646aayc826zv/ALbK6BOw0u5PANsePzCDGsM?rlkey=tns4b16zt86ce5tmjpdxdrbnh

The title contains dynamic weights but are not mentioned in detail

Based 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.

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)).

• [1] Indyk, Piotr, and Rajeev Motwani. "Approximate nearest neighbors: towards removing the curse of dimensionality." STOC 1998.
• [2] Baumgärtner, Tim, et al. "Incorporating Relevance Feedback for Information-Seeking Retrieval using Few-Shot Document Re-Ranking." EMNLP 2022.

What is the effect of the complex vector spaces?

The 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. More 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.

It is meaningful to study the general norm.

This 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.

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.

Use toy examples to show the probability bound and the privacy-preserving similarity search

We 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.

An 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. We plan to add the following sentence (at line 434, second column):

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.

What is the near-uniform vector? A 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.

We are very confused by this review, and we believe that it might be due to a misunderstanding. The 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.

We 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.

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].

We 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.

We then kindly ask the reviewer to re-evaluate the paper, in light of this clarification of our results.

References:

• [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.
• [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.
• [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.
• [4] Upadhyay, Jalaj. "Randomness efficient fast-johnson-lindenstrauss transform with applications in differential privacy and compressed sensing." arXiv preprint arXiv:1410.2470 (2014).
• [5] Yang, Tianbao, et al. "Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees." arXiv preprint arXiv:1507.05185 (2015).
• [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).
• [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.