stringtranslate.com

Descomposición en valores singulares de orden superior

En álgebra multilineal , la descomposición en valores singulares de orden superior ( HOSVD ) de un tensor es una descomposición de Tucker ortogonal específica . Puede considerarse como un tipo de generalización de la descomposición en valores singulares de la matriz . Tiene aplicaciones en visión por computadora , gráficos por computadora , aprendizaje automático , computación científica y procesamiento de señales . Algunos aspectos se pueden rastrear hasta FL Hitchcock en 1928, [1] pero fue LR Tucker quien desarrolló para tensores de tercer orden la descomposición general de Tucker en la década de 1960, [2] [3] [4] defendida además por L. De Lathauwer et al. [5] en su trabajo de SVD multilineal que emplea el método de potencia, o defendida por Vasilescu y Terzopoulos que desarrollaron SVD en modo M, un algoritmo paralelo que emplea la SVD matricial.

El término descomposición en valores singulares de orden superior (HOSVD) fue acuñado por DeLathauwer, pero el algoritmo al que se hace referencia comúnmente en la literatura como HOSVD y que se atribuye a Tucker o DeLathauwer fue desarrollado por Vasilescu y Terzopoulos. [6] [7] [8] También se han propuesto variantes robustas y basadas en la norma L1 de HOSVD. [9] [10] [11] [12]

Definición

Para los fines de este artículo, se supone que el tensor abstracto se da en coordenadas con respecto a alguna base como una matriz de M vías , también denotada por , donde M es el número de modos y el orden del tensor. son los números complejos e incluye tanto los números reales como los números imaginarios puros.

Sea el aplanamiento estándar del modo- m de , de modo que el índice izquierdo de corresponde al 'ésimo índice y el índice derecho de corresponde a todos los demás índices de combinados. Sea una matriz unitaria que contiene una base de los vectores singulares izquierdos de tal que la j -ésima columna de corresponde al j -ésimo valor singular más grande de . Observe que la matriz de modo/factor no depende del particular de la definición específica del aplanamiento del modo m . Por las propiedades de la multiplicación multilineal , tenemos donde denota la transpuesta conjugada . La segunda igualdad es porque las son matrices unitarias. Definamos ahora el tensor central Entonces, la HOSVD [5] de es la descomposición La construcción anterior muestra que cada tensor tiene una HOSVD.

HOSVD compacto

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 los valores singulares que desaparecen, también es posible considerar una HOSVD compacta , que es muy útil en aplicaciones.

Supongamos que es una matriz con columnas unitarias que contienen una base de los vectores singulares izquierdos correspondientes a los valores singulares distintos de cero del factor estándar- m aplanamiento de . Dejemos que las columnas de se ordenen de modo que la ésima columna de corresponda al ésimo valor singular distinto de cero más grande de . Dado que las columnas de forman una base para la imagen de , tenemos donde la primera igualdad se debe a las propiedades de las proyecciones ortogonales (en el producto interno hermítico) y la última igualdad se debe a las propiedades de la multiplicación multilineal. Como los aplanamientos son mapas biyectivos y la fórmula anterior es válida para todos los , encontramos como antes que donde el tensor central ahora tiene un tamaño .

Rango multilineal

El rango multilineal [1] de se denota con rango- . El rango multilineal es una tupla en donde . No todas las tuplas en son rangos multilineales. [13] Los rangos multilineales están limitados por y satisfacen la restricción debe cumplirse. [13]

La HOSVD compacta es una descomposición que revela rango en el sentido de que las dimensiones de su tensor central corresponden con los componentes del rango multilineal del tensor.

Interpretación

La siguiente interpretación geométrica es válida tanto para la HOSVD completa como para la compacta. Sea el rango multilineal del tensor . Como es una matriz multidimensional, podemos expandirla de la siguiente manera donde es el ésimo vector base estándar de . Por definición de la multiplicación multilineal, se cumple que donde son las columnas de . Es fácil verificar que es un conjunto ortonormal de tensores. Esto significa que la HOSVD puede interpretarse como una forma de expresar el tensor con respecto a una base ortonormal elegida específicamente con los coeficientes dados como la matriz multidimensional .

