Tensor rank nedbrytning

I multilinjär algebra är sönderdelningen av tensorrangen eller r $\displaystyle rank-R}$ sönderdelningen av en tensor nedbrytningen av en tensor i termer av summan av minimum $R$$rank-1$ tensorer. Detta är ett öppet problem.

Kanonisk polyadisk nedbrytning (CPD) är en variant av ranguppdelningen som beräknar de bäst passande $K$$rank-1$ termer för en användarspecificerad $K$ . CP-nedbrytningen har funnit vissa tillämpningar inom lingvistik och kemometri . CP-rankningen introducerades av Frank Lauren Hitchcock 1927 och återupptäcktes senare flera gånger, särskilt inom psykometri. CP-nedbrytningen hänvisas till som CANDECOMP, PARAFAC eller CANDECOMP/PARAFAC (CP). Nedbrytning av PARAFAC2-rankningen är ännu att utforska.

En annan populär generalisering av matrisen SVD, känd som singularvärdesuppdelningen av högre ordning, beräknar matriser i ortonormalt läge och har hittat tillämpningar inom ekonometri , signalbehandling , datorseende , datorgrafik , psykometri .

Notation

En skalär variabel betecknas med kursiv versal, $a$ och en skalär med övre gräns betecknas med en versal kursiv bokstav, $A$ .

Index betecknas med en kombination av gemener och versaler kursiverade bokstäver, $1\leq i\leq I$ . Flera index som man kan stöta på när man hänvisar till en tensors multipla lägen betecknas lämpligen med $1\leq i_{m}\leq I_{m}$ där ${ \displaystyle 1\leq m\leq M}$ .

En vektor betecknas med små bokstäver med fetstil Times Roman, $\mathbf {a}$ och en matris betecknas med feta versaler $\mathbf {A}$ .

En högre ordnings tensor betecknas med kalligrafiska bokstäver, ${\mathcal {A}}$ . Ett element av en $M$ -order tensor ${\mathcal {A}}\in \mathbb {C} ^{I_{ 1}\times I_{2}\times \dots I_{m}\times \dots I_{M}}$ betecknas med $a_{i_ {1},i_{2},\dots ,i_{m},\dots i_{M}}$ eller ${\mathcal {A} }_{i_{1},i_{2},\dots ,i_{m},\dots i_{M}}$ .

Definition

En datatensor ${\mathcal {A}}\in {\mathbb {F} }^{I_{0}\times I_{1}\times \ldots \times I_{C}}$ är en samling multivariata observationer organiserade i en M -vägsmatris där M = C +1. Varje tensor kan representeras med en lämpligt stor $R$ som en linjär kombination av $r$ rank-1 tensorer:

${\mathcal {A}}=\sum _ {r=1}^{R}\lambda _{r}\mathbf {a} _{0,r}\otimes \mathbf {a} _{1,r}\otimes \mathbf {a} _{2, r}\dots \otimes \mathbf {a} _{c,r}\otimes \cdots \otimes \mathbf {a} _{C,r},$

där $\lambda _{r}\in {\mathbb {R} }$ och $\mathbf {a} _{m,r}\in { \mathbb {F} }^{I_{m}}$ där $1\leq m\leq M$ . När antalet termer $R$ är minimalt i uttrycket ovan, kallas ${\displaystyle R} för$ tensorns rang , och nedbrytningen kallas ofta för en (tensor) rangnedbrytning , minimal CP sönderdelning eller kanonisk polyadisk sönderdelning (CPD) . Om antalet termer inte är minimalt, så benämns ovanstående sönderdelning ofta som CANDECOMP/PARAFAC , polyadisk sönderdelning'.

Tensor rang

NP-hårt att beräkna rangen för en tensor . Det enda anmärkningsvärda välförstådda fallet består av tensorer i $F^{I_{m}}\otimes F^{I_{n}}\otimes F^{2}$ , vars rang kan erhållas från Kronecker – Weierstrass normalform av den linjära matrispenna som tensorn representerar. Det finns en enkel polynom-tidsalgoritm för att intyga att en tensor är av rang 1, nämligen den högre ordningens singularvärdesupplösning .

Rangen för tensorn av nollor är noll enligt konventionen. Rangen för en tensor ${\displaystyle \mathbf {a} _{1}\otimes \cdots \otimes \mathbf {a} _{M}} är en,$ förutsatt att $\mathbf {a} _{m}\in F^{I_{m}}\setminus \{0\}$ .

