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 de baja dimensión . El lema establece que un conjunto de puntos en un espacio de alta dimensión se puede incrustar en un espacio de dimensión mucho más baja de tal manera que las distancias entre los puntos casi se preserven . 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 múltiple , reducción de dimensionalidad e incrustación de gráficos . Gran parte de los datos almacenados y manipulados en las 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 este sentido.

Además, el lema está ajustado a un factor constante, es decir, existe un conjunto de puntos de tamaño m que necesitan 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 . ^{[2] [3]} ${\displaystyle (1\pm \varepsilon )}$

Lema

Dado un conjunto de puntos en ( ) y un número entero ^{[ disputado ]} , existe un mapa lineal tal que ${\displaystyle 0<\varepsilon <1}$ ${\displaystyle X}$ ${\displaystyle m\in \mathbb {Z} _{\geq 1}}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle N\in \mathbb {Z} _{\geq 0}}$ ${\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 reordenar:

$${\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 )}$

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 los vectores en el espacio. Bajo las condiciones del lema, la concentración de medida garantiza que exista una probabilidad distinta de cero de que una proyección ortogonal aleatoria reduzca las distancias por pares entre todos los puntos 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 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 una alta probabilidad muestrear repetidamente matrices de proyección ortogonales al azar. Si sigues tirando los dados, eventualmente obtendrás uno en tiempo aleatorio polinómico.

Declaración alternativa

Un lema relacionado es el lema distribucional JL. Este lema establece que para cualquier entero positivo , existe una distribución a partir de la cual se extrae la matriz de manera que para cualquier vector de longitud unitaria , se cumple la siguiente afirmación. ^[4] ${\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 de la versión distribucional configurando y para algún par u , v ambos en X. Luego, el lema JL sigue una unión ligada a 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 vectorial matricial lleva tiempo. Se han realizado algunos trabajos para derivar distribuciones para las cuales el producto vectorial matricial pueda calcularse en menos tiempo. ${\displaystyle O(kd)}$ ${\displaystyle O(kd)}$

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

Otro enfoque es construir una distribución soportada sobre matrices dispersas. ^[6] 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 el momento justo. Además, si el vector solo tiene entradas distintas de cero, Sparse JL requiere tiempo , que puede ser mucho menor que el tiempo utilizado por Fast JL. ${\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 ^[7] en 1996 ^{[8] [9] [10] [11] [12]} 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 ^{[8] [9] [10] [11] [12]} ${\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. por una privacidad diferencial . ^[13]

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

${\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]}$,

¿Dónde está el producto por elementos ( Hadamard )? Estos cálculos se han utilizado para calcular eficientemente núcleos polinómicos y muchos otros algoritmos de álgebra lineal ^{[ se necesita aclaración ]} . ^[14] ${\displaystyle \circ }$

En 2020 ^[15] se demostró que si las matrices son independientes o gaussianas, la matriz combinada satisface el lema distribucional JL 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 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}}$

Ver también

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

Notas

