Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry

We sincerely thank you for the positive feedback and valuable suggestions! Responses to your concern are given below, please feel free with follow-up questions.

Response to “Table 2 presents only non-robust metrics for comparison with classic JL”

Thanks for pointing it out. We obtain the results on the median and 75 percentile of distortion for all three methods, and present them below. The same observations on their performances hold.

Reporting the max and mean follows from a broad class of algorithms designed for metric embedding. In these problems, a point set A in one space is projected to a point set B in another space such that pairwise distances are preserved. The analysis is commonly done for the worst-case distortion and average distortion, corresponding to the max and mean relative error reported in our experiments. We completely agree a robust metric such as the median would greatly help with a comprehensive evaluation.

Response to “Impact on large scale problems such as facial recognition, which also uses non-Euclidean metrics in high-dimensions.”

Thank you for the thoughtful question. In applications like face recognition and information retrieval, non-Euclidean metrics such as cosine similarity or learned distances are commonly used. However, these approaches typically operate in the original high-dimensional space or rely on data-dependent embeddings learned through supervision.

The non-Euclidean JL, on the other hand, is data-independent. Though our results have extra terms in the bounds, they offer insights on uncertainty ($r$ in JL-power) or how deviated is a certain data pair from Euclidean ($C_{ij}$ in JL-pq). In addition to dimension reduction helping with efficiency and scalability of those tasks, we also obtain some understanding of the geometry the dataset lies on.

Lastly, we largely agree with you that many valuable questions on ML tasks can be asked about the new JL transforms. We regard these as future directions.

Response to “The authors do not dedicate a section to limitations”

We thank the reviewer for the valuable suggestion. We will add a limitation section to the paper as below.

We establish two approaches for non-Euclidean JL transform. However, we do not have a proof showing the conditions that one outperforms the other; neither a connection between the two representations. Another limitation is we are not aware of any lower bound result complementing the fine-grained JL guarantee from the pseudo-Euclidean representation. Last, our work is mainly theoretical, the practical impact of applying the proposed JL transforms in downstream ML applications is one of the future directions.

I wish to thank the authors for the comprehensive response, which addressed my concerns.

A small clarification on the large scale question -
My intention was that even if such problems (like face recognition) operate on non-Euclidean metrics (line cosine), they might still enjoy any boost in performance that JL might offer. If the approximation is tighter, and/or better fit to the metric, the boost might be more significant w.r.t. 'standard' JL.

A small note on the limitation -
Thanks for sharing this. Indeed, both in Table 2 and the new Table in the rebuttal, one can observe the inconsistency between the two suggested methods; Even if one of them always improves distortion, usually the other might still be very close to standard JL.

Last question on the tables -
Did you share any 2nd order statistics? IOW - how consistent is the improvements in any of the variants

I think the note about the eigenvalue is great! Even if there's no rigorous proof, consider sharing this as a note or a Conjecture

We are sincerely grateful for the valuable insights and thoughtful questions. We would like to address the questions by response below. Please feel free to add any follow-up questions.

Response to “Clarification of Section 2.1”

We provide more details related to Section 2.1. Hopefully this helps to clarify. We will add the clarification to the paper in the revised version.

• The differences between the Gram matrix for Euclidean data and non-Euclidean data.

In the Euclidean setting, the Gram matrix $B=-CDC/2$ with $D$ as the squared Euclidean distances and $C$ as the centering matrix has $B_{ij} = \langle x_i, x_j \rangle$ where $\langle, \rangle$ is the standard inner product. The squared Euclidean distance is then induced by this inner product as $d^2(x_i, x_j) =\langle x_i - x_j, x_i - x_j \rangle = \langle x_i, x_i \rangle - 2\langle x_i, x_j \rangle + \langle x_j, x_j \rangle$.

Now, for the pseudo-Euclidean space we replace the standard inner product with the bilinear form $\langle \rangle_{p,q}$ where $\langle u, v \rangle_{p,q}=\sum_{k=1}^p u_iv_i-\sum_{k=p+1}^{p+q} u_i v_i$. We keep a similar definition of (squared) distance: $D(x_i, x_j) =\langle x_i - x_j, x_i - x_j \rangle_{p,q} = \langle x_i, x_i \rangle_{p,q} - 2\langle x_i, x_j \rangle_{p,q} + \langle x_j, x_j \rangle_{p,q}$. The relationship between the Euclidean squared distances matrix and the Gram matrix still holds in the pseudo-Euclidean space, as will be elaborated next.