Fältberoende

Rangen för en tensor beror på det fält över vilket tensorn bryts ned. Det är känt att vissa verkliga tensorer kan medge en komplex nedbrytning vars rang är strikt lägre än rangordningen för en verklig nedbrytning av samma tensor. Som ett exempel, betrakta följande verkliga tensor

${\mathcal {A}}= mathbf {x} _{1}\otimes \mathbf {x} _{2}\otimes \mathbf {x} _{3}+\mathbf {x} _{1}\otimes \mathbf {y} _{2 }\otimes \mathbf {y} _{3}-\mathbf {y} _{1}\otimes \mathbf {x} _{2}\otimes \mathbf {y} _{3}+\mathbf {y} _{1}\otimes \mathbf {y} _{2}\otimes \mathbf {x} _{3},$

där $\mathbf {x} _{i},\mathbf {y} _{j}\in \mathbb {R} ^{2}$ . Rangen för denna tensor över realerna är känd för att vara 3, medan dess komplexa rang bara är 2 eftersom den är summan av en komplex rang-1 tensor med dess komplexa konjugat , nämligen

${\mathcal {A}}={\frac {1}{2}}({ \bar {\mathbf {z} }}_{1}\otimes \mathbf {z} _{2}\otimes {\bar {\mathbf {z} }}_{3}+\mathbf {z} _{ 1}\otimes {\bar {\mathbf {z} }}_{2}\otimes \mathbf {z} _{3}),$

där $\mathbf {z} _{k}=\mathbf {x} _{k}+i\mathbf {y} _{k}$ .

Däremot kommer rankningen av verkliga matriser aldrig att minska under en fältförlängning till $\mathbb {C}$ : verklig matrisrankning och komplex matrisrankning sammanfaller för verkliga matriser.

Generisk rang

Den generiska rangordningen $r(I_{1},\ldots ,I_{M})$ definieras som den lägsta rangordningen $r$ så att stängningen i Zariski-topologin för uppsättningen tensorer av högst rang $r$ är hela rymden $F^{I_{1}}\otimes \cdots \otimes F^{ I_{M}}$ . När det gäller komplexa tensorer bildar tensorer med högst rang $r(I_{1},\ldots ,I_{M})$ en tät mängd $S$ : varje tensor i det ovannämnda utrymmet har antingen rang som är lägre än den generiska rangordningen, eller så är den gränsen i den euklidiska topologin för en sekvens av tensorer från $S$ . När det gäller verkliga tensorer, bildar uppsättningen tensorer av högst rang $r(I_{1},\ldots ,I_{M})$ endast en öppen uppsättning av positivt mått i den euklidiska topologin. Det kan finnas euklidiska öppna uppsättningar av tensorer av rang som är strikt högre än den generiska rangordningen. Alla rangordningar som förekommer på öppna uppsättningar i den euklidiska topologin kallas typiska rangordningar . Den minsta typiska rangen kallas generisk rang; denna definition gäller både komplexa och verkliga tensorer. Den generiska rangordningen av tensorutrymmen studerades ursprungligen 1983 av Volker Strassen .

Som en illustration av ovanstående begrepp är det känt att både 2 och 3 är typiska rangordningar av $\mathbb {R} ^{2}\otimes \mathbb {R} ^{2 }\otimes \mathbb {R} ^{2}$ medan den generiska rangordningen för $\mathbb {C} ^{2}\otimes \mathbb {C} ^{2}\ otimes \mathbb {C} ^{2}$ är 2. Praktiskt taget betyder detta att en slumpmässigt samplade reell tensor (från ett kontinuerligt sannolikhetsmått på tensorernas rymd) med storleken $2\times 2 \times 2$ kommer att vara en rang-1-tensor med sannolikhet noll, en rang-2-tensor med positiv sannolikhet och rang-3 med positiv sannolikhet. Å andra sidan kommer en slumpmässigt samplade komplex tensor av samma storlek att vara en rang-1-tensor med sannolikhet noll, en rang-2-tensor med sannolikhet ett och en rang-3-tensor med sannolikhet noll. Det är till och med känt att den generiska rank-3 verkliga tensorn i $\mathbb {R} ^{2}\otimes \mathbb {R} ^{2}\otimes \mathbb {R } ^{2}$ kommer att ha komplex rang lika med 2.

