Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
Authors: Chengyuan Deng
Jie Gao
Kevin Lu
Feng Luo
Cheng Xin
Venue: NeurIPS 2025 poster ()
Keywords: Johnson-Lindenstrauss Lemma
Non-Euclidean Geometry
Primary area: theory

Abstract: The Johnson-Lindenstrauss (JL) lemma is a cornerstone of dimensionality reduction in Euclidean space, but its applicability to non-Euclidean data has remained limited. This paper extends the JL lemma beyond Euclidean geometry to handle general dissimilarity matrices that are prevalent in real-world applications. We present two complementary approaches: First, we show how the JL transform can be applied to vectors in pseudo-Euclidean space with signature $(p,q)$, providing theoretical guarantees that depend on the ratio of the $(p, q)$ norm and Euclidean norm of two vectors, measuring the deviation from Euclidean geometry. Second, we prove that any symmetric hollow dissimilarity matrix can be represented as a matrix of generalized power distances, with an additional parameter representing the uncertainty level within the data. In this representation, applying the JL transform yields multiplicative approximation with a controlled additive error term proportional to the deviation from Euclidean geometry. Our theoretical results provide fine-grained performance analysis based on the degree to which the input data deviates from Euclidean geometry, making practical and meaningful reduction in dimensionality accessible to a wider class of data. We validate our approaches on both synthetic and real-world datasets, demonstrating the effectiveness of extending the JL lemma to non-Euclidean settings.

Johnson-Lindenstraus Lemma Beyond Euclidean Geometry
Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Cheng Xin"
Abstract
The Hainson-Lindenstrauss (JL) lemma is a cornerstone of dimensionality redue- tion in Euclidean space, but its upplicability to non-Euclidean data has remained limited. This paper extends the JI lemma beyond Euclidean geometry to handle general dissimilarity matrices that are prevalent in real-world applications. We present two complementary approaches: First, show the JL transform applied to vectors in pseudo-Euclideds space with signature (p, q). providing theo- retical guarantees that depend on the ratio of the (p. q) norm and Euclidean norm of two vectors, measuring the deviation from Euclidean geometry. Second, we prove that any symmetric hollow dissimilarity matrix can be represented as matrix of generalized power distances, with an additional parameter representing the uncer- tainty level within the data. In this representation, applying the JL transform yields multiplicative approximation with controlled additive eπrоr term proportional to the deviation from Euclidean geometry. Our theoretical results provide fine-grained performance analysis based on the degree to which the input data deviates from Euclidean geometry, making practical and meaningful reduction in dimensionality accessible to a wider class of data. We validate our approaches on both synthetic and real-world datasets, demonstrating effectiveness extending the JL lemma to non-Euclidean settings.
be
Introduction
The Linddenidntttusss (JL) lemma 1 stands as cornerstone result in dimensionality reduction. states that random linear projection can reduce the dimensionality datasets in Euclidean space, while approximately preserving pairwise distances. Formally,
Proposition 1.1 (Johnson- Lindenstrauus Lemma). For any set of n points Iı, T2.... ... Fn in Rd and E (0, 1), there exists map Rd R,, where OOlog n/e²2) =²) such that for any i,j [n],
- =]]a)] - x, 1l2 s (lf(zz)) f(r))) fx1))12 (1++))ll +)]l=, -1,12
(1)
In modern algorithm design, the JL lemma is widely used as key component or pre-pros pre-processing step for nigh-dimensional data analysis. In addition effectiveness, another crucial reason for its significant impact is that the JL lemma can be achieved by random linear maps, which are data- independent and easy implement. Johnson-Lindenntrauc Lemma has found numerous applications in machine learning, from the most immediate applications in approximating all pairs distances (when the input data is high-dimg dine--imenssona),, regression 3. clustering [4] [ 6 71, functional analysis [ and compressed sensing 99]
approximate nearest neighbor search [2] approximate linear
apply the JL. lemma: (1) the data points lie in high- dimensional Euclidean space, and (2) the coordinates of all points are available. However, many real-world applications do not satisfy these two conditions. First, the dissimilarity measures used in modern data analysis are often non-Euclidean and sometimes even non-metric. Common examples
Note that conditions must be
Rutgers University. {cd751, jg1555, k11160, fluo, cx122))0rugeerr.oo
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

