Rozklad singulární hodnoty vyššího řádu - Higher-order singular value decomposition
v multilineární algebra, rozklad singulární hodnoty vyššího řádu (HOSVD) a tenzor je specifický ortogonální Tuckerův rozklad. Lze to považovat za jedno zobecnění matice rozklad singulární hodnoty. HOSVD má aplikace v počítačová grafika, strojové učení, vědecké výpočty, a zpracování signálu. Některé klíčové složky HOSVD lze vysledovat až v minulosti F. L. Hitchcock v roce 1928,[1] ale bylo L. R. Tucker který vyvinul pro tenzory třetího řádu generála Tuckerův rozklad v 60. letech[2][3][4] včetně HOSVD. HOSVD jako jeho vlastní rozklad dále prosazoval L. De Lathauwer et al.[5] v roce 2000. Robustní a L1-norma Byly rovněž navrženy varianty HOSVD na bázi.[6][7][8][9]
Vzhledem k tomu, že HOSVD byl studován v mnoha vědeckých oborech, je někdy historicky označován jako víceřádkový rozklad singulární hodnoty, m-režim SVDnebo kostka SVD, a někdy je nesprávně identifikován s Tuckerovým rozkladem.
Definice
Pro účely tohoto článku je to abstraktní tenzor Předpokládá se, že je uveden v souřadnicích s ohledem na nějaký základ jako a vícerozměrné pole, také označeno , v , kde d je řád tenzoru a je buď nebo .
Nechat být unitární matice obsahující základ levých singulárních vektorů standardní faktor-k zploštění z takové, že jth sloupec z odpovídá jt největší singulární hodnota . Všimněte si, že faktorová matice nezávisí na konkrétní svobodě volby v definici standardního faktoruk zploštění. Podle vlastností multilineární násobení, my máme
Kompaktní HOSVD
Stejně jako v případě kompaktního singulárního rozkladu matice je také možné uvažovat a kompaktní HOSVD, což je v aplikacích velmi užitečné.
Předpokládat, že je matice s jednotnými sloupci obsahující základ levých singulárních vektorů odpovídajících nenulovým singulárním hodnotám standardního faktoru -k zploštění z . Nechte sloupce být tříděny tak, aby jth sloupec z odpovídá jnejvětší nenulová singulární hodnota . Vzhledem k tomu, že sloupce tvoří základ pro obraz , my máme
Multilineární hodnost
N-tice kde se nazývá multilineární hodnost[1] z . Podle definice má každý tenzor jedinečnou multilineární hodnost a jeho komponenty jsou omezeny . Ne všechny n-tice jsou multilineární řady.[10] Zejména je známo, že musí držet.[10]
Kompaktní HOSVD je faktorem odhalujícím hodnost v tom smyslu, že rozměry jeho tenzoru jádra odpovídají složkám multilineární řady tenzoru.
Výklad
Následující geometrická interpretace platí pro plnou i kompaktní HOSVD. Nechat být multilineární hodnost tenzoru . Od té doby je vícerozměrné pole, můžeme jej rozšířit následujícím způsobem
Výpočet
Nechat , kde je buď nebo , být tenzorem multilineární hodnosti .
Klasický výpočet
Klasickou strategii pro výpočet kompaktního HOSVD představil v roce 1966 L. R. Tucker[2] a dále obhajuje L. De Lathauwer et al.;[5] je založen na definici rozkladu. Je třeba provést další tři kroky:
- Pro , Udělej následující:
- Vytvořte standardní faktor -k zploštění ;
- Vypočítat (kompaktní) rozklad singulární hodnoty a uložte levé singulární vektory ;
- Vypočítejte tenzor jádra přes multilineární násobení
Prokládaný výpočet
Strategie, která je výrazně rychlejší, když některé nebo všechny sestává z prokládání výpočtu tenzoru jádra a faktorových matic následovně:[11][12]
- Soubor ;
- Pro proveďte následující:
- Vytvořte standardní faktor -k zploštění ;
- Vypočítejte (kompaktní) rozklad singulární hodnoty a uložte levé singulární vektory ;
- Soubor , nebo ekvivalentně .
Přiblížení
V aplikacích, jako jsou ty, které jsou uvedeny níže, běžný problém spočívá v aproximaci daného tenzoru jedním z nízkých multilineárních hodnot. Formálně, pokud označuje multilineární hodnost , pak nelineární nekonvexní -optimalizační problém je
Na základě výše uvedených algoritmů pro výpočet kompaktního HOSVD je přirozeným nápadem pokusit se vyřešit tento problém s optimalizací zkrátit (kompaktní) SVD v kroku 2 klasického nebo prokládaného výpočtu. A klasicky zkrácený HOSVD se získá nahrazením kroku 2 v klasickém výpočtu znakem
- Vypočítat hodnocení zkrácený SVD a horní část uložte levé singulární vektory ;
zatímco a postupně zkrácen HOSVD (nebo postupně zkrácen HOSVD) se získá nahrazením kroku 2 v prokládaném výpočtu znakem
- Vypočítat hodnocení zkrácený SVD a horní část uložte levé singulární vektory ;
Bohužel ani jedna z těchto strategií nevede k optimálnímu řešení nejlepšího problému optimalizace nízkého multilineárního pořadí,[5][11] na rozdíl od případu matice, kde Eckart-Youngova věta drží. Výsledkem klasicky i sekvenčně zkráceného HOSVD však je a kvazi-optimální řešení:[11][12][13] -li označuje klasicky nebo postupně zkrácený HOSVD a potom označuje optimální řešení problému s nejlepší aproximací nízkého multilineárního řádu
Aplikace
HOSVD se nejčastěji používá k extrakci příslušných informací z vícecestných polí.
Kolem roku 2001 Vasilescu přetvořil problémy s analýzou dat, rozpoznáváním a syntézou jako multilineární tenzorové problémy na základě poznatku, že většina pozorovaných dat je výsledkem několika kauzálních faktorů formování dat a jsou vhodná pro multimodální tenzorovou analýzu dat. Síla tenzorového rámce byla vizuálně a matematicky přesvědčivě předvedena rozložením a představením obrazu z hlediska jeho kauzálních faktorů formování dat, v kontextu Human Motion Signatures,[14] rozpoznávání obličejů-TensorFaces[15][16] a počítačová grafika - TensorTextures.[17]
HOSVD byl úspěšně aplikován na zpracování signálu a velkých dat, například při zpracování genomového signálu.[18][19][20] Tyto aplikace také inspirovaly GSVD vyššího řádu (HO GSVD)[21] a tenzor GSVD.[22]
Kombinace HOSVD a SVD byla také použita pro detekci událostí v reálném čase ze složitých datových toků (vícerozměrná data s prostorovými a časovými rozměry) v dohled nad chorobami.[23]
Používá se také v transformace modelu produktu tensor - návrh řadiče na základě.[24][25] v multilineární podprostorové učení,[26] to bylo aplikováno na modelování tenzorových objektů[27] pro rozpoznávání chůze.
Koncept HOSVD přenesli do funkcí Baranyi a Yam prostřednictvím Transformace modelu TP.[24][25] Toto rozšíření vedlo k definici kanonické formy funkcí tenzorového produktu založené na HOSVD a modelech systému s lineárními parametry[28] a k teorii optimalizace řízení založené na manipulaci s konvexním trupem, viz Transformace modelu TP v řídících teoriích.
Bylo navrženo použití HOSVD pro analýzu dat s více pohledy[29] a byl úspěšně aplikován na in silico objev léků z genové exprese.[30]
Robustní varianta normy L1
L1-Tucker je L1-norma -na základě, robustní varianta Tuckerův rozklad.[7][8] L1-HOSVD je obdobou HOSVD pro řešení L1-Tucker.[7][9]
Reference
- ^ A b Hitchcock, Frank L (01.04.1928). "Vícenásobné invarianty a generalizovaná hodnost P-Way matice nebo tenzoru". Journal of Mathematics and Physics. 7 (1–4): 39–79. doi:10,1002 / sapm19287139. ISSN 1467-9590.
- ^ A b Tucker, Ledyard R. (01.09.1966). "Některé matematické poznámky k faktorové analýze ve třech režimech". Psychometrika. 31 (3): 279–311. doi:10.1007 / bf02289464. ISSN 0033-3123. PMID 5221127.
- ^ Tucker, L. R. (1963). "Důsledky faktorové analýzy třícestných matic pro měření změny". In C. W. Harris (Ed.), Problems in Measuring Change. Madison, Wis .: Univ. Wis. Stiskněte.: 122–137.
- ^ Tucker, L. R. (1964). "Rozšíření faktorové analýzy na trojrozměrné matice". V N. Frederiksen a H. Gulliksen (Eds.), Příspěvky k matematické psychologii. New York: Holt, Rinehart a Winston: 109–127.
- ^ A b C d De Lathauwer, L .; De Moor, B .; Vandewalle, J. (01.01.2000). "Víceřádkový rozklad singulární hodnoty". SIAM Journal on Matrix Analysis and Applications. 21 (4): 1253–1278. CiteSeerX 10.1.1.102.9135. doi:10.1137 / s0895479896305696. ISSN 0895-4798.
- ^ Godfarb, Donald; Zhiwei, Qin (2014). "Robustní nízká pozice tenzorového zotavení: Modely a algoritmy". SIAM Journal on Matrix Analysis and Applications. 35 (1): 225–253. arXiv:1311.6182. doi:10.1137/130905010.
- ^ A b C Chachlakis, Dimitris G .; Prater-Bennette, Ashley; Markopoulos, Panos P. (22. listopadu 2019). „T1 - Tuckerův tenzorový rozklad normou L1“. Přístup IEEE. 7: 178454–178465. doi:10.1109 / PŘÍSTUP.2019.2955134.
- ^ A b Markopoulos, Panos P .; Chachlakis, Dimitris G .; Papalexakis, Evangelos (duben 2018). „Přesné řešení rozkladu TUCKER2 úrovně 1 L1-Norma“. Dopisy pro zpracování signálu IEEE. 25 (4). arXiv:1710.11306. doi:10.1109 / LSP.2018.2790901.
- ^ A b Markopoulos, Panos P .; Chachlakis, Dimitris G .; Prater-Bennette, Ashley (21. února 2019). „L1-norm vyššího řádu rozkladu singulární hodnoty“. IEEE Proc. 2018 IEEE Global Conference on Signal and Information Processing. doi:10.1109 / GlobalSIP.2018.8646385.
- ^ A b Carlini, Enrico; Kleppe, Johannes (2011). „Hodnosti odvozené z víceřádkových map“. Journal of Pure and Applied Algebra. 215 (8): 1999–2004. doi:10.1016 / j.jpaa.2010.11.010.
- ^ A b C d Vannieuwenhoven, N .; Vandebril, R .; Meerbergen, K. (01.01.2012). „Nová strategie zkrácení pro rozklad singulární hodnoty vyšších řádů“. SIAM Journal on Scientific Computing. 34 (2): A1027 – A1052. doi:10.1137/110836067. ISSN 1064-8275.
- ^ A b Hackbusch, Wolfgang (2012). Tenzorové prostory a numerický počet tenzorů SpringerLink. Springerova řada ve výpočetní matematice. 42. doi:10.1007/978-3-642-28027-6. ISBN 978-3-642-28026-9.
- ^ Grasedyck, L. (01.01.2010). "Hierarchický rozklad singulární hodnoty tenzorů". SIAM Journal on Matrix Analysis and Applications. 31 (4): 2029–2054. CiteSeerX 10.1.1.660.8333. doi:10.1137/090764189. ISSN 0895-4798.
- ^ M. A. O. Vasilescu (2002) „Signalizace lidského pohybu: analýza, syntéza, rozpoznávání,“ Sborník z mezinárodní konference o rozpoznávání vzorů (ICPR 2002), sv. 3, Quebec City, Kanada, srpen 2002, 456–460.
- ^ M.A.O. Vasilescu, D. Terzopoulos (2003) „Multilineární subprostorová analýza pro obrazové soubory, M. A. O. Vasilescu, D. Terzopoulos, Proc. Počítačové vidění a rozpoznávání vzorů konf. (CVPR '03), sv. 2, Madison, WI, červen 2003, 93–99.
- ^ M.A.O. Vasilescu, D. Terzopoulos (2002) „Multilineární analýza obrazových souborů: TensorFaces,“ Proc. 7. Evropská konference o počítačovém vidění (ECCV'02), Kodaň, Dánsko, květen 2002, Computer Vision - ECCV 2002, Lecture Notes in Computer Science, Vol. 2350, A. Heyden a kol. (Eds.), Springer-Verlag, Berlin, 2002, 447–460.
- ^ M.A.O. Vasilescu, D. Terzopoulos (2004) „TensorTextures: Multilinear Image-Based Rendering“, M. A. O. Vasilescu a D. Terzopoulos, Proc. Konference ACM SIGGRAPH 2004 Los Angeles, CA, srpen 2004, ve sborníku z počítačové grafiky, ročník konference, 2004, 336–342.
- ^ L. Omberg; G. H. Golub; O. Alter (listopad 2007). „Rozklad singulární hodnoty tenzoru vyššího řádu pro integrační analýzu dat DNA microarray z různých studií“. PNAS. 104 (47): 18371–18376. Bibcode:2007PNAS..10418371O. doi:10.1073 / pnas.0709146104. PMC 2147680. PMID 18003902.
- ^ L. Omberg; J. R. Meyerson; K. Kobayashi; L. S. Drury; J. F. X. Diffley; O. Alter (říjen 2009). „Globální účinky replikace DNA a aktivity původu replikace DNA na expresi eukaryotických genů“. Molekulární systémy biologie. 5: 312. doi:10.1038 / msb.2009,70. PMC 2779084. PMID 19888207. Zvýraznit.
- ^ C. Muralidhara; A. M. Gross; R. R. Gutell; O. Alter (duben 2011). „Tenzorový rozklad odhaluje souběžné evoluční konvergence a divergence a korelace se strukturálními motivy v ribozomální RNA“. PLOS ONE. 6 (4): e18768. Bibcode:2011PLoSO ... 618768M. doi:10.1371 / journal.pone.0018768. PMC 3094155. PMID 21625625. Zvýraznit.
- ^ S. P. Ponnapalli; M. A. Saunders; C. F. Van Loan; O. Alter (prosinec 2011). „Generalizovaný singulární hodnotový rozklad vyššího řádu pro srovnání globální exprese mRNA z více organizmů“. PLOS ONE. 6 (12): e28072. Bibcode:2011PLoSO ... 628072P. doi:10.1371 / journal.pone.0028072. PMC 3245232. PMID 22216090. Zvýraznit.
- ^ P. Sankaranarayanan; T. E. Schomay; K. A. Aiello; O. Alter (duben 2015). „Tenzor GSVD nádorů odpovídajících pacientovi a platformě a profily počtu kopií normální DNA odkrývají chromozomové ramenní vzory exkluzivních změn konzistentních s nádory, které kódují transformaci buněk a předpovídají přežití rakoviny vaječníků“. PLOS ONE. 10 (4): e0121396. Bibcode:2015PLoSO..1021396S. doi:10.1371 / journal.pone.0121396. PMC 4398562. PMID 25875127. AAAS EurekAlert! Tisková zpráva a Funkce NAE Podcast.
- ^ Hadi Fanaee-T; João Gama (květen 2015). "EigenEvent: Algoritmus pro detekci událostí ze složitých datových toků v syndikálním sledování". Inteligentní analýza dat. 19 (3): 597–616. arXiv:1406.3496. Bibcode:2014arXiv1406.3496F. doi:10,3233 / IDA-150734.
- ^ A b P. Baranyi (duben 2004). "Transformace modelu TP jako cesta k návrhu ovladače založeného na LMI". Transakce IEEE na průmyslovou elektroniku. 51 (2): 387–400. doi:10.1109 / kravata.2003.822037.
- ^ A b P. Baranyi; D. Tikk; Y. Yam; R. J. Patton (2003). "Od diferenciálních rovnic k návrhu řadiče PDC pomocí numerické transformace". Počítače v průmyslu. 51 (3): 281–297. doi:10.1016 / s0166-3615 (03) 00058-7.
- ^ Haiping Lu, K.N. Plataniotis a A.N. Venetsanopoulos, “Průzkum multilineárního podprostorového učení pro tenzorová data ", Pattern Recognition, sv. 44, č. 7, str. 1540–1551, červenec 2011.
- ^ H. Lu, K. N. Plataniotis a A. N. Venetsanopoulos, "MPCA: Multilineární analýza hlavních komponent tenzorových objektů „IEEE Trans. Neural Netw., Sv. 19, č. 1, s. 18–39, leden 2008.
- ^ P. Baranyi; L. Szeidl; P. Várlaki; Y. Yam (3. – 5. Července 2006). Definice kanonické formy polytopických dynamických modelů na bázi HOSVD. Budapešť, Maďarsko. str. 660–665.
- ^ Y-h. Taguchi (srpen 2017). „Extrakce bez dozoru na základě rozkladu tenzorů aplikovaná na produkty matice pro zpracování dat s více pohledy“. PLOS ONE. 12 (8): e0183933. Bibcode:2017PLoSO..1283933T. doi:10.1371 / journal.pone.0183933. PMC 5571984. PMID 28841719.
- ^ Y-h. Taguchi (říjen 2017). „Identifikace kandidátních léčiv pomocí extrakce bez dozoru na základě tenzoru a dekompozice v integrované analýze genové exprese mezi nemocemi a datovými soubory DrugMatrix“. Vědecké zprávy. 7 (1): 13733. Bibcode:2017NatSR ... 713733T. doi:10.1038 / s41598-017-13003-0. PMC 5653784. PMID 29062063.