Den generiska rangordningen av tensorrum beror på skillnaden mellan balanserade och obalanserade tensorrum. Ett tensorrum ${\displaystyle F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}} ,$ där $I_{1}\geq I_{2}\geq \cdots \geq I_{M}$ , kallas obalanserad närhelst

$I_{1}>1+\prod _{m=2}^{M}I_{m }-\summa _{m=2}^{M}(I_{m}-1),$

och det kallas balanserat annars.

Obalanserade tensorutrymmen

När den första faktorn är mycket stor med avseende på de andra faktorerna i tensorprodukten, uppträder tensorutrymmet väsentligen som ett matrisutrymme. Det är känt att den generiska rangordningen av tensorer som lever i obalanserade tensorutrymmen är lika

$r(I_{1},\ldots ,I_{M})=\min \left\{I_ {1},\prod _{m=2}^{M}I_{m}\right\}$

nästan överallt . Mer exakt, rangordningen för varje tensor i ett obalanserat tensorutrymme ${\displaystyle F^{I_{1}\times \cdots \times I_{M}}\setminus Z} ,$ där $Z$ är någon obestämd sluten uppsättning i Zariski-topologin, lika med ovanstående värde.

Balanserade tensorutrymmen

Den förväntade generiska rangordningen för tensorer som lever i ett balanserat tensorutrymme är lika med

$r_{E}(I_{1},\ldots ,I_{M})=\left\lceil {\frac {\Pi }{\Sigma +1}}\right\rceil$

nästan överallt för komplexa tensorer och på ett euklidiskt öppet set för riktiga tensorer, var

$\Pi =\prod _{m=1}^{M}I_{m}\quad {\text{and}}\quad \Sigma =\sum _{m=1}^{M}(I_ {m}-1).$

Mer exakt, rangordningen för varje tensor i ${\displaystyle \mathbb {C} ^{I_{1}\times \cdots \times I_{M}}\setminus Z} ,$ där $Z$ är någon obestämd sluten uppsättning i Zariski-topologin , förväntas vara lika med ovanstående värde. För verkliga tensorer är $r_{E}(I_{1},\ldots ,I_{M})$ den lägsta rangordningen som förväntas inträffa på en uppsättning av positivt euklidiskt mått. Värdet $r_{E}(I_{1},\ldots ,I_{M})$ hänvisas ofta till som den förväntade generiska rangordningen för tensorrymden $F^{I_{1}\times \cdots \times I_{M}}$ eftersom det bara är gissningsmässigt korrekt. Det är känt att den sanna generiska rangen alltid uppfyller

$r(I_{1},\ldots ,I_{M})\geq r_{E}(I_{1},\ldots ,I_{M}).$

Abo –Ottaviani–Peterson gissningen säger att jämlikhet förväntas, dvs ${\displaystyle r(I_{1},\ldots , I_{M})=r_{E}(I_{1},\ldots ,I_{M})} ,$ med följande undantagsfall:

• $F^{(2m+1)\times (2m+1)\times 3}{\text{ med }}m=1,2,\ldots$
• $F^{(m+1)\ gånger (m+1)\ gånger 2\ gånger 2}{ \text{ med }}m=2,3,\ldots$

I vart och ett av dessa undantagsfall är den generiska rangordningen känd för att vara $r(I_{ 1},\ldots,I_{m},\ldots,I_{M})=r_{E}(I_{1},\ldots,I_{M})+1$ . Observera att även om uppsättningen av tensorer av rang 3 i $F^{2\times 2\times 2\times 2}$ är defekt (13 och inte den förväntade 14), den generiska rangen i det utrymmet är fortfarande den förväntade, 4. På samma sätt är uppsättningen tensorer av rang 5 i $F^{4\times 4\times 3}$ defekt (44 och inte förväntad 45), men den generiska rangordningen i det utrymmet är fortfarande den förväntade 6.

AOP-gissningen har bevisats fullständigt i ett antal specialfall. Lickteig visade redan 1985 att ${\displaystyle r(n,n,n)=r_{E}(n,n,n)} ,$ förutsatt att $n\neq 3$ . 2011 etablerades ett stort genombrott av Catalisano, Geramita och Gimigliano som bevisade att den förväntade dimensionen av uppsättningen av rang s $\displaystyle s}$ tensorer av formatet $2\times 2\ gånger \cdots \times 2$ är den förväntade utom för rang 3 tensorer i 4-faktorfallet, men den förväntade rangordningen i det fallet är fortfarande 4. Som en konsekvens är $r(2,2,\ldots ,2)=r_{E}(2,2,\ldots ,2)$ för alla binära tensorer.

