Decomposizione di tensori e teoria spettrale Workshop...

Decomposizione di tensori e teoria spettraleWorkshop

Varieta reali e complesse, geometria, topologia eanalisi armonica

(28/2 - 3/3, 2013)SNS, Pisa

Giorgio Ottaviani

Universita di Firenze

Giorgio Ottaviani Decomposizione di tensori e teoria spettrale

Corso estivo

Il CIME e il CIRM organizzano un corso estivo a Levico Terme(Italy)June 10th - 15th, 2013Combinatorial Algebraic GeometryLecturers

Aldo Conca (Genova)

Sandra Di Rocco (KTH Stockholm)

Jan Draisma (TU Eindhoven)

Bernd Sturmfels (UC Berkeley)

Filippo Viviani (Roma Tre)


Annuncio di convegno

August June 1st - 4th, 2013Applied Algebraic Geometry


Tensori d-dimensionalicome generalizzazioni delle matrici (d=2)

Le matrici sono elementi di V1 ⊗ V2, Vi spazi vettoriali

Vediamo i tensori come elementi di V1 ⊗ . . .⊗ Vd , Vi spazi

vettorialiLa differenza principale e che in generaledimGL(V1)× . . .× GL(Vd) < dim V1 ⊗ . . .⊗ Vd per d ≥ 3.C’e un’altra differenza piu sottile nel caso d ≥ 3 chespiegheremo piu avanti (rango versus rango bordo).


Coppie di vettori singolari

La coppia (x1, x2) ∈ (Rn \ {0})× (Rm \ {0}) si dice coppia divettori singolari per una matrice rettangolare A di formato n ×mse esiste λ ∈ R≥0 tale che

Ax2 = λx1 x t1A = λx t

2

λ di dice valore singolare.I valori singolari sono

√λi dove λi sono gli autovalori di AtA.

x2 e autovettore di AtA.x1 e autovettore di AAt .A generale ha min(n,m) coppie di vettori singolari.


Singular Value Decomposition, SVD

Se M e una matrice (reale) m × n , la SVD di M e

M = UΣV t

doveU e una matrice ortogonale m ×m.V e una matrice ortogonale n × n.Σ e una matrice diagonale m × n, con σ1 ≥ σ2 ≥ . . . ≥ σr ≥ 0sulla diagonale, che sono i valori singolari di M.Le prime r colonne di V sono i vettori singolari destri.Le prime r colonne di U sono i vettori singolari sinistri.

Se M e simmetrica allora U = V e la SVD si riduce al teoremaspettrale M = UDUt .


Migliore approssimazione in rango k

Sia Xk = {matrici di rango ≤ k}abbiamo X1 ⊂ X2 ⊂ X3 ⊂ . . .La norma di Frobenius e ‖A‖F =

√∑i ,j ‖a2

ij‖.

Teorema

Data una matrice A con valori singolari σ1 ≥ σ2 ≥ . . . ≥ σr ,

min{B|B∈Xk}

‖A− B‖F =

√ ∑i≥k+1

σ2i

e la matrice B che minimizza e costruita dai k valori singolarimaggiori (cioe mandando a zero i restanti valori singolari nellaSVD di A).


Immagini create da Emanuele Frandi, Alessandra Papini(Universita di Firenze).

L’immagine originale e 256× 256

rank 256

rank 64, occupa 14 della memoria rispetto

all’originale.


Le d-ple singolari

Ogni tensore t ∈ Rm1 × . . .× Rmd definisce per contrazione unafunzione ft sul prodotto S = Sm1−1 × . . .× Smd−1 dellecorrispondenti d sfere.ft : S → R

Teorema (Lim, Qi)

I punti critici di ft corrispondono ai tensori (x1, . . . , xd) ∈ S tali che

t(x1, . . . , xi , . . . , xd) = λixi

Le d-ple che soddisfano l’equazione del teorema si dicono d-plesingolari. Generalizzano le coppie di vettori singolari viste nel casod = 2.

Quante sono le d-ple singolari di un tensore generale? Nel formato(2, 2, 2) sono 6, nel formato (3, 3, 3) sono 37. Notiamo che sono innumero maggiore della dimensione dello spazio!


Il numero di d-ple singolari

Teorema (Friedland-O)

Il numero delle d-ple singolari di un tensore generalet ∈ P(Rm1)× . . .× P(Rmd ) su C di formato (m1, . . . ,md) e ilcoefficiente di

∏di=1 tmi−1

i nel polinomio

d∏i=1

timi − tmi

i

ti − ti

dove ti =∑

j 6=i tj


Migliore approssimazione in rango uno per tensori.

