Lemme de Johnson-Lindenstrauss
Le lemme de Johnson-Lindenstrauss est un théorème de géométrie. Il établit qu'un petit ensemble de points dans un espace euclidien de grande dimension peut être plongé dans un espace de plus petite dimension, avec une faible distorsion, c'est-à-dire en préservant les distances de façon approchée.
Ce lemme de réduction de la dimensionnalité est utilisée en informatique théorique, notamment en algorithmique, en apprentissage automatique et en acquisition comprimée. Il est dû à William B. Johnson (en) et Joram Lindenstrauss.
Énoncé
Le lemme peut être énoncé de la façon suivante[1] :
Étant donné et un entier , soit un entier tel que . Pour tout ensemble de points dans , il existe un plongement de dans , tel que :
pour tout .
Autrement dit[2], pour tout , toute -métrique de points peut être plongée dans .
Preuve
La preuve classique repose sur l'idée de faire une projection sur un espace de dimension k choisi de manière aléatoire[1].
Applications
Pour de nombreux problèmes algorithmiques, la complexité en temps des algorithmes connus grandit avec la dimension. On peut alors commencer par calculer un plongement dans un espace de dimension logarithmique et utiliser l'algorithme sur cette nouvelle instance. La solution trouvée est une bonne approximation grâce au lemme. C'est une façon de contourner le fléau de la dimension.
Un exemple d'application est la version approchée de la recherche des plus proches voisins[3]. D'autres exemple sont des problèmes de flot, de partitionnement de données et de séparateurs[4].
Historique
Le lemme est dû à William B. Johnson et Joram Lindenstrauss[5].
Notes et références
- ↑ a et b Dimitris Achlioptas, « Database-friendly random projections: Johnson-Lindenstrauss with binary coins », J. Comput. Syst. Sci., vol. 66, no 4, {2003},, p. 671-687 (DOI 10.1016/S0022-0000(03)00025-4)
- ↑ Piotr Indyk et Jiří Matoušek, « The Johnson-Lindenstrauss lemma: flattening in », dans Handbook of Discrete and Computational Geometry (présentation en ligne), p. 182
- ↑ Piotr Indyk et Rajeev Motwani, « Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality », dans Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, (DOI 10.1145/276698.276876), p. 604-613
- ↑ Nathan Linial, Eran London et Yuri Rabinovich, « The Geometry of Graphs and Some of its Algorithmic Applications », Combinatorica, vol. 15, no 2, , p. 215-245 (DOI 10.1007/BF01200757)
- ↑ William B. Johnson (en) et Joram Lindenstrauss, « Extensions of Lipschitz mappings into a Hilbert space », Contemp. Math., no 26, , p. 189-206.
Portail des mathématiques
Portail de l'informatique théorique