Lema de Johnson-Lindenstrauss

En matemáticas, el lema de Johnson-Lindenstrauss es un resultado que lleva el nombre de William B. Johnson y Joram Lindenstrauss sobre incrustaciones de puntos de baja distorsión desde el espacio euclidiano de alta dimensión al espacio euclidiano de baja dimensión . El lema establece que un conjunto de puntos en un espacio de alta dimensión puede incrustarse en un espacio de dimensión mucho más baja de tal manera que las distancias entre los puntos se conserven casi por completo . El mapa utilizado para la incrustación es al menos Lipschitz , e incluso puede tomarse como una proyección ortogonal .

El lema tiene aplicaciones en detección comprimida , aprendizaje múltiple , reducción de dimensionalidad e incrustación de gráficos . Gran parte de los datos almacenados y manipulados en las computadoras, incluido el texto y las imágenes, se pueden representar como puntos en un espacio de alta dimensión (consulte el modelo de espacio vectorial para el caso del texto). Sin embargo, los algoritmos esenciales para trabajar con tales datos tienden a empantanarse muy rápidamente a medida que aumenta la dimensión. ^[1] Por lo tanto, es deseable reducir la dimensionalidad de los datos de manera que se preserve su estructura relevante. El lema de Johnson-Lindenstrauss es un resultado clásico en este sentido.

Además, el lema está ajustado a un factor constante, es decir, existe un conjunto de puntos de tamaño m que necesita dimensión.

para preservar las distancias entre todos los pares de puntos dentro de un factor de . ^[2] ${\ Displaystyle (1 \ pm \ varepsilon)}$

Dado , un conjunto de puntos y un número , hay un mapa lineal tal que ${\ displaystyle 0 <\ varepsilon <1}$ ${\ Displaystyle X}$ ${\ Displaystyle m}$ ${\ Displaystyle \ mathbb {R} ^ {N}}$ ${\ Displaystyle n> 8 \ ln (m) / \ varepsilon ^ {2}}$ ${\ Displaystyle f: \ mathbb {R} ^ {N} \ rightarrow \ mathbb {R} ^ {n}}$

para todos . ${\ Displaystyle u, v \ en X}$