Singularvärdesupplösning av högre ordning

I multilinjär algebra är den högre ordningens singularvärdesupplösning ( HOSVD ) av en tensor en specifik ortogonal Tucker-nedbrytning . Det kan betraktas som en generalisering av matrisens singularvärdesupplösning . Den har applikationer inom datorseende , datorgrafik , maskininlärning , vetenskaplig beräkning och signalbehandling . Vissa aspekter kan spåras så långt tillbaka som FL Hitchcock 1928, men det var LR Tucker som utvecklade för tredje ordningens tensorer den allmänna Tucker-nedbrytningen på 1960-talet, ytterligare förespråkad av L. De Lathauwer et al. i deras multilinjära SVD-arbete som använder kraftmetoden, och förespråkas av Vasilescu och Terzopoulos som utvecklade M-mode SVD.

Termen HOSVD myntades av Lieven DeLathauwer, men den algoritm som i litteraturen ofta kallas HOSVD och tillskrivs antingen Tucker eller DeLathauwer utvecklades av Vasilescu och Terzopoulos. Robusta och L1-normbaserade varianter av HOSVD har också föreslagits.

Definition

För syftet med denna artikel antas den abstrakta tensorn ${\mathcal {A}}$ ges i koordinater med avseende på någon bas som en M-way array , även betecknad med ${\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\cdots \times \cdots I_{m} \cdots \times I_{M}}$ , där M är antalet lägen och tensorns ordning. $\mathbb {C}$ är de komplexa talen och det inkluderar både de reella talen $\mathbb {R}$ och de rena imaginära talen.

Låt ${\displaystyle {\bf {U}}_{m}\in \mathbb {C} ^{I_{m}\ gånger R_{m}}} vara en enhetlig$ matris som innehåller en bas för de vänstra singularvektorerna för standardmode- m plattning ${\mathcal {A}}_{[m]}$ av ${\mathcal {A}}$ så att den j: te kolumnen $\mathbf {u} _{j}$ av ${\bf {U}}_{m}$ motsvarar det j :e största singularvärdet för ${\mathcal {A}}_{[m]}$ . Observera att mod/faktormatrisen ${\bf {U}}_{m}$ inte beror på den specifika definitionen av modens m - utjämning. Genom egenskaperna hos den multilinjära multiplikationen har vi

$${\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är $\cdot ^{H}$ anger den konjugata transponeringen . Den andra likheten beror på att ${\bf {U}}_{m}$ är enhetliga matriser. Definiera nu kärntensorn

$${\mathcal {S}}:={\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^ {H},\ldots ,{\bf {U}}_{M}^{H}).$$

Sedan är HOSVD för ${\mathcal {A}}$ nedbrytningen

$${\mathcal {A}}={\mathcal {S}}\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\ bf {U}}_{M}).$$

Ovanstående konstruktion visar att varje tensor har en HOSVD.

Kompakt HOSVD

Som i fallet med den kompakta singularvärdesuppdelningen av en matris, är det också möjligt att överväga en kompakt HOSVD , som är mycket användbar i applikationer.

Antag att ${\displaystyle {\bf {U}}_{m}\in \mathbb {C} ^{I_{m}\times R_{m}}} är en matris$ med enhetskolumner som innehåller en bas av de vänstra singularvektorerna som motsvarar singularvärdena som inte är noll för standardfaktorn- m utplattande ${\mathcal {A}}_{[m]}$ av ${ \mathcal {A}}$ . Låt kolumnerna i ${\bf {U}}_{m}$ sorteras så att den $r_{m}$ kolumnen ${\bf {u} }_{r_{m}}$ av ${\bf {U}}_{m}$ motsvarar ${\displaystyle r_{m}}:$ e största singularvärdet som inte är noll av ${\mathcal {A}}_{[m]}$ . Eftersom kolumnerna i ${\bf {U}}_{m}$ utgör en grund för bilden av ${\mathcal {A}}_{[m]}$ , vi har

$${\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]},$$

där den första likheten beror på egenskaperna hos ortogonala projektioner (i den hermitiska inre produkten) och den sista likheten beror på egenskaperna hos multilinjär multiplikation. Eftersom tillplattningar är bijektiva kartor och formeln ovan gäller för alla $m=1,2,\ldots ,m,\ldots ,M$ , finner vi som tidigare den där

$$\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)\ gånger ({\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}}}$$

där kärntensorn ${\mathcal {S}}$ nu har storleken $R_{1}\times R_{2}\times \cdots \times R_ {M}$ .

Multilinjär rangordning

Den multilinjära rangordningen för $A}}}$$(R_{1},R_{2},\ldots , R_{M})$ betecknas med rang- . Den multilinjära rangordningen är en tupel i $\mathbb {N} ^{M}$ där $R_{m}:=\mathrm {rank } ({\mathcal {A}}_{[m]})$ . Inte alla tupler i $\mathbb {N} ^{M}$ är multilinjära rangordningar. De multilinjära rankorna begränsas av $1\leq R_{m}\leq I_{m}$ och den uppfyller begränsningen ${\textstyle R_{m }\leq \prod _{i\neq m}R_{i}}$ måste hålla.