• A proof of the following claim.

Claim: For any hollow symmetric matrix $D$, there is a symmetric bilinear form $\langle, \rangle_{p,q}$ for integers $p, q$ and $n$ vectors $v_1, \cdots, v_n$ such that $D_{ij}=\langle v_i - v_j, v_i - v_j \rangle_{p,q}$.

Proof: Define $B=-CDC/2$ where the centering matrix $C=I-J/n$ with $J$ as the matrix of entry $1$ everywhere. Expanding the multiplication, we have $B=-0.5 (D-DJ/n-JD/n+JDJ/n^2)$. In particular, the $(i, j)$ element $B_{ij}$ is given by $B_{ij}= -0.5 (D_{ij} - 1/n \sum_{k} (D_{ik}+D_{kj}) + 1/n^2 \sum_k \sum_{\ell} D_{k\ell})$. Call this equation (*). Notice that the last term is a constant that is independent of $i, j$. We can also verify that the sum of each row in matrix $B$ is zero. So $B$ has at least one zero eigenvalue with an all-1 vector as the corresponding eigenvector.

Since $B$ is a symmetric matrix, all eigenvalues are real numbers. Suppose that there are $p$ positive eigenvalues and $q$ negative eigenvalues (we ignore the eigenvalue 0). Define $\Lambda$ to be a diagonal matrix of dimension $p+q$ by $p+q$ with the first $p$ entries to be $1$ and the next $q$ diagonal entries to be $-1$. Now we can find $n$ vectors $v_1, \cdots v_n$ each of dimension $p+q$, such that write $B=V^T \Lambda V$ where $V$ has $j$th column vector as $v_j$. In particular, $B_{ij}=v_i^T \Lambda v_j$. Using the notation of the bilinear form of the $(p, q)$ signature, we can write $B_{ij}=\langle v_i, v_j \rangle_{p,q}$.

Now we claim that $D_{ij}=(v_i-v_j)^T \Lambda (v_i-v_j)=\langle v_i-v_j, v_i-v_j \rangle_{p,q}$. Re-organizing, this is equivalent to $D_{ij}=B_{ii}+B_{jj}-2B_{ij}$. To show that, we plug in the equation ( * ) on $B_{ij}$ and verify that $B_{ii}+B_{jj}-2B_{ij}$ indeed gives $D_{ij}$. Here we use the fact that the last term in ( * ) is a constant and thus is cancelled out. Also $D$ is a symmetric hollow matrix, i.e., $D_{ii}=0$ and $D_{ij}=D_{ji}$.

Response to questions on the centering matrix.

It is correct that since $D$ is symmetric, we can directly write down $D=Z^T \Lambda Z$ with $\Lambda$ as again a diagonal matrix with $p$ ($q$) as the number of positive (negative) eigenvalues of $D$. This means $D_{ij}=Z_i^T \Lambda Z_j = \langle Z_i, Z_j \rangle_{p,q}$. This way, $D_{ij}$ takes the form of doing a “dot product” of $Z_i$ and $Z_j$ with the $(p, q)$ bilinear form. We hope to keep the format to be consistent with the Euclidean setting where we take $D_{ij}$ as the “dot product” of $X_i-X_j$ with $X_i-X_j$. The centering trick and transforming $D$ into the Gram matrix $B$ achieve this, as shown above. This also means that when $B$ has all eigenvalues to be non-negative, we are indeed in the Euclidean setting and the coordinates are exactly the Euclidean coordinates recovering $D$ – in that case, the pseudo Euclidean JL is exactly standard Euclidean JL.

Response to questions on the complex space.

It is true that the pseudo-Euclidean bilinear form, defined by the matrix $\Lambda$ with entries of +1 and -1, can be represented algebraically by introducing complex-valued coordinates. Specifically, for a vector $x \in \mathbb{R}^{p,q}$, we can construct a corresponding vector $z \in \mathbb{C}^{p+q}$ where coordinates corresponding to the -1 entries in $\Lambda$ are pure imaginary. The squared pseudo-Euclidean distance is then equivalent to the standard Euclidean squared norm of the difference between these complex vectors, as the imaginary unit $i$ squares to -1.

