Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces

Abstract

A finite metric space with N points admits an exact representation in a pseudo-Euclidean space of dimension at most N−1. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for 4/5<ε<1, dimension O((N/k)log N+kρ_k⁴log N/(ε−4/5)²) suffices, where ρ_k is the largest ratio, over all points, between the distance to the kth closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in [1,Φ], where Φ≥5 is fixed, the worst-case dimension is Θ(N) for 0<ε<4/5, lies between Ω(√N) and O(√Nlog N) for 4/5<ε<12/13, and is Θ(log N) for ε>(Φ²−1)/(Φ²+1). For Φ>5, an intermediate range remains without matching bounds. Sign-pattern counting yields the Ω(√N) lower bound for 4/5<ε<12/13, while Hadamard matrices give explicit linear lower bounds for ε<4/5 via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains N−1 for every ε<1. Finally, for every fixed 0<ε<3/5, we show that the quadratic dependence on the parameter C in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.

The Calderón problem for near-Euclidean metrics
Gunther Uhlmann, Yiran Wang
arXiv1 Nov 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Local rigidity of conformally Euclidean metrics for the anisotropic Calderón problem
Sebastián Muñoz-Thon, Plamen Stefanov
arXiv6 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
Jack Spalding-Jamieson
arXiv30 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
A relative Euclidean thickening
John R. Klein
arXiv1 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
Local rigidity of conformally Euclidean metrics for the anisotropic Helmholtz equation at fixed energy
Sebastián Muñoz-Thon, Plamen Stefanov
arXiv27 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{muravya2026dimension,
  title = {{Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces}},
  author = {Nikita Muravya and Aleksandr Bespalov and Anna Vozianova},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.24254},
  eprint = {2610.24254},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.24254},
}

RIS

TY  - UNPB
TI  - Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces
AU  - Nikita Muravya
AU  - Aleksandr Bespalov
AU  - Anna Vozianova
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.24254
UR  - https://arxiv.org/abs/2610.24254
AB  - A finite metric space with N points admits an exact representation in a pseudo-Euclidean space of dimension at most N−1. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for 4/5<ε<1, dimension O((N/k)log N+kρ_k^4log N/(ε−4/5)^2) suffices, where ρ_k is the largest ratio, over all points, between the distance to the kth closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in [1,Φ], where Φ≥5 is fixed, the worst-case dimension is Θ(N) for 0<ε<4/5, lies between Ω(√N) and O(√Nlog N) for 4/5<ε<12/13, and is Θ(log N) for ε>(Φ^2−1)/(Φ^2+1). For Φ>5, an intermediate range remains without matching bounds. Sign-pattern counting yields the Ω(√N) lower bound for 4/5<ε<12/13, while Hadamard matrices give explicit linear lower bounds for ε<4/5 via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains N−1 for every ε<1. Finally, for every fixed 0<ε<3/5, we show that the quadratic dependence on the parameter C in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.
ER  -

Abstract

Related

Cite