1. O cualquier número entero ${\displaystyle n>128(\ln m)/(9\varepsilon ^{2}).}$
2. Este resultado se deriva del resultado anterior. Bosquejo de la prueba: Nota y para todos . Realice un trabajo de casos para 1= m y 1< m , aplicando el resultado anterior en el último caso, teniendo en cuenta ${\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 suelen lograr 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 casos promedio de heurísticas como los árboles kd revelan una dependencia exponencial de d en el tiempo de consulta. Kleinberg, Jon M. (1997), "Two Algorithms for Nearest-neighbor Search in High Dimensions", Actas de la vigésima novena edición anual Simposio ACM sobre Teoría de la Computación , STOC '97, Nueva York, NY, EE. UU.: ACM, págs. 599–608, doi : 10.1145/258533.258653 , ISBN 0-89791-888-6.
2. Larsen, Kasper Verde; Nelson, Jelani (2017), "Optimalidad del lema de Johnson-Lindenstrauss", Actas del 58.º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) , págs. 633–638, arXiv : 1609.02094 , doi : 10.1109/FOCS.2017.64 , S2CID  16745
3. 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
4. Johnson, William B .; Lindenstrauss, Joram (1984), "Extensiones de asignaciones de Lipschitz en un espacio de Hilbert", en Beals, Richard; Beck, Anatole; A continuación, Alexandra; et al. (eds.), Conferencia sobre análisis y probabilidad modernos (New Haven, Connecticut, 1982) , Matemáticas contemporáneas, vol. 26, Providence, RI: Sociedad Matemática Estadounidense, págs. 189–206, doi :10.1090/conm/026/737400, ISBN 0-8218-5030-X, SEÑOR  0737400, S2CID  117819162
5. Ailon, Nir; Chazelle, Bernard (2006), "Aproximados vecinos más cercanos y la rápida transformación de Johnson-Lindenstrauss", Actas del 38º Simposio anual de ACM sobre teoría de la informática , Nueva York: ACM Press, págs. 557–563, doi :10.1145/1132516.1132597, ISBN 1-59593-134-1, SEÑOR  2277181, S2CID  490517
6. Kane, Daniel M.; Nelson, Jelani (2014), "Sparser Johnson-Lindenstrauss Transforms", Journal of the ACM , 61 (1): 1, arXiv : 1012.1577 , doi : 10.1145/2559902, MR  3167920, S2CID  7821848. Una versión preliminar de este artículo se publicó en las Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos , 2012.
7. Esteve, Ana; Boj, Eva; Fortiana, Josep (2009), "Términos de interacción en regresión basada en distancia", Communications in Statistics , 38 (18–20): 3498–3509, doi :10.1080/03610920802592860, MR  2589790, S2CID  122303508
8. Slyusar, VI (27 de diciembre de 1996), "Productos finales en matrices en aplicaciones de radar". (PDF) , Sistemas de radioelectrónica y comunicaciones , 41 (3): 50–53
9. Slyusar, VI (20 de mayo de 1997), "Modelo analítico del conjunto de antenas digitales sobre la base de productos de matriz de división de caras". (PDF) , Proc. ICATT-97, Kiev : 108-109
10. Slyusar, VI (15 de septiembre de 1997), "Producto de nuevas operaciones 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
11. Slyusar, VI (13 de marzo de 1998), "Una familia de productos faciales de matrices y sus propiedades" (PDF) , Análisis de sistemas y cibernética C/C de Kibernetika I Sistemnyi Analiz.- 1999. , 35 (3): 379–384, doi :10.1007/BF02733426, S2CID  119661450
12. Slyusar, VI (2003), "Productos faciales generalizados de matrices en modelos de conjuntos de antenas digitales con canales no idénticos" (PDF) , Sistemas de comunicaciones y radioelectrónica , 46 (10): 9–17
13. Kasiviswanathan, Shiva Prasad; Rudelson, Marcos; Smith, Adam D.; Ullman, Jonathan R. (2010), "El precio de publicar de forma privada tablas de contingencia y espectros de matrices aleatorias con filas correlacionadas", en Schulman, Leonard J. (ed.), Actas del 42º Simposio ACM sobre Teoría de la Computación, STOC 2010, Cambridge, Massachusetts, EE. UU., 5 a 8 de junio de 2010 , Association for Computing Machinery, págs. 775–784, doi :10.1145/1806689.1806795, S2CID  5714334
14. Woodruff, David P. (2014), El dibujo 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, SEÑOR  3285427, S2CID  51783444
15. Ahlé, Thomas; Kapralov, Michael; Knudsen, Jacob; Pagh, Rasmus ; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020), "Boceto inconsciente de núcleos polinomiales de alto grado", Simposio ACM-SIAM sobre algoritmos discretos , Asociación de Maquinaria de Computación, arXiv : 1909.01410 , doi : 10.1137/1.9781611975994.9

Otras lecturas

• 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 , SEÑOR  2005771. Versión de revista de un artículo que apareció anteriormente en PODC 2001.
• Baraniuk, Richard ; Davenport, Marcos; DeVore, Ronald ; Wakin, Michael (2008), "Una prueba simple de la propiedad de isometría restringida para matrices aleatorias", Aproximación constructiva , 28 (3): 253–263, doi :10.1007/s00365-007-9003-x, hdl : 1911/21683 , SEÑOR  2453366, S2CID  15911073.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), "Una prueba elemental de un teorema de Johnson y Lindenstrauss" (PDF) , Estructuras y algoritmos aleatorios , 22 (1): 60–65, doi :10.1002/rsa.10073, MR  1943859, S2CID  10327785.
• Landweber, Peter ; Lazar, Emanuel A.; Patel, Neel (2016), "Sobre diámetros de fibra de 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 del conjunto de antenas digitales basado en productos de matriz de división de caras". (PDF) , Proc. ICATT-97, Kiev : 108-109
• Slyusar, VI (13 de marzo de 1998), "Una familia de productos faciales de matrices y sus propiedades" (PDF) , Cibernética y análisis de sistemas C/C de Kibernetika I Sistemnyi Analiz.- 1999. , 35 (3): 379– 384, doi :10.1007/BF02733426, S2CID  119661450.
• Conferencia n.º 4 de la caja de herramientas algorítmica moderna: Reducción de dimensionalidad (PDF) , 2023