Lema de Johnson-Lindenstrauss

Resultado matemático

En matemáticas, el lema de Johnson-Lindenstrauss es un resultado que lleva el nombre de William B. Johnson y Joram Lindenstrauss y que se refiere a incrustaciones de baja distorsión de puntos de un espacio euclidiano de alta dimensión a uno de baja dimensión . El lema afirma que un conjunto de puntos de un espacio de alta dimensión se puede incrustar en un espacio de dimensión mucho menor de tal manera que las distancias entre los puntos se conservan casi por completo . En la prueba clásica del lema, la incrustación es una proyección ortogonal aleatoria .

El lema tiene aplicaciones en detección comprimida , aprendizaje de variedades , reducción de dimensionalidad e incrustación de grafos . Gran parte de los datos almacenados y manipulados en computadoras, incluidos texto e 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 dichos datos tienden a atascarse muy rápidamente a medida que aumenta la dimensión. ^[1] Por lo tanto, es deseable reducir la dimensionalidad de los datos de una manera que preserve su estructura relevante. El lema de Johnson-Lindenstrauss es un resultado clásico en esta línea.

Lema

Dado un conjunto de puntos en y un entero , ^[2] existe una función 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}}$

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

Para todos . ${\displaystyle u,v\in X}$

La fórmula se puede reorganizar: $${\displaystyle (1+\varepsilon )^{-1}\|f(u)-f(v)\|^{2}\leq \|u-v\|^{2}\leq (1-\varepsilon )^{-1}\|f(u)-f(v)\|^{2}}$$

Alternativamente, para cualquier número entero ^{[Nota 1]} existe una función lineal tal que la restricción es - bi-Lipschitz . ^{[Nota 2]} ${\displaystyle \epsilon \in (0,1)}$ ${\displaystyle n\geq 15(\ln m)/\varepsilon ^{2}}$ ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}}$ ${\displaystyle f|_{X}}$ ${\displaystyle (1+\varepsilon )}$

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

${\displaystyle \Omega \left({\frac {\log(m)}{\varepsilon ^{2}}}\right)}$

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

La prueba clásica del lema toma como un múltiplo escalar de una proyección ortogonal sobre un subespacio aleatorio de dimensión en . Una proyección ortogonal colapsa algunas dimensiones del espacio al que se aplica, lo que reduce la longitud de todos los vectores, así como la distancia entre vectores en el espacio. Bajo las condiciones del lema, la concentración de la medida asegura que existe una probabilidad distinta de cero de que una proyección ortogonal aleatoria reduzca las distancias por pares entre todos los puntos en en aproximadamente un factor constante . Dado que la probabilidad es distinta de cero, tales proyecciones deben existir, por lo que podemos elegir una y establecer . ${\displaystyle f}$ ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle X}$ ${\displaystyle c}$ ${\displaystyle P}$ ${\displaystyle f(v)=Pv/c}$

Para obtener la proyección algorítmicamente, basta con muestrear repetidamente al azar matrices de proyección ortogonal con alta probabilidad. Si se siguen tirando los dados, se obtendrá eventualmente una en tiempo aleatorio polinómico.

Declaración alternativa

Un lema relacionado es el lema JL distribucional. Este lema establece que para cualquier entero positivo y , existe una distribución sobre de la cual se extrae la matriz tal que para y para cualquier vector de longitud unitaria , se cumple la afirmación siguiente. ^[5] ${\displaystyle 0<\varepsilon ,\delta <1/2}$ ${\displaystyle d}$ ${\displaystyle \mathbb {R} ^{k\times d}}$ ${\displaystyle A}$ ${\displaystyle k=O(\varepsilon ^{-2}\log(1/\delta ))}$ ${\displaystyle x\in \mathbb {R} ^{d}}$

${\displaystyle P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta }$