Den kompakta HOSVD är en rangavslöjande deomposition i den meningen att dimensionerna på dess kärntensor överensstämmer med komponenterna i tensorns multilinjära rangordning.

Tolkning

Följande geometriska tolkning är giltig för både full och kompakt HOSVD. Låt $(R_{1},R_{2},\ldots ,R_{M})$ vara den multilinjära rangordningen för tensor ${\mathcal {A}}$ . Eftersom ${\mathcal {S}}\in {\mathbb {C} }^{R_{1}\times R_{2}\times \cdots \ gånger R_{M}}$ är en flerdimensionell matris, vi kan utöka den enligt följande

$${$$

där $\mathbf {e} _{r_{m}}$ är ${\displaystyle r_{m}}:$ e standardbasvektorn för ${\mathbb {C} } ^{I_{m}}$ . Per definition av den multilinjära multiplikationen håller den det

$$_ \displaystyle {\mathcal {A}}=\sum _{r_{1}=1}^{R_{1}}\summa _{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}},}$$

där $\mathbf {u} _{r_{m}}$ är kolumnerna för ${\bf {U}}_{m}\in {\mathbb {C} }^{I_{m}\times R_{m}}$ . Det är lätt att verifiera att $B=\{\mathbf {u} _{r_{1 }}\otimes \mathbf {u} _{r_{2}}\otimes \cdots \otimes \mathbf {u} _{r_{M}}\}_{r_{1},r_{2},\ldots ,r_{M}}$ är en ortonormal uppsättning av tensorer. Detta betyder att HOSVD kan tolkas som ett sätt att uttrycka tensorn ${\mathcal {A}}$ med avseende på en specifikt vald ortonormal bas $B$ med koefficienterna angivna som den flerdimensionella matrisen ${\mathcal {S}}$ .

Beräkning

Låt ${\mathcal {A}}\in {\mathbb {C} }^{I_{1}\times I_{2}\times \cdots \ gånger I_{M}}$ vara en tensor med en rang- ${\displaystyle (R_{1},R_{2},\ldots ,R_{M})$ , där $\mathbb {C}$ innehåller reals $\mathbb {R}$ som en delmängd.

Klassisk beräkning

Strategin för att beräkna multilinjär SVD och M-mode SVD introducerades på 1960-talet av LR Tucker , ytterligare förespråkad av L. De Lathauwer et al. , och av Vasilescu och Terzopulous. Termen HOSVD myntades av Lieven De Lathauwer, men den algoritm som vanligtvis kallas HOSVD i litteraturen introducerades av Vasilescu och Terzopoulos med namnet M-mode SVD. Det är en parallell beräkning som använder matrisen SVD för att beräkna de ortonormala modmatriserna.

M-mode SVD:

• För $m=0,1,\ldots ,M$ , gör följande:

1. Konstruera mode- m tillplattning ${\mathcal {A}}_{[m]}$ ;
2. Beräkna (kompakt) singularisvärdesuppdelningen ${\displaystyle {\mathcal {A}}_{[m]}={\bf {U}}_{m}{\ bf {\Sigma }}_{m}{\bf {V}}_{m}^{T}} , och lagra$ de vänstra singularvektorerna ${\bf {U} }\in \mathbb {C} ^{I_{m}\times R_{m}}$ ;

• Beräkna kärntensorn ${\mathcal {S}}$ via multilinjär multiplikation ${\ displaystyle {\mathcal {S}}={\mathcal {A}}\times _{0}{\bf {U}}_{0}^{H}\times _{1}{\bf {U}} _{1}^{H}\times _{2}{\bf {U}}_{2}^{H}\ldots \times _{m}{\bf {U}}_{m}^{ H}\ldots \times _{M}{\bf {U}}_{M}^{H}}$

Interlacing beräkning

En strategi som är betydligt snabbare när några eller alla $r_{k}\ll n_{k}$ består av sammanflätning av beräkningen av kärntensorn och faktormatriserna, enligt följande:

• Set ${\mathcal {A}}^{0}={\mathcal {A}}$ ;
• För $m=0,1,2\ldots ,M$ utför följande:
  1. Konstruera standardmoden- m tillplattning ${\mathcal {A}}_{[m]}^{m-1}$ ;
  2. Beräkna (kompakt) singularisvärdesuppdelningen ${\mathcal {A}}_{[m]}^{m-1}=U_{m} \Sigma _{m}V_{m}^{T}$ och lagra de vänstra singularvektorerna $U_{m}\in F^{I_{m}\times R_ {m}}$ ;
  3. Set ${\mathcal {A}}^{m}=U_{m}^{H}\times _{m}{\mathcal {A}}^ {m-1}$ , eller, ekvivalent, ${\mathcal {A}}_{[m]}^{m}=\Sigma _{m}V_ {m}^{T}$ .

Beräkning på plats

HOSVD kan beräknas på plats via algoritmen Fused In-place Sequentially Truncated Higher Order Singular Value Decomposition (FIST-HOSVD) genom att skriva över den ursprungliga tensorn av HOSVD-kärntensorn, vilket avsevärt minskar minnesförbrukningen för dator HOSVD.

Approximation

I applikationer, som de som nämns nedan, består ett vanligt problem av att approximera en given tensor ${\mathcal {A}}\in \mathbb { C} ^{I_{1}\times I_{2}\times \cdots \times I_{m}\cdots \times I_{M}}$ med en med reducerad multilinjär rang. Formellt, om den multilinjära rangordningen för ${\mathcal {A}}$${\displaystyle \mathrm$ med den optimala ${\mathcal {\bar {A} }}$ som approximerar ${\mathcal {A}}$ för en given reducerad $\mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{m},\ldots ,{ \bar {R}}_{M})$ är ett icke-linjärt icke-konvext $\ell _{2}$ -optimeringsproblem

$$\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{st}}\quad \mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{ 2},\ldots ,{\bar {R}}_{M}),$$