Corollario

Un tensore generale ha un numero finito di d-ple singolari, convalori singolari distinti.La migliore approssimazione in rango uno e unica, data ancora dalvalore singolare massimo.

I tensori di rango uno sono quelli decomponibili, cioe della formav1 ⊗ . . .⊗ vd , costituiscono la varieta di Segre.Vedremo piu avanti i problemi con il rango superiore.


Interpretazione con i fibrati vettoriali

Per la dimostrazione si esprimono le d-ple di vettori singolari comezeri di sezione di un opportuno fibrato vettoriale sulla varieta diSegre. Il calcolo si riduce a una classe di Chern .Nel formato (2, . . . , 2︸︷︷︸

d

) il numero delle d-ple singolari e d!.


Tabella nel caso 3-dimensionale

Tabella del numero di triple singolari nel formato (d1, d2, d3)

d1, d2, d3 c(d1, d2, d3)

2, 2, 2 62, 2, n 8 n ≥ 32, 3, 3 152, 3, 4 18 n ≥ 43, 3, 3 373, 3, 4 553, 3, n 61 n ≥ 53, 4, 4 1043, 4, 5 1383, 4, n 148 n ≥ 6

Il risultato si stabilizza per (a, b, c) con c ≥ a + b − 1.Il formato (a, b, a + b− 1) e il formato bordo, ben noto nella teoriadegli iperdeterminanti. Generalizza il caso quadrato.


Il formato bordo

Per d qualunque, il formato k1 × k2 × . . .× kd con k1 = maxj kj edetto formato bordo sek1 − 1 =

∑di=2(ki − 1)

Questo e il formato dove e possibile definire la diagonaleanalogamente al caso delle matrici quadrate.

L’esempio fondamentale e dato dal tensore di moltiplicazione

Sk2−1C2 ⊗ . . .⊗ Skd−1C2 → S∑

i (ki−1)C2

che appartiene a

⊗di=1

(Ski−1C2

)


La diagonale

Nel formato bordo e ben definita una unica “diagonale” data daelementi ai1...id che soddisfano i1 =

∑dj=2 ij

(numeriamo gli indici a partire da zero)Sono definite in modo naturale matrici diagonalizzabili etriangolabili.


Teorema

([Ancona-O] for d = 3, [Dionisi] for d ≥ 4) SiaA ∈ P(V1 ⊗ V2 ⊗ . . .⊗ Vd) di formato bordo tale che Det A 6= 0.Allora esiste uno spazio vettoriale 2-dimensionale U tale che SL(U)agisce su Vi ' Ski−1U e rispetto a questa azione su V1 ⊗ . . .⊗ Vd

abbiamo Stab (A)0 ⊂ SL(U). Inoltre i seguenti casi sono possibili

Stab (A)0 '

{0}CC∗

SL(2) (se e solo se A corrispondeal tensore di moltiplicazione precedente)


Il caso simmetrico

Nel caso simmetrico, un tensore in Sd(Cm) ha

(d − 1)m − 1

d − 2

vettori singolari.Per d = m = 3 viene 7.In generale si calcola [Oeding-O]

cm−1(TPm−1(d − 2)) =(d − 1)m − 1

d − 2

La prima dimostrazione della formula nel caso simmetrico e statadata da [Cartwright-Sturmfels] mediante il calcolo di un volumetorico.


Vantaggi dell’interpretazione geometrica con i fibrati

Nel formato 3× 3× 3 , i casi possibili per gli zeri di sezione sono

7 punti (con molteplicita)

1 retta e 3 punti (con molteplicita)

1 conica

Questi corrispondono alle configurazioni possibili degliautovettori del tensore.


Decomposizione di Tensori e Rango

Viste le difficolta a generalizzare la SVD, si da la seguente

Definizione

Una decomposizione di un tensore f di formato (m1, . . . ,md) e

f =r∑

i=1

civi ,1 ⊗ . . .⊗ vi ,d con ci ∈ C, vi ,j ∈ Cmj

Definizione

Il rango rk(f ) e il minimo numero di addendi in unadecomposizione di f . Una decomposizione minimale ha rk(f )addendi ed e chiamata CANDECOMP o PARAFAC.

La nota positiva e che la decomposizione minimale e quasi sempreunica per d ≥ 3, cosa che non accade per d = 2.


Il risultato negativo di Limsulla complessita del calcolo del rango

Lek-Heng Lim ha provato nel 2005 che il calcolo del rango e delladecomposizione di un tensore e NP-hard per d ≥ 3.La migliore approssimazione di rango ≤ r puo non esistere permotivi geometrici che spieghiamo tra poco.Nondimeno ci sono algoritmi che lavorano in casi di rango basso eMATLAB packages che calcolano una decomposizione che ecorretta in molti casi.