Cálculo

Sea un tensor con rango , donde contiene los números reales como un subconjunto.

Computación clásica

La estrategia para calcular la SVD multilineal y la SVD de modo M fue introducida en la década de 1960 por LR Tucker [3] , defendida posteriormente por L. De Lathauwer et al. [ 5] y por Vasilescu y Terzopulous. [8] [6] El término HOSVD fue acuñado por Lieven De Lathauwer, pero el algoritmo al que normalmente se hace referencia en la literatura como HOSVD fue introducido por Vasilescu y Terzopoulos [6] [8] con el nombre de SVD de modo M. Es un cálculo paralelo que emplea la SVD matricial para calcular las matrices de modo ortonormal.

SVD en modo M

Fuentes: [6] [8]

  1. Construir el modelo de aplanamiento ;
  2. Calcular la descomposición en valores singulares (compactos) y almacenar los vectores singulares de la izquierda ;

Cálculo de entrelazado

Una estrategia que es significativamente más rápida cuando parte o la totalidad consiste en entrelazar el cálculo del tensor central y las matrices factoriales, como sigue: [14] [15] [16]

Computación in situ

El HOSVD se puede calcular en el lugar a través del algoritmo de descomposición en valores singulares de orden superior truncado secuencialmente fusionado en el lugar (FIST-HOSVD) [16] sobrescribiendo el tensor original con el tensor central del HOSVD, lo que reduce significativamente el consumo de memoria en el cálculo del HOSVD.

Aproximación

En aplicaciones como las que se mencionan a continuación, un problema común consiste en aproximar un tensor dado por uno con un rango multilineal reducido. Formalmente, si el rango multilineal de se denota por , entonces calcular el óptimo que se aproxima para un reducido dado es un problema de optimización no lineal no convexa donde es el rango multilineal reducido con , y la norma 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 entrelazado. Una HOSVD truncada clásicamente se obtiene reemplazando el paso 2 en el cálculo clásico por

mientras que un HOSVD truncado secuencialmente (o un HOSVD truncado sucesivamente ) se obtiene reemplazando el paso 2 en el cálculo entrelazado por

Aplicaciones

El HOSVD se aplica más comúnmente a la extracción de información relevante de matrices multidireccionales.

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

El HOSVD se ha aplicado con éxito al procesamiento de señales y big data, por ejemplo, en el procesamiento de señales genómicas. [22] [23] [24] Estas aplicaciones también inspiraron un GSVD de orden superior (HO GSVD) [25] y un GSVD tensorial. [26]

También se ha aplicado una combinación de 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 . [27]

También se utiliza en el diseño de controladores basados ​​en la transformación del modelo de producto tensorial . [28] [29]

El concepto de HOSVD fue trasladado a las funciones por Baranyi y Yam a través de la transformación del modelo TP . [28] [29] Esta extensión condujo a la definición de la forma canónica basada en HOSVD de las funciones de producto tensorial y los modelos de sistemas de variación de parámetros lineales [30] y a la teoría de optimización de control basada en la manipulación de la envoltura convexa, consulte la transformación del modelo TP en las teorías de control .

Se propuso aplicar HOSVD al análisis de datos de múltiples vistas [31] y se aplicó con éxito al descubrimiento de fármacos in silico a partir de la expresión genética. [32]

Variante robusta de la norma L1

L1-Tucker es la variante robusta basada en la norma L1 de la descomposición de Tucker . [10] [11] L1-HOSVD es el análogo de HOSVD para la solución de L1-Tucker. [10] [12]

