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)
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
Annuncio di convegno
August June 1st - 4th, 2013Applied Algebraic Geometry
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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).
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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 .
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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).
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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!
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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!.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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
)
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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)
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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).
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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)
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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]).
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
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.
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale
Monografia consigliata
J.M. Lansberg, Tensors, Geometry and Applications, AMS,2012
Giorgio Ottaviani Decomposizione di tensori e teoria spettrale