include Minkowski distance, cosine similarity. Hamming distance, Jaccard index, Mahalanobis distance, Chebyshev distance, and Kullback-Leible (KL) divergence, etc. Psychological studies have long observed that human similarity judgments do not conform to metric properties [TO]. Second, high-dimensional coordinates may be unavailable or costly to obtain, whereas pairwise dissimilarities are easier to access. In recommendation systems, for instance, computing user or item embeddings can be expensive, while estimating pairwise dissimilarities (e.g. from co-click or co-purchase data) is relatively efficient. To date, our understanding of the JL lemma deviating from these two classical conditions mainly revolves around lp metrics and lower bound results.
In this paper, we study how to apply the Johnson-Lindenstruus transform (a.k.a. random linear projection) in Euclidean, non non-metric settings. We provide theoretical analysis on the performance of the JL transform in these settings and show experiments with both synthetic and real-world data.
Our setting. We consider the input as dissimilarity matrix D of size n X n. where Diy is the dissimilarity between item i and j. We make only two assumptions for the dissimilarity measure: symmetric (Daj = Dyj) and reflexive (D.: 0). Note that we do not require the triangle inequality to be satisfied, therefore the dissimilarity can be non-metric. In short, the input is a symmetric hollow dissimilarity matrix, and the expected output is a low-dimensional embedding of the original dataset that approximately preserves pairwise distances.
The major challenge encounter in this setting is two-fold. The first is obtain good coordinates from a generic input dissimilarity matrix to represent the data, before we can even apply the JL transform. Second, need geometric characterization of the non-Fuclidean non-metric setting, to show how different our setting stands from Euclidean geometry, which the JI. Lemma is based on.
Before we explain our results, we first mention existing lower bounds for dimension reduction in non-Euclidean settings. JL Lemma considers Euclidean spaces only. Naturally, one asks whether such a result is possible for other spaces. There are several non-trivial dimension reduction results for & norm MT and f, norm [12. However, the target embedding dimension for & lp and nuclear norm is necessarily polynomial in for constant distortion 13 14 15 These lower bounds remind us that a worst-case guarantee on low distortion and logarithmic target dimension is not possible. Rather, our results provide error analysis which depends parameters characterizing how the input data deviates from Euclidean geometry. In other words, we have fine-grained performance analysis.
Our Contributions. We present two approaches to recover coordinates that fit into the non- non-Euclidean non-metric setting. For both approaches, we generalize the Euclidean norm lg to new form to capture the input data geometry, together with certain geometric parameters indicating how far it deviates from Euclidean geometry. We give error analysis on the dissimilarity distortion, which may involve an additive term whose magnitude is proportional to the geometric parameters.
At the heart of our first approach is the observation that any symmetric hollow matrix can be written as Euclidean space [7] Here the distance between two vectors (I1, Z2, ....,) and y (y), 1/2 ... ) captured by a bilinear form of signature (p. q). ptg which is defined as (ar, y) = P J.lhi 1 TzHh, The squared (p, -dddstannce between x and y is ||æ =1li, will give a more detailed introduction later. At this point, it suffices to interpret the parameter p resembling and q negating the Euclidean space. Our first result shows the generalization of the JL. lemma to the pseudo-Eun Euclideen geometry.
the distance matrix of vectors in
(x y, y). When
n, q = 0, it is the squared Euclidean norm. We
Theorem 1.2
JL lemma, informal Version of Theorem 2.3). Given any symmetric hollow dissimilarity matrix D of size n, are able obtain embeddings X in the pseudo-Euclidean space. For any e E (0, 1), there exists a JL transform to X with target dimension O n/=²). such that any pairwise dissimilarity Dig is preserved with at most + E Cij multiplicative factor, where Cij is the ratio of the squared Euclidean distance and squared (p, q) distance.
Our second result takes a different route. We prove that a symmetric hollow matrix is also a matrix of generalized power distances. Given two points x and y with respective radius Tx and Ty, the generalized power distance is defined as ||æ- a1 (rz + ryy? where ||æ vl denotes the Euclidean norm. This is the squared length of the tangent line segments of two balls centered at ær, y with radii rx, Ty. Again, at this point, it suffices to interpret Tx: Ty as a measure of deviation from Fuclidean space, with both a geometric meaning and a statistical interpretation of distance between points with uncertainties.

---

We show that any imput symmetric hollow matrix D of size n can be written as the generalized power distance matrix of n points {p:} with the same radius v/eal/2 where en is the smallest eigenvalue of the Gram matrix of D. This linear algebra result may be of independent interest. Only when D is a Euclidean distance matrix, all eigenvalues are non-negative and = O. Our second result follows from applying the JL transform on the ball centers (i.e. {p:}). We obtain (1 multiplicatiie approximation of the generalized power distance with additive error of 4er
Theorem 1.3 (Power-distance
Lemma, informal Version of Theorem 3.3 Given any symmetric hollow dissimilarity matrix D of size and (0,1), there exists JL transform with target dimension m = Olog n//="), such that any pairwise distance Dij is preserved with at most 1 + multiplicative factor and an 4er² additive factor, where r /2enl/2 with en as the smallest eigenvalue of the Gram matrix of D.
To complement Theorem 1.3 we are able to extend the techniques in [9 and give lower bound of (loog n/=²) on the target dimension to achieve the multiplicative and additive factors mentioned. Note that m = (loog n===)) matches the JL lemma lower bound.
Experiments. We implement both methods of JL transform with respect to the above results and evaluate their performances on datasets. We observe that the experiment results corroborate with our theoretical results, and outperform classical JL transform consistently on non-Euclidean datasts. Our codes are on the Anonymous Githut
1.1 Related Work
Random Linear Projection and JL Lemma A nice survey on JL. transform can be found in 20
There was series of work (2122) 23 24
that studied whether the bound the target embedding
dimension JL lemma tight, starting from the original JL. paper [. and the optimality of JL. lemma
for Euclidean dimension reduction is finally established even among non-linear embeddings [19 25
In terms of algorithms, there have been developments of variants of random projections that are more
friendly for implementations 26 27
29
30)
Empirical study of JL Lemma can be found in K]
Last, Benjamini and Makarychev 32 considered dimension reduction using the Poincaré half-space model of hyperbolic space HI where each point is represented by (z, 2) with R=-1 and height 2 E RR They considered using JL random projection of on the Euclidean part and obtain (f(x),²) with ((x in Euclidean space of dimension Ollog n/ achieving + e distortion.
Data-dependent dimension reduction. number of dimension reduction techniques that are also popular in practice include Multidimensional scaling (MDS) 333 and Principal Component Analysis (PCA) 34 These methods are data-dependent and choose linear projections based on the input data. There has also been recent work trying to apply these methods non-Euclidean data, for example PCA in hyperbolic or spherical geometry [35] 36
37 [8]. Manifold learning (such as Isomap [39] and LLE [40)) considers input data points that come from a cow-dimensional manifold, recovers the distances between points along the manifold and applics existing dimension reduction methods. A recent work called Non-Euclidean MDS [18] considers dimension reduction of sseudo-Euclidess settings and minimizes the loss called STRESS (the sum of squared difference of pairwise embedding distances the input dissimilarities). It does not provide error analysis or guarantees for individual dissimilarity distortion.
Johnson-LLindentrraus Lemma in Pseudo-Euclidean space
2.1 Pseudo-Euclidean space of signature (p.g)
We consider the d-dimensional vector space IRd equipped with (p, q) bilincar form (,) where p + q d. For simplicity, we use RP- to denote Rd with the (p. q) bilinear form (.). Consider two d-dimensional (column) vectors u, RP-9, with (u,, Ug upg))) and (0), U2 ... Up.9p)
we define the bilinear norm as:
(u, v)
U:U
4
1=p+1
3

---

Equivalently, we can write (u, = u" Av with A as a d x d diagonal matrix with with the first p diagonal elements as 1 and the remaining diagonal elements as -1. For a vector u, its scalar square {u, u). For two vectors
their interval square is obtained by (u v, v).
Consider given symmetric dissimilarity matrix D IR*x,, where Dig refers to the dissimilarity measure of element i and element j. We assume that D is hallow, Dis O, and symmetric, Dij Djj. The following proposition shows that a set of vectors in the Pseudo-Euclidean space of signature (p, q) can be obtained via D.
Proposition 2.1. For any hollow symmetric matrix D, there is a symmetric bilinear form (p)p. for integers p, q and vectors ; such that Dij = (xag - 2j, Zz))
We now explain how achieve this. With an input D, we first perform centralization obtain the Gram matrix B Gram D) = -CDC/2, where C = - 7! ,,,,,, is the centering matrix and 1, is vector of ones. Since DCDC symmetric matrix, eigenvalues are real, denoted as A 2 Ao 2 ... 2 Ay. We take as the number of non-negative eigenvalues and q to be the number of negative eigenvalues. p + q = n. Further, suppose U E Raxn the orthogonal vectors, we have
B = CDCC22 U Diag(Ai, 'm))
Now can recover the coordinates of the elements as n-dimensional vectors. Specifically X is matrix of dimension n x n with the columns representing the coordinate vectors of the n points.
X = (x1, ... , = Diag( V/li,................ .......... v (An)) UT
This way, we have B p diagonal elements as either (or 0) if the corresponding eigenvalue is positive (or 0), and the remaining diagonal elements
CCDC/2 XTAX, with A
x diagonal matrix with the first
Equivalently, have
Dij (z; - x; A(x; 2z) (z. -y - xz))
That is, the dissimilarity D.j is precisely the (p, 9) interval square of I;. Zj.
If the input dissimilarity matrix D is the squared Euclidean distance matrix of points, the Gram matrix is positive semi-definite and the above procedure would recover the Euclidean coordinates { This is referred as the classical Multidimensional scaling (MDS) [33. If the input dissimilarity matrix D generalizes beyond the squared Euclidean distance matrix but remains a hallow symmetric matrix, we can still recover the coordinates so that they produce the entries in D using a general (p. q)
bilinear form. Notice that the above procedure generates coordinate vectors in dimension n..
The (p.q) sp-ace has deep connections to spacetime and special relativity theory. Specifically, the Lorentzian n-space is the vector space R" with the n--diennsional Lorentzian inner product, where the squared norm of vector u (wa, #1," Un-1) has the form |u| -n + of +... + w Thus the Loerentizan space has signature (n 1). Four-dimensional Lorentzian space is called the Minkowski space and forms the basis of special relativity. Furthermore, the collection of vectors in ==+ with Lorentzian inner product of -1 has imaginary Lorentzian length and is precisely the hyperboloid model of the hyperbolic n-space H
2.2 Johnson-Lindenstraun Lemma in (p. -spsae
We start with some notation. For a vector v = (01, u.. :ppt)) E RP-9, we will use ||u||p to denote the "(p, g)-orm (v, u) and [|v|[2 to denote the squared Fuclidean norm c. Further, we denote (()) = (v), U2 -.)))) E R² and ((4) = (up+1, Up42, Up+g) E R9, Then ||u|| p.u (1o()) [|2 - || and [|a|| = || (| I|g-
First, we will prove a Lindenn--nndesstruuss style dimension reduction by applying the JL-lemma on the p part and part respectively. The proofs in this section can be found in Appendix
Lemma 2.2. For any set of n points Ii, F1,22,.. I2....I ... in IRP-2 and E E (0, 1). there exists a map f: IRP.4 + RR a where p', q' = O(log n2/e2) such that for any i, E [n]].
|| =,
1|, 21 S [.. f(,))) S ||= x, 1|2, + =||=; - 2,
(2)
'In general, for the bilinear form A, there can also be additional r dimensions with zero as diagonal elements. in addition to elements of 1 and elements of -1. In that case + + r = d. In our writing we skipped as they do not contribute to the similarity values for ease of exposition.

---

Essentially for (p. -space we can still have similar JL-lemma, which, compared with the standard multiplicative enror but rather an additive error to
JL-lemma Eq (1). we do not have the the squared Euclidean norm. This gives us an immediate JI.-style result when ||=; æÿ Il and
||: 2y11 are constant factor of each other. Formally, we have the following statement.
Theorem 2.3. For any set of n. points 21, 21,22..... In in Re-9 and E E (0, 1), there exists a map f: IR2. + Re al, where p', o' O(logn/e2) such that for any i,j E [n].
(1 - c City 11
xyy 2yll2aa - (1f(z)) f(2))1B S (1 +1+0 Ciy)lla; - -xyll
(3)
|| li
where Cij
few remarks are in place. First, one can apply any JL-style algorithm for the and g parts, for example, by using the fast JL algorithm. Suppose fp is implemented by random matrix My'p and fy is implemented by a random matrix My Then f is implemented by a matrix M of dimension +') x (p + q) with Mp and Mg at the diagonal and zero elsewhere, f(x) Mæ. Second, random projection for the (p, q) space setting provides an error-bound guarantee for pair of points that gracefully degrades as the (p. 9) norm deviates from the Euclidean norm. Below we show few natural situations where the (p, q) norm and Euclidean norm are indeed bounded.
Lemma 2.4. Let U E RP- If each coordinate of v is selected from the same distribution, f with finite second moment, then we have with high probability, |oll < C/ if
C-1 C+1P or
C-1 I|ull2 < -C if < C+1 forr C>1
Corollary 2.5. A random vector v chosen uniformly over the unit sphere Sp+9-1 has with high probability, ||=l2 < ClIvllp.. if < CTiP.
Now we put together all of the previous results into a single statement on a set of random points in (p, 9) space.
Theorem 2.6. Let X C Rpa be randomly selected point set of size n, with q C for constant C. For all u, E X,
a-#
has distribution equal to uniformly choosing a vector on
TH-
Sptg-1. Then, with high probability, there exists map IPPa + +B''s ot p.. O c² log(n) such that for any i,j E [nz].
(1 -1- -=] - -xxxxyl =2112. S 11(())) - 1xx S (1 + e)(l,, - x 1.112.00
Johnson-Lindenstrauss Lemma for Generalized Power Distances
3.1 Generalized Power Distance
Given two balls centered at p, RRd, with radii rp; Fq. we define the generalized power distance as:
Pow((p, (p), (g, = -eplppplh a - (rp + r2
(5)
This power distance measures the distance of the internal tangents between two disjoint circles (the tangent line that keeps two circles on different sides. See the middle picture in Figure [ Note that there is another second generalized power distance between two circles centered at p; of radius r, given by [p: 121 (r) r2)² which measures the distance of the external tangents between the circles (the tangent line that keeps circles the same side).
Geometric Interpretation. In elementary plane geometry, the power of a point is a real number that reflects the relative distance of given point from given circle, introduced by Jakob Steiner in 1826.
The power of a point with respect to a circle with center q and radius is defined as ||p - g|| , This value is positive when p outside the circle, and by Pythagorean theorem it is squared tangential distance pt] where t a tangent point of to the circle. When p is inside the circle, the power is negative, and precisely the negative of squared distance (ps| where is point the circle with Apsq to be a right triangle with Zspq as 90 degree.
The generalized power distance considers the distance between two circles and reduces to the classical power distance if one of the circles a point. Furthermore, two circles are disjoint and only if their generalized power distance is positive. In this case, their generalized power distance is equal to the
5

---

1p
Pa
F4 9
P1a
p
Pp
2
p q (rp + riy)
Figure 1: Left: power distance from a point to ball at of radius ry Middle: power distance between two balls at points y with radius rpp and respectively; Right: Casey's Theorem.
square of the distance between the two tangent points on the common internal tangent line between the two circles (with the two circles on different sides). See Figure for examples. The generalized power distance can be called power distance of weighted points with rp as the weight pf
There are several interesting properties of the generalized power distance. First, the Casey's 's the- orem 42 43 still holds for generalized power distance. That is, if four circles in the plane are langent to the fifth circle, then the generalized power distances P.j. i,j E {1, 3, 4}. between them satisfy the Ptolemy identity P12P34 P23Pa P1aP24. This Ptolemy identity plays a key role in applications of the generalized power distances. Indeed, the Ptolemy identity and the associated Ptolemy inequality Pi2P34 + P1 2 P1sP2s have been used in optimization and approximation for prune search space and optimize geometric networks, for approximate distance estimate, circle fitting and cyclic polygon detection; in distance geometry for ensuring distance constraints for sensor networks [44] and molecule reconstruction 45). In metric geometry [46]. metric space is called Ptolemaic space if Ptolemy inequality holds for any quadriple points. It is well known that Euclidean space and any inner- manrr-prouctt spaces are Ptolemaie and normed vector space is Ptolemaic if and only if the norm comes from an inner product [4 48). Furthermore, a Riemannian manifold is a Ptolemaic space if and only if its sectional curvature is non-positive [49]. It shows that Ptolemy inequalities can be used for studying curvature properties of metric spaces. Recall that a length space (X, d) is Gromov 5-hyperbolic if it satisfies Gromov's 's Four-Poil Point Condition: for any 2; y, 2, w E X, d(x, 2) + d(y, w) I max d(xxz) y) + d(2, w), d( w) + d(y, 2)} + 28. The Ptolemy inequality is another four-point condition on metric spaces for investigating curvature of general spaces (50)
Any Symmetric Dissimilarities are Power Distances. Now, we show that any symmetrie hollow dissimilarity matrix can be written as the matrix of power distances between weighted points.
Lemma 3.1. Given any n. X n. symmetric hollow dissimilarity matrix, D, we can rewrite D
E + 2T - J) where r E RR,, E is Euclidean distance matrix, I is an n x n. identity matrix, J J= 1, More specifically F. is a Euclidean distance matrix if and only if 2r " leal where en, the least eigenvalue of Gram(D).
From Theorem 3.1 suppose E is an Euclidean distance matrix where the (i, element is [|:; - Py ||2 with n points {Ps Then D is the matrix of generalized power distances ((pi, r)), i.e., with the (1,j) element as ||p: 123 - 2 Here all the weighted points have radius r which can be seen as a measure of how far the input matrix D is away from being Euclidean. When D is a Euclidean distance matrix, the Gram matrix Gram( D) is positive semi-definieg and the smallest eigenvalue is and the generalized power distance reduces the squared Euclidean distance. When D is no longer a Euclidean distance matrix, Gram D) necessarily have negative eigenvalues, i.e. 6n O. This makes r to be non-trivial.
en = O. Thus
Statistical Interpretation The generalized power distance also has a statistical interpretation using the silhouette coefficient [51], which measures how similar two clusters are. Consider two clusters X, Y, the silhouette value of a point x E X is the average distance from x to points in Y minus the average distance from x other points in X. The silhouette coefficient of the two clusters X, Y is the average of the silhouette coefficient of all points in X, Y. In Appendix A we show that the silhouette coefficient of two Gaussian distributions X N(uu Jx),y' N (Py σy) is SCw (X.)) = || Myl 2 (az + oyy Notice that this is precisely the generalized power distance of weighted points (/an ) and (My. a.))
Therefore, Theorem 3.1 suggests that any input dissimilarity matrix D that is hollow and symmetric is actually the silhouette coefficients of n Gaussian distributions centered at {p:} with variance r which is given by Theorem 3.1 Note that this statistical interpretation resonates with prior literature [3

---

which identified that one major source of data in non-Euclidede geometry is due to measurement noises and uncertainties.
3.2 Johnson-LLnndentrrauss Lemma for Power Distance
Lemma 3.2. Given n weighted points (px, r;) with p; E (R", there exists a map f :. RR, where m Ollog n/E") such that for any + E [n].
(1 Pow(Ppoopp (p), (p),r,))
=(r; t,y)² < Pow((f(p:), r.), (f(ps).rz)
(6)
(1 E) Pow rı). (p), e(ri r,)². (7)
With Lemma 3.1 and Lemma 3.2 we immediately have the following.
Theorem 3.3. Given any
symmetric hollow dissimilarity matrix, D, with power distance representation by (p:,r)) where
v/em./2 and en is the smallest eigenvalue of Gram(D) J/n and J is all 1 matrix, there exists map f R - R", where
DC with C Ollog n/c²) such that for any + [n].
=)) (ow((ps,r)) (Pj,r)) =4r²
$ (1 +) Pow (P.. (p,, E4r
Last, we remark that the error bounds in Lemma 3.2 also imply 1 distortion for dimension reduction on the Euclidean distances of the centers (as in the JL Lemma D.. Therefore, the lower bound on the target dimension being (2logg n/s") for dimension reduction algorithm satisfying the error bounds in Lemma 3.2 for generalized power distances holds, by the same argument in the proof of dimension optimality standard JL-lemma [19.
4 Algorithms for Non-Euclidean Johnson-LLnndessrraus Transforms
The algorithms used for the experiments are presented as follows. In both cases we assume an input dissimilarity matrix D which is symmetric (D,j Dj:)) and hollow (D, 0).
JL Transform
1. Find the orthogonal decomposition of the dissimilarity matrix D OAOT where a diagonal matrix of the eigenvalues.
2. Let A be the (p, g) signature, i.e. A = sign(A)
3. Compute the the embedding into R2.9 by finding VAVT,
4. For each point x in the embedding, split it into (P) and (1)), Use standard JL transform to project into RR' and I& respectively where p' and g' are the specified target dimension.
5. Return the projected points (z.00), ,(('') along with their (p',9') signature.
Power distance JL Transform
1. Find the orthogonal decomposition of the dissimilarity matrix O
2. Compute e,, the smallest eigenvalue of Gram(D). Set r = Vlem./2.
3. Add 4r² I) to D obtain the new Euclidean distance matrix, E.
4. Recover the Euclidean coordinates X' such that Esg ||~| 2/11². Perform standard JL transform X' to target dimension m.
5. Return the projected points along with their radii r.
Computational efficiency. Since both methods start with dissimilarity matrix we necessarily need to recover the 'coordinates' first. This can be done by running the singular value decomposition
7

---

(SVD) on the Gram matrix in (nn)) time. There are several possible ways to speed up this step in practice by using landmark MDS for example. Another approach, motivated by the generalized power distance formulation, is to consider appending a proper term 4y to the input matrix 7) and later use the power distance with the recovered coordinates. it happens that the coordinates are to be learned from a representation learning module, we can skip this part and directly apply dimension reduction. When applying standard JL transform we use random projection of Gaussian vectors. One can use any JL transform for example [26] 27
28 29
30 for this purpose.
5 Experiments
In this section, we present experimental results of the proposed JL transforms in non- Euclideen settings with only dissimilarity matrix as input. First, we validate our theoretical results by showing the approximation error on datasets that are highly non-Euclidean. Next, we evaluate the algorithms on real-world datasets, with the classical JL. transform as a baseline. Finally, we test the proposed JL transforms downstream task, k-means clustering, to show its potential wide applications.
Datasets. We use two synthetic datasets that are made non-Euclidean: Random- mampolxsimppex and Euclidean-ball. At a high level, for the Random-simplex, given a dataset of size n, each point is constructed such that its first 1 coordinates form a simplex, while the final coordinate dominates the pairwise distances. This design induces large negative eigenvalue in the Gram matrix. The Euclidean-bail dataset, inspired by Delft's balls [53] consists of n balls with varying radii. The distance between two balls is defined as the minimal distance between any two points on their surfaces, resulting dissimilarities that violate the triangle inequality. For real-world data, We consider three categories: genomics, image and graph data. The genomics data includes three cancer-related datasets from the Curated Microarray Database (CuMiDa) (54). Following the practice prior work (T8), we obtain dissimilarities with entropic affinity. We also test two celebrated image datasets: MNIST and CIFAR-10, each with 1000 images randomly sampled. We use the measures mentioned in (55) to caleulate the dissimilarities. The graph datasets are selected from the SNAP project [56]. The pairwise distances are shortest path distances. The basic statistics of all datasets are shown in Table We defer more details in Appendix C
Dataset
Simplex
Ball
Brain
Breast
Renal
MNIST
CIFARIO
Email
Facebook
Monc
Size
1000
1000
130
151
143
1000
1000
986
4039
7047
# (A
0}
900
887
53
59
57
454
399
465
1566
268
Metric
x
x
X
X
/
/
Table 1: Non-Eaclideann/Non-merri Datasets used in experiments
5.1
Validation of Theoretical Results
Eseudo-Euclident JL Transform. We start with demonstrating the multiplicative factor of pscudo- Euclidean projection indeed falls into the range of = Cit), corroboration of Theorem 2.3 Throughout, we set = 0.5 and the constant in the target dimension O n/(²)) as 2. Figure 2 verifies the approximation ratio on the Simplex and Brain datasets. We observe that most pairwise dissimilarities behave as claimed. For the Brain dataset, even the bar range is very small we still have all green points. There are minor exceptions indicated by the red points in the Simplex dataset. However, first observe that they are still very close to the error bars. Further, we did not optimize the constant factor in Olog n/)")). In fact, we double the target dimension (from 80 to 160), the percentage of violations drops significantly from 12.01% to 4.62% for the Simplex dataset. We defer the plots of other datasets to Appendix
Power Distance JL Transform. To validate Theorem 3.3 we show the residual additive error of the power distance JL transform. By 'residual' we refer to the absolute difference between the dissimilarities given by the JL transform and the (1 = =) approximation of the true dissimilarities. This term should be smaller than 4er?. As shown Figure all sampled points appear below the red line, which is taken as (r(r/000) much tighter upper bound. Recall that a larger r indicates more deviation from Fuclidean geometry, the fact that the residual error is small shows the effectiveness of our JL transform. We defer the plots of other datasets to Appendix C
8

---

Pauado-Est Mean Prgection Aeudis Jiper Lower Bounds umzho Outanet
Caciidaa & Projctionn feult with Upper Lower Sourch Exteet
Nerionaa sertng
The left is for Simplex dataset and right for the Brain dataset. Green points indicate the approximation ratio is within the range and red the opposite. The error hars match the upper and lower bounds given by + .Cy). We sample 20 pairs of dissimilarities for presentation.
Figure 2:
Power Distance Projection Residual Additive 1epe1n1000033
Power Distance Projection Res dual Additive Erro for CIFAR-10 Dataser
Sampli viliis
Saugleel vakies
Sempled pair
10C
Samples
Figure 3: The left is for MNIST and right for CIFAR-10 10 dataset. We sampled 100 pairs of dissimilarities and r for presentation. Using the original makes the red line roughly y 40000, which is very loose.
5.2 Performance of JL Transforms
Performance on Relative Error. We compare two proposed JL transforms with the classical JL transform on all datasets and report the relative error, which is defined as the maximum among [., D.. for all (i.j) pairs. D.j is the dissimilarity matrix obtained from any JL transform. It is Di;
suitable metric because all three algorithms have different theoretical guarantees, but the end goal is always preserving pairwise dissimilarities. In Table 2 show the worst-case (defined above) average and median relative error. A smaller value indicates better performance.
We observe JI.-PE performs the best for genomics data and Joopow performs the best for the rest, on both metrics. The significant improvement implies when the JL. transform matches with geometry, we can expect really good results. The image datasets report inf for JL because different images are projected to the same point. In a few cases JI-PE has slightly worse relative error than JL, but note that this might be the outcome of really large factor C, which the performance of JL-PE is based on.
Method
Simplex
Ball
Brain
Breast
Renal
MNIST CIFAR
Email
Facebook
MOOC
IL Max
6.47c5
5.97e5
L.0e12
7.09c10
3.42e12
inf
inf
3,85e4
1.1866
2.94e5
JL-PE Max
1.1c6
5.31eS
8,21e4
262.20
2.37e4
8.47c5
2.24c6
3.24c6
2.51e7
1.35e7
JL-Power Max
109.18
12.102
3.11c7
1.9266
1.17c8
85.76
55.74
781.45
82.74
24.22
JL Ave
442.65
43.78
1.1
9.86c7
1.50c9
inf
inf
15.64
12.62
39.83
JL-PE Ave
47.59
23.71
8.16
1.15
6.60
15.93
18.24
13.79
52.52
63.44
JI. Power Ave
13.52
1.002
3.73e4
3.12e3
5,57e4
1.47
1.61
1.60
1.32
2.04
Median
6.36
6.68
2.69e12
1.95e11
1.18e12
1.78
2.29
7.00
5.08
6.13
JL-PE Median
2.57
2.78
1284.06
174.74
3160.58
2.11
2.04
2.06
5.83
6.03
JI. Power Median
12.79
1.00
1.01e7
8.20e6
7.57c7
1.30
1.35
1.35
1.16
1.99
Table 2: Max and Average Relative Error of All Datasets on Three JL Transforms.

---

Performance on Downstream k-Means Clustering, We now evaluate if the propsoed JL transforms consistently perform well on downstream tasks. The setup is straightforward: we first apply JL transform to reduce the dimension of the original data, then we compare k-Means clustering cost. obtained from the processed data with the original optimal clustering cost.
Datasct
#Clusters (k)
Original
JL
JL-pq
JL-power
Brain
5
3.92
10
728.00
3.13
33.26
Breast
4
827.69
28.93
12.53
Email
42
5614
22634
21244
20764
Facebook
15
20499
284142
91644
303203
Table 3: Performance of Three Transforms with k-MMans Clustering.
Table demonstrates that both of the proposed JL transforms outperforms the classical JL. with only one exception on Facebook where JL-power is slightly worse than JL. This observation shows better effectiveness of the proposed JL transforms in downstream tasks. However, similar as above, the relative performance varies between JL-ppq and JL-power. This raises key direction for future research: formalize the conditions under which a specific transform is most suitable.
Discussions
The Pscudo-Euclidean space study shares conceptual foundations with recent advances in similar- ity learning. Notably, [57] proposed neural similarity learning (NSL) which uses bilinear matrices to generalize inner product similarity in convolutional neural networks through both static and dynamic approaches. The bilinear form structures also appear in modern neural architectures [58]. In the scaled dot-product attention mechanism used in transformers, the attention score between two tokens is computed as a bilinear form: score(g, k) q Wk, where and k are query and key vectors and W is learned weight matrix. This mechanism effectively learns similarity function the token space, which aligns with our use of bilinear forms to represent pairwise dissimilarities in non-Fuclidean geometry.
Future Direction. A promising future direction is to integrate the mathematical formulation in this paper using both the pseudo-Euclidean representation and the generalized power distance representation with current machine learning pipelines for representation and similarity learning. Recently there has been increasing interest in representation learning
non-Euulidean spaces, e.g.,
learning modules in hyperbolic [59 60
63 64 65], spherical or mixed-cuu -ixed-curvature product manifolds (Cartesian products of hyperbolic, hyperspherical and Fuclidean manifolds) [35] 66 67 68
61
62
or general manifolds [69] Many of the prior work assume (piecewise) constant curvature in the embedded space and setting includes these spaces and beyond. One limitation of current work is we are not able to build a theoretical connection between two proposed representations, or conditions that one outperforms the other. Further, we not aware of any lower bound result complementing the fine-grained JL guarantee from the Aecudo-Euclidean representation.
Transform in the -un-ddelde setting with dissimi- larity matrix as the input. Via two different approaches, pseudo-Euee Euclidean geometry and generalized power distance, first gives a fine-gre grained error analysis and the second has an extra additive error term, both having parameters indicating the deviation from Fuclidean geometry. The experiment results corroborate with our theoretical results, and demonstrate the superior performance of two proposed approaches for Jl-type dimension reduction with Euclidean data.
Conclusion.
We explore
show two theoretical results with similar flavor to the classical JL lemma. The
7
Acknowledgements
The authors would like to acknowledge funding from IIS 262922297 DMS-2220271, DMS-231 1064, TRRCNS-2204444 CCF-2118952 and C55-2515159. The authors would like thank Hongbin Sun for helpful discussions.
10

---

References
[1] William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26118--20):,, 1984.
[2] Piotr Indyk and Assaf Naor. seneess-neighborrpeeeeiiiii embeddings. ACM Trans, Algorithms, 3(3):31-es, August 2007.
[3] Mert Pilanci and Martin J Wainwright, Randomized sketches of convex programs with sharp guarantees. IEEE Trans. Inf. Theory, (1(9))5096-5111 September 2015.
[4] Konstantin Makarychev, Yury Makarychev, and Ily P. Razenshteyn. Performance of Johnson- Lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51 Anmual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1027-1038, 2019.
[5] Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for Wasserstein barycenter. Advances in neural information processing systems, 34:15582-15594, 2021.
[6] Shyam Narayanan, Sandeep Silwal, Piotr Indyk, and Or Zamir. Randomized dimensionality reduction for facility location and single-linkage clustering. Proceedings of the 38th Inter- national Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Research, pages 7948-7957, PMLR, 2021.
[7] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Linndenstraus lemma. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 1039-1050, New York, NY, USA, 2019. Association for Computing Machinery.
[8] William B Johnson and Assaf Naor. The Linienn-Lindessttauss lemma almost characterizes Hilbert space, but not quite. Discrete & Computational Geometry, 43(3):542-553, 2010.
[9] Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. simple proof of the restricted isometry property for random matrices. Constructive approximation, 28:253-263, 2008.
[10] Amos Tversky and Itamar Gati. Similarity, separability, and the triangle inequality. Psychol. Rev,, 1222)1123-154, March 1982.
[11] Jifí Matoušek. On variants of the Johnson-Linndensrraus lemma. Random Struct. Algorithms, 132 September 2008.
[12] James R Lee, Manor Mendel, and Assaf Naor. Metric structures in &; dimension, snowflakes, and average distortion. Eur. J. Comb., 26(8):1 11 180-118111 190,, November 2005.
[13] Gideon Schechtman. Dimension reduction in 1p. 0 < < 2. arXiv [math.MG]. October 201 1.
[14] Assaf Naor, Gilles Pisier, and Gideon Schechtman. Impossibility of dimension reduction in the nuclear norm. Discrete Comput. Geom., 63(2)311--34, March 2020.
[15] Bo Brinkman and Moses Charikar. On the impossibility of dimension reduction in é, J. ACM, 52(5):766-788 September 2005.
[16] Lev Goldfarb. unified approach to pattern recognition. Pattern Recognition, 1765)5575-582,
1984.
[17] Elzbieta Pekalska and Robert P. W. Duin. The Dissimilarity Representation for Pattern Recogni- tion: Foundations And Applications (Machine Perception and Artificial Intelligence). World Scientific Publishing Co., Inc., USA, 2005.
[18] Chengyuan Deng, Jie Gao, Kevin Lu, Feng Luo, Hongbin Sun, and Cheng Xin. Neue-MDS: Non-Euclidean multidimensional scaling through bilinear forms. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS 2024), volume 37, pages 121539-121569, December 2024.