Maximal rang

Den maximala rang som kan tillåtas av någon av tensorerna i ett tensorutrymme är i allmänhet okänd; till och med en gissning om denna högsta rang saknas. För närvarande anger den bästa allmänna övre gränsen att den maximala rangordningen $r_{\mbox{max}}(I_{1},\ldots ,I_{M})$ av ${\displaystyle F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}} ,$ där ${\displaystyle I_{1}\geq I_{2}\geq \cdots \geq I_{M}} ,$ uppfyller

$r_{\mbox{max}}(I_{ 1},\ldots ,I_{M})\leq \min \left\{\prod _{m=2}^{M}I_{m},2\cdot r(I_{1},\ldots ,I_ {M})\right\},$

där $r(I_{1},\ldots ,I_{M})$ är den (minsta) generiska rangordningen för $F^{I_{1}}\otimes \cdots \otimes F^{I_{M}}$ . Det är välkänt att ovanstående ojämlikhet kan vara strikt. Till exempel är den generiska rangordningen för tensorer i $\mathbb {R} ^{2\times 2\times 2}$ två, så att ovanstående gräns ger ${\displaystyle r_{\mbox{max}}(2,2,2)\leq 4} ,$ medan det är känt att den maximala rangen är lika med 3.

Gränsrankning

En rank- $s$ tensor ${\mathcal {A}}$ kallas en gränstensor om det finns en sekvens av tensorer med högst rang $r<s$ vars gräns är ${\mathcal {A}}$ . Om $r$ är det minsta värdet för vilket en sådan konvergent sekvens existerar, så kallas det gränsrankningen av ${\mathcal {A}}$ . För tensorer av ordning 2, dvs matriser, sammanfaller alltid rang- och kantrankning, men för tensorer av ordning $\geq 3$ kan de skilja sig åt. Gränstensorer studerades först i samband med snabba, ungefärliga matrismultiplikationsalgoritmer av Bini, Lotti och Romani 1980.

Ett klassiskt exempel på en gränstensor är rank-3 tensor

${\mathcal {A}}= \mathbf {u} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {u} +\mathbf {v} \otimes \mathbf { u} \otimes \mathbf {u} ,\quad {\text{med }}\|\mathbf {u} \|=\|\mathbf {v} \|=1{\text{ och }}\langle \ mathbf {u} ,\mathbf {v} \rangle \neq 1.$

Det kan approximeras godtyckligt väl genom följande sekvens av rang-2-tensorer

${\begin{aligned}{\mathcal {A}}_ {m}&=m(\mathbf {u} +{\frac {1}{m}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{m}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{m}}\mathbf {v} )-m\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {u} \\&=\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {u} +\mathbf {v} \ ibland \mathbf {u} \otimes \mathbf {u} +{\frac {1}{m}}(\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {v} +\mathbf {v} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {v} \otimes \mathbf {v} \otimes \mathbf {u} )+{\frac {1}{m^{2}}} \mathbf {v} \otimes \mathbf {v} \otimes \mathbf {v} \end{aligned}}$

som $m\to \infty$ . Därför är dess gränsrankning 2, vilket är strikt lägre än dess rang. När de två vektorerna är ortogonala är detta exempel också känt som ett W-tillstånd .

Egenskaper

Identifierbarhet

Det följer av definitionen av en ren tensor att ${\mathcal {A}}=\mathbf {a} _ {1}\otimes \mathbf {a} _{2}\otimes \cdots \otimes \mathbf {a} _{M}=\mathbf {b} _{1}\otimes \mathbf {b} _{2} \otimes \cdots \otimes \mathbf {b} _{M}$ om och endast om det finns $\lambda _{k}$ så att $\lambda _{1}\lambda _{2}\cdots \lambda _{M}=1$ och $\mathbf {a} _{m}=\lambda _{m}\mathbf {b} _{m}$ för alla m . Av denna anledning är parametrarna $\{\mathbf {a} _{m}\}_{m=1}^{M}$ för en rank-1 tensor ${\ displaystyle {\mathcal {A}}}$ kallas identifierbara eller i huvudsak unika. A rank- $r$ tensor ${\mathcal {A}}\in F^{I_{1}}\otimes F^{ I_{2}}\otimes \cdots \otimes F^{I_{M}}$ kallas identifierbar om var och en av dess tensorranguppdelningar är summan av samma uppsättning $r$ distinkta tensorer $\{{\mathcal {A}}_{1},{\mathcal {A}}_{2},\ldots ,{\mathcal {A}}_{r }\}$ där ${\mathcal {A}}_{i}$ är av rang 1. En identifierbar rang- $r$ har alltså bara en väsentligen unik uppdelning

