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

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\mathrm{/}5<\epsilon <1$, dimension $O((N\mathrm{/}k)\log N+k{\rho }_k^4\log N\mathrm{/}(\epsilon -4\mathrm{/}5{)}^2)$ suffices, where ${\rho }_k$ is the largest ratio, over all points, between the distance to the $k$th 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,\mathrm{\Phi }]$, where $\mathrm{\Phi }\ge 5$ is fixed, the worst-case dimension is $\mathrm{\Theta }(N)$ for $0<\epsilon <4\mathrm{/}5$, lies between $\mathrm{\Omega }(\sqrt{N})$ and $O(\sqrt{N}\log N)$ for $4\mathrm{/}5<\epsilon <12\mathrm{/}13$, and is $\mathrm{\Theta }(\log N)$ for $\epsilon >({\mathrm{\Phi }}^2-1)\mathrm{/}({\mathrm{\Phi }}^2+1)$. For $\mathrm{\Phi }>5$, an intermediate range remains without matching bounds. Sign-pattern counting yields the $\mathrm{\Omega }(\sqrt{N})$ lower bound for $4\mathrm{/}5<\epsilon <12\mathrm{/}13$, while Hadamard matrices give explicit linear lower bounds for $\epsilon <4\mathrm{/}5$ via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains $N-1$ for every $\epsilon <1$. Finally, for every fixed $0<\epsilon <3\mathrm{/}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.