Скачать или смотреть Nicolò Zava (3/17/23): Every stable invariant of finite metric spaces produces false positives

In computational topology and geometry, the Gromov-Hausdorff distance between metric spaces provides a theoretical framework to tackle the problem of shape recognition and comparison. However, the direct computation of the Gromov-Hausdorff distance between finite metric spaces is known to be NP-hard. A possible approach to approximate it consists of studying invariants associating to every metric space a value in another, more manageable space. Invariants are usually required to be stable so that the invariants of two close metric spaces in the Gromov-Hausdorff distance are close. On the other hand, false positives, i.e., situations where the invariants associated with very different metric spaces are close, are generally accepted.

In this talk, we show that false positives are unavoidable if the stable invariant takes values in a Hilbert space. We deduce the claim from proving that the space of isometry classes of finite metric spaces endowed with the Gromov-Hausdorff distance cannot be coarsely embedded into any Hilbert space. More precisely, the same conclusion is obtained for the relatively small subspace consisting of isometry classes of finite subsets of the real line.