Étude des applications entre espaces métriques qui préservent approximativement ou exactement les distances, en quantifiant la distorsion, les constantes bi‑Lipschitz et les compromis entre dimension cible, distorsion et complexité algorithmique ; inclut plongements linéaires et non linéaires dans des espaces Lp, des espaces hilbertiens et des espaces euclidiens de dimension finie.

Principe

Caractériser quand un espace métrique peut être plongé dans un autre avec distorsion contrôlée et dimension minimale à l'aide d'applications Lipschitz, bi‑Lipschitz ou de faible distorsion ; exploiter des propriétés structurelles (dimension doublante, métriques en arbre, type négatif) pour obtenir bornes et plongements constructifs.

Démonstration

Lemme de Johnson–Lindenstrauss : tout ensemble fini de points dans un espace euclidien de grande dimension peut être projeté avec faible distorsion dans O(log n / ε^2) dimensions par une projection linéaire aléatoire. Autre exemple : plongement isométrique de métriques d'arbres finis dans l1.

Mauvaise application

Supposer qu'un plongement linéaire de faible distorsion et faible dimension existe pour des familles métriques infinies ou adversariales ; ou appliquer des méthodes de projection euclidienne à des métriques dépourvues des propriétés de concentration ou de type négatif requises, entraînant une forte distorsion.

Conséquence

Les plongements métriques fournissent des outils de réduction de dimension, des algorithmes d'approximation pour le clustering et la recherche du plus proche voisin, ainsi que des insights structurels qui traduisent des contraintes géométriques en efficacité algorithmique ou en résultats de difficulté.

Inversion

Considérer les métriques seulement à l'échelle grossière (quasi‑isométrie) ou la topologie ignore les mesures de distorsion pertinentes pour les algorithmes ; un plongement isométrique ou de faible distorsion peut être impossible, d'où la nécessité d'accepter approximations et bornes inférieures.

Limite

Concerne principalement les espaces métriques et métriques finies ; ne s'applique pas directement à des mesures de similarité arbitraires qui ne sont pas des métriques, ni aux questions de préservation de structures d'ordre supérieur (p. ex. courbure) au-delà des distances par paires sans contraintes supplémentaires.

Tension sémantique

Tension entre la préservation des distances par paires (fidélité métrique) et la minimisation de la dimension cible ou du coût computationnel : une plus grande fidélité augmente la dimension/complexité ; tension aussi avec les approches d'apprentissage de variétés qui supposent une structure latente lisse plutôt que des bornes de distorsion en pire cas.

Synthèse

La théorie des plongements métriques fournit des applications quantitatives d'un espace métrique vers un autre qui équilibrent distorsion, dimension et complexité, permettant réduction de dimension et exploitation algorithmique de la structure géométrique avec garanties démontrables.