Bosquejo del tensor

Algoritmo para reducir la dimensión de los tensores

En estadística , aprendizaje automático y algoritmos , un bosquejo tensorial es un tipo de reducción de dimensionalidad que es particularmente eficiente cuando se aplica a vectores que tienen estructura tensorial . ^{[1] [2]} Un bosquejo de este tipo se puede utilizar para acelerar los métodos de kernel explícitos , la agrupación bilineal en redes neuronales y es una piedra angular en muchos algoritmos de álgebra lineal numérica . ^[3]

Definición matemática

Matemáticamente, una matriz de reducción o dibujo de dimensionalidad es una matriz , donde , tal que para cualquier vector ${\displaystyle M\in \mathbb {R} ^{k\times d}}$ ${\displaystyle k<d}$ ${\displaystyle x\in \mathbb {R} ^{d}}$

${\displaystyle |\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}}$

con alta probabilidad. En otras palabras, conserva la norma de los vectores hasta un pequeño error. ${\displaystyle M}$

Un bosquejo tensorial tiene la propiedad adicional de que si para algunos vectores tales que , la transformación se puede calcular de manera más eficiente. Aquí denota el producto de Kronecker , en lugar del producto externo , aunque los dos están relacionados por un aplanamiento . ${\displaystyle x=y\otimes z}$ ${\displaystyle y\in \mathbb {R} ^{d_{1}},z\in \mathbb {R} ^{d_{2}}}$ ${\displaystyle d_{1}d_{2}=d}$ ${\displaystyle M(y\otimes z)}$ ${\displaystyle \otimes }$

La aceleración se logra reescribiendo primero , donde denota el producto de Hadamard por elemento . Cada uno de y se puede calcular en tiempo y , respectivamente; incluido el producto de Hadamard, se obtiene el tiempo total . En la mayoría de los casos de uso, este método es significativamente más rápido que el tiempo total que requiere . ${\displaystyle M(y\otimes z)=M'y\circ M''z}$ ${\displaystyle \circ }$ ${\displaystyle M'y}$ ${\displaystyle M''z}$ ${\displaystyle O(kd_{1})}$ ${\displaystyle O(kd_{2})}$ ${\displaystyle O(d_{1}d_{2}+kd_{1}+kd_{2})}$ ${\displaystyle M(y\otimes z)}$ ${\displaystyle O(kd)=O(kd_{1}d_{2})}$

Para tensores de orden superior, como , los ahorros son aún más impresionantes. ${\displaystyle x=y\otimes z\otimes t}$

Historia

El término "bosquejo tensorial" fue acuñado en 2013 ^[4] para describir una técnica de Rasmus Pagh ^[5] del mismo año. Originalmente, se entendía que se usaba la transformada rápida de Fourier para realizar una convolución rápida de bosquejos de conteo . Investigaciones posteriores lo generalizaron a una clase mucho más grande de reducciones de dimensionalidad a través de incrustaciones aleatorias de tensores.

Las incrustaciones aleatorias tensoriales se introdujeron en 2010 en un artículo ^[6] sobre privacidad diferencial y fueron analizadas por primera vez por Rudelson et al. en 2012 en el contexto de la recuperación dispersa. ^[7]

Avron et al. ^[8] fueron los primeros en estudiar las propiedades de incrustación de subespacios de los bosquejos tensoriales, particularmente enfocados en aplicaciones a núcleos polinómicos . En este contexto, se requiere que el bosquejo no solo preserve la norma de cada vector individual con una cierta probabilidad, sino que preserve la norma de todos los vectores en cada subespacio lineal individual . Esta es una propiedad mucho más fuerte y requiere tamaños de bosquejo más grandes, pero permite que los métodos de núcleo se usen de manera muy amplia, como se explora en el libro de David Woodruff. ^[3]

Proyecciones aleatorias tensoriales