Referencias

  1. ^ ab Hitchcock, Frank L (1 de abril de 1928). "Invariantes múltiples y rango generalizado de una matriz o tensor de M-Way". Revista de matemáticas y física . 7 (1–4): 39–79. doi :10.1002/sapm19287139. ISSN  1467-9590.
  2. ^ Tucker, Ledyard R. (1966-09-01). "Algunas notas matemáticas sobre el análisis factorial de tres modos". Psychometrika . 31 (3): 279–311. doi :10.1007/bf02289464. ISSN  0033-3123. PMID  5221127. S2CID  44301099.
  3. ^ ab Tucker, LR (1963). "Implicaciones del análisis factorial de matrices de tres vías para la medición del cambio". En CW Harris (Ed.), Problemas en la medición del cambio. Madison, Wis.: Univ. Wis. Press. : 122–137.
  4. ^ Tucker, LR (1964). "La extensión del análisis factorial a matrices tridimensionales". En N. Frederiksen y H. Gulliksen (Eds.), Contribuciones a la psicología matemática. Nueva York: Holt, Rinehart y Winston : 109–127.
  5. ^ abcd De Lathauwer, L.; De Moor, B.; Vandewalle, J. (1 de enero de 2000). "Una descomposición multilineal en valores singulares". Revista SIAM sobre análisis de matrices y aplicaciones . 21 (4): 1253–1278. CiteSeerX 10.1.1.102.9135 . doi :10.1137/s0895479896305696. ISSN  0895-4798. 
  6. ^ abcde MAO Vasilescu, D. Terzopoulos (2002) con el nombre de SVD en modo M. El SVD en modo M es adecuado para computación paralela y emplea la matriz SVD "Análisis multilineal de conjuntos de imágenes: TensorFaces" Archivado el 29 de diciembre de 2022 en Wayback Machine , Proc. 7.ª Conferencia Europea sobre Visión por Computador (ECCV'02), Copenhague, Dinamarca, mayo de 2002
  7. ^ MAO Vasilescu, D. Terzopoulos (2003) "Análisis de subespacios multilineales de conjuntos de imágenes", "Actas de la Conferencia IEEE sobre visión artificial y reconocimiento de patrones (CVPR'03), Madison, WI, junio de 2003"
  8. ^ abcd MAO Vasilescu, D. Terzopoulos (2005) "Análisis de componentes independientes multilineales", "Actas de la Conferencia IEEE sobre visión artificial y reconocimiento de patrones (CVPR'05), San Diego, CA, junio de 2005, vol. 1, 547–553".
  9. ^ Godfarb, Donald; Zhiwei, Qin (2014). "Recuperación robusta de tensores de bajo rango: modelos y algoritmos". Revista SIAM sobre análisis de matrices y aplicaciones . 35 (1): 225–253. arXiv : 1311.6182 . doi :10.1137/130905010. S2CID  1051205.
  10. ^ abc Chachlakis, Dimitris G.; Prater-Bennette, Ashley; Markopoulos, Panos P. (22 de noviembre de 2019). "Descomposición del tensor de Tucker según la norma L1". IEEE Access . 7 : 178454–178465. arXiv : 1904.06455 . doi : 10.1109/ACCESS.2019.2955134 .
  11. ^ ab Markopoulos, Panos P.; Chachlakis, Dimitris G.; Papalexakis, Evangelos (abril de 2018). "La solución exacta para la descomposición de TUCKER2 según la norma L1 de rango 1". IEEE Signal Processing Letters . 25 (4): 511–515. arXiv : 1710.11306 . Código Bibliográfico :2018ISPL...25..511M. doi :10.1109/LSP.2018.2790901. S2CID  3693326.
  12. ^ ab Markopoulos, Panos P.; Chachlakis, Dimitris G.; Prater-Bennette, Ashley (21 de febrero de 2019). "Descomposición en valores singulares de orden superior según la norma L1". Conferencia global IEEE de 2018 sobre procesamiento de señales e información (GlobalSIP) . págs. 1353–1357. doi :10.1109/GlobalSIP.2018.8646385. ISBN . 978-1-7281-1295-4.S2CID67874182  .​
  13. ^ ab Carlini, Enrico; Kleppe, Johannes (2011). "Rangos derivados de aplicaciones multilineales". Revista de Álgebra Pura y Aplicada . 215 (8): 1999–2004. doi : 10.1016/j.jpaa.2010.11.010 .
  14. ^ abc Vannieuwenhoven, N.; Vandebril, R.; Meerbergen, K. (1 de enero de 2012). "Una nueva estrategia de truncamiento para la descomposición en valores singulares de orden superior". Revista SIAM de informática científica . 34 (2): A1027–A1052. Bibcode :2012SJSC...34A1027V. doi :10.1137/110836067. ISSN  1064-8275. S2CID  15318433.
  15. ^ de Hackbusch, Wolfgang (2012). Espacios tensoriales y cálculo numérico de tensores | SpringerLink . Springer Series in Computational Mathematics. Vol. 42. doi :10.1007/978-3-642-28027-6. ISBN 978-3-642-28026-9.S2CID117253621  .​
  16. ^ abcd Cobb, Benjamin; Kolla, Hemanth; Phipps, Eric; Çatalyürek, Ümit V. (2022). FIST-HOSVD: Descomposición en valores singulares de orden superior truncada secuencialmente y fusionada en el lugar . Plataforma para la computación científica avanzada (PASC). doi : 10.1145/3539781.3539798 . ISBN . 9781450394109.
  17. ^ Grasedyck, L. (1 de enero de 2010). "Descomposición jerárquica de tensores en valores singulares". Revista SIAM sobre análisis de matrices y aplicaciones . 31 (4): 2029–2054. CiteSeerX 10.1.1.660.8333 . doi :10.1137/090764189. ISSN  0895-4798. 
  18. ^ MAO Vasilescu (2002) "Firmas de movimiento humano: análisis, síntesis, reconocimiento", Actas de la Conferencia internacional sobre reconocimiento de patrones (ICPR 2002), vol. 3, Ciudad de Quebec, Canadá, agosto de 2002, 456–460.
  19. ^ MAO Vasilescu, D. Terzopoulos (2003) "Análisis de subespacios multilineales para conjuntos de imágenes", MAO Vasilescu, D. Terzopoulos, Proc. Computer Vision and Pattern Recognition Conf. (CVPR '03), Vol. 2, Madison, WI, junio de 2003, 93–99.
  20. ^ MAO Vasilescu, D. Terzopoulos (2002) "Análisis multilineal de conjuntos de imágenes: TensorFaces", Proc. 7th European Conference on Computer Vision (ECCV'02), Copenhague, Dinamarca, mayo de 2002, en Computer Vision -- ECCV 2002, Lecture Notes in Computer Science, vol. 2350, A. Heyden et al. (Eds.), Springer-Verlag, Berlín, 2002, 447–460.
  21. ^ MAO Vasilescu, D. Terzopoulos (2004) "TensorTextures: Multilinear Image-Based Rendering", MAO Vasilescu y D. Terzopoulos, Proc. Conferencia ACM SIGGRAPH 2004 Los Ángeles, CA, agosto de 2004, en Actas de Computer Graphics, Serie de conferencias anuales, 2004, 336–342.
  22. ^ L. Omberg; GH Golub; O. Alter (noviembre de 2007). "Una descomposición en valores singulares de orden superior mediante tensores para el análisis integrador de datos de microarrays de ADN de diferentes estudios". PNAS . 104 (47): 18371–18376. Bibcode :2007PNAS..10418371O. doi : 10.1073/pnas.0709146104 . PMC 2147680 . PMID  18003902. 
  23. ^ L. Omberg; JR Meyerson; K. Kobayashi; LS Drury; JFX Diffley; O. Alter (octubre de 2009). "Efectos globales de la replicación del ADN y la actividad del origen de la replicación del ADN en la expresión génica eucariota". Biología de sistemas moleculares . 5 : 312. doi :10.1038/msb.2009.70. PMC 2779084. PMID 19888207.  Destacado. 
  24. ^ C. Muralidhara; AM Gross; RR Gutell; O. Alter (abril de 2011). "La descomposición del tensor revela convergencias y divergencias evolutivas concurrentes y correlaciones con motivos estructurales en el ARN ribosómico". PLOS ONE . ​​6 (4): e18768. Bibcode :2011PLoSO...618768M. doi : 10.1371/journal.pone.0018768 . PMC 3094155 . PMID  21625625. Destacado. 
  25. ^ SP Ponnapalli; MA Saunders; CF Van Loan; O. Alter (diciembre de 2011). "Una descomposición en valores singulares generalizada de orden superior para la comparación de la expresión global de ARNm de múltiples organismos". PLOS ONE . ​​6 (12): e28072. Bibcode :2011PLoSO...628072P. doi : 10.1371/journal.pone.0028072 . PMC 3245232 . PMID  22216090. Destacado. 
  26. ^ P. Sankaranarayanan; TE Schomay; KA Aiello; O. Alter (abril de 2015). "El tensor GSVD de perfiles de número de copias de ADN tumoral y normal emparejados por plataforma y paciente descubre patrones cromosómicos de alteraciones exclusivas del tumor consistentes con la plataforma que codifican la transformación celular y predicen la supervivencia del cáncer de ovario". PLOS ONE . ​​10 (4): e0121396. Bibcode :2015PLoSO..1021396S. doi : 10.1371/journal.pone.0121396 . PMC 4398562 . PMID  25875127. Comunicado de prensa de AAAS EurekAlert! y función de podcast de NAE. 
  27. ^ Hadi Fanaee-T; João Gama (mayo de 2015). "EigenEvent: Un algoritmo para la detección de eventos a partir de flujos de datos complejos en la vigilancia sindrómica". Análisis inteligente de datos . 19 (3): 597–616. arXiv : 1406.3496 . Código Bibliográfico :2014arXiv1406.3496F. doi :10.3233/IDA-150734. S2CID  17966555.
  28. ^ ab P. Baranyi (abril de 2004). "Transformación del modelo TP como una forma de diseño de controladores basado en LMI". IEEE Transactions on Industrial Electronics . 51 (2): 387–400. doi :10.1109/tie.2003.822037. S2CID  7957799.
  29. ^ ab P. Baranyi; D. Tikk; Y. Yam; RJ Patton (2003). "De ecuaciones diferenciales al diseño de controladores PDC mediante transformación numérica". Computadoras en la industria . 51 (3): 281–297. doi :10.1016/s0166-3615(03)00058-7.
  30. ^ P. Baranyi; L. Szeidl; P. Várlaki; Y. Yam (3–5 de julio de 2006). Definición de la forma canónica basada en HOSVD de los modelos dinámicos politópicos . 3.ª Conferencia Internacional sobre Mecatrónica (ICM 2006). Budapest, Hungría. págs. 660–665.
  31. ^ Yh. Taguchi (agosto de 2017). "Extracción de características no supervisada basada en descomposición de tensores aplicada a productos matriciales para procesamiento de datos de múltiples vistas". PLOS ONE . ​​12 (8): e0183933. Bibcode :2017PLoSO..1283933T. doi : 10.1371/journal.pone.0183933 . PMC 5571984 . PMID  28841719. 
  32. ^ Yh. Taguchi (octubre de 2017). "Identificación de fármacos candidatos mediante extracción de características no supervisada basada en descomposición de tensores en el análisis integrado de la expresión génica entre enfermedades y conjuntos de datos de DrugMatrix". Scientific Reports . 7 (1): 13733. Bibcode :2017NatSR...713733T. doi :10.1038/s41598-017-13003-0. PMC 5653784 . PMID  29062063.