$${\mathcal {A}}=\sum _{i=1}^{r}{\mathcal {A}}_{i},$$

och alla $r!$ tensorranguppdelningar av ${\mathcal {A}}$ kan erhållas genom att permutera ordningen på summeringarna. Observera att i en tensor rank nedbrytning alla ${\mathcal {A}}_{i}$ är distinkta, för annars skulle rangen för ${\mathcal {A}}$ vara högst $r-1$ .

Generisk identifierbarhet

Ordnings-2 tensorer i $F^{I_{1}}\otimes F^{I_{2}}\simeq F^{I_{1}\ gånger I_{2}}$ , dvs matriser, är inte identifierbara för $r>1$ . Detta följer i huvudsak av observationen

$${\mathcal {A}}=\sum _{i=1}^{r}\mathbf {a} _{i}\otimes \mathbf { b} _{i}=\summa _{i=1}^{r}\mathbf {a} _{i}\mathbf {b} _{i}^{T}=AB^{T}=(AX ^{-1})(BX^{T})^{T}=\summa _{i=1}^{r}\mathbf {c} _{i}\mathbf {d} _{i}^{ T}=\summa _{i=1}^{r}\mathbf {c} _{i}\otimes \mathbf {d} _{i},$$

där $X\in \mathrm {GL} _{r}(F)$ är en inverterbar $r\times r$ matris, ${\displaystyle A=[\mathbf {a} _{i}]_{i=1}^{r}} , B$ = $displaystyle B=[\mathbf {b} _{i}]_{i=1}^{r}}$ , $AX^{-1}=[\mathbf {c} _ {i}]_{i=1}^{r}$ och $BX^{T}=[\mathbf {d} _{i}]_{ i=1}^{r}$ . Det kan visas att för varje ${\displaystyle X\in \mathrm {GL} _{n}(F)\setminus Z} ,$ där $Z$ är en sluten satt i Zariski-topologin, är nedbrytningen på höger sida summan av en annan uppsättning av rang-1-tensorer än nedbrytningen på vänster sida, vilket innebär att order-2 tensorer med rang r > $displaystyle r>1}$ är generellt inte identifierbara.

Situationen förändras helt för högre ordningens tensorer i $F^{I_{1}}\otimes F^{I_{2}}\otimes \cdots \otimes F^{I_{M}}$ med $M>2$ och alla $I_{m}\geq 2$ . För enkelhetens skull, anta utan förlust av allmänhet att faktorerna är ordnade så att $I_{1}\geq I_{2}\geq \cdots \geq I_{ M}\geq 2$ . Låt $S_{r}\subset F^{I_{1}}\otimes \cdots F^{I_{m}}\otimes \ cdots \otimes F^{I_{M}}$ betecknar uppsättningen av tensorer av rang som begränsas av $r$ . Sedan visade sig följande påstående vara korrekt med hjälp av ett datorstödt bevis för alla utrymmen med dimensionen ${\displaystyle \Pi <15000} ,$ och det antas vara giltigt i allmänhet:

Det finns en sluten uppsättning $Z_{r}$ i Zariski-topologin så att varje tensor ${\mathcal {A}}\in S_{r}\setminus Z_{ r}$ är identifierbar ( $S_{r}$ kallas generiskt identifierbar i det här fallet), såvida inte något av följande undantagsfall gäller:

