Descomposición en valores singulares de orden superior

En álgebra multilineal , la descomposición en valores singulares de orden superior ( HOSVD ) es un nombre inapropiado. No existe una única descomposición tensorial que conserve todas las propiedades definitorias de la SVD matricial. La SVD matricial produce simultáneamente una

• descomposición de rango R y
• subespacios ortonormales para los espacios de filas y columnas.

Estas propiedades no se logran mediante un único algoritmo para tensores de orden superior, sino que se consiguen mediante dos desarrollos algorítmicos distintos y representan dos líneas de investigación diferentes. Harshman, así como el equipo de Carol y Chang, propusieron la descomposición poliádica canónica (CPD), una variante de la descomposición de rango tensorial , en la que un tensor se aproxima como una suma de K tensores de rango 1 para un K especificado por el usuario . LR Tucker propuso una estrategia para calcular subespacios ortonormales para tensores de tercer orden. Algunos aspectos de estos algoritmos se remontan a FL Hitchcock en 1928. ^{[ 1 ]}

De Lathauwer et al. ^{[ 2 ] [ 3 ]} aportaron claridad a los conceptos de Tucker, mientras que Vasilescu y Terzopoulos ^{[ 4 ] [ 5 ] [ 6 ]} aportaron claridad algorítmica. Vasilescu y Terzopoulos ^{[ 4 ] [ 6 ]} introdujeron la SVD en modo M , que es el algoritmo clásico al que actualmente se hace referencia en la literatura como Tucker o HOSVD . El enfoque de Tucker y la implementación de De Lathauwer son secuenciales y se basan en procedimientos iterativos como el descenso de gradiente o el método de potencia. Por el contrario, la SVD en modo M proporciona una solución de forma cerrada que puede ejecutarse secuencialmente y es muy adecuada para la computación paralela.

Esta atribución errónea ha tenido un impacto duradero en el registro académico, oscureciendo la fuente original de un algoritmo ampliamente adoptado y complicando los esfuerzos por rastrear su desarrollo, reproducir resultados y reconocer las contribuciones respectivas de diferentes esfuerzos de investigación.

El término SVD en modo M refleja con precisión el algoritmo empleado. Describe el cálculo real, un conjunto de SVD sobre aplanamientos de modo sin hacer suposiciones sobre la estructura del tensor central ni implicar una descomposición de rango.

Desde entonces se han propuesto variantes robustas y basadas en la norma L1 de este marco de descomposición. ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]}

Para los fines de este artículo, el tensor abstracto${\displaystyle {\mathcal {A}}}$se supone que se da en coordenadas con respecto a alguna base como una matriz de M vías , también denotada por${\displaystyle {\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\cdots \times \cdots I_{m}\cdots \times I_{M}}}$donde M es el número de modos y el orden del tensor.${\displaystyle \mathbb {C} }$son los números complejos e incluyen tanto los números reales como los números reales.${\displaystyle \mathbb {R} }$y los números imaginarios puros.

Dejar${\displaystyle {\mathcal {A}}_{[m]}\in \mathbb {C} ^{I_{m}\times (I_{1}I_{2}\cdots I_{m-1}I_{m+1}\cdots I_{M})}}$denota el aplanamiento del modo m de${\displaystyle {\mathcal {A}}}$, de modo que el índice izquierdo de${\displaystyle {\mathcal {A}}_{[m]}}$corresponde a la${\displaystyle m}$índice 'º${\displaystyle {\mathcal {A}}}$y el índice derecho de${\displaystyle {\mathcal {A}}_{[m]}}$corresponde a todos los demás índices de${\displaystyle {\mathcal {A}}}$combinados. Deje${\displaystyle {\bf {U}}_{m}\in \mathbb {C} ^{I_{m}\times I_{m}}}$sea ​​una matriz unitaria que contiene una base de los vectores singulares izquierdos de la${\displaystyle {\mathcal {A}}_{[m]}}$de tal manera que la j- ésima columna${\displaystyle \mathbf {u} _ {j}}$de${\displaystyle {\bf {U}}_{m}}$corresponde al j -ésimo valor singular más grande de${\displaystyle {\mathcal {A}}_{[m]}}$. Observe que la matriz moda/factor${\displaystyle {\bf {U}}_{m}}$no depende de la definición particular y específica del aplanamiento del modo m . Por las propiedades de la multiplicación multilineal , tenemos$${\displaystyle {\begin{array}{rcl}{\mathcal {A}}&=&{\mathcal {A}}\times ({\bf {I}},{\bf {I}},\ldots ,{\bf {I}})\\&=&{\mathcal {A}}\times ({\bf {U}}_{1}{\bf {U}}_{1}^{H},{\bf {U}}_{2}{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}{\bf {U}}_{M}^{H})\\&=&\left({\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H})\right)\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}),\end{array}}}$$dónde${\displaystyle \cdot ^{H}}$denota la transpuesta conjugada . La segunda igualdad se debe a que la${\displaystyle {\bf {U}}_{m}}$Las son matrices unitarias. Definamos ahora el tensor central .$${\displaystyle {\mathcal {S}}:={\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H}).}$$Luego, el SVD en modo M (HOSVD) ^{[ 2 ]} de${\displaystyle {\mathcal {A}}}$es la descomposición$${\displaystyle {\mathcal {A}}={\mathcal {S}}\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}).}$$La construcción anterior muestra que cada tensor tiene una descomposición en valores singulares (SVD) de modo M (HOSVD).

