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 encajes de puntos de baja distorsión, desde el espacio euclídeo de alta dimensión al espacio euclídeo de baja dimensión. 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.

El lema tiene aplicaciones en detección comprimida, aprendizaje de variedades, reducción de dimensionalidad y embebido de grafos. 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.

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

$\mathrm{\Omega }\left(\frac{\log (m)}{{\epsilon }^2}\right)$

para que se puedan preservar las distancias entre todos los pares de puntos dentro de un factor de $(1\pm \epsilon )$.

Lema

Dado $0<\epsilon <1$, un conjunto $X$ de $m\in {\mathbb{Z}}_{\ge 1}$ puntos en ${ℝ}^N$ ( $N\in {\mathbb{Z}}_{\ge 0}$ ), y un número entero $n>8(\ln m)/{\epsilon }^2$ , existe un mapa lineal $f:{ℝ}^N\to {ℝ}^n$ tal que

$(1-\epsilon )\Vert u-v{\Vert }^2\le \Vert f(u)-f(v){\Vert }^2\le (1+\epsilon )\Vert u-v{\Vert }^2$

para todos $u,v\in X$.

La fórmula se puede reorganizar como sigue:$$(1+\epsilon {)}^{-1}\Vert f(u)-f(v){\Vert }^2\le \Vert u-v{\Vert }^2\le (1-\epsilon {)}^{-1}\Vert f(u)-f(v){\Vert }^2$$Alternativamente, para cualquier $ϵ\in (0,1)$ y cualquier entero $n\ge 15(\ln m)/{\epsilon }^2$ existe una función lineal $f:{ℝ}^N\to {ℝ}^n$ tal que la restricción $f{|}_X$ es $(1+\epsilon )$ - bi-lipschitziana.

Una prueba del lema toma ƒ como un múltiplo adecuado de la proyección ortogonal sobre un subespacio aleatorio de dimensión $n$ en ${ℝ}^N$, y explota el fenómeno de la concentración de la medida.

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.

Declaración alternativa del lema

Un lema relacionado es el lema distribucional JL. Este lema establece que para cualquier $0<\epsilon ,\delta <1/2$ y entero positivo $d$, existe una distribución probabilística sobre el espacio ${ℝ}^{k\times d}$ de donde la matriz $A$ se toma tal que para $k=O({\epsilon }^{-2}\log (1/\delta ))$ y para cualquier vector de longitud unitaria $x\in {ℝ}^d$, se mantiene la siguiente afirmación.

$P(|\Vert Ax{\Vert }_2^2-1|>\epsilon )<\delta$

Se puede obtener el lema JL de la versión distribucional definiendo $x=(u-v)/\Vert u-v{\Vert }_2$ y $\delta <1/n^2$ para algún par $u,v$ambos en $X$. Entonces el lema JL sigue por una cuota de unión sobre todos esos pares.

Aceleramiento de la transformación JL

Dado A, calcular el producto vectorial de la matriz toma tiempo $O(kd)$. 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 $O(kd)$.

Hay dos grandes líneas de trabajo. La primera, Fast Johnson Lindenstrauss Transform (FJLT), fue presentada por Ailon y Chazelle en 2006. Este método permite calcular el producto matriz-vector en tan solo $d\log d+k^{2+\gamma }$ para cualquier constante $\gamma >0$.

Otro enfoque es construir una distribución compatible con matrices que son dispersas. Este método permite mantener sólo un fracción $\epsilon$ de las entradas en la matriz, lo que significa que el cálculo se puede hacer en tiempo tan solo $kd\epsilon$. Además, si el vector tiene sólo $b$ entradas distintas de cero, el Lema JL disperso toma tiempo $kb\epsilon$, que puede ser mucho menor que el tiempo utilizado por el Lema JL rápido, que es $d\log d$.

Proyecciones aleatorias tensorizadas

Es posible combinar dos matrices JL tomando el llamado producto de división de caras, que se define como los productos tensoriales de las filas (propuesto por V. Slyusar en 1996 para aplicaciones de conjuntos de antenas digitales y de radares ). Más concretamente, sean $C\in {ℝ}^{3\times 3}$ y $D\in {ℝ}^{3\times 3}$ dos matrices. Entonces el producto de división de cara $C\bullet D$ es dado por

$C\bullet D=\left[\begin{array}{c}{C}_1\otimes D_1\\ C_2\otimes D_2\\ C_3\otimes D_3\end{array}\right].$

La idea de tensorización fue utilizada por Kasiviswanathan et al. 2010 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:

$(𝐂\bullet 𝐃)(x\otimes y)=𝐂x\circ 𝐃y=\left[\begin{array}{c}(𝐂x{)}_1(𝐃y{)}_1\\ (𝐂x{)}_2(𝐃y{)}_2\\ ⋮\end{array}\right]$ ,

dónde $\circ$ es el producto entrada por entrada (Hadamard). Dichos cálculos se han utilizado para calcular de manera eficiente los núcleos polinómicos y muchos otros algoritmos de álgebra lineal.

En 2020 se demostró que si las matrices $C_1,C_2,\dots ,C_c$ son matrices independientes con entradas $\pm 1$ o Gaussianas, la matriz combinada $C_1\bullet \dots \bullet C_c$ satisface el lema distribucional JL si el número de filas es al menos

$O({ϵ}^{-2}\log 1/\delta +{ϵ}^{-1}(\frac{1}{c}\log 1/\delta {)}^c)$.

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 $(\log 1/\delta {)}^c$ es necesaria. Se sugieren construcciones JL alternativas para evitar esta circunstancia.

Véase también

• Proyección aleatoria
• Propiedad de isometría restringida

Lecturas adicionales

• Plantilla:Obra citada. Journal version of a paper previously appearing at PODC 2001.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Cita publicación
• Plantilla:Cita publicación
• Plantilla:Cita publicación