1. Rangen är för stor: $r>r_{E}(I_{1},I_{2},\ldots ,I_{M})$ ;
2. Utrymmet är identifierbarhetsobalanserat, dvs ${\textstyle I_{1}>\prod _{m=2}^{M }i_{m}-\sum _{m=2}^{M}(I_{m}-1)} ,$ och rangordningen är för stor: ${\textstyle r\geq \prod _{m=2}^{M}I_{m}-\summa _{m=2}^{M}(I_{m}-1)}$ ;
3. Mellanrummet är det defekta fallet $F^{4}\otimes F^{4}\otimes F^{3}$ och rangordningen är $r=5$ ;
4. Mellanrummet är det defekta fallet ${\displaystyle F^{n}\otimes F^{n}\otimes F^{2}\otimes F^{2}} ,$ där $n\geq 2$ , och rangordningen är $r=2n-1$ ;
5. Mellanrummet är $F^{4}\otimes F^{4}\otimes F^{4}$ och rangordningen är $r=6$ ;
6. Mellanrummet är $F^{6}\otimes F^{6}\otimes F^{3}$ och rangordningen är $r=8$ ; eller
7. Mellanrummet är $F^{2}\otimes F^{2}\otimes F^{2}\otimes F^{2}\otimes F^ {2}$ och rangordningen är $r=5$ .
8. Utrymmet är perfekt, dvs ${\textstyle r_{E}(I_{1},I_{2},\ldots ,I_{M })={\frac {\Pi }{\Sigma +1}}}$ är ett heltal, och rangordningen är ${\textstyle r=r_{E }(I_{1},I_{2},\ldots ,I_{M})}$ .

I dessa undantagsfall är det generiska (och även minsta) antalet komplexa nedbrytningar

• visade sig vara $\infty$ i de första 4 fallen;
• visade sig vara två i fall 5;
• förväntas vara sex i fall 6;
• visade sig vara två i fall 7; och
• förväntas vara minst två i fall 8 med undantag för de två identifierbara fallen $F^{5}\otimes F^{4}\otimes F^{3}$ och $F^{3}\otimes F^{2}\otimes F^{2}\otimes F^{2}$ .

Sammanfattningsvis, den generiska tensorn av ordningen $M>2$ och rang ${\textstyle r<{\frac {\Pi }{\Sigma +1}}}$ som inte är identifierbar -obalanserad förväntas vara identifierbar (modulo undantagsfallen i små utrymmen).

Problemet med standardapproximation är dåligt ställd

Rangapproximationsproblemet frågar efter rank- $r$ -nedbrytningen närmast (i den vanliga euklidiska topologin) någon rang- $s$ tensor ${\mathcal {A}}$ , där $r<s$ . Det vill säga man söker lösa

$\min _{\mathbf {a} _{i}^{ m}\in F^{I_{m}}}\|{\mathcal {A}}-\sum _{i=1}^{r}\mathbf {a} _{i}^{1}\otimes \mathbf {a} _{i}^{2}\otimes \cdots \otimes \mathbf {a} _{i}^{M}\|_{F},$

där $\|\cdot \|_{F}$ är Frobenius-normen .

Det visades i en uppsats från 2008 av de Silva och Lim att ovanstående standardapproximationsproblem kan vara dåligt ställt . En lösning på ovannämnda problem kanske ibland inte finns eftersom den uppsättning som man optimerar över inte är stängd. Som sådan kanske en minimerare inte existerar, även om ett infimum skulle finnas. I synnerhet är det känt att vissa så kallade gränstensorer kan approximeras godtyckligt väl av en tensorsekvens av högst $r$ , även om gränsen för sekvensen konvergerar till en tensor av rang som är strikt högre än $r$ . rank-3 tensor

${\mathcal {A}}=\ mathbf {u} \otimes \mathbf {u} \otimes \mathbf {v} +\mathbf {u} \otimes \mathbf {v} \otimes \mathbf {u} +\mathbf {v} \otimes \mathbf {u } \otimes \mathbf {u} ,\quad {\text{med }}\|\mathbf {u} \|=\|\mathbf {v} \|=1{\text{ och }}\langle \mathbf {u} ,\mathbf {v} \rangle \neq 1$

kan approximeras godtyckligt väl genom följande sekvens av rang-2-tensorer

${\mathcal {A}}_{n}=n (\mathbf {u} +{\frac {1}{n}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{n}}\mathbf {v} )\otimes (\mathbf {u} +{\frac {1}{n}}\mathbf {v} )-n\mathbf {u} \otimes \mathbf {u} \otimes \mathbf {u}$