Al igual que en el caso de la descomposición compacta en valores singulares de una matriz, donde se eliminan las filas y columnas correspondientes a valores singulares nulos, también es posible considerar una descomposición compacta en valores singulares en modo M (HOSVD), que resulta muy útil en diversas aplicaciones.

Supongamos que${\displaystyle {\bf {U}}_{m}\in \mathbb {C} ^{I_{m}\times R_{m}}}$es una matriz con columnas unitarias que contiene una base de los vectores singulares izquierdos correspondientes a los valores singulares no nulos del aplanamiento factor -m estándar${\displaystyle {\mathcal {A}}_{[m]}}$de${\displaystyle {\mathcal {A}}}$. Sean las columnas de${\displaystyle {\bf {U}}_{m}}$ser ordenado de tal manera que el${\displaystyle r_{m}}$columna th${\displaystyle {\bf {u}}_{r_{m}}}$de${\displaystyle {\bf {U}}_{m}}$corresponde a la${\displaystyle r_{m}}$el mayor valor singular distinto de cero de${\displaystyle {\mathcal {A}}_{[m]}}$Dado que las columnas de${\displaystyle {\bf {U}}_{m}}$formar una base para la imagen de${\displaystyle {\mathcal {A}}_{[m]}}$, tenemos$${\displaystyle {\mathcal {A}}_{[m]}={\bf {U}}_{m}{\bf {U}}_{m}^{H}{\mathcal {A}}_{[m]}={\bigl (}{\mathcal {A}}\times _{m}({\bf {U}}_{m}{\bf {U}}_{m}^{H}){\bigr )}_{[m]},}$$donde la primera igualdad se debe a las propiedades de las proyecciones ortogonales (en el producto interno hermitiano) y la última igualdad se debe a las propiedades de la multiplicación multilineal. Como los aplanamientos son aplicaciones biyectivas y la fórmula anterior es válida para todos${\displaystyle m=1,2,\ldots ,m,\ldots ,M}$, encontramos como antes que$${\displaystyle {\begin{array}{rcl}{\mathcal {A}}&=&{\mathcal {A}}\times ({\bf {U}}_{1}{\bf {U}}_{1}^{H},{\bf {U}}_{2}{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}{\bf {U}}_{M}^{H})\\&=&\left({\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H})\right)\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M})\\&=&{\mathcal {S}}\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}),\end{array}}}$$donde el tensor central${\displaystyle {\mathcal {S}}}$ahora es de tamaño${\displaystyle R_{1}\times R_{2}\times \cdots \times R_{M}}$.

El rango multilineal ^{[ 1 ]} de${\displaystyle {\mathcal {A}}}$se denota con rango-${\displaystyle (R_{1},R_{2},\ldots ,R_{M})}$. El rango multilineal es una tupla en${\displaystyle \mathbb {N} ^{M}}$dónde${\displaystyle R_{m}:=\mathrm {rank} ({\mathcal {A}}_{[m]})}$. No todas las tuplas en${\displaystyle \mathbb {N} ^{M}}$son rangos multilineales. ^{[ 11 ]} Los rangos multilineales están acotados por${\displaystyle 1\leq R_{m}\leq I_{m}}$y satisface la restricción${\textstyle R_{m}\leq \prod _{i\neq m}R_{i}}$debe mantenerse. ^{[ 11 ]}

La descomposición en valores singulares (SVD) compacta en modo M (HOSVD) es una descomposición que revela el rango en el sentido de que las dimensiones de su tensor central se corresponden con los componentes del rango multilineal del tensor.