Se puede obtener el lema JL a partir de la versión distributiva estableciendo y para algún par u , v ambos en X . Luego el lema JL sigue por un límite de unión sobre todos esos pares. ${\displaystyle x=(u-v)/\|u-v\|_{2}}$ ${\displaystyle \delta <1/n^{2}}$

Acelerando la transformación JL

Dado A , calcular el producto matriz-vector lleva tiempo. Se han realizado algunos trabajos para derivar distribuciones para las cuales el producto matriz-vector puede calcularse en menos de tiempo. ${\displaystyle O(kd)}$ ${\displaystyle O(kd)}$

Existen dos líneas de trabajo principales. La primera, la Transformada Rápida Johnson Lindenstrauss (FJLT), ^[6] fue introducida por Ailon y Chazelle en 2006. Este método permite el cálculo del producto matriz-vector en solo para cualquier constante . ${\displaystyle d\log d+k^{2+\gamma }}$ ${\displaystyle \gamma >0}$

Otro enfoque es construir una distribución soportada sobre matrices que son dispersas. ^[7] Este método permite mantener solo una fracción de las entradas en la matriz, lo que significa que el cálculo se puede realizar en poco tiempo. Además, si el vector solo tiene entradas distintas de cero, el JL Sparse toma tiempo , que puede ser mucho menor que el tiempo utilizado por el JL Fast. ${\displaystyle \varepsilon }$ ${\displaystyle kd\varepsilon }$ ${\displaystyle b}$ ${\displaystyle kb\varepsilon }$ ${\displaystyle 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 (fue propuesto por V. Slyusar ^[8] en 1996 ^{[9] [10] [11] [ 12] [13]} para aplicaciones de radar y conjuntos de antenas digitales ). Más directamente, sean y dos matrices. Entonces el producto de división de caras es ^{[9] [10] [11] [12] [13]} ${\displaystyle {C}\in \mathbb {R} ^{3\times 3}}$ ${\displaystyle {D}\in \mathbb {R} ^{3\times 3}}$ ${\displaystyle {C}\bullet {D}}$

${\displaystyle {C}\bullet {D}=\left[{\begin{array}{c }{C}_{1}\otimes {D}_{1}\\\hline {C}_{2}\otimes {D}_{2}\\\hline {C}_{3}\otimes {D}_{3}\\\end{array}}\right].}$

Esta idea de tensorización fue utilizada por Kasiviswanathan et al. para la privacidad diferencial . ^[14]

Las matrices JL definidas de esta manera utilizan menos bits aleatorios y se pueden aplicar rápidamente a vectores que tienen estructura tensorial, debido a la siguiente identidad: ^[11]

${\displaystyle (\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right]}$,

donde es el producto de Hadamard elemento por elemento . Estos cálculos se han utilizado para calcular de manera eficiente núcleos polinómicos y muchos otros algoritmos de álgebra lineal ^{[ se necesita aclaración ]} . ^[15] ${\displaystyle \circ }$

En 2020 ^[16] se demostró que si las matrices son matrices independientes o gaussianas, la matriz combinada satisface el lema JL distribucional si el número de filas es al menos ${\displaystyle C_{1},C_{2},\dots ,C_{c}}$ ${\displaystyle \pm 1}$ ${\displaystyle C_{1}\bullet \dots \bullet C_{c}}$

${\displaystyle O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$.

Para valores grandes, esto es tan bueno como el Johnson-Lindenstrauss completamente aleatorio, pero un límite inferior coincidente en el mismo artículo muestra que esta dependencia exponencial es necesaria. Se sugieren construcciones JL alternativas para evitar esto. ${\displaystyle \epsilon }$ ${\displaystyle (\log 1/\delta )^{c}}$

Véase también

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

Notas

1. O cualquier entero ${\displaystyle n>128(\ln m)/(9\varepsilon ^{2}).}$
2. Este resultado se desprende del resultado anterior. Bosquejo de la prueba: Nótese y para todos . Realice el trabajo de caso para 1= m y 1< m , aplicando el resultado anterior a en el último caso, notando ${\displaystyle 1/(1+\varepsilon )<{\sqrt {1-3\varepsilon /4}}}$ ${\displaystyle {\sqrt {1+3\varepsilon /4}}<{\sqrt {1+\varepsilon }}<1+\varepsilon }$ ${\displaystyle \varepsilon \in (0,1)}$ ${\displaystyle 3\varepsilon /4}$ ${\displaystyle 128/9<15.}$

Referencias

1. Por ejemplo, al escribir sobre la búsqueda del vecino más cercano en conjuntos de datos de alta dimensión, Jon Kleinberg escribe: "Los algoritmos más sofisticados normalmente logran un tiempo de consulta que es logarítmico en n a expensas de una dependencia exponencial de la dimensión d ; de hecho, incluso el análisis de caso promedio de heurísticas como árboles kd revela una dependencia exponencial de d en el tiempo de consulta. Kleinberg, Jon M. (1997), "Two Algorithms for Nearest-neighbor Search in High Dimensions", Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing , STOC '97, Nueva York, NY, EE. UU.: ACM, págs. 599–608, doi : 10.1145/258533.258653 , ISBN 0-89791-888-6.
2. Fernández-Granda, Carlos. "Apuntes de la conferencia 5: Proyecciones aleatorias" (PDF) . pag. 6. Lema 2.6 (lema de Johnson-Lindenstrauss)
3. Larsen, Kasper Green; Nelson, Jelani (2017), "Optimalidad del lema de Johnson-Lindenstrauss", Actas del 58.º Simposio anual IEEE sobre fundamentos de la informática (FOCS) , págs. 633-638, arXiv : 1609.02094 , doi : 10.1109/FOCS.2017.64, S2CID  16745
4. Nielsen, Frank (2016), "10. Optimización aproximada rápida en dimensiones altas con conjuntos de núcleos y reducción rápida de dimensiones", Introducción a HPC con MPI para ciencia de datos, Springer, págs. 259-272, ISBN 978-3-319-21903-5
5. Johnson, William B. ; Lindenstrauss, Joram (1984), "Extensiones de las aplicaciones de Lipschitz en un espacio de Hilbert", en Beals, Richard; Beck, Anatole; Bellow, Alexandra; et al. (eds.), Conferencia sobre análisis y probabilidad modernos (New Haven, Connecticut, 1982) , Contemporary Mathematics, vol. 26, Providence, RI: American Mathematical Society, págs. 189–206, doi :10.1090/conm/026/737400, ISBN 0-8218-5030-X, MR  0737400, S2CID  117819162
6. Ailon, Nir; Chazelle, Bernard (2006), "Vecinos más próximos aproximados y la transformada rápida de Johnson-Lindenstrauss", Actas del 38.º Simposio anual de la ACM sobre teoría de la computación , Nueva York: ACM Press, págs. 557-563, doi :10.1145/1132516.1132597, ISBN 1-59593-134-1, MR  2277181, S2CID  490517
7. Kane, Daniel M.; Nelson, Jelani (2014), "Transformadas de Johnson-Lindenstrauss más dispersas", Journal of the ACM , 61 (1): 1, arXiv : 1012.1577 , doi :10.1145/2559902, MR  3167920, S2CID  7821848Una versión preliminar de este artículo se publicó en las Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos , 2012.
8. Esteve, Anna; Boj, Eva; Fortiana, Josep (2009), "Términos de interacción en la regresión basada en la distancia", Communications in Statistics , 38 (18–20): 3498–3509, doi :10.1080/03610920802592860, MR  2589790, S2CID  122303508
9. Slyusar, VI (27 de diciembre de 1996), "Productos finales en matrices en aplicaciones de radar". (PDF) , Radioelectronics and Communications Systems , 41 (3): 50–53
10. Slyusar, VI (20 de mayo de 1997), "Modelo analítico de la red de antenas digitales basado en productos matriciales de división de caras". (PDF) , Proc. ICATT-97, Kyiv : 108–109
11. Slyusar, VI (15 de septiembre de 1997), "Nuevas operaciones de productos de matrices para aplicaciones de radares" (PDF) , Proc. Problemas directos e inversos de la teoría de ondas electromagnéticas y acústicas (DIPED-97), Lviv. : 73–74
12. Slyusar, VI (13 de marzo de 1998), "Una familia de productos faciales de matrices y sus propiedades" (PDF) , Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. , 35 (3): 379–384, doi :10.1007/BF02733426, S2CID  119661450
13. Slyusar, VI (2003), "Productos faciales generalizados de matrices en modelos de conjuntos de antenas digitales con canales no idénticos" (PDF) , Radioelectronics and Communications Systems , 46 (10): 9–17
14. Kasiviswanathan, Shiva Prasad; Rudelson, Mark; Smith, Adam D.; Ullman, Jonathan R. (2010), "El precio de publicar de forma privada tablas de contingencia y los espectros de matrices aleatorias con filas correlacionadas", en Schulman, Leonard J. (ed.), Actas del 42.º Simposio de la ACM sobre teoría de la computación, STOC 2010, Cambridge, Massachusetts, EE. UU., 5-8 de junio de 2010 , Association for Computing Machinery, págs. 775-784, doi :10.1145/1806689.1806795, S2CID  5714334
15. Woodruff, David P. (2014), El boceto como herramienta para el álgebra lineal numérica , Fundamentos y tendencias en informática teórica, vol. 10, arXiv : 1411.4357 , doi :10.1561/0400000060, MR  3285427, S2CID  51783444
16. Ahle, Thomas; Kapralov, Michael; Knudsen, Jakob; Pagh, Rasmus ; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020), "Boceto inconsciente de núcleos polinomiales de alto grado", Simposio ACM-SIAM sobre algoritmos discretos , Association for Computing Machinery, arXiv : 1909.01410 , doi : 10.1137/1.9781611975994.9

Lectura adicional

• Achlioptas, Dimitris (2003), "Proyecciones aleatorias compatibles con bases de datos: Johnson-Lindenstrauss con monedas binarias", Journal of Computer and System Sciences , 66 (4): 671–687, doi : 10.1016/S0022-0000(03)00025-4 , MR  2005771Versión de revista de un artículo publicado previamente en PODC 2001.
• Baraniuk, Richard ; Davenport, Mark; DeVore, Ronald ; Wakin, Michael (2008), "Una prueba simple de la propiedad de isometría restringida para matrices aleatorias", Constructive Approximation , 28 (3): 253–263, doi :10.1007/s00365-007-9003-x, hdl : 1911/21683 , MR  2453366, S2CID  15911073.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), "Una prueba elemental de un teorema de Johnson y Lindenstrauss" (PDF) , Random Structures & Algorithms , 22 (1): 60–65, doi :10.1002/rsa.10073, MR  1943859, S2CID  10327785.
• Landweber, Peter ; Lazar, Emanuel A.; Patel, Neel (2016), "Sobre los diámetros de fibra de los mapas continuos", American Mathematical Monthly , 123 (4): 392–397, arXiv : 1503.07597 , doi :10.4169/amer.math.monthly.123.4.392, S2CID  51751732
• Slyusar, VI (20 de mayo de 1997), "Modelo analítico de la red de antenas digitales basado en productos matriciales de división de caras". (PDF) , Proc. ICATT-97, Kyiv : 108–109
• Slyusar, VI (13 de marzo de 1998), "Una familia de productos faciales de matrices y sus propiedades" (PDF) , Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. , 35 (3): 379–384, doi :10.1007/BF02733426, S2CID  119661450.
• La caja de herramientas algorítmica moderna, lección n.° 4: reducción de la dimensionalidad (PDF) , 2023