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é 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é ${\displaystyle 0<\varepsilon <1}$ et un entier ${\displaystyle n}$, soit ${\displaystyle k}$ un entier tel que ${\displaystyle k>8\log(n)/\varepsilon ^{2}}$. Pour tout ensemble ${\displaystyle X}$ de ${\displaystyle n}$ points dans ${\displaystyle \mathbb {R} ^{N}}$, il existe ${\displaystyle f}$ un plongement de ${\displaystyle \mathbb {R} ^{N}}$dans ${\displaystyle \mathbb {R} ^{k}}$, tel que :

${\displaystyle (1-\varepsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|u-v\|^{2}}$

pour tout ${\displaystyle u,v\in X}$.

Autrement dit[2], pour tout ${\displaystyle \varepsilon }$, toute ${\displaystyle \ell _{2}}$-métrique de ${\displaystyle n}$ points peut être plongée dans ${\displaystyle \ell _{2}^{O(\log(n)/\varepsilon ^{2})}}$.

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 exemples 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

1. Dimitris Achlioptas, « Database-friendly random projections: Johnson-Lindenstrauss with binary coins », J. Comput. Syst. Sci., vol. 66, n^o 4,‎ {2003},, p. 671-687 (DOI 10.1016/S0022-0000(03)00025-4)
2. Piotr Indyk et Jiří Matoušek, « The Johnson-Lindenstrauss lemma: flattening in ${\displaystyle \ell _{2}}$ », dans Handbook of Discrete and Computational Geometry (présentation en ligne), p. 182
3. 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, 1998 (DOI 10.1145/276698.276876), p. 604-613
4. Nathan Linial, Eran London et Yuri Rabinovich, « The Geometry of Graphs and Some of its Algorithmic Applications », Combinatorica, vol. 15, n^o 2,‎ 1995, p. 215-245 (DOI 10.1007/BF01200757)
5. William B. Johnson (en) et Joram Lindenstrauss, « Extensions of Lipschitz mappings into a Hilbert space », Contemp. Math., n^o 26,‎ 1984, p. 189-206.