---

[19] Kasper Green Larsen and Jelani Nelson. Optimality of the BaanssnnLLndenstruuss lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 633-638, 2017.
[20] Jelani Nelson. Dimensionality reduction in Euclidean space. Not. Am. Muth. Soc., 67 November 2020.
[21] Noga Alon. Problems and results in extremal combinatorics i. Discrete Math., 273(1-3):1--53, December 2003.
[22] Daniel Kane, Raghu Meka, and Jelani Nelson. Almost optimal explicit Johnson-Linden Lindenstrauss families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Lecture notes in computer science, pages 228..39.00 Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
[23] TS Jayram and David P Woodruff. Optimal bounds for streaming problems with subconstant error. ACM Trans. Algorithms, 9(3):1-17, June 2013.
transforms and
[24] Kasper Green Larsen and Jelani Nelson. The Johnson-Lindensttrauss Lemma is optimal for linear dimensionality reduction. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informaties (LIPlcs), pages 82:1-82:11, Dagstuhl, Germany, 2016. Schloss Dagstuhl Leibniz-Zentru für Informatik.
[25] Noga Alon and Bo' az Klartag. Optimal compression of approximate inner products and dimension reduction. In 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pages 639-650. IEEE, October 2017.
[26] Dimitris Achlioptas. Database-friendie random projections: Johnson--Lindenstrauss with binary coins. J. Comput. Syst. Sci., (6(4))671-687 June 2003.
[27] Nir Ailon and Bernard Chazelle. The fast Linnstnn transform and approximate nearest neighbors. SIAM J. Comput.. 39(1):302-322, January 2009.
[28] Anirban Dasgupta, Ravi Kumar, and Tamás Sarlos. A sparse STOC 10, page 341-350, New York, NY, USA, 2010. Association for Computing Machinery.
transform.
[29] Rong Yin, Yong Liu, Weiping Wang, and Dan Meng. Extremely sparse Londesn-Lindenstrauuss transform: From theory to algorithm. In 2020 IEEE International Conference on Data Mining (ICDM), pages 1376-1381 IEEE, 2020.
[30] Daniel M Kane and Jelani Nelson. Sparser Shanson-Lindenstrauss transforms. J. 61(1):1-
23, January 2014.
[31] Suresh Venkatasubrane aankatasubramanian and Qiushi Wang. The Johnson-LLndenstraane transform: An empirical study. In 2011 Proceedings of the Thirteenth Workshop on Algorithum Engineering and Experiments (ALENEX). pages 164-173. Society for Industrial and Applied Mathematics, Philadelphia, PA, January 2011.
[32] Itai Benjamini and Yury Makarychev. Dimension reduction for hyperbolic space. Proc. Am. Math. Soc., 137(02):695-69) (69, September 2008
[33] Warren S Torgerson. Multidimensional scaling: I. Theory and method. Psychometrika, 17(4):401-11, December 1952.
[34] Karl Pearson. LIII. on lines and planes of closest fit to systems of points in space. Lond, Edinh. Dublin Philos. Mag. J. Sci., 2(1 ((1))559-572, November 1901.
[35] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature represen- tations in product spaces. 7th International Conference on Learning Representations, ICLR 2019, New Orleans. LA, USA, May 6-9, 2019. OpenReview.net, 2019.
12

---

[36] Ines Chami, Albert Gu, Dat P Nguyen, and Christopher Re. HoroPCA: Hyperbolic dimen- sionality reduction via horospherical projections. Marina Meila and Tong Zhang, editors. Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 1419-1429, PMLR, 18-24 Jul 2021.
[37] Puoya Tabaghi, Michael Khanzadeh, Yusu Wang, and Siavash Mirarab. Principal component analysis in space forms. IEEE Trans. Signal Process., 72:4428 0222884443,200 2024.
[38] Xiran Fan, Chun- Hao Yang, and Baba C Vemuri. Nested hyperbolic spaces for dimensionality reduction and hyperbolic NN design. Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit, 2022:356-365, June 2022.
[39] Joshua B Tenenbaum. A global geometric framework for nonlinear dimensionality reduction. Science, 290(55000:2319-22222 2000.
[40] Sam T Roweis and Lawrence K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323 2326,, 2000.
[41] John G Ratcliffe. Foundations of Hyperbolic Manifolds. Springer International Publishing, 2006.
[42] John Casey. On the equations and properties: (I) of the system of circles touching three circles in plane; (2) of the system of spheres touching four spheres in space; (3) of the system of circles touching three circles on a sphere; (4) of the system of conics inscribed to a conic, and touching three inscribed conics in a plane. Proceedings of the Royal Irish Academy (1836-180) 1869), 9:396-423. 1864.
[43] Arnold Emch and Julian Lowell Coolidge. A treatise on the circle and the sphere. Am. Math. Mon., 24(6):276, June 1917.
[44] Pejman Khadivi. Adaptive distance estimation and localization in wireless networks with triangle and ptolemy inequalities. In 2010 IEEE 4th International Symposium on Advanced Networks and Telecommunication Systems, pages 88-90. IEEE, December 2010.
[45] Gordon M. Crippen and Timothy F. Havel. Distance geometry and molecular conformation, volume 15 of Chemometrics Series. Research Studies Press, Ltd., Chichester; John Wiley & Sons, Inc., New York, 1988.
[46] Dmitrij Jurévič Burago, Jurij D. Burago, and Sergej Ivanov. A course in metric geometry. Graduate studies in mathematics 33. American Mathem. Soc., Providence, RI, 2001.
[47] IJ Schoenberg. On metric ares of vanishing menger curvature. Ann. Math., 41(4):715, October 1940.
[48] I Schoenberg. A remark on M. M. day's characterization of inner-product spaces and conjecture of L. M. blumenthal. Proc. Am. Math. Soc., 3(6)99119944, 1952.
[49] S. M. Buckley, K. Falk, and D. J. Wraith. Ptolemaic spaces and CAT(O). Glasg. Math. J., 51(2):301-314 2009.
[50] Thomas Foertsch, Alexander Lytchak, and Viktor Schroeder. Nonpositive curvature and the Ptolemy inequality. Int. Mathem, Res. Not., 100mmm000-rmm1 100, July 2010.
[51] Peter Rousseeuw. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math., 20(1):53-65, nov 1987.
[52] Weiping Xu, Richard C Wilson, and Edwin R Hancock. Determining the cause of negative dissimilarity cigenvalues. In Computer Analysis of Images and Patterns, pages 589-597. Springer Berlin Heidelberg, 2011.
[53] Robert P W Duin and Elžbieta Pękalska. Non-Euclidean dissimilarities: Causes and informa- tiveness. In Structural, Syntactic, and Statistical Pottern Recognition, pages 323-333. Springer Berlin Heidelberg, 2010.
13

---

[54] Bruno Cesar Feltes, Eduardo Bassani Chandelier, Bruno lochins Grisci, and Márcio Dorn. CuMiDa: an extensively curated microarray database for benchmarking and testing of machine learning approaches in cancer research. Journal of Computational Biology, 26(4):376-366 2019.
[55] Rishi Sonthalia, Greg Van Buskirk, Benjamin Raichel, and Anna Gilbert. How can classi- cal multidimensional scaling go wrong? In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12304-12315, 2021.
[56] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http::/snap. http:///saap...affff...o. stanforddd.........
edu/data, June 2014.
[57] Weiyang Liu, Zhen Liu, James M Rehg, and Le Song. Neural similarity learning. Neural Inf Process Syst, abs/19100 13003, October 2019.
[58] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, page 6000-6010, 2017.
[59] Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. In Proceedings of the 31 International Conference Neural Information Processing Systems, NIPS' 17, page 6341-6350, Red Hook, NY, USA, 2017. Curran Associates Inc.
[60] Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, and Nando de Freitas. Hyperbolic attention networks. In International Conference on Learning Representations, 2019.
[61] Octavian Ganea, Gary Becigneul, and Thomas Hofmann. Hyperbolic neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[62] Alexandru Tifrea, Gary Becigneul, and Octavian- Eugen Ganea. Poincaré glove: Hyperbolic word embeddings. In International Conference Learning Representations, 2019.
[63] Christopher De Sa, Albert Gu, Christopher Ré, and Frederic Sala. Representation tradeoffs for hyperbolic embeddings. Proc. Mach. Learn. Res., 80:4460-4469, 2018.
[64] Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th An- nual Meeting of the Association for Computational Linguisties, Stroudsburg, PA, USA, 2020. Association for Computational Linguistics.
[65] Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Adv. Neural Inf. Process. Syst., 32:4869-4888, December 2019.
[66] Sharon Zhang, Amit Moscovich, and Amit Singer. Product manifold learning. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pages 3241-3249 PMLR, 13-15 Apr 2021.
[67] Daniel McNeela, Frederic Sala, and Anthony Gitter. Product manifold representations for learning on biological pathways. arXiv 2401.15478, 2025.
[68] Philippe Chlenski, Kaizhu Du, Dylan Satow, and Itsik Pe'er. Manify: A python library for learning non-euclidean representations. arXiy 2503.09576, 2025.
[69] Max Aalto and Nakul Verma. Metric learning on manifolds. CoRR, abs/1992.01133, 2019.
[70] Leonard Kaufman and Peter J. Roussceuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley, 1990.
[71] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1), 2007.
14

---

[72] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '19), pages 1265-1275. ACM, 2019.
[73] Julian McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In P. L. Bartlett, F.C.N. Pereira, C.J.C. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems 25 (NIPS 2012), pages 539-547, 2012.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims in the abstract and introduction reflect the contribution of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The introduction mentioned two issues defining the scope of the work. First, for non-Euclidean data there are strong lower bound on dimension reduction (even with nonlinear projections). Therefore, our work cannot bypass the theoretical lower bound. Nevertheless, we provide fine-graines analysis which does not contradict with the strong lower bound yet provide meaningful results with performance characterized by parameters measuring the deviation scope of the paper is to study the conditions performance and effectiveness of JL- style dimension reduction and we leave out the integration with existing machine learning pipelines future work.
the input data from Euclidean geometry. Second, the main
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
15

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All proofs are included with the paper or in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All datasets and parameters for evaluation are included in the paper or Ap- pendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
16

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification; All data source and code are made available either in the paper supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7/nips. //nips.cc/publl.. wttpc//gg///////eeocoooccc hubblic/ggiddss//deeuubiiii wwweesuubmisssooPPe.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All data and parameters for experiments were included in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
17

---

Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The reported enror is straightforward, either multiplicative or additive factors.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the information in the appendix experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp////eorrpp..cc///bbb///iie
Answer: [Yes]
Justification:
We reviewed the code of ethics and the work in this paper conforms to the
code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
18

---

10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discussed the potential benefit of using the dimension reduction technique proposed in this paper for speeding up machine learning for non-Euclidean data.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: N/A
19

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
20

---

Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is required.
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy httc:p////oourpsssscooooeeeeeeee for what should or should not be described.
21

---

A Relation of Generalized Power Distance to Silhouette Coefficient
The silhouette coefficient [51] a measure of how similar an object its own cluster compared to other clusters. The silhouette coefficient ranges from -1 to I, where a high value indicates that the object well matched its own cluster and poorly matched to neighboring clusters. If most objects have a high value, then the clustering configuration is appropriate. If many points have low or negative value, then the clustering configuration may have too many or too few clusters.
For simplicity, let us consider two clusters of finite points X,Y S C.T with X = Y = n. The classical silhouette coefficient (in two clusters) be defined follows: For each point E X, define "inner distance" a(x:) as the average distance between æ and all other points in the same cluster, and "cross distance" b(x:) the average distance between x: and all points in the other cluster Y. That is:
a(x)
d(x,,²')
(8)
Z'E,
b(z)
d(z, y)
n yEY
Then, the silhouette coefficient for point æ E X is defined as:
b(x) - a(x)
((x)
Norm(a(z))b(ea) b(x))
and the silhouette coefficient for the cluster X is defined as the average of the silhouette coefficients for all points in the cluster:
5 ((X)
Σ 5(z).
ZEX
Here the denominator Norm is a normalizing function which is usually chosen to be Norm(a(z), b(x)
max{a(>), b(x) for the classical silhouette coefficient make sure the range lies in -1,+11, The silhouette coefficient can be used to measure the quality of a cluster. For the overall clustering, the average silhouette coefficient scores over all clusters can be used to measure the quality of the whole clustering results (70).
Now interested in using a similar idea to study the dissimilarity (divergence) between two probability distributions, say two Gaussian distributions naturally view the two distributions as clusters. Here interested in the "silhouette coefficient score" of the whole clustering.
[N o2), = (My, (My.,,)) σy). We
To better analyze the "silhouette coefficient score" between two Gaussian distributions, we consider an unnormalized version the silhouette coefficient. For any x X, let
a(x) = Ex - x 1|
b(x) = Ey~-y || y/
sX' E [b(x) c az))
where e 2 1 is constant parameter used as a trade-off balance between inner distance and cross distance. Now can define (unnormalized) silhouette score between two Gaussian distributions X' and y as:
SC(X))) A ) [x(X)+
E (b(x) c. a(x)] + Ey-y(b(u) - c- c-vlll]]
Exyxxxx ||| y||3| (Bu,wwalle 1111 + B By.wrrllyy ----y'l y'(13)
Based on properties of Gaussian distributions, we could calculate:
SC(X' ||ma 1 (c 1)(0
In general, we could consider a silhouette score between two Gaussian distributions composed with two parts balanced with each other:
22

---

1. Some distance (I 3" measures the similarity between the two distributions.
2. Some negative terms A represent the variances of the two distributions themselves.
Here we consider the following construction of silhouette score between two Gaussian distributions we are interested in: Let A _ > [||=
SCw (x.3) _ DIS (A - (A[X) + A(D1)
(10)
1| Myy 11 + (o= ,²)) 2 + +
(11)
|| Myy 1| (o, + o,y²
(12)
where DISW is the squared 2-Wasserstein distance. This construction is interesting because it is consistent with our construction of generalized power distance, which brings up a potential statistical interpretation.
Normalized Silhouette Score One could also define a normalized version of the Silhouette Score. In general, it could be defined as:
DIS - C. C. (4[X) + + Norm (orm(Dis;(X,))), C (A[X) A(D)
)C(X))) &
(13)
with some normalizer function Norm().
For example, we could define the normalized version SCw as:
| Myll (o, + ,,)
SC wC
(14)
Pz Myll 2 + (ox + o,)²
The range of SCw is [-1, Intuitively, it be used measure how well two Gaussian distri- butions are separated. When these two Gaussian distributions have very close centers or very large variances, the normalized silhouette score is close to -1, which means sampling from these two distributions has low chance of being well separated. It becomes -1 when they are identical X' = y. When these two distributions are far away or variances are very small, the normalized silhouette score is close to 1, which means sampling from these two distributions enjoys high chance of being well separated. becomes +1 when these two distributions are delta distributions on distinct center points. Zero represents borderline cases. We set it to be -1 for Pa My and o₂ Jy = 0.
B
Missing Proofs in Section 2 and Section
B.1 Prool's in Section 2
Proof of Lemma We apply the standard Johnson-Lindenstraute lemma to the collection of points {x(P)) and {o separately. By Eq (1) there are two random projection fz fg R + Rd with p',q' O(log n/e²) such that for any + j.
R
R and
(1-s)
- |2 (m) 1 1 S [1))(x()) - fn(aa))) (1 < (1 + e)(l - (1)
(1 (1-=) =|| - 20 1 S - )1 < (1 + ))(l,((0 2 1/
Now we can bound the ( -ormm of the vector under projection f which produces f(x,) (Jp(a,), (xx))) of dimension p' + v'.
[[((z)) - f(x))) = (f,(( - (=;)( -1
S (1+ (1+s)]lz(?) -
21"² 1| - 1 -11-)) xz 12
| 2lbl +ellx; 13
The other direction is similar.
Proof of Lemma 2.4 Consider the variables ||0||2/ / (p + 9) and |||||| || / + 9). Let == 2o and using Central Limit Theorem implies that [|<]]///(p + q) and ||ul|2_ (p + q) will converge to their means which are and p respectively. Plugging in g-1 and C419 give what want.
where X is random variable with distribution f. Taking p
23

---

Proof of Theorem 2.6
We may first write the uniform distribution over the sphere as Y where each Y; (0, 1). Then the distribution of ||u-el| ||--
Yi
y will be:
VE. y
E Y Σ 2impt1 Y?
Σ Y?
Now E/= y is just chi-squared random variable with + degrees of freedom. A common known concentration inequality is:
12x22 E (1 + +)) 2 1 2e- - (56
On the other hand, Ei=1 Y? Eptg Y?² has mean p - 9 and we have the following concentration inequality:
P(x² E (p 2) + (p + 9)) 2 1 - 2e (20---66
since Σ (1 (p + 9) implies Σ Y?² Ex=pt1 Y? + + q). The C-1 greatest error ratio clearly is bounded by q C+1 p and at:
(L (L+ 9)
p P-q
2pC(1+ +1
2
( () -60pp + 9) p
+
1-250
E Y?2
p p 2BC
2 2 -6-
P Σ Y Epto Y?
(
25C
Now let 8 10+2+e0.
EPtey? Y? E Y? Eipt Y?
P
E (1+
9 5 9 2 p 9
2 2e (0-0((t)))10)) 2=0
The last inequality comes from the fact that our target dimension is O log(n)/(2), so we can make the assumption + > O log(n)/2). From a union bound, then we have with high probability, -u- gives the error bound:
|| S xC(1+ + 5) Then, we can use Theorem 2.2 with input e' e/(2C) which
I1/(x:) - [(=))) S ||: - 22112. +
||:
(15)
2C
|| xy 112.0
+
C(1 "]1|z: 23 11
(16)
20
2
||= 2y112.1 + ( + )||:; xz 12.4
(17)
2
S (1 + )), - Iz 12
(18)
(19)
n
B.2 Proofs in Section
Proof of Lemma 3.1 We begin by finding the Gram Matrix of E = D - -r - J). Recall that the centering matrix C' = I J. The Gram matrix of E is
-CCC=--Cc --C - 4 --C + -2
1 CEC = -
1 _
CDC +22C. 2
2
n symmetric and positive semi-definite. C' has a single eigenvalue of 0 with 1, as its eigenvector. We see that Gram(D) = 2 CDC and C' share that eigenvalue and eigenvector. The rest of the eigenvalues of C are 1. Then, the eigenvalues of Gram E.) are exactly 2r added the eigenvalues of Gram (D). Thus, it is clear all of its eigenvalues are greater than equal to zero as long as 2r > len]
Here we use the fact that C(I - J) C and C² C. Further,
L
24

---

Proof of Lemma 3.2 We apply the standard Johnson-Lindensse Lindenstraass Lemma on the centers of the
power distance representation {p:} with random projection F R By Eq (1) we have
Pow((f(p),rt) (f(p)) = (15(p)) - -(p;)) (r)+
< (1 + ->)p -
(ri+ ry)²
= (1 Pow((o,))))) (p)) + E(r: try)²
The other direction is similar.
C
Additional Experimental Results
C.1 Details of Data Sets
SNAP dataset. We tested our methods on a diverse collection of real-world network datasets sourced from the Stanford Network Analysis Project (SNAP) [56]. These datasets span various domains and exhibit a wide range of structural properties, helping to validate the robustness and generalizability of our findings.
Email-Eu-core (Email) 771 Email exchanges within European research institution.
MOOC-actions (MOOC) 722 User actions on a Massive Open Online Course platform.
Facebook--go-nettorrs (aatrrkssFaeeeeerr (Facebook)
73
Ego-networks of Facebook users.
We only used the graph structures and ignored the edge weights and directions. That means all graphs treated as unweighted and undirected.
Synthetic datasets for examples. We also manually generated two datasets to demonstrate when projecting in Fueliden space is better than projecting with power distances and vice versa. In the first dataset, we had a single very large negative eigenvalue and the rest all positive eigenvalues in the diagonal matrix of the orthogonal decomposition of the distance matrix. In this situation, power distances of the points would have large radii and the error would be large while Eseudo-Euclidee projection would be on a signature of (p, 1). so the error bound would be much smaller. In the second dataset, we had the ratio of positive eigenvalues to negative eigenvalues was constant fraction, and the negative eigenvalues were all small. In this way, Pseudo-Euclidedd Euclidean projection would have large error bound while power distance projection would have very small radii and a small error bound.
Other datasets. We randomly select 1000 images from MNIST and CIFAR-10. The distance measure between two images are computed by the k-neareast neighbor (i.e. Isomap) with k = 10. The distance measure of genomics dataset is Entopic Affinity, introduced in prior works and commonly used for this datasets. The details of implementation can be found in our Github Repo.
C.2 Details of Implementation
All experiments are done with Macbook Pro with Apple M2 Chip of 16GB memory. The algorithms are fairly efficient and we did not encounter issues on computational resources.
The JL Transforms have only one parameter E, and set that to be 0.5 throughout the paper. The constant used in the big O notation of O(log n/e²) is 2. Another caveat is, our setting does not give access to data coordinates, therefore after obtaining coordinates from the JL transform, original dissimilarity measure reconstruct D. If the original measure is inexplicit unknown, use Euclidean distance. We only use the data coordinates for the classical J..
the
C.3 More Illustrations
The illustrations here extend the experiments to verify Theorem 2.3 and Theorem 3.3
25

---

Power Dicance 11 Propetios Nenicual Acdtiie Emp for vindle Cotwort
Tower Destaco Projection fandin Add Cree bebwer
14
(a) Residual error simplex
Residual error on ball
Datance Deribaa Additii Detwert
Prpection Secccaal Kdiitiu Erar facebook
3000
(c) Residual
(d) Residual
Figure Illustrations Power Distance Transform Residual Error
PrudeCiaclees UPhlection Eoxuts Lever Oounds
Injecten Upeer
8 Uodee
(a) Approximation factor for email
Approximation factor for facebook
TradeCir Bean L'reecio fan with Uper and Lovar Counds for enter stantt
Teast Cac Sean frceedo Nuse spper and Lowee Eounda cheld Desuee
(c) Approximation
(d) Approximation CIFAR.E
Figure 5: Illustrations of Pseudo Euclidean Transform Multiplicative Error
26


Reviews:
[{"review_id": "p00MFcVHxR", "reviewer": "Reviewer_2mBJ", "summary": "This submission aims to extend the Johnson-Lindenstrauss (JL) lemma to general non-Euclidean dissimilarity matrices by proposing two approaches: one based on pseudo-Euclidean embeddings and another based on generalized power distances. The authors provide theoretical guarantees and empirical results on both synthetic and real-world datasets.", "questions": "Can the authors demonstrate the utility of the proposed JL embeddings beyond preserving pairwise dissimilarities? For example, do these embeddings improve performance in downstream tasks such as clustering, classification, or nearest neighbor search on non-Euclidean data?", "limitations": "The impossibility of worst-case dimension reduction guarantees for general non-Euclidean data.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: Motivated Extension of JL Lemma: The work addresses an important and timely question: extending dimensionality reduction techniques beyond standard Euclidean spaces. The authors provide a structured attempt to generalize JL guarantees to non-metric or non-Euclidean dissimilarities, which are common in practice (e.g., in genomics, information retrieval, etc.). Conceptual Contribution: The connection between generalized power distance and data uncertainty is interesting and provides a new lens for interpreting structure in non-Euclidean datasets. The interpretation via eigenvalues of the Gram matrix offers some insight into when JL-like guarantees are meaningful.\n\nWeaknesses: Incremental Techniques: While the problem setup is novel, many of the tools (e.g., pseudo-Euclidean embedding via centralized Gram matrices, standard JL transforms) are not new. The contribution lies mostly in framing and packaging, rather than in fundamentally new techniques or insights. Heavy Computation Assumptions: The approach assumes full access to the dissimilarity matrix and requires SVD of the Gram matrix, which is cubic in time and not scalable to large datasets. This makes the current form more of a theoretical contribution than a practical algorithm.", "was_revised": true, "final_justification": "The authors' detailed rebuttal effectively strengthened the paper in two critical areas: (1) the new k-means clustering experiments provide compelling evidence of the proposed embeddings' downstream utility, directly addressing the need for enhanced empirical validation; and (2) the explicit acknowledgment of the work's primarily theoretical nature and the clear identification of scalability as future work appropriately frame the paper's scope and limitations. While scalability remains an open challenge, this is acceptably deferred for future research given the paper's theoretical focus. These positive developments in demonstrating practical relevance and clarifying the work's positioning confirm the initial recommendation. Therefore, I maintain my original score.", "rebuttal": "We sincerely thank you for the valuable feedback, please find our responses below, and feel free with follow-up questions.\n\n### __Response to “Incremental techniques”__\n\nIndeed, 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.\n\n### __Response to “Heavy computation assumptions”__\n\nThank 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.\n\nIn 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. \n\n### __Response to “The utility of the proposed JL embeddings beyond preserving pairwise dissimilarities? For example, do these embeddings improve performance in downstream tasks?”__\n\nThese 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.\n\nClustering 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.\n\n| Dataset | #Clusters (k) | Original | JL | JL-pq | JL-power |\n|----------|----------|----------|----------|----------|----------|\n| Brain    |     5     |    3.92e-3      |      728.00    |     3.13     |     33.26     |\n| Breast    |     4     |     0.03     |     8207.69    |     28.93  |     12.53     |\n| Email    |    42      |     5614     |     22634     |    21244      |     20764     |\n| Facebook    |     15     |    20499     |     284142     |     91644     |     303203     |\n\n\n### __Response to “The impossibility of worst-case dimension reduction guarantees for general non-Euclidean data.”__\n\nWe 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. \n\nThanks again for helping us improving the paper and pointing out future directions!"}, {"review_id": "oXTJ9kqy5X", "reviewer": "Reviewer_ZREf", "summary": "This paper generalizes the Johnson-Lindenstrauss lemma to (slightly) non-Euclidean geometries. We are given as input a dissimilarity matrix D for n points, which need only be symmetric and hollow (diagonal entries 0). The existential result gives points of dimension O(log n / eps^2) such that the pairwise distances equal the entries of D up to multiplicative (1 + eps) and additive 4 * eps * r^2, where r measures how much D deviates from Euclidean distances. \n\n\nTwo different versions are given. First, the desired dimensionality reduction is shown for points in \"pseudo-Euclidean space\" where, when computing the inner product, some coordinates are negated. Second, it is shown that for any symmetric hollow D, one can find points in \"generalized power distance\" space whose pairwise distances give the entries of D, and dimensionality reduction is also given for such points.", "questions": "Please write \"hollow\" instead of \"reflexive\" on line 49, since that's the word you use in the rest of the paper.\n\nWhat is the running time of your algorithm for finding the points in theorem 1.3?\n\nIs there evidence that these notions (\"pseudo-Euclidean space\" and \"generalized power distance\") are the correct ones to use in ML applications?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The second result is quite general and can work for any dissimilarity matrix D\n- Gives two nice generalizations of the JL lemma to non-Euclidean data\n- Appear effective in a few experiments\n\nWeaknesses\n- The results, as stated, are non-algorithmic; it would be nice to know how efficiently these can be computed\n- It is not clear that these are the correct ways to generalize to non-Euclidean data for ML applications. It is only hinted at what the ML applications are.", "was_revised": true, "final_justification": "This is a nice theoretical paper. The main weakness is that it is unclear whether these notions (\"pseudo-Euclidean space\" and \"generalized power distance\") are the correct ones to use in ML applications, but the authors give some data and say they are studying this in future work.", "rebuttal": "We appreciate your suggestions and questions! Please see our responses below, and feel free with follow-up questions.\n\n### __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?”__\n\nThank you for raising the issue. We will clarify this in the paper.\n\nFor 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. \n\nTo 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. \nThere 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. \n\n### __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?”\"__\n\nThank 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.\n\nMany 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.\n\n| Dataset | #Clusters (k) | Original | JL | JL-pq | JL-power |\n|----------|----------|----------|----------|----------|----------|\n| Brain    |     5     |    3.92e-3      |      728.00    |     3.13     |     33.26     |\n| Breast    |     4     |     0.03     |     8207.69    |     28.93  |     12.53     |\n| Email    |    42      |     5614     |     22634     |    21244      |     20764     |\n| Facebook    |     15     |    20499     |     284142     |     91644     |     303203     |\n\nWe 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. \n\n### __Response to “Please write \"hollow\" instead of \"reflexive\" on line 49.”__\n\nThank you. We have corrected the wording."}, {"review_id": "veTxWqOKei", "reviewer": "Reviewer_hxtR", "summary": "The authors present variants to the Johnson Lindenstrauss lemma for non-metric settings. The first uses a generalization of metric distances by defining an inner product in $\\mathbb{R}^{p + q}$ which adds the inner product of the first p dimensions and then subtracts the inner product of the next q dimensions. The second uses a separate generalization of distances termed \"power distances\", where each point is endowed with a radius and the distances between two points correspond to the length of the tangent lines between their corresponding circles. In both cases, the authors show theoretical results which are essentially consistent with those for the standard JL transform.", "questions": "My primary questions are regarding Section 2.1. I am *not* convinced by the provided text that one can take an arbitrary dissimilarity matrix and convert it into a set of observations in the given manner. The arguments are much too handwavy and something isn't passing the smell test for me. It would be good to write up a formal lemma or proposition and proof to clean this exposition up.\n\nFurthermore, I believe that the \"non-metric\" pseudo-euclidean dissimilarities might actually be metric, just in a complex space.\n\n### Regarding the centering:\n\n- In the case of D containing *squared* Euclidean distances, it is clear that we have the equality $-0.5 C D C = C G_X C$. However, this is explicitly due to the fact that the distances are induced by a norm and therefore we can distribute $D$.\n  - Specifically, for some dataset $\\mathbf{X} \\in \\mathbb{R}^{n \\times d}$, let $\\mathbf{\\alpha}$ be the vector of $\\alpha_i = \\langle x_i, x_i \\rangle$ and $\\mathbf{1}$ be the all ones vector. This lets us write any matrix $D$ of pairwise metric squared distances via $D = \\mathbf{1} \\mathbf{\\alpha}^\\top + \\mathbf{\\alpha} \\mathbf{1}^\\top - 2 \\mathbf{G}_X$. In this case, we get that the centering matrix cancels with the all-ones vectors and we get $-\\frac{1}{2} C D C = C G_X C$.\n  - However, in the setting considered in the paper, we can make no such assumption on the structure of $D$ since it is not obtained from an inner product space. Thus, I am not convinced that, for non-metric $D$, we can re-write it as a Gram matrix via centering. This then throws the subsequent derivations into question.\n\n- Moreover... why are the centering matrices necessary at all for the operations as they are laid out in the paper? Ostensibly, since the matrix D is already symmetric, one could immediately compute its singular value decomposition and perform all of the subsequent steps without ever applying the centering. Am I missing something where the centering is actually necessary for the downstream calculations? Something doesn't feel right.\n  - Specifically, the paper states \"Since $−CDC/2$ is a symmetric matrix, its eigenvalues are real...\" But D is also symmetric by definition. So why are we applying the centering?\n\nIn summary, it seems the centering is necessary for the theory to obtain a Gram matrix which can be analyzed accordingly. But I am not convinced that this is well-motivated in the non-metric setting. This is my primary concern and resolving it would certainly increase my score.\n\n### Regarding the complex space\n\n- To make sure I'm understanding, the $\\Lambda$ matrix in Section 2.1 could be replaced by simply having the $x$ values be complex values, right? I.e., we have some negative eigenvalues, so the $X X^T$ which produces those would consist of complex-valued observations.\n  - But then this would imply that the dissimilarity matrix being considered is actually metric; it just happens to come from points which live in a complex space. If this line of reasoning is correct, then I feel that the presentation should be amended significantly to mention that the paper presents results for JL transforms in non-metric spaces and in complex metric spaces.", "limitations": "As mentioned above, the limitations as presented could be expanded on but it's not a big issue. I think the work could use an explicit limitations section which describes which assumptions were necessary, how these assumptions factor through, and how these assumptions may be avoided in the future.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- I consider both cases interesting with regards to the JL lemma but find the main results to be the evidence that any symmetric hollow matrix can be written as either a pseudo-distance matrix or a power-distance matrix. I have questions regarding one of these results, but if everything is correct then this is a nice fact which would be useful for many applications beyond simply the JL-transform.\n- The paper is very clearly wriitten and quite easy to follow. I have experience in other classical dimensionality reduction algorithms (PCA, MDS, LLE, etc.) and this text introduced the relevant ideas so that I could follow them, despite not being particularly well-versed in JL theory.\n\nWeaknesses:\n- A few steps are presented without sufficient explanation for their validity (specifically in Section 2.1)\n- I am not sure what purpose the long exposition on Ptolemaic identities serves.\n- The experimental results are presented with insufficient care in my opinion. Some small issues include:\n  - The text in the plots is tiny\n  - It is unclear what the entropic affinity is or why JL-PE suddenly performs better on this metric when it dramatically fails on the other ones.\n  - It is not clear how one applies the JL transform to a graph dataset (perhaps I missed this somewhere?)\n- Absence of a limitations section (as encouraged by the guidelines). The limitations discussed in the checklist are quite spurious I and get the sense the authors were just trying to check a box rather than provide meaningful insight into how their work could be improved upon.", "was_revised": true, "final_justification": "The authors' rebuttal addressed my concerns and I believe the paper should be accepted. My primary remaining concern is that I am not convinced that this is an immediately necessary result, but it is clean and I believe the neurips community is likely to find it useful.", "rebuttal": "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.\n\n### __Response to “Clarification of Section 2.1”__\nWe 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.\n\n- **The differences between the Gram matrix for Euclidean data and non-Euclidean data.**\n\nIn 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$. \n\nNow, 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.\n\n- **A proof of the following claim.**\n\n**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}$.\n\n*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. \n\nSince $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}$.\n\nNow 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}$.  \n\n### __Response to questions on the centering matrix.__\n\nIt 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. \n\n### __Response to questions on the complex space.__\n\nIt 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.\n\nOn 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. \n\nWe hope this helps to clarify. We will also consider adding these discussions to the paper.\n\n### __Response to “What purpose the long exposition on Ptolemaic identities serves”__\n\nWe 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. \n\n### __Response to Questions regarding the experiments__\n\n- **“The text in the plots is tiny.”** Thank you for the observation, we have adopted larger fonts.\n- **“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.\n- **“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.\n\n### __Response to “Absence of a limitations section with elaboration on assumptions”__\n\nWe 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.\n\nThe 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.\n\nOne 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."}, {"review_id": "xZW2Ydb6hk", "reviewer": "Reviewer_GXa6", "summary": "This paper formulates the case of the JL lemma in non Euclidean cases.\nThe authors propose two complementary approaches to achieve this generalization:\n* Pseudo-Euclidean representation, which shows how any symmetric hollow dissimilarity matrix can be represented as distances between vectors with a specific signature $(p, q)$. JL transform in this space guarantees w.p. a multiplicative factor that depends on the ratio of the squared Euclidean distance and the squared (p,q) distance. This offers a fine-grained performance analysis based on the data's deviation from Euclidean geometry.\n* Generalized power distances, which shows that any symmetric hollow dissimilarity matrix can be expressed as a matrix of generalized power distances. Here, the JL transform yields the multiplicative approximation with an additional additive error term, proportional to a parameter 'r' (radius) that quantifies the uncertainty level within the data (and its deviation from Euclidean geometry). This approach also offers a statistical interpretation using silhouette coefficients of Gaussian distributions.\n\nThe theoretical results provide error analyses that depend on parameters characterizing how the input data deviates from Euclidean geometry, allowing for practical and meaningful dimensionality reduction in a wider range of data types. \n\nThe authors validate their approaches on both synthetic and real-world datasets, showing their effectiveness and superior performance compared to the classical JL transform on non-Euclidean data.", "questions": "* How do you think the proposed method(s) will compare in Table 2, if we measure a robust statistic of relative error like median, ans/or some higher percentile \n* There are some existing methods that already use non Euclidean (pseudo) metrics in high dimensions, such as face recognition and information retrieval. I would appreciate a short discussion on the impact on large(r) sacle problems like these.", "limitations": "The authors do not dedicate a section to limitations w.r.t. the current SOTA, i.e. classic JL.\nNotwithstanding, the authors do point to possible future directions and cases where the applicability of the proposed approach is not known.\nAdditionally, they note that a theoretical connection between the two proposed methods is not clear.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths \nThis paper is very well written, and easy to follow.\nAdditionally, the authors provide relevant real-world applications to the proposed methods, e.g. Minkowski space and Casey’s Theorem.\n\n## Weakness\nJL transform is, by now, a very studied topic, with many efficient and scalable implementations. \nHowever, the authors chose only trivial/toy datasets to showcase their method. \nAdditionally, Table 2 presents only non-robust metrics (i.e. max and mean) for comparison with classic JL - this is slightly unfair and the bounds hold only w.p. and the worst case error might be unbounded.", "was_revised": true, "final_justification": "This is a very nice paper, which addresses an gap in an important lemma. \nIt was worthy of publication even before the rebuttal, and the authors have addressed my main concerns and questions", "rebuttal": "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.\n\n### __Response to “Table 2 presents only non-robust metrics for comparison with classic JL”__\n\nThanks 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.\n\n| Method | Simplex | Ball | Brain | Breast | Renal | MNIST | CIFAR10 | Email | Facebook | MOOC |\n|------|------|------|------|------|------|------|------|------|-------|-------|\n| JL Median    | 6.36     | 6.68    | 2.69e12  | 1.95e11  | 1.18e12  | 1.78   | 2.29    | 7.00    | 5.08     | 6.13    |\n| JL-PE Median | **2.57**  | 2.78    | **1284.06** | **174.74** | **3160.58** | 2.11   | 2.04    | 2.06    | 5.83     | 6.03    |\n| JL-Power Median | 12.79  | **1.00** | 1.01e7   | 8.20e6   | 7.57e7   | **1.30** | **1.35** | **1.35** | **1.16** | **1.99**  |\n|------|------|------|------|------|------|------|------|------|-------|-------|\n| JL 75 percentile     | 13.85  | 14.51  | 4.69e12    | 2.30e11    | 8.02e12    | 5.78  | 8.09  | 17.70 | 11.08 | 10.45  |\n| JL-PE 75 percentile  | **5.31** | 5.78  | **38864.33** | **3318.65** | **1.18e6**  | 4.18  | 3.96  | 4.01  | 12.55 | 13.09  |\n| JL-Power 75 percentile | 15.30  | **1.00** | 1.50e8     | 8.59e7     | 3.85e8     | **1.62** | **1.91** | **1.92** | **1.31** | **2.20** |\n\n\nReporting 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.\n\n### __Response to “Impact on large scale problems such as facial recognition, which also uses non-Euclidean metrics in high-dimensions.”__\n\nThank 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.\n\nThe 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.\n\nLastly, 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.\n\n### __Response to “The authors do not dedicate a section to limitations”__\n\nWe thank the reviewer for the valuable suggestion. We will add a limitation section to the paper as below.\n\nWe 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."}]

Author rebuttal:

Meta-review: The paper studies dimensionality reduction for general dissimilarity matrix of n points. The key observation is that any symmetric dissimilarity matrix with 0s on the diagonal can be factorized into distances with the positive dot product component and the component with the negative sign. The paper shows that dimensionality reduction still works with approximation factor depending on the ratio between the Euclidean distance and the dissimilarity. Intuitively this characterizes how close the dissimilarity to Euclidean distances.

All reviewers are positive about the paper with varying degrees of support. Given the universal support from the reviewers, I recommend accepting the paper.
Decision: Accept (poster)