Tensori simmetrici come polinomi omogenei

Nel caso m1 = . . . = md = m possiamo considerare tensorisimmetrici f ∈ SdRm f ∈ SdCm. Corrispondono in modo naturalea polinomi omogenei di grado d in m variabili.I tensori simmetrici di rango uno corrispondono ai polinomiomogenei che sono potenza di una forma lineare (varieta diVeronese).


Decomposizione di un tensore simmetrico (Waring)

Una decomposizione di Waring di f ∈ SdV e

f =r∑

i=1

ci (li )d with li ∈ V

con r minimale.r e detto il rango simmetrico di f .

Esempio: 7x3 − 30x2y + 42xy 2 − 19y 3 = (−x + 2y)3 + (2x − 3y)3

rks(7x3 − 30x2y + 42xy 2 − 19y 3

)= 2

Hilbert, 1888

Il polinomio generale f di grado 5 in tre variabili ha una unicadecomposizione come somma di 7 potenze di forme lineari.


Algoritmo per la decomposizione

Teorema (Oeding-O)

Costruzione di un algoritmo che calcola la decomposizione diWaring (in rango basso) via autovettori di tensori.

Funziona ad esempio nel caso di Hilbert dei polinomi di grado 5 in3 variabili.Si costruisce in aritmetica esatta l’ideale che si annulla sullesoluzioni.


La congettura di Comon

Congettura (Comon)

Per un tensore simmetrico, il rango simmetrico e uguale al rango.

La congettura e dimostrata per forme binarie [Buczynski, Ginensky,Landsberg] e in grado 2 e il classico teorema di Sylvester.

Teorema (Zhang, Ling, Qi, ,Friedland)

La migliore approssimazione in rango uno di un tensore simmetricoe simmetrica.


Gli insiemi di tensori di rango ≤ r non sono chiusi

rk(x3) = 1

rk(x3 + y 3) = 2

x2y = 13

[(x + y)3 − (x − y)3 − 2y 3

], da cui rk(x2y) = 3 ma.....

x2y = limt→0(x+ty)3−x3

3tcosı che un polinomio di rango 3 puo essere approssimato dapolinomi di rango 2. In questo caso diciamo che il rango bordo dix2y e 2.Quindi la migliore approssimazione in rango ≤ r non e ben definita.Questo da una spiegazione geometrica di un fenomeno osservatoper la prima volta da Dario Bini e approfondito dalla scuola di M.Capovani.La “speranza” e che il calcolo del rango bordo NON sia NP-hard.


La varieta secante

La chiusura della varieta dei tensori di rango ≤ r si dice varietar -secante (alla varieta di Segre nel caso generale, alla varieta diVeronese nel caso simmetrico).Abbiamo la catena di inclusioni

X = σ1(X ) ⊂ σ2(X ) ⊂ . . . ⊂ PN

La dimensione aspettata di σk(X ) e min(k · dim X + (k − 1),N)


Il Teorema di Alexander-Hirschowitz

Teorema (Campbell, Terracini, Alexander-Hirschowitz

[1891] [1916] [1995])

Il polinomio generale f ∈ SdCn+1 (d ≥ 3) ha rango

d(n+d

d

)n + 1

e

rango generico, con le sole eccezioni

2 ≤ n ≤ 4, d = 4, dove il rango generico e(n+2

2

)(n, d) = (4, 3), dove il rango generico e 8

Ci sono tabelle analoghe per l’unicita della decomposizione, condue casi eccezionali in piu ([Chiantini, Ciliberto, Mella, Ballico]).


Come estendere il teorema di Alexander-Hirschowitz ?

Uno dei problemi piu importanti e l’estensione del Teorema diAlexander-Hirschowitz al caso non simmetrico.

Teorema (Catalisano-Geramita-Gimigliano)

Le varieta secanti di P1 × . . .× P1 hanno sempre la dimensioneaspettata per n 6= 4.

Teorema (Abo-O-Peterson)

Le varieta secanti di Pn × . . .× Pn hanno sempre la dimensioneaspettata escluso al piu gli ultimi n valori del rango.

Diamo una congettura sui casi dove la varieta secante nondovrebbe avere la dimensione aspettata.


Monografia consigliata

J.M. Lansberg, Tensors, Geometry and Applications, AMS,2012


Thanks !!


Decomposizione di tensori e teoria spettrale Workshop...

Documents

Transcript of Decomposizione di tensori e teoria spettrale Workshop...