Dekompozycja wartości osobliwych wyższego rzędu
W algebrze wieloliniowej rozkład na wartości osobliwe wyższego rzędu ( HOSVD ) tensora jest specyficznym rozkładem ortogonalnym Tuckera . Można to uznać za jedno uogólnienie rozkładu macierzy na wartości osobliwe . Ma zastosowania w wizji komputerowej , grafice komputerowej , uczeniu maszynowym , obliczeniach naukowych i przetwarzaniu sygnałów . Niektóre aspekty można prześledzić już w FL Hitchcock w 1928 r., ale to LR Tucker opracował dla tensorów trzeciego rzędu ogólną dekompozycję Tuckera w latach 60. XX wieku, za którą dalej opowiadali się L. De Lathauwer i in. w ich pracy Multilinear SVD, która wykorzystuje metodę potęgową, i popierana przez Vasilescu i Terzopoulosa, którzy opracowali SVD w trybie M.
Termin HOSVD został wymyślony przez Lievena DeLathauwera, ale algorytm określany powszechnie w literaturze jako HOSVD i przypisywany Tuckerowi lub DeLathauwerowi został opracowany przez Vasilescu i Terzopoulosa. Zaproponowano również solidne i oparte na normie L1 warianty HOSVD.
Definicja
Na potrzeby tego artykułu zakłada się, że abstrakcyjny tensor podany we współrzędnych w odniesieniu do jakiejś bazy jako M-way , również oznaczona przez , gdzie M to liczba modów i rząd tensora. to liczby zespolone i obejmuje zarówno liczby rzeczywiste, czyste liczby urojone.
Niech jednostkową macierzą zawierającą podstawa lewych pojedynczych wektorów standardowego modemu taka , że ZA j ta kolumna U odpowiada j-tej największej wartości pojedynczej . Zauważ że macierz / czynników nie zależy od konkretnej definicji modu . Dzięki właściwościom mnożenia wieloliniowego mamy
Kompaktowy HOSVD
Podobnie jak w przypadku zwartej dekompozycji macierzy na wartości osobliwe, można również rozważyć zwarty HOSVD , co jest bardzo przydatne w zastosowaniach.
do z jednolite kolumny zawierające podstawę lewych wektorów osobliwych odpowiadających niezerowym wartościom osobliwym współczynnika standardowego - m spłaszczania ZA . Niech kolumny być posortowane w taki sposób, że kolumna { odpowiada niezerowej wartości osobliwej . kolumny obrazu mamy
Ranga wieloliniowa
Wieloliniowy stopień jest oznaczony rangą- } . Ranga wieloliniowa jest krotką w gdzie } Nie wszystkie krotki w . Rangi wieloliniowe są ograniczone przez i spełnia ograniczenie musi się utrzymać.
Zwarty HOSVD jest dekompozycją ujawniającą rangę w tym sensie, że wymiary jego tensora rdzenia odpowiadają składowym wieloliniowego rzędu tensora.
Interpretacja
Poniższa interpretacja geometryczna obowiązuje zarówno dla pełnego, jak i zwartego HOSVD. Niech będzie wieloliniowym rzędem tensora . Ponieważ możemy rozwiń go w następujący sposób
Obliczenie
Niech być tensorem o randze - , gdzie do {\ Displaystyle \ mathbb { zawiera liczby rzeczywiste jako podzbiór.
Klasyczne obliczenia
Strategia obliczania wieloliniowych SVD i SVD w trybie M została wprowadzona w latach 60. XX wieku przez LR Tuckera , a następnie popierana przez L. De Lathauwer i in. oraz Vasilescu i Terzopulousa. Termin HOSVD został wymyślony przez Lievena De Lathauwera, ale algorytm zwykle określany w literaturze jako HOSVD został wprowadzony przez Vasilescu i Terzopoulosa pod nazwą M-mode SVD. Jest to obliczenia równoległe, które wykorzystują macierz SVD do obliczania macierzy trybu ortonormalnego.
SVD w trybie M:
- Dla wykonaj następujące czynności:
- spłaszczenie modemu } ;
- Oblicz (zwarty) rozkład na wartości osobliwe i zapisz lewe wektory liczby pojedynczej ;
- tensor rdzenia pomocą mnożenia wieloliniowego
Obliczenia z przeplotem
Strategia, która jest znacznie szybsza, gdy niektóre lub wszystkie na przeplataniu obliczeń tensora rdzenia i macierzy czynników w następujący sposób: r
- Za ;
- Dla wykonaj następujące czynności:
- Skonstruuj tryb standardowy - m spłaszczanie ;
- Za [ i zapisz lewe wektory osobliwe ;
- Za lub równoważnie .
Obliczenia na miejscu
HOSVD można obliczyć na miejscu za pomocą algorytmu Fused In-place Sequentially Truncated Higher Order Singular Value Decomposition (FIST-HOSVD) poprzez nadpisanie oryginalnego tensora przez tensor rdzenia HOSVD, znacznie zmniejszając zużycie pamięci podczas obliczania HOSVD.
Przybliżenie
W aplikacjach, takich jak te wymienione poniżej, powszechny problem polega na przybliżeniu danego tensora ze zmniejszoną rangą wieloliniową. Formalnie, jeśli wieloliniowy rząd jest oznaczony przez optymalnego dla danego zredukowanego 2 {
Prostym pomysłem na rozwiązanie tego problemu optymalizacji jest obcięcie (zwartego) SVD w kroku 2 obliczeń klasycznych lub z przeplotem. Klasycznie obcięty HOSVD uzyskuje się przez zastąpienie kroku 2 w klasycznych obliczeniach przez
- Oblicz rangę - obcięty SVD i zapisz górne wektory liczby pojedynczej ;
podczas gdy sekwencyjnie obcinany HOSVD (lub kolejno obcinany HOSVD ) jest uzyskiwany przez zastąpienie kroku 2 w obliczeniach z przeplotem przez
- Oblicz rangę - obcięty SVD m lewe wektory osobliwe . Niestety, obcięcie nie daje optymalnego rozwiązania dla problemu optymalizacji najlepszych niskich rang wieloliniowych. Jednak zarówno klasycznie, jak i przeplatane obcięte HOSVD dają rozwiązanie : jeśli oznacza klasycznie lub sekwencyjnie obcięte oznacza optymalne rozwiązanie problemu aproksymacji najlepszych niskich rang wieloliniowych, a następnie
Aplikacje
HOSVD jest najczęściej stosowany do wydobywania odpowiednich informacji z tablic wielokierunkowych.
Począwszy od początku XXI wieku, Vasilescu zajmował się kwestiami przyczynowymi, przeformułowując problemy analizy, rozpoznawania i syntezy danych jako wieloliniowe problemy tensorowe. Potęga struktury tensorowej została zademonstrowana poprzez dekompozycję i reprezentację obrazu pod względem przyczynowych czynników tworzenia danych, w kontekście sygnatur ruchu człowieka do rozpoznawania chodu, rozpoznawania twarzy — TensorFaces i grafiki komputerowej — TensorTextures.
HOSVD został z powodzeniem zastosowany do przetwarzania sygnałów i dużych zbiorów danych, np. w przetwarzaniu sygnałów genomowych. Aplikacje te zainspirowały również GSVD wyższego rzędu (HO GSVD) i tensor GSVD.
Kombinacja HOSVD i SVD została również zastosowana do wykrywania zdarzeń w czasie rzeczywistym ze złożonych strumieni danych (dane wielowymiarowe z wymiarami przestrzennymi i czasowymi) w nadzorze nad chorobami .
Jest również używany w projektowaniu kontrolerów opartych na transformacji modeli produktów tensorowych .
Koncepcja HOSVD została przeniesiona do funkcji przez Baranyi i Yam poprzez transformację modelu TP . To rozszerzenie doprowadziło do zdefiniowania kanonicznej postaci funkcji iloczynu tensorowego opartej na HOSVD i modeli systemów o zmiennych parametrach liniowych oraz do teorii optymalizacji sterowania opartej na manipulacji wypukłym kadłubem, patrz transformacja modelu TP w teoriach sterowania .
Zaproponowano zastosowanie HOSVD do analizy danych z wielu widoków iz powodzeniem zastosowano go do odkrywania leków in silico na podstawie ekspresji genów.
Solidny wariant z normą L1
L1-Tucker to oparty na normie L1 , solidny wariant dekompozycji Tuckera . L1-HOSVD jest odpowiednikiem HOSVD dla rozwiązania L1-Tucker.
- ^ a b Hitchcock, Frank L (1928-04-01). „Wiele niezmienników i uogólniona ranga tablicy M-Way lub tensora”. Dziennik matematyki i fizyki . 7 (1–4): 39–79. doi : 10.1002/sapm19287139 . ISSN 1467-9590 .
- ^ Tucker, Ledyard R. (1966-09-01). „Kilka uwag matematycznych na temat analizy czynnikowej w trzech trybach”. Psychometria . 31 (3): 279–311. doi : 10.1007/bf02289464 . ISSN 0033-3123 . PMID 5221127 . S2CID 44301099 .
- ^ b Tucker , LR (1963). „Implikacje analizy czynnikowej macierzy trójdrożnych do pomiaru zmiany”. W CW Harris (red.), Problemy w mierzeniu zmian. Madison, Wis.: Uniw. Naciśnij. : 122–137.
- ^ Tucker, LR (1964). „Rozszerzenie analizy czynnikowej na macierze trójwymiarowe”. W N. Frederiksen i H. Gulliksen (red.), Wkład do psychologii matematycznej. Nowy Jork: Holt, Rinehart i Winston : 109–127.
- ^ a b c d De Lathauwer, L .; De Moor, B.; Vandewalle, J. (2000-01-01). „Wieloliniowy rozkład wartości osobliwych”. SIAM Journal o analizie macierzy i zastosowaniach . 21 (4): 1253–1278. CiteSeerX 10.1.1.102.9135 . doi : 10.1137/s0895479896305696 . ISSN 0895-4798 .
- ^ a b c d e M. AO Vasilescu, D. Terzopoulos (2002) pod nazwą M-mode SVD. Jest to szczególny ortogonalny Tucker, który jest odpowiedni do obliczeń równoległych „Multilinear Analysis of Image Ensembles: TensorFaces” , Proc. 7th European Conference on Computer Vision (ECCV'02), Kopenhaga, Dania, maj 2002
- ^ a b M. AO Vasilescu, D. Terzopoulos (2003) „Multilinear Subspace Analysis of Image Ensembles” , „Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR'03), Madison, WI, czerwiec 2003”
- ^ a b c d M. AO Vasilescu, D. Terzopoulos (2005) „Multilinear Independent Component Analysis” , „Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR'05), San Diego, Kalifornia, czerwiec 2005, tom .1, 547–553”.
- Bibliografia _ Zhiwei, Qin (2014). „Solidne odzyskiwanie tensorów niskiego rzędu: modele i algorytmy”. SIAM Journal o analizie macierzy i zastosowaniach . 35 (1): 225–253. ar Xiv : 1311.6182 . doi : 10.1137/130905010 . S2CID 1051205 .
- ^ abc Chachlakis .; , Dimitris G Prater-Bennette, Ashley; Markopoulos, Panos P. (22 listopada 2019). „Rozkład tensora Tuckera w normie L1” . Dostęp IEEE . 7 : 178454–178465. doi : 10.1109/ACCESS.2019.2955134 .
- ^ ab Markopoulos, Panos P.; Chachlakis, Dimitris G.; Papalexakis, Evangelos (kwiecień 2018). „Dokładne rozwiązanie rozkładu rangi 1 L1-Norm TUCKER2” . Listy przetwarzania sygnału IEEE . 25 (4): 511–515. ar Xiv : 1710.11306 . Bibcode : 2018ISPL...25..511M . doi : 10.1109/LSP.2018.2790901 . S2CID 3693326 .
- ^ ab Markopoulos, Panos P.; Chachlakis, Dimitris G.; Prater-Bennette, Ashley (21 lutego 2019). „Dekompozycja wartości osobliwej wyższego rzędu normy L1” . IEEE Proc. Globalna konferencja IEEE 2018 na temat przetwarzania sygnałów i informacji : 1353–1357. doi : 10.1109/GlobalSIP.2018.8646385 . ISBN 978-1-7281-1295-4 . S2CID 67874182 .
- ^ a b Carlini, Enrico; Kleppe, Johannes (2011). „Rangi wyprowadzone z map wieloliniowych” . Dziennik algebry czystej i stosowanej . 215 (8): 1999–2004. doi : 10.1016/j.jpaa.2010.11.010 .
- ^ abc Vannieuwenhoven , N.; Vandebril R.; Meerbergen, K. (2012-01-01). „Nowa strategia obcinania dla rozkładu wartości osobliwej wyższego rzędu” . SIAM Journal o obliczeniach naukowych . 34 (2): A1027–A1052. doi : 10.1137/110836067 . ISSN 1064-8275 .
- ^ a b Hackbusch, Wolfgang (2012). Przestrzenie tensorowe i numeryczny rachunek tensorowy | Springer Link . Seria Springera w matematyce obliczeniowej. Tom. 42. doi : 10.1007/978-3-642-28027-6 . ISBN 978-3-642-28026-9 .
- ^ a b c d Cobb, Benjamin; Kolla, Hemanth; Phipps, Eric; Çatalyürek, Ümit V. (2022). FIST-HOSVD: Stopiony w miejscu, sekwencyjnie obcięty, dekompozycja wartości osobliwej wyższego rzędu . Platforma zaawansowanych obliczeń naukowych (PASC). doi : 10.1145/3539781.3539798 . ISBN 9781450394109 .
- ^ Grasedyck, L. (2010-01-01). „Hierarchiczny rozkład tensorów na wartości osobliwe”. SIAM Journal o analizie macierzy i zastosowaniach . 31 (4): 2029–2054. CiteSeerX 10.1.1.660.8333 . doi : 10.1137/090764189 . ISSN 0895-4798 .
- ^ MAO Vasilescu (2002) „Podpisy ruchu ludzkiego: analiza, synteza, rozpoznawanie”, Proceedings of International Conference on Pattern Recognition (ICPR 2002), tom. 3, Quebec City, Kanada, sierpień 2002, s. 456–460.
- Referencje _ _ _ 2003, 93–99.
- ^ MAO Vasilescu, D. Terzopoulos (2002) „Wieloliniowa analiza zespołów obrazów: TensorFaces”, Proc. 7th European Conference on Computer Vision (ECCV'02), Kopenhaga, Dania, maj 2002, w Computer Vision -- ECCV 2002, Lecture Notes in Computer Science, tom. 2350, A. Heyden i in. (red.), Springer-Verlag, Berlin, 2002, 447–460.
- ^ MAO Vasilescu, D. Terzopoulos (2004) „TensorTextures: wieloliniowe renderowanie oparte na obrazie”, MAO Vasilescu i D. Terzopoulos, Proc. Konferencja ACM SIGGRAPH 2004 Los Angeles, Kalifornia, sierpień 2004, w Computer Graphics Proceedings, Annual Conference Series, 2004, 336–342.
- Bibliografia _ GH Golub; O. Alter (listopad 2007). „Dekompozycja wartości osobliwej wyższego rzędu tensora do integracyjnej analizy danych z mikromacierzy DNA z różnych badań” . PNAS . 104 (47): 18371–18376. Bibcode : 2007PNAS..10418371O . doi : 10.1073/pnas.0709146104 . PMC 2147680 . PMID 18003902 .
- Bibliografia _ JR Meyersona; K. Kobayashiego; LS Drury; JFX Diffley; O. Alter (październik 2009). „Globalny wpływ replikacji DNA i aktywności pochodzenia replikacji DNA na ekspresję genów eukariotycznych” . Biologia systemów molekularnych . 5 : 312. doi : 10.1038/msb.2009.70 . PMC 2779084 . PMID 19888207 . Zaznacz .
- ^ C. Muralidhara; AM brutto; RR Gutell; O. Alter (kwiecień 2011). „Dekompozycja tensorowa ujawnia równoczesne ewolucyjne zbieżności i rozbieżności oraz korelacje z motywami strukturalnymi w rybosomalnym RNA” . PLOS JEDEN . 6 (4): e18768. Bibcode : 2011PLoSO...618768M . doi : 10.1371/journal.pone.0018768 . PMC 3094155 . PMID 21625625 . Zaznacz .
- Bibliografia _ mgr Saundersa; Pożyczka CF Van; O. Alter (grudzień 2011). „Uogólniony rozkład wartości pojedynczej wyższego rzędu do porównania globalnej ekspresji mRNA z wielu organizmów” . PLOS JEDEN . 6 (12): e28072. Bibcode : 2011PLoSO...628072P . doi : 10.1371/journal.pone.0028072 . PMC 3245232 . PMID 22216090 . Zaznacz .
- ^ P. Sankaranarayanan; TE Schomay; KA Aiello; O. Alter (kwiecień 2015). „Tensor GSVD guza dopasowanego do pacjenta i platformy oraz profil liczby kopii normalnego DNA ujawnia wzorce obejmujące całe ramię chromosomu wyłącznych dla guza zmian zgodnych z platformą, kodujących transformację komórek i przewidujących przeżycie raka jajnika” . PLOS JEDEN . 10 (4): e0121396. Bibcode : 2015PLoSO..1021396S . doi : 10.1371/journal.pone.0121396 . PMC 4398562 . PMID 25875127 . AAAS Eurek Uwaga! Komunikat prasowy i funkcja podcastu NAE .
- Bibliografia _ João Gama (maj 2015). „EigenEvent: algorytm wykrywania zdarzeń ze złożonych strumieni danych w nadzorze syndromicznym”. Inteligentna analiza danych . 19 (3): 597–616. ar Xiv : 1406.3496 . Bibcode : 2014arXiv1406.3496F . doi : 10.3233/IDA-150734 . S2CID 17966555 .
- ^ a b P. Baranyi (kwiecień 2004). „Transformacja modelu TP jako sposób na projektowanie kontrolerów opartych na LMI”. Transakcje IEEE dotyczące elektroniki przemysłowej . 51 (2): 387–400. doi : 10.1109/tie.2003.822037 . S2CID 7957799 .
- ^ a b P. Baranyi; D. Tikk; Y. Jam; RJ Pattona (2003). „Od równań różniczkowych do projektowania kontrolera PDC poprzez transformację numeryczną”. Komputery w przemyśle . 51 (3): 281–297. doi : 10.1016/s0166-3615(03)00058-7 .
- ^ P. Baranyi; L. Szeidla; P. Várlaki; Y. Yam (3-5 lipca 2006). Definicja kanonicznej postaci wielotopowych modeli dynamicznych opartej na HOSVD . III Międzynarodowa Konferencja Mechatroniki (ICM 2006). Budapeszt, Węgry. s. 660–665.
- Bibliografia _ Taguchi (sierpień 2017). „Nienadzorowana ekstrakcja cech oparta na dekompozycji tensorowej zastosowana w produktach macierzowych do przetwarzania danych w wielu widokach” . PLOS JEDEN . 12 (8): e0183933. Bibcode : 2017PLoSO..1283933T . doi : 10.1371/journal.pone.0183933 . PMC 5571984 . PMID 28841719 .
- Bibliografia _ Taguchi (październik 2017). „Identyfikacja leków kandydujących przy użyciu nienadzorowanej ekstrakcji cech opartej na rozkładzie tensorowym w zintegrowanej analizie ekspresji genów między chorobami a zbiorami danych DrugMatrix” . Raporty naukowe . 7 (1): 13733. Bibcode : 2017NatSR...713733T . doi : 10.1038/s41598-017-13003-0 . PMC 5653784 . PMID 29062063 .