Lemme de Johnson-Lindenstrauss

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})}}$.

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].

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].

Le lemme est dû à William B. Johnson et Joram Lindenstrauss[5].