On the other hand, we are not using the complex inner product space. In a complex inner product space the inner product $\langle u,v \rangle$ is defined using the complex conjugate (i.e., $\langle u,v \rangle = u^H v$), which ensures that the induced norm $||u||^2 = \langle u,u \rangle = \sum_k |u_k|^2$ is always real and non-negative. In our case, the bilinear form $\langle u,v \rangle_{p,q} = u^T \Lambda v$ does not involve a complex conjugate. As a result, the squared "distance" $D_{ij} = ||x_i - x_j||_{p,q}^2$ for points in the $(p, q)$-space can be negative. Further, our input dissimilarity measures $D$ do not necessarily meet triangle inequality. Thus we are handling non-metric measures.

We hope this helps to clarify. We will also consider adding these discussions to the paper.

Response to “What purpose the long exposition on Ptolemaic identities serves”

We will cut it shorter to make space for adding more clarification to section 2.1. The reason we put it here is because the Ptolemaic identities serve to introduce the power distance notion. More precisely, our introduction to the generalized power distance was inspired by the Casey’s theorem on Ptolemaic identity.

Response to Questions regarding the experiments

• “The text in the plots is tiny.” Thank you for the observation, we have adopted larger fonts.
• “Not clear what the entropic affinity is and why JL-PE performs better.” The entropic affinity is only used for the Genomics datasets and has been considered as a reasonable metric by a line of previous work, here we follow the common practice. We will add its definition to appendix. It is an excellent question to ask when JL-PE performs better than JL-power. Our observation is if there are many (but not too extreme) negative eigenvalues, JL-PE usually performs better. The case of genomics data is exactly due to this. However this is only an observation without rigorous proof.
• “Not clear how to apply the JL transform to a graph dataset.” A graph with shortest distance metric is non-Euclidean and very common in data mining tasks. The input dissimilarity matrix has shape $n$, corresponding to $n$ vertices, and each entry refers to the shortest distances between two vertices.

Response to “Absence of a limitations section with elaboration on assumptions”

We will add a section to make it explicit 1) the assumptions made in the paper; 2) limitations of current results; 3) computation and suggestions for practitioners, as below.

The assumption of the current work is that a matrix of non-Euclidean pairwise dissimilarities is given. We establish two approaches for JL transform in this setting, both requiring $O(n^3)$ time. There are several possible ways to speed up this step in practice – by using landmark MDS for example. Further, if the dimension reduction step is already embedded in some machine learning pipeline (e.g., with a representation learning step), there can be better ways to integrate the non-Euclidean JL step. For example, some work already considers learning a bilinear form (to replace standard dot product) [57, 58]. One may consider using JL in the pseudo Euclidean space. Another approach, motivated by the generalized power distance formulation, is to consider appending a proper term $4r^2$ to the input matrix $D$ and later use the power distance (instead of standard Euclidean distance) with the recovered coordinates/vectors.

One limitation is we do not have a proof showing the conditions that one outperforms the other; neither a connection between the two representations. Another limitation is we are not aware of any lower bound result complementing the fine-grained JL guarantee from the pseudo-Euclidean representation. Last, our work is mainly theoretical, the practical impact of applying the proposed JL transforms in downstream ML applications is one of the future directions.

We appreciate your suggestions and questions! Please see our responses below, and feel free with follow-up questions.

Response to “The results are non-algorithmic; it would be nice to know how efficiently these can be computed” and “What is the running time of your algorithm for finding the points in theorem 1.3?”

Thank you for raising the issue. We will clarify this in the paper.

For the two proposed JL algorithms for dimension reduction, as presented in Section 4, there are two steps: (1) Obtain the Gram Matrix and find the coordinates by our proposed methods. (2) Perform JL accordingly.

To find coordinates from the Gram matrix, it takes $O(n^3)$ time since we need to find eigenvalues of an $n \times n$ matrix, which is the same order of running time even in classical Euclidean settings (such as classical multi-dimensional scaling). For Theorem 1.3, we first find the smallest eigenvalue of the Gram matrix of $D$. Using it to amend the input matrix $D$, and then solve for the coordinates. If the coordinates are given, we can directly use JL which is $O(nk)$ with $k$ as the target dimension. There are several possible ways to speed up the coordinate recovery part in practice – by using landmark MDS for example. Further, if the dimension reduction step is already embedded in some machine learning pipeline (e.g., with a representation learning step), there can be better ways to integrate the non-Euclidean JL step. For example, some work already considers learning a bilinear form (to replace standard dot product) [57, 58]. One may consider using JL in the pseudo Euclidean space. Another suggestion is to append a proper term $4r^2$ to the input matrix $D$ and later use the power distance (instead of standard Euclidean distance) with the recovered coordinates/vectors.

