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 :

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

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

pour tout $u,v\in X$.

Autrement dit, pour tout $\varepsilon$, toute $\ell _{2}$-métrique de $n$ points peut être plongée dans $\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.

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. D'autres exemple sont des problèmes de flot, de partitionnement de données et de séparateurs.

Historique

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