El lema establece que un conjunto de puntos en un espacio de dimensión alta se puede incrustar en un espacio de dimensión mucho más baja de tal manera que las distancias entre los puntos casi se conservan.
El mapa utilizado para el encaje es al menos lipschitziano, e incluso puede tomarse como una proyección ortogonal.
Gran parte de los datos almacenados y manipulados en las computadoras, incluyendo texto e imágenes, se pueden representar como puntos en un espacio de alta dimensión (consúltese el artículo modelo de espacio vectorial para el caso del texto).
Sin embargo, los algoritmos esenciales para trabajar con dichos datos tienden a funcionar cada vez con mayor lentitud a medida que aumenta la dimensión.
Por lo tanto, es deseable reducir la dimensionalidad de los datos de una manera que conserve su estructura relevante.
El lema de Johnson-Lindenstrauss es un resultado clásico en este sentido.
La fórmula se puede reorganizar como sigue:
[Nota 2] Una prueba del lema toma ƒ como un múltiplo adecuado de la proyección ortogonal sobre un subespacio aleatorio de dimensión
En general, una proyección ortogonal reducirá la distancia promedio entre los puntos, pero se puede considerar que el lema trata con distancias relativas, que no cambian con la escala.
En pocas palabras, tiras los dados y obtienes una proyección aleatoria, que reducirá la distancia promedio, y luego aumentas las distancias para que la distancia promedio vuelva a su valor anterior.
Si continúa tirando los dados, encontrará, en tiempo aleatorio polinomial, una proyección para la cual las distancias (escaladas) satisfacen el lema.
Este lema establece que para cualquier
se toma tal que para
y para cualquier vector de longitud unitaria
[3] Se puede obtener el lema JL de la versión distribucional definiendo
Entonces el lema JL sigue por una cuota de unión sobre todos esos pares.
Dado A, calcular el producto vectorial de la matriz toma tiempo
Ha habido investigación en la derivación de distribuciones para las cuales el producto vectorial de matrices se puede calcular en tiempo menor que
La primera, Fast Johnson Lindenstrauss Transform (FJLT),[4] fue presentada por Ailon y Chazelle en 2006.
Este método permite calcular el producto matriz-vector en tan solo
Otro enfoque es construir una distribución compatible con matrices que son dispersas.
[5] Este método permite mantener sólo un fracción
entradas distintas de cero, el Lema JL disperso toma tiempo
es dado por[7][8][9][10][11] La idea de tensorización fue utilizada por Kasiviswanathan et al.
2010[12] para la rama de privacidad diferencial.
Las matrices JL definidas así usan menos bits aleatorios y se pueden aplicar rápidamente a vectores que tienen estructura tensorial, debido a la siguiente identidad:[9] dónde
Dichos cálculos se han utilizado para calcular de manera eficiente los núcleos polinómicos y muchos otros algoritmos de álgebra lineal.
satisface el lema distribucional JL si el número de filas es al menos Para valores grandes de
esto es tan bueno como el Lema Johnson-Lindenstrauss completamente aleatorio, pero un límite inferior coincidente en el mismo documento muestra que esta dependencia exponencial de
Se sugieren construcciones JL alternativas para evitar esta circunstancia.