Research map / Learning theory and algorithms / Matrix and tensor methods
Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the Johnson-Lindenstrauss lemma to non-Euclidean, non-metric symmetric hollow dissimilarity matrices via two routes: pseudo-Euclidean (p,q) projection and generalized power distances with an additive error term.
Problem
Dimensionality reduction with the JL lemma is limited to Euclidean data with available coordinates; many real dissimilarity measures are non-Euclidean and non-metric, and only pairwise dissimilarities may be accessible.
Approach
Represent any symmetric hollow dissimilarity matrix either as squared distances in pseudo-Euclidean space of signature (p,q) and apply JL separately to the positive and negative parts (multiplicative error scaled by the ratio C_ij), or as generalized power distances with a common radius r set from the smallest Gram eigenvalue and apply JL to the centers (multiplicative error plus additive 4εr² ter
Key results
- JL-power achieves the lowest average and median relative error on 7 of 10 datasets (e.g., Email average 1.60 vs JL-PE 13.79 and JL 15.64), while JL-PE is best on genomics datasets (e.g., Breast average 1.15).
- On downstream k-means, JL-power gives lowest cost on Breast (12.53 vs original 0.03 and JL 827.69) and Email (20764 vs JL 22634), while JL-pq is best on Brain and Facebook.
- Empirically, the power-distance residual error stays below the 4εr² bound on sampled pairs; doubling target dimension for Simplex reduces violation rate of the pseudo-Euclidean bound from 12.01% to 4.62%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use JL-PE instead of classical JL | Brain relative-error evaluation · Brain | average relative error: 1.11e9 -> 8.16 | Helped |
| Use JL-PE instead of classical JL | Breast relative-error evaluation · Breast | average relative error: 9.86e7 -> 1.15 | Helped |
| Use JL-PE instead of classical JL | Renal relative-error evaluation · Renal | average relative error: 1.50e9 -> 6.60 | Helped |
| Use JL-PE instead of classical JL | Email relative-error evaluation · Email | average relative error: 15.64 -> 13.79 | Helped |
| Use JL-PE instead of classical JL | Facebook relative-error evaluation · Facebook | average relative error: 12.62 -> 52.52 | Hurt |
| Use JL-PE instead of classical JL | MOOC relative-error evaluation · MOOC | average relative error: 39.83 -> 63.44 | Hurt |
| Use JL-Power instead of classical JL | Simplex relative-error evaluation · Simplex | average relative error: 442.65 -> 13.52 | Helped |
| Use JL-Power instead of classical JL | Ball relative-error evaluation · Ball | average relative error: 43.78 -> 1.002 | Helped |
| Use JL-Power instead of classical JL | Brain relative-error evaluation · Brain | average relative error: 1.11e9 -> 3.73e4 | Helped |
| Use JL-Power instead of classical JL | Breast relative-error evaluation · Breast | average relative error: 9.86e7 -> 3.12e3 | Helped |
| Use JL-Power instead of classical JL | Renal relative-error evaluation · Renal | average relative error: 1.50e9 -> 5.57e4 | Helped |
| Use JL-Power instead of classical JL | JL relative-error evaluation · MNIST and CIFAR-10 | average relative error: inf -> 1.47; inf -> 1.61 | Helped |
Surprising findings
- Naive classical JL yields infinite relative error on MNIST and CIFAR-10 because distinct images collapse to the same projected point.
- Neither proposed transform dominates: JL-pq is better on genomics data while JL-power is better on most other datasets, and the paper does not give conditions for choosing between them.
Limitations
- No theoretical connection or dominance condition between the pseudo-Euclidean and power-distance representations.
- Requires O(n^3) eigendecomposition to recover coordinates; scalability relies on heuristics such as landmark MDS not evaluated.
- Some theoretical claims (e.g., lower bound and random-sphere concentration) are sketched or rely on informal arguments; experiments use a fixed epsilon of 0.5.
Experimental setup
Datasets: Random-simplex (synthetic) Euclidean-ball (synthetic) CuMiDa Brain CuMiDa Breast CuMiDa Renal MNIST (1000 sampled) CIFAR-10 (1000 sampled) Email-Eu-core Facebook ego-networks MOOC-actions
Benchmarks: Random-simplex Euclidean-ball Brain Breast Renal MNIST CIFAR-10 Email Facebook MOOC
Metrics: maximum relative error average relative error median relative error k-means clustering cost multiplicative approximation ratio residual additive error
Baselines: classical JL transform
Builds on: Johnson-Lindenstrauss lemma classical multidimensional scaling power distance silhouette coefficient
Closest papers by meaning
- Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights (ICML 2025 · similarity 0.87)
- Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms (NeurIPS 2024 · similarity 0.87)
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.86)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.85)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.85)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.