El producto de división de caras se define como los productos tensoriales de las filas (fue propuesto por V. Slyusar ^[9] en 1996 ^{[10] [11] [12] [13] [14]} 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 ^{[10] [11] [12] [13]} La razón por la que este producto es útil es la siguiente identidad: ${\displaystyle \mathbf {C} \in \mathbb {R} ^{3\times 3}}$ ${\displaystyle \mathbf {D} \in \mathbb {R} ^{3\times 3}}$ ${\displaystyle \mathbf {C} \bullet \mathbf {D} }$ ${\displaystyle \mathbf {C} \bullet \mathbf {D} =\left[{\begin{array}{c }\mathbf {C} _{1}\otimes \mathbf {D} _{1}\\\hline \mathbf {C} _{2}\otimes \mathbf {D} _{2}\\\hline \mathbf {C} _{3}\otimes \mathbf {D} _{3}\\\end{array}}\right]=\left[{\begin{array}{c c c c c c c c c }\mathbf {C} _{1,1}\mathbf {D} _{1,1}&\mathbf {C} _{1,1}\mathbf {D} _{1,2}&\mathbf {C} _{1,1}\mathbf {D} _{1,3}&\mathbf {C} _{1,2}\mathbf {D} _{1,1}&\mathbf {C} _{1,2}\mathbf {D} _{1,2}&\mathbf {C} _{1,2}\mathbf {D} _{1,3}&\mathbf {C} _{1,3}\mathbf {D} _{1,1}&\mathbf {C} _{1,3}\mathbf {D} _{1,2}&\mathbf {C} _{1,3}\mathbf {D} _{1,3}\\\hline \mathbf {C} _{2,1}\mathbf {D} _{2,1}&\mathbf {C} _{2,1}\mathbf {D} _{2,2}&\mathbf {C} _{2,1}\mathbf {D} _{2,3}&\mathbf {C} _{2,2}\mathbf {D} _{2,1}&\mathbf {C} _{2,2}\mathbf {D} _{2,2}&\mathbf {C} _{2,2}\mathbf {D} _{2,3}&\mathbf {C} _{2,3}\mathbf {D} _{2,1}&\mathbf {C} _{2,3}\mathbf {D} _{2,2}&\mathbf {C} _{2,3}\mathbf {D} _{2,3}\\\hline \mathbf {C} _{3,1}\mathbf {D} _{3,1}&\mathbf {C} _{3,1}\mathbf {D} _{3,2}&\mathbf {C} _{3,1}\mathbf {D} _{3,3}&\mathbf {C} _{3,2}\mathbf {D} _{3,1}&\mathbf {C} _{3,2}\mathbf {D} _{3,2}&\mathbf {C} _{3,2}\mathbf {D} _{3,3}&\mathbf {C} _{3,3}\mathbf {D} _{3,1}&\mathbf {C} _{3,3}\mathbf {D} _{3,2}&\mathbf {C} _{3,3}\mathbf {D} _{3,3}\end{array}}\right].}$

${\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 . Dado que esta operación se puede calcular en tiempo lineal, se puede multiplicar sobre vectores con estructura tensorial mucho más rápido que las matrices normales. ${\displaystyle \circ }$ ${\displaystyle \mathbf {C} \bullet \mathbf {D} }$

Construcción con transformada rápida de Fourier

El bosquejo tensorial de Pham y Pagh ^[4] calcula , donde y son matrices de bosquejo de conteo independientes y es una convolución vectorial . Demuestran que, sorprendentemente, esto equivale a : ¡un bosquejo de conteo del producto tensorial! ${\displaystyle C^{(1)}x\ast C^{(2)}y}$ ${\displaystyle C^{(1)}}$ ${\displaystyle C^{(2)}}$ ${\displaystyle \ast }$ ${\displaystyle C(x\otimes y)}$

Resulta que esta relación se puede ver en términos del producto de división de caras como

${\displaystyle C^{(1)}x\ast C^{(2)}y={\mathcal {F}}^{-1}({\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y)}$, donde es la matriz de transformada de Fourier . ${\displaystyle {\mathcal {F}}}$

Dado que es una matriz ortonormal , no afecta la norma de y puede ignorarse. Lo que queda es que . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}^{-1}}$ ${\displaystyle Cx}$ ${\displaystyle C\sim {\mathcal {C}}^{(1)}\bullet {\mathcal {C}}^{(2)}}$

Por otro lado,

${\displaystyle {\mathcal {F}}(C^{(1)}x\ast C^{(2)}y)={\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y=({\mathcal {F}}C^{(1)}\bullet {\mathcal {F}}C^{(2)})(x\otimes y)}$.

Aplicación a matrices generales

El problema con el algoritmo de boceto tensorial original era que utilizaba matrices de boceto de conteo , que no siempre son reducciones de dimensionalidad muy buenas.

En 2020 ^[15] se demostró que cualquier matriz con filas independientes lo suficientemente aleatorias es suficiente para crear un esquema tensorial. Esto permite utilizar matrices con garantías más sólidas, como las matrices Johnson Lindenstrauss gaussianas reales .

En particular, obtenemos el siguiente teorema

Consideremos una matriz con filas iid , tal que y . Sea independiente y consista en y . ${\displaystyle T}$ ${\displaystyle T_{1},\dots ,T_{m}\in \mathbb {R} ^{d}}$ ${\displaystyle E[(T_{1}x)^{2}]=\|x\|_{2}^{2}}$ ${\displaystyle E[(T_{1}x)^{p}]^{1/p}\leq {\sqrt {ap}}\|x\|_{2}}$ ${\displaystyle T^{(1)},\dots ,T^{(c)}}$ ${\displaystyle T}$ ${\displaystyle M=T^{(1)}\bullet \dots \bullet T^{(c)}}$

Entonces con probabilidad para cualquier vector si ${\displaystyle |\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}}$ ${\displaystyle 1-\delta }$ ${\displaystyle x}$

${\displaystyle m=(4a)^{2c}\varepsilon ^{-2}\log 1/\delta +(2ae)\varepsilon ^{-1}(\log 1/\delta )^{c}}$.

En particular, si las entradas de son obtenemos que coincide con el teorema normal de Johnson Lindenstrauss de cuando es pequeño. ${\displaystyle T}$ ${\displaystyle \pm 1}$ ${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta +\varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$ ${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta )}$ ${\displaystyle \varepsilon }$

El artículo ^[15] también muestra que la dependencia es necesaria para construcciones que utilizan proyecciones tensoriales aleatorias con entradas gaussianas . ${\displaystyle \varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c}}$