La siguiente interpretación geométrica es válida tanto para la descomposición en valores singulares (SVD) en modo M completa como compacta (HOSVD). Sea${\displaystyle (R_{1},R_{2},\ldots ,R_{M})}$sea ​​el rango multilineal del tensor${\displaystyle {\mathcal {A}}}$. Desde${\displaystyle {\mathcal {S}}\in {\mathbb {C} }^{R_{1}\times R_{2}\times \cdots \times R_{M}}}$es una matriz multidimensional, podemos expandirla de la siguiente manera$${\displaystyle {\mathcal {S}}=\sum _{r_{1}=1}^{R_{1}}\sum _{r_{2}=1}^{R_{2}}\cdots \sum _{r_{M}=1}^{R_{M}}s_{r_{1},r_{2},\ldots ,r_{M}}\mathbf {e} _{r_{1}}\otimes \mathbf {e} _{r_{2}}\otimes \cdots \otimes \mathbf {e} _{r_{M}},}$$dónde${\displaystyle \mathbf {e} _{r_{m}}}$es el${\displaystyle r_{m}}$vector base estándar de${\displaystyle {\mathbb {C} }^{I_{m}}}$Por definición de la multiplicación multilineal, se cumple que$${\displaystyle {\mathcal {A}}=\sum _{r_{1}=1}^{R_{1}}\sum _{r_{2}=1}^{R_{2}}\cdots \sum _{r_{M}=1}^{R_{M}}s_{r_{1},r_{2},\ldots ,r_{M}}\mathbf {u} _{r_{1}}\otimes \mathbf {u} _{r_{2}}\otimes \cdots \otimes \mathbf {u} _{r_{M}},}$$donde el${\displaystyle \mathbf {u} _{r_{m}}}$son las columnas de${\displaystyle {\bf {U}}_{m}\in {\mathbb {C} }^{I_{m}\times R_{m}}}$Es fácil verificar que${\displaystyle B=\{\mathbf {u} _{r_{1}}\otimes \mathbf {u} _{r_{2}}\otimes \cdots \otimes \mathbf {u} _{r_{M}}\}_{r_{1},r_{2},\ldots ,r_{M}}}$es un conjunto ortonormal de tensores. Esto significa que el SVD en modo M (HOSVD) puede interpretarse como una forma de expresar el tensor.${\displaystyle {\mathcal {A}}}$con respecto a una base ortonormal específicamente elegida${\displaystyle B}$con los coeficientes dados como la matriz multidimensional${\displaystyle {\mathcal {S}}}$.

Dejar${\displaystyle {\mathcal {A}}\in {\mathbb {C} }^{I_{1}\times I_{2}\times \cdots \times I_{M}}}$ser un tensor con un rango-${\displaystyle (R_{1},R_{2},\ldots ,R_{M})}$, dónde${\displaystyle \mathbb {C} }$contiene los reales${\displaystyle \mathbb {R} }$como un subconjunto.

En aplicaciones como las que se mencionan a continuación, un problema común consiste en aproximar un tensor dado.${\displaystyle {\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\times \cdots \times I_{m}\cdots \times I_{M}}}$por uno con un rango multilineal reducido. Formalmente, si el rango multilineal de${\displaystyle {\mathcal {A}}}$se denota por${\displaystyle \mathrm {rank-} (R_{1},R_{2},\ldots ,R_{m},\ldots ,R_{M})}$, luego calculando el óptimo${\displaystyle {\mathcal {\bar {A}}}}$que se aproxima${\displaystyle {\mathcal {A}}}$para un valor reducido dado${\displaystyle \mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{m},\ldots ,{\bar {R}}_{M})}$ es un sistema no lineal no convexo${\displaystyle \ell _{2}}$-problema de optimización $${\displaystyle \min _{{\mathcal {\bar {A}}}\in \mathbb {C} ^{I_{1}\times I_{2}\times \cdots \times I_{M}}}{\frac {1}{2}}\|{\mathcal {A}}-{\mathcal {\bar {A}}}\|_{F}^{2}\quad {\text{s.t.}}\quad \mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{M}),}$$dónde${\displaystyle ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{M})\in \mathbb {N} ^{M}}$es el rango multilineal reducido con${\displaystyle 1\leq {\bar {R}}_{m}<R_{m}\leq I_{m}}$y la norma${\displaystyle \|.\|_{F}}$es la norma de Frobenius .

Una idea sencilla para intentar resolver este problema de optimización es truncar la SVD (compacta) en el paso 2 del cálculo clásico o del entrelazado. Una SVD/HOSVD en modo M truncada clásicamente se obtiene reemplazando el paso 2 en el cálculo clásico por

• Calcular un rango-${\displaystyle {\bar {R}}_{m}}$SVD truncada${\displaystyle {\mathcal {A}}_{[m]}\approx U_{m}\Sigma _{m}V_{m}^{T}}$y almacenar la parte superior${\displaystyle {\bar {R}}_{m}}$vectores singulares izquierdos${\displaystyle U_{m}\in F^{I_{m}\times {\bar {R}}_{m}}}$;

