pipette
ENEnglish

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

Nikita Muravya, Aleksandr Bespalov, Anna Vozianova

Preprint

En palabras de los autores

A finite metric space with points admits an exact representation in a pseudo-Euclidean space of dimension at most . 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 , dimension suffices, where is the largest ratio, over all points, between the distance to the 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 , where is fixed, the worst-case dimension is for , lies between and for , and is for . For , an intermediate range remains without matching bounds. Sign-pattern counting yields the lower bound for , while Hadamard matrices give explicit linear lower bounds for via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains for every . Finally, for every fixed , we show that the quadratic dependence on the parameter in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.