Variaciones

Construcción recursiva

Debido a la dependencia exponencial de los bocetos tensoriales basados ​​en el producto de división de caras , en 2020 se desarrolló un enfoque diferente ^[15] que aplica ${\displaystyle c}$

${\displaystyle M(x\otimes y\otimes \cdots )=M^{(1)}(x\otimes (M^{(2)}y\otimes \cdots ))}$

Podemos lograrlo si dejamos que ${\displaystyle M}$

${\displaystyle M=M^{(c)}(M^{(c-1)}\otimes I_{d})(M^{(c-2)}\otimes I_{d^{2}})\cdots (M^{(1)}\otimes I_{d^{c-1}})}$.

Con este método, solo aplicamos el método general de boceto de tensores para ordenar 2 tensores, lo que evita la dependencia exponencial en el número de filas.

Se puede demostrar ^[15] que la combinación de reducciones de dimensionalidad como esta solo aumenta en un factor . ${\displaystyle c}$ ${\displaystyle \varepsilon }$ ${\displaystyle {\sqrt {c}}}$

Construcciones rápidas

La transformada rápida de Johnson-Lindenstrauss es una matriz de reducción de dimensionalidad

Dada una matriz , calcular el producto matriz-vector lleva tiempo. La Transformada Rápida de Johnson Lindenstrauss (FJLT), ^[16] fue introducida por Ailon y Chazelle en 2006. ${\displaystyle M\in \mathbb {R} ^{k\times d}}$ ${\displaystyle Mx}$ ${\displaystyle kd}$

Una versión de este método se lleva a cabo donde ${\displaystyle M=\operatorname {SHD} }$

1. ${\displaystyle D}$es una matriz diagonal donde cada entrada diagonal es independiente. ${\displaystyle D_{i,i}}$ ${\displaystyle \pm 1}$

La multiplicación matriz-vector se puede calcular en el tiempo. ${\displaystyle Dx}$ ${\displaystyle O(d)}$

1. ${\displaystyle H}$es una matriz de Hadamard , que permite la multiplicación matriz-vector en el tiempo ${\displaystyle O(d\log d)}$
2. ${\displaystyle S}$es una matriz de muestreo que consta exclusivamente de ceros, excepto un único 1 en cada fila. ${\displaystyle k\times d}$

Si la matriz diagonal se reemplaza por una que tiene un producto tensorial de valores en la diagonal, en lugar de ser completamente independiente, es posible realizar cálculos rápidos. ${\displaystyle \pm 1}$ ${\displaystyle \operatorname {SHD} (x\otimes y)}$