Response to “It is not clear that these are the correct ways to generalize to non-Euclidean data for ML applications.” and "“Is there evidence that these notions are the correct ones to use in ML applications?”"

Thank you for the valuable insight. Downstream ML applications are great directions and in fact these are our current/future work. Algorithms that go beyond non-Euclidean non-metric data for many of the data processing tasks are largely unexplored. We showcase the potential with a clustering example below.

Many real-world tasks do clustering after JL, which pre-processes the data into low-dimension with the expectation that the clustering quality would not degrade. We evaluate three JL transforms for k-means clustering on 4 datasets. Below we report the k-means cost on the original dataset, and the projected data by three JL transforms. It can be observed that the JL-pq and JL-power give much better results than JL in the Brain and Breast datasets. On the graph datasets, they are at least competitive and sometimes better. We believe this illustrates potentials of the proposed JL transforms to be a better dimension reduction for other downstream learning tasks with non-Euclidean data.

We agree that a deeper insight and further study on how these notions fit the non-Euclidean setting would benefit a lot. Our work is making one step towards that --- with theoretical worst case performance analysis as well as empirical evaluation of their performance. It will be very interesting future work to consider integrate our work with additional downstream tasks and further evaluate the empirical performance.

Response to “Please write "hollow" instead of "reflexive" on line 49.”

Thank you. We have corrected the wording.

We sincerely thank you for the valuable feedback, please find our responses below, and feel free with follow-up questions.

Response to “Incremental techniques”

Indeed, the dimension reduction part, after our formulation to obtain the “coordinates”, resembles the classical JL lemma. This is on purpose as we wish to keep the simplicity and applicability of JL transform. The part of obtaining the coordinates so that we can apply JL style dimension reduction is the main contribution of the paper – when the input is a general hollow symmetric matrix and is no longer Euclidean. We propose two ways (pseudo Euclidean framework and the generalized power distance framework) to construct vectors such that applying JL type of random projection still have provable guarantees. Our proof of these guarantees are new, and any hollow symmetric matrix can be written as the generalized power distance may be of independent interest.

Response to “Heavy computation assumptions”

Thank you for raising the concern. The assumption of the setting is that we are given the input of a dissimilarity matrix of size $n \times n$, for the purpose of exploring JL type random projection on non-Euclidean data input.

In this setting, running conventional dimension reduction methods (such as classical MDS) to recover coordinates takes $O(n^3)$ time, which matches with our computation time. There are several possible ways to speed up this step in practice – by using landmark MDS for example. Further, if the dimension reduction step is already embedded in some machine learning pipeline (e.g., with a representation learning step), there can be better ways to integrate the non-Euclidean JL step. For example, some work already considers learning a bilinear form (to replace standard dot product) [57, 58]. One may consider using JL in the pseudo Euclidean space. Another approach, motivated by the generalized power distance formulation, is to consider appending a proper term $4r^2$ to the input matrix $D$ and later use the power distance (instead of standard Euclidean distance) with the recovered coordinates/vectors. The current paper is mainly theoretical and we consider the above discussion to be possible future work.

Response to “The utility of the proposed JL embeddings beyond preserving pairwise dissimilarities? For example, do these embeddings improve performance in downstream tasks?”

These are great directions and in fact these are our current/future work. Algorithms that go beyond non-Euclidean non-metric data for many of the data processing tasks are largely unexplored. We showcase the potential with a clustering example below.

Clustering is one of the downstream applications of JL, which pre-processes the data into low-dimension with the expectation that the clustering quality would not degrade too much. We evaluate three JL transforms for k-means clustering on 4 datasets. Below we report the k-means cost on the original dataset and the projected data by three JL transforms. It can be observed that the JL-pq and JL-power give much better results than JL in the Brain and Breast datasets. On the graph datasets, they are at least competitive and sometimes better. This helps to illustrate potentials of the proposed JL transforms for downstream learning tasks with non-Euclidean data.

Response to “The impossibility of worst-case dimension reduction guarantees for general non-Euclidean data.”

We largely agree with you on this. Indeed it has been established in prior work [13, 14, 15] that JL transform has to use dimensions polynomial in $n$ when we consider non-Euclidean norms ($L_1$ or $L_p$). Thus we cannot expect to achieve the same dimension reduction results for our setting (which is more general). On the other hand, our results show performance guarantees that depend on parameters characterizing how the dissimilarities deviate from Euclidean distances. This means that distances that are close to Euclidean can still enjoy good performance.

Thanks again for helping us improving the paper and pointing out future directions!