som $n\to \infty$ . Det här exemplet illustrerar på ett snyggt sätt den allmänna principen att en sekvens av rank- $r$ -tensorer som konvergerar till en tensor med strikt högre rang måste tillåta minst två individuella rank-1-termer vars normer blir obegränsade. Anges formellt, närhelst en sekvens

${\mathcal {A}}_{n}=\summa _{i=1} ^{r}\mathbf {a} _{i,n}^{1}\otimes \mathbf {a} _{i,n}^{2}\otimes \cdots \otimes \mathbf {a} _{i ,n}^{M}$

har egenskapen att ${\displaystyle {\mathcal {A}}_{n}\to {\mathcal {A}}} ($ i den euklidiska topologin) som $n\to \infty$ , då bör det finnas minst $1\leq i\neq j\leq r$ så att

$→$

som $n\to \infty$ . Detta fenomen uppstår ofta när man försöker approximera en tensor med hjälp av numeriska optimeringsalgoritmer. Det kallas ibland problemet med divergerande komponenter . Det visades dessutom att en slumpmässig lågrankad tensor över realerna kanske inte medger en rank-2 approximation med positiv sannolikhet, vilket leder till förståelsen att ill-posedness-problemet är ett viktigt övervägande när man använder tensor rank-nedbrytningen.

En vanlig dellösning på illamåendeproblemet består i att införa en ytterligare ojämlikhetsbegränsning som begränsar normen för de individuella rang-1-termerna med någon konstant. Andra begränsningar som resulterar i en sluten uppsättning, och därmed ett välpositivt optimeringsproblem, inkluderar att påtvinga positivitet eller en avgränsad inre produkt som är strikt mindre än enhet mellan rang-1-termerna som förekommer i den sökta nedbrytningen.

Beräknar CPD

Alternerande algoritmer:

• alternerande minsta kvadrater (ALS)
• alternerande skivvis diagonalisering (ASD)

Direkta algoritmer:

• blyertsbaserade algoritmer
• momentbaserade algoritmer

Allmänna optimeringsalgoritmer:

• simultan diagonalisering (SD)
• simultan generaliserad Schur-nedbrytning (SGSD)
• Levenberg–Marquardt (LM)
• icke-linjär konjugerad gradient (NCG)
• begränsat minne BFGS (L-BFGS)

Allmänna polynomsystemlösningsalgoritmer:

• homotopi fortsättning

Ansökningar

Inom maskininlärning är CP-nedbrytningen den centrala ingrediensen i inlärning av probabilistiska latenta variabelmodeller via tekniken för momentmatchning. Tänk till exempel på multi-view modellen som är en probabilistisk latent variabel modell. I denna modell ställs genereringen av sampel på följande sätt: det finns en dold slumpvariabel som inte observeras direkt, givet vilken det finns flera villkorligt oberoende slumpvariabler kända som de olika "vyerna" av den dolda variabeln. För enkelhets skull, antag att det finns tre symmetriska vyer $x$ av en $k$ -state kategorisk dold variabel $h$ . Sedan kan det empiriska tredje momentet i denna latenta variabelmodell skrivas som: $T=\sum _{i=1}^{k}Pr(h=i)E[x|h=i]^{\otimes 3}$ .

I applikationer som ämnesmodellering kan detta tolkas som att ord förekommer samtidigt i ett dokument. Då kan egenvärdena för denna empiriska momenttensor tolkas som sannolikheten för att välja ett specifikt ämne och varje kolumn i faktormatrisen $E[x|h=k]$ motsvarar sannolikheter för ord i vokabulären i motsvarande ämne.

Se även

• Latent klassanalys
• Multilinjär subspace-inlärning
• Singulärvärdesfaktorisering
• Tuckers nedbrytning
• Singularvärdesupplösning av högre ordning
• Tensornedbrytning

Vidare läsning

•   Kolda, Tamara G. ; Bader, Brett W. (2009). "Tensorupplösningar och tillämpningar". SIAM Rev. 51 (3): 455–500. Bibcode : 2009SIAMR..51..455K . CiteSeerX 10.1.1.153.2059 . doi : 10.1137/07070111X .
• Landsberg, Joseph M. (2012). Tensorer: Geometri och tillämpningar . AMS.

externa länkar

• Handledning för PARAFAC
• Parallellfaktoranalys (PARAFAC)
• FactoMineR (gratis utforskande multivariat dataanalysprogramvara kopplad till R )