Como ejemplo de esto, supongamos que son dos vectores independientes y que es una matriz diagonal con en la diagonal. Podemos descomponerla de la siguiente manera: ${\displaystyle \rho ,\sigma \in \{-1,1\}^{2}}$ ${\displaystyle \pm 1}$ ${\displaystyle D}$ ${\displaystyle \rho \otimes \sigma }$ ${\displaystyle \operatorname {SHD} (x\otimes y)}$

${\displaystyle {\begin{aligned}&\operatorname {SHD} (x\otimes y)\\&\quad ={\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\end{bmatrix}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}\rho _{1}&0&0&0\\0&\sigma _{1}\rho _{2}&0&0\\0&0&\sigma _{2}\rho _{1}&0\\0&0&0&\sigma _{2}\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}y_{1}\\x_{2}y_{1}\\x_{1}y_{2}\\x_{2}y_{2}\end{bmatrix}}\\[5pt]&\quad =\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\left({\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}\otimes {\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}\right)\left({\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\otimes {\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]&\quad =\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\otimes \,{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]&\quad ={\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\circ \,{\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}.\end{aligned}}}$

En otras palabras, , se divide en dos transformaciones rápidas de Johnson-Lindenstrauss, y la reducción total toma tiempo en lugar de lo que toma con el enfoque directo. ${\displaystyle \operatorname {SHD} =S^{(1)}HD^{(1)}\bullet S^{(2)}HD^{(2)}}$ ${\displaystyle O(d_{1}\log d_{1}+d_{2}\log d_{2})}$ ${\displaystyle d_{1}d_{2}\log(d_{1}d_{2})}$

El mismo enfoque se puede extender para calcular productos de grado superior, como ${\displaystyle \operatorname {SHD} (x\otimes y\otimes z)}$

Ahle et al. ^[15] muestra que si tiene filas, entonces para cualquier vector con probabilidad , al tiempo que permite una multiplicación rápida con tensores de grado. ${\displaystyle \operatorname {SHD} }$ ${\displaystyle \varepsilon ^{-2}(\log 1/\delta )^{c+1}}$ ${\displaystyle |\|\operatorname {SHD} x\|_{2}-\|x\||\leq \varepsilon \|x\|_{2}}$ ${\displaystyle x\in \mathbb {R} ^{d^{c}}}$ ${\displaystyle 1-\delta }$ ${\displaystyle c}$

Jin et al., ^[17] el mismo año, mostraron un resultado similar para la clase más general de matrices llamada RIP , que incluye las matrices de Hadamard submuestreadas. Demostraron que estas matrices permiten la división en tensores siempre que el número de filas sea . En el caso, esto coincide con el resultado anterior. ${\displaystyle \varepsilon ^{-2}(\log 1/\delta )^{2c-1}\log d}$ ${\displaystyle c=2}$

Estas construcciones rápidas se pueden combinar nuevamente con el enfoque de recursión mencionado anteriormente, lo que da como resultado el boceto tensorial general más rápido.

Bocetos que tienen en cuenta los datos

También es posible realizar el llamado bosquejo tensorial "consciente de los datos". En lugar de multiplicar una matriz aleatoria sobre los datos, los puntos de datos se muestrean de forma independiente con una cierta probabilidad que depende de la norma del punto. ^[18]

Aplicaciones

Núcleos polinómicos explícitos

Los métodos de kernel son populares en el aprendizaje automático, ya que le dan al algoritmo diseñado la libertad de diseñar un "espacio de características" en el que medir la similitud de sus puntos de datos. Un clasificador binario simple basado en kernel se basa en el siguiente cálculo:

${\displaystyle {\hat {y}}(\mathbf {x'} )=\operatorname {sgn} \sum _{i=1}^{n}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),}$

donde son los puntos de datos, es la etiqueta del punto n (ya sea −1 o +1), y es la predicción de la clase de . La función es el núcleo. Ejemplos típicos son el núcleo de la función de base radial , y los núcleos polinómicos como . ${\displaystyle \mathbf {x} _{i}\in \mathbb {R} ^{d}}$ ${\displaystyle y_{i}}$ ${\displaystyle i}$ ${\displaystyle {\hat {y}}(\mathbf {x'} )}$ ${\displaystyle \mathbf {x'} }$ ${\displaystyle k:\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R} }$ ${\displaystyle k(x,x')=\exp(-\|x-x'\|_{2}^{2})}$ ${\displaystyle k(x,x')=(1+\langle x,x'\rangle )^{2}}$

Cuando se utiliza de esta manera, el método kernel se denomina "implícito". A veces es más rápido realizar un método kernel "explícito", en el que se encuentran un par de funciones, tales que . Esto permite expresar el cálculo anterior como ${\displaystyle f,g:\mathbb {R} ^{d}\to \mathbb {R} ^{D}}$ ${\displaystyle k(x,x')=\langle f(x),g(x')\rangle }$

${\displaystyle {\hat {y}}(\mathbf {x'} )=\operatorname {sgn} \sum _{i=1}^{n}y_{i}\langle f(\mathbf {x} _{i}),g(\mathbf {x'} )\rangle =\operatorname {sgn} \left\langle \left(\sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})\right),g(\mathbf {x'} )\right\rangle ,}$

donde el valor se puede calcular de antemano. ${\displaystyle \sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})}$

El problema con este método es que el espacio de características puede ser muy grande. Es decir , . Por ejemplo, para el núcleo polinomial obtenemos y , donde es el producto tensorial y donde . Si ya es grande, puede ser mucho mayor que el número de puntos de datos ( ) y, por lo tanto, el método explícito es ineficiente. ${\displaystyle D>>d}$ ${\displaystyle k(x,x')=\langle x,x'\rangle ^{3}}$ ${\displaystyle f(x)=x\otimes x\otimes x}$ ${\displaystyle g(x')=x'\otimes x'\otimes x'}$ ${\displaystyle \otimes }$ ${\displaystyle f(x),g(x')\in \mathbb {R} ^{D}}$ ${\displaystyle D=d^{3}}$ ${\displaystyle d}$ ${\displaystyle D}$ ${\displaystyle n}$

La idea del bosquejo tensorial es que podemos calcular funciones aproximadas donde incluso pueden ser más pequeñas que , y que aún tienen la propiedad de que . ${\displaystyle f',g':\mathbb {R} ^{d}\to \mathbb {R} ^{t}}$ ${\displaystyle t}$ ${\displaystyle d}$ ${\displaystyle \langle f'(x),g'(x')\rangle \approx k(x,x')}$

^{En 2020 [15]} se demostró que este método funciona incluso para polinomios de alto grado y núcleos de funciones de base radial.

Multiplicación de matrices comprimidas

Supongamos que tenemos dos grandes conjuntos de datos, representados como matrices , y queremos encontrar las filas con los productos internos más grandes . Podríamos calcular y simplemente observar todas las posibilidades. Sin embargo, esto llevaría al menos tiempo y probablemente sería más parecido al uso de técnicas de multiplicación de matrices estándar. ${\displaystyle X,Y\in \mathbb {R} ^{n\times d}}$ ${\displaystyle i,j}$ ${\displaystyle \langle X_{i},Y_{j}\rangle }$ ${\displaystyle Z=XY^{T}\in \mathbb {R} ^{n\times n}}$ ${\displaystyle n^{2}}$ ${\displaystyle n^{2}}$ ${\displaystyle n^{2}d}$

La idea de la multiplicación de matrices comprimidas es la identidad general

${\displaystyle XY^{T}=\sum _{i=1}^{d}X_{i}\otimes Y_{i}}$

donde es el producto tensorial . Como podemos calcular una aproximación ( lineal ) de manera eficiente, podemos sumarlas para obtener una aproximación del producto completo. ${\displaystyle \otimes }$ ${\displaystyle X_{i}\otimes Y_{i}}$

Agrupamiento multilineal compacto

Los bocetos tensoriales se pueden utilizar para disminuir la cantidad de variables necesarias al implementar la agrupación bilineal en una red neuronal .

La agrupación bilineal es la técnica de tomar dos vectores de entrada, de diferentes fuentes, y utilizar el producto tensorial como capa de entrada a una red neuronal. ${\displaystyle x,y}$ ${\displaystyle x\otimes y}$

En ^[19] los autores consideraron utilizar un esquema tensorial para reducir la cantidad de variables necesarias.

En 2017, otro artículo ^[20] toma la FFT de las características de entrada, antes de combinarlas mediante el producto elemento por elemento. Esto nuevamente corresponde al esquema tensorial original.

Referencias

1. "Descomposición de Tucker de bajo rango de tensores grandes usando: Tensor Sketch" (PDF) . amath.colorado.edu . Boulder, Colorado: Universidad de Colorado en Boulder .
2. Ahle, Thomas; Knudsen, Jakob (3 de septiembre de 2019). "Bosquejo tensorial casi óptimo". ResearchGate . Consultado el 11 de julio de 2020 .
3. Woodruff, David P. "El boceto como herramienta para el álgebra lineal numérica Archivado el 22 de octubre de 2022 en Wayback Machine ." Theoretical Computer Science 10.1-2 (2014): 1–157.
4. Ninh, Pham; Pagh, Rasmus (2013). Núcleos polinómicos rápidos y escalables a través de mapas de características explícitas . Conferencia internacional SIGKDD sobre descubrimiento de conocimiento y minería de datos. Association for Computing Machinery. doi :10.1145/2487575.2487591.
5. Pagh, Rasmus (2013). "Multiplicación de matrices comprimidas". ACM Transactions on Computation Theory . 5 (3). Association for Computing Machinery: 1–17. arXiv : 1108.1320 . doi :10.1145/2493252.2493254. S2CID  47560654.
6. Kasiviswanathan, Shiva Prasad, et al. "El precio de publicar de forma privada tablas de contingencia y espectros de matrices aleatorias con filas correlacionadas Archivado el 22 de octubre de 2022 en Wayback Machine ". Actas del cuadragésimo segundo simposio de la ACM sobre teoría de la computación. 2010.
7. Rudelson, Mark y Shuheng Zhou. "Reconstrucción a partir de mediciones aleatorias anisotrópicas Archivado el 17 de octubre de 2022 en Wayback Machine ". Conferencia sobre teoría del aprendizaje. 2012.
8. Avron, Haim; Nguyen, Huy; Woodruff, David (2014). "Incorporaciones de subespacios para el núcleo polinomial" (PDF) . Avances en sistemas de procesamiento de información neuronal . S2CID  16658740.
9. Anna Esteve, Eva Boj y Josep Fortiana (2009): Términos de interacción en la regresión basada en la distancia, Communications in Statistics – Theory and Methods, 38:19, pág. 3501 [1] Archivado el 26 de abril de 2021 en Wayback Machine.
10. Slyusar, VI (1998). "Productos finales en matrices en aplicaciones de radar" (PDF) . Radioelectrónica y sistemas de comunicaciones . 41 (3): 50–53.
11. 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.
12. Slyusar, VI (15 de septiembre de 1997). "Nuevas operaciones de producto de matrices para aplicaciones de radares" (PDF) . Proc. Problemas directos e inversos de teoría de ondas electromagnéticas y acústicas (DIPED-97), Lviv. : 73–74.
13. 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.
14. Slyusar, VI (2003). "Productos faciales generalizados de matrices en modelos de conjuntos de antenas digitales con canales no idénticos" (PDF) . Radioelectrónica y sistemas de comunicaciones . 46 (10): 9–17.
15. Ahle, Thomas; Kapralov, Michael; Knudsen, Jakob; Pagh, Rasmus ; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Bosquejo inconsciente de núcleos polinomiales de alto grado . Simposio ACM-SIAM sobre algoritmos discretos. Asociación para Maquinaria Computacional. arXiv : 1909.01410 . doi : 10.1137/1.9781611975994.9 .
16. 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. Sr.  2277181. S2CID  490517.
17. Jin, Ruhui, Tamara G. Kolda y Rachel Ward. "Transformaciones más rápidas de Johnson-Lindenstrauss mediante productos Kronecker". Preimpresión de arXiv arXiv:1909.04801 (2019).
18. Wang, Yining; Tung, Hsiao-Yu; Smola, Alexander; Anandkumar, Anima. Descomposición tensorial rápida y garantizada mediante bocetos . Avances en sistemas de procesamiento de información neuronal 28 (NIPS 2015). arXiv : 1506.04448 .
19. Gao, Yang, et al. "Compact bilinear pooling Archivado el 20 de enero de 2022 en Wayback Machine ". Actas de la conferencia IEEE sobre visión artificial y reconocimiento de patrones. 2016.
20. Algashaam, Faisal M., et al. "Clasificación periocular multiespectral con agrupamiento multilineal compacto multimodal". IEEE Access 5 (2017): 14572–14578.

Lectura adicional

• Ahle, Thomas; Knudsen, Jakob (3 de septiembre de 2019). "Bosquejo tensorial casi óptimo". ResearchGate . Consultado el 11 de julio de 2020 .
• Slyusar, VI (1998). "Productos finales en matrices en aplicaciones de radar" (PDF) . Radioelectrónica y sistemas de comunicaciones . 41 (3): 50–53.
• 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 (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.
• 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.