där $({\bar {R}}_{1},{\bar {R}}_{2},\ldots, {\bar {R}}_{M})\in \mathbb {N} ^{M}$ är den reducerade multilinjära rangordningen med $1\leq {\bar {R}}_{m}<R_{m}\leq I_{m}$ och normen $\|.\|_{F}$ är Frobenius-normen .

En enkel idé för att försöka lösa detta optimeringsproblem är att trunkera den (kompakta) SVD:n i steg 2 av antingen den klassiska eller den sammanflätade beräkningen. En klassiskt trunkerad HOSVD erhålls genom att ersätta steg 2 i den klassiska beräkningen med

• Beräkna en rang- ${\bar {R}}_{m}$ trunkerad SVD ${\mathcal {A}}_{[m ]}\approx U_{m}\Sigma _{m}V_{m}^{T}$ och lagra de övre ${\bar {R}}_{m}$ vänstersingularvektorerna $U_{m}\in F^{I_{m}\times {\bar {R}}_{m}}$ ;

medan en sekventiellt trunkerad HOSVD (eller successivt trunkerad HOSVD ) erhålls genom att ersätta steg 2 i den sammanflätade beräkningen med

• Beräkna en rang- ${\bar {R}}_{m}$ trunkerad SVD ${\displaystyle {\mathcal {A}}_ {[m]}^{m-1}\approx U_{m}\Sigma _{m}V_{m}^{T}} och lagra den översta R ¯$ m ${\bar {R}} _{m}}$ vänstersingularvektorer $U_{m}\in F^{I_{m}\times {\bar {R}}_{m}}$ . Tyvärr resulterar trunkering inte i en optimal lösning för det bästa optimeringsproblemet med låg multilinjär rangordning. Men både den klassiskt och interfolierade trunkerade HOSVD resulterar i en kvasioptimal lösning: om ${\mathcal {\bar {A}}}_{t}$ betecknar den klassiskt eller sekventiellt trunkerade HOSVD och ${\mathcal {\bar {A}}}^{*}$ betecknar den optimala lösningen på det bästa approximationsproblemet med låg multilinjär rangordning, då
  $$\|{\mathcal {A}}-{\mathcal {\bar {A}}}_{t}\|_{F}\leq {\sqrt {M}}\|{\mathcal {A }}-{\mathcal {\bar {A}}}^{*}\|_{F};$$
  i praktiken betyder detta att om det finns en optimal lösning med ett litet fel, så kommer en trunkerad HOSVD för många avsedda ändamål också att ge en tillräckligt bra lösning.

Ansökningar

HOSVD används oftast för att extrahera relevant information från flervägsmatriser.

Med början i början av 2000-talet tog Vasilescu upp kausala frågor genom att omformulera problem med dataanalys, igenkänning och syntes som multilinjära tensorproblem. Tensorramverkets kraft visades upp genom att sönderdela och representera en bild i termer av dess orsaksfaktorer för databildning, i samband med Human Motion Signatures för gångigenkänning, ansiktsigenkänning—TensorFaces och datorgrafik—TensorTextures.

HOSVD har framgångsrikt tillämpats på signalbehandling och big data, t.ex. i genomisk signalbehandling. Dessa applikationer inspirerade också en högre ordning GSVD (HO GSVD) och en tensor GSVD.

En kombination av HOSVD och SVD har också använts för händelsedetektering i realtid från komplexa dataströmmar (multivariatdata med rums- och tidsdimensioner) vid sjukdomsövervakning .

Den används också i tensorproduktmodelltransformationsbaserad kontrolldesign.

Begreppet HOSVD överfördes till funktioner av Baranyi och Yam via TP-modellomvandlingen . Denna utvidgning ledde till definitionen av den HOSVD-baserade kanoniska formen av tensorproduktfunktioner och linjära parametervarierande systemmodeller och till konvex skrovmanipulationsbaserad styroptimeringsteori, se TP-modelltransformation i styrteorier .

HOSVD föreslogs att användas för multi-view dataanalys och tillämpades framgångsrikt på in silico läkemedelsupptäckt från genuttryck.

Robust L1-norm variant

L1-Tucker är den L1-normbaserade , robusta varianten av Tucker-nedbrytning . L1-HOSVD är analog med HOSVD för lösningen till L1-Tucker.