mientras que una SVD de modo M truncada secuencialmente (HOSVD) (o SVD de modo M truncada sucesivamente (HOSVD) ) se obtiene reemplazando el paso 2 en el cálculo entrelazado por

• Calcular un rango-${\displaystyle {\bar {R}}_{m}}$SVD truncada${\displaystyle {\mathcal {A}}_{[m]}^{m-1}\approx U_{m}\Sigma _{m}V_{m}^{T}}$y almacenar la parte superior${\displaystyle {\bar {R}}_{m}}$vectores singulares izquierdos${\displaystyle U_{m}\in F^{I_{m}\times {\bar {R}}_{m}}}$Desafortunadamente, la truncación no resulta en una solución óptima para el mejor problema de optimización de rango multilineal bajo. ^{[ 2 ] [ 5 ] [ 12 ] [ 14 ]} Sin embargo, tanto la SVD/HOSVD de modo M truncada clásica como la intercalada resultan en una solución cuasi-óptima : ^{[ 5 ] [ 12 ] [ 13 ] [ 15 ]} si${\displaystyle {\mathcal {\bar {A}}}_{t}}$denota la descomposición en valores singulares (SVD) de modo M truncada clásica o secuencialmente (HOSVD) y${\displaystyle {\mathcal {\bar {A}}}^{*}}$denota la solución óptima al mejor problema de aproximación multilineal de bajo rango, entonces$${\displaystyle \|{\mathcal {A}}-{\mathcal {\bar {A}}}_{t}\|_{F}\leq {\sqrt {M}}\|{\mathcal {A}}-{\mathcal {\bar {A}}}^{*}\|_{F};}$$En la práctica, esto significa que si existe una solución óptima con un pequeño error, entonces una descomposición en valores singulares (SVD) o una descomposición en valores singulares de orden superior (HOSVD) truncada en modo M también proporcionará una solución suficientemente buena para muchos de los propósitos previstos.

La descomposición en valores singulares en modo M (HOSVD/Tucker) se aplica con mayor frecuencia a la extracción de información relevante de matrices multidimensionales.

A principios de la década de 2000, Vasilescu abordó cuestiones causales reformulando los problemas de análisis, reconocimiento y síntesis de datos como problemas de tensores multilineales. El poder del marco tensorial se demostró al descomponer y representar una imagen en términos de sus factores causales de formación de datos, en el contexto de firmas de movimiento humano para el reconocimiento de la marcha, ^{[ 16 ]} el reconocimiento facial (TensorFaces ^{[ 17 ] [ 18 ])} y los gráficos por computadora (TensorTextures). ^{[ 19 ]}

La descomposición en valores singulares en modo M (HOSVD) se ha aplicado con éxito al procesamiento de señales y a grandes conjuntos de datos, por ejemplo, en el procesamiento de señales genómicas. ^{[ 20 ] [ 21 ] [ 22 ]} Estas aplicaciones también inspiraron una descomposición en valores singulares de orden superior (HO GSVD) ^{[ 23 ]} y una descomposición en valores singulares tensorial. ^{[ 24 ]}

También se ha aplicado una combinación de SVD en modo M (HOSVD) y SVD para la detección de eventos en tiempo real a partir de flujos de datos complejos (datos multivariados con dimensiones espaciales y temporales) en la vigilancia de enfermedades . ^{[ 25 ]}

También se utiliza en el diseño de controladores basados ​​en la transformación de modelos de producto tensorial . ^{[ 26 ] [ 27 ]}

El concepto de SVD de modo M (HOSVD) fue trasladado a funciones por Baranyi y Yam a través de la transformación del modelo TP . ^{[ 26 ] [ 27 ]} Esta extensión condujo a la definición de la forma canónica de SVD/HOSVD de modo M de funciones de producto tensorial y modelos de sistemas de parámetros variables lineales ^{[ 28 ]} y a la teoría de optimización de control basada en la manipulación de la envoltura convexa , véase la transformación del modelo TP en teorías de control .

Se propuso aplicar la descomposición en valores singulares en modo M (HOSVD) al análisis de datos multivariados de forma no supervisada ^{[ 29 ]} y se aplicó con éxito al descubrimiento de fármacos in silico a partir de la expresión génica. ^{[ 30 ]}

L1-Tucker es la variante robusta de la descomposición de Tucker basada en la norma L1 . ^{[ 8 ] [ 9 ]} L1-HOSVD es el análogo de M-mode SVD(HOSVD) para la solución de L1-Tucker. ^{[ 8 ] [ 10 ]}