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

gdzie oznacza sprzężoną transpozycję . Druga równość wynika z faktu, że macierze jednostkowe są Zdefiniuj teraz tensor rdzenia
Następnie HOSVD z jest rozkładem
Powyższa konstrukcja pokazuje, że każdy tensor ma HOSVD.

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

gdzie pierwsza równość wynika z właściwości rzutów ortogonalnych (w hermitowskim iloczynie wewnętrznym), a ostatnia równość wynika z właściwości mnożenia wieloliniowego. dla wszystkich znajdujemy To
gdzie tensor rdzenia teraz rozmiar .

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

mi jest standardowym wektorem bazowym r m {\ displaystyle r_ {m}} do . Z definicji mnożenia wieloliniowego wynika, że
u to kolumny . Łatwo sprawdzić, że jest ortonormalnym zbiorem tensorów. Oznacza to, że HOSVD można interpretować jako sposób wyrażenia tensora odniesieniu do specjalnie wybranej podstawy ortonormalnej jako tablica wielowymiarowa mathcal

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:
  1. spłaszczenie modemu } ;
  2. 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:
    1. Skonstruuj tryb standardowy - m spłaszczanie ;
    2. Za [ i zapisz lewe wektory osobliwe ;
    3. 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 {

gdzie to zredukowana ranga wieloliniowa z , a norma to norma Frobeniusa .

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
    w praktyce oznacza to, że jeśli istnieje optymalne rozwiązanie z małym błędem, to okrojony HOSVD dla wielu zamierzonych celów również da wystarczająco dobre rozwiązanie.

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.

  1. ^ 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 .
  2. ^     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 .
  3. ^ 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.
  4. ^ 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.
  5. ^ 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 .
  6. ^ 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
  7. ^ 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”
  8. ^ 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”.
  9. 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 .
  10. ^ 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 .
  11. ^ 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 .
  12. ^ 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 .
  13. ^ 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 .
  14. ^ 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 .
  15. ^ 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 .
  16. ^ 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 .
  17. ^    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 .
  18. ^ 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.
  19. Referencje _ _ _ 2003, 93–99.
  20. ^ 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.
  21. ^ 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.
  22. 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 .
  23. 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 .
  24. ^    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 .
  25. 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 .
  26. ^   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 .
  27. 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 .
  28. ^ 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 .
  29. ^ 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 .
  30. ^ 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.
  31. 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 .
  32. 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 .