CORSO DI LAUREA IN MATEMATICA
L’algoritmo di Sinkhorn-Knopp come metodo
delle potenze per un operatore non lineare:
velocità di convergenza e tecniche di accelerazione.
Tesi di Laurea magistrale
8 Giugno 2018
Relatore:
Prof. Luca Gemignani
Candidato: Alessio Aristodemo
Introduzione 5
1 Il problema di scaling 7
1.1 Introduzione e risultati preliminari . . . 7
1.2 Teoria di Perron-Frobenius non lineare . . . 12
1.3 Teoremi di Sinkhorn-Knopp . . . 23
2 Algoritmo di Sinkhorn Knopp 25 2.1 Metrica proiettiva di Hilbert . . . 25
2.2 Studio della convergenza . . . 34
2.3 Velocità di convergenza . . . 39
3 Tecniche di accelerazione 47 3.1 Una tecnica di accelerazione . . . 47
3.2 Il caso quasi decomponibile . . . 52
3.2.1 Una variante a blocchi . . . 57
3.3 Considerazioni finali . . . 59
Bibliografia 59
Se una matrice quadrata non negativa A possiede un numero sufficiente di elementi non nulli, essa può essere bilanciata: esistono cioè matrici diagonali D1 e D2, con en-trate diagonali strettamente positive, tali che P = D1AD2 risulta essere doppiamente
stocastica. Una matrice è detta doppiamente stocastica se è non negativa e la somma delle sue entrate su ciascuna riga e su ciascuna colonna è uguale a 1. Il problema di bilanciamento o di scaling appena descritto è stato storicamente studiato nell’ambito di problemi di traffico, ma ha trovato successivamente applicazione in diversi ambiti: dal precondizionamento di matrici, al problema del PageRank. In due lavori del 1962 e del 1967 Sinkhorn e Knopp hanno dato condizioni necessarie e sufficienti affinchè una ma-trice non negativa possa essere bilanciata; negli stessi lavori hanno inoltre descritto una procedura per ottenere, qualora esista, uno scaling doppiamente stocastico.
In questa tesi descriveremo dapprima sotto quali ipotesi il problema di scaling am-mette una risposta affermativa. Il nostro approccio sarà differente da quello adottato da Sinkhorn e Knopp: l’idea chiave sarà quella di considerare un operatore non lineare T -definito sul cono dei vettori non negativi di Rn - il cui punto fisso, se esiste, fornirà una soluzione del problema. A tal fine svilupperemo una teoria di Perron-Frobenius non li-neare che sotto precise ipotesi sullo zero-pattern della matrice A ci permetterà di dedurre l’esistenza di un punto fisso per T .
Successivamente il nostro scopo sarà quello di studiare sotto quali ipotesi l’algoritmo di Sinkhorn-Knopp converge alla soluzione del problema di bilanciamento. Vedremo che è possibile inquadrare la procedura descritta dai due autori come un metodo delle potenze non lineare per la mappa T . Le peculiarità di questa mappa ci guideranno alla definizione di una metrica proiettiva sul cono dei vettori non negativi di Rn, rispetto alla quale T risulterà essere una contrazione. Un’applicazione del teorema del punto fisso di Banach concluderà la dimostrazione della convergenza.
Discuteremo quindi risultati circa la velocità di convergenza dell’algoritmo appena descritto: sotto le opportune ipotesi l’algoritmo di Sinkhorn-Knopp converge linearmente con un tasso di convergenza che è governato dal secondo più grande valore singolare di P .
Nell’ultima sezione presenteremo il contributo originale di questa tesi. Proporremo un metodo per accelerare la convergenza dell’algoritmo di Sinkhorn-Knopp. La tecnica di accelerazione che proponiamo risulta particolarmente efficiente se applicata a matri-ci quasi decomponibili di grandi dimensioni. Matrimatri-ci di questo tipo si incontrano nello studio di problemi di comunicabilità su reti e su di esse l’algoritmo standard si rivela assolutamente inefficiente in termini di velocità di convergenza. La nostra procedura, basata su un metodo di Arnoldi a blocchi, evidenzia sperimentalmente un tasso di con-vergenza quadratico di gran lunga preferibile alla concon-vergenza lineare dell’algoritmo di Sinkhorn-Knopp.
Il problema di scaling
1.1
Introduzione e risultati preliminari
Il problema di trasformare una matrice quadrata non negativa in una matrice doppia-mente stocastica è da anni oggetto di studi in diversi ambiti. Data una matrice quadrata A ∈ Rn×n, che supporremo avere entrate tutte non negative (A ≥ 0), siamo interessati a trovare due matrici diagonali D1, D2 tali che S = D1AD2 risulti doppiamente stocastica.
Con questo termine ci riferiamo ad una matrice lo ribadiamo, ad entrate non negative -la cui somma degli elementi su ciascuna riga e su ciascuna colonna di S sia uguale ad 1.
Se introduciamo l’operatore
D : Rn→ Rn×n
che associa al vettore v ∈ Rn la matrice D(v) = diag(v1, . . . , vn) possiamo riformulare il
problema come ricerca di due vettori r, c ∈ Rn strettamente positivi e tali che D(r)AD(c)e = D(r)Ac = e,
D(c)ATD(r)e = D(c)ATr = e (1.1)
dove con e = (1, . . . , 1)T abbiamo indicato il vettore di tutti 1.
Il problema appena descritto, noto in letteratura come equilibratura, scaling o bi-lanciamento di matrici è stato - come detto - a lungo studiato. In una serie di articoli degli anni ’60 Sinkhorn e Knopp hanno fornito condizioni necessarie e sufficienti affinché una matrice quadrata non negativa ammetta uno scaling del tipo sopra indicato. Tali condizioni riguardano sostanzialmente lo zero-pattern di A ovvero la disposizione degli elementi nulli al suo interno.
Diamo ora alcune definizioni che ci permetteranno di caratterizzare tale disposizione. Definizione 1.1. Sia A ∈ Rn×n una matrice quadrata, σ ∈ Sn una permutazione di 1, . . . , n . Diremo che la n-upla a1,σ(1), . . . , an,σ(n) è una diagonale di A. Nel caso in
cui σ = idSn la diagonale è detta principale.
Definizione 1.2 (Supporto). Sia A ∈ Rn×n, A ≥ 0 una matrice quadrata non negativa. Diremo che A ha supporto totale se ogni elemento aij > 0 è contenuto in una diagonale positiva.
Se A contiene una diagonale positiva diremo semplicemente che A ha supporto.
Definizione 1.3 (Riducibilità). A ∈ Rn×n è detta riducibile se esiste una matrice di permutazione P ∈ Rn×n tale che
P APT =A11 0 A21 A22
(1.2)
con A11, A22 quadrate.
Se una matrice P siffatta non esiste, A è detta irriducibile.
Osservazione 1.1. Un’interpretazione combinatoria della precedente definizione può es-sere data mediante il grafo di adiacenza associato alla matrice A. In questo contesto l’irriducibilità della matrice è equivalente alla forte connessione del suo grafo di adiacenza. Definizione 1.4 (Decomponibilità). A ∈ Rn×n è detta parzialmente decomponibile se esistono matrici di permutazione P, Q ∈ Rn×n tale che
P AQ =A11 0 A21 A22
(1.3)
con A11, A22 quadrate.
Se P e Q siffatte non esistono, A è detta completamente indecomponibile.
Osservazione 1.2. Chiaramente una matrice completamente indecomponibile è a mag-gior ragione irriducibile.
Noti questi prerequisiti possiamo procedere ad enunciare i due teoremi dovuti a Sinkhorn e Kopp cui accennavamo prima.
Teorema 1.1 (Sinkhorn 1962). Sia A ∈ Rn×n, A > 0. Esistono D1, D2 ∈ Rn×ndiagonali strettamente positive tali che D1AD2 sia doppiamente stocastica.
D1, D2 sono uniche a meno di un fattore moltiplicativo.
Teorema 1.2 (Sinkhorn-Knopp 1967). Sia A ∈ Rn×n, A ≥ 0. Condizione necessaria e sufficiente affinché esistano D1, D2 ∈ Rn×n diagonali strettamente positive tali che
S = D1AD2 sia doppiamente stocastica è che A abbia supporto totale.
Se S esiste allora e’ unica.
D1, D2 sono uniche a meno di un fattore moltiplicativo se e solo se A è completamente
La dimostrazione di questi due risultati (in realtà il primo dei due teoremi è un’im-mediata conseguenza del secondo) è rimandata alla fine di questo capitolo. Non percorre-remo la dimostrazione originale proposta dai due autori ma sviluppepercorre-remo una teoria più generale che ci permetterà di provare gli stessi risultati in maniera più elegante.
Nei due lavori del 1964 e del 1967 Sinkhorn e Knopp proposero inoltre un sempli-ce algoritmo che consente, sotto le ipotesi dei teoremi appena enunciati, di ottenere il bilanciamento richiesto.
Consideriamo le equazioni (1.1). Sfruttando la relazione D(v)w = D(w)v otteniamo: c = D(ATr)−1e,
r = D(Ac)−1e. (1.4) La natura ricorsiva delle (1.4) ci suggerisce il seguente algoritmo iterativo:
ck+1= D(ATrk)−1e,
rk+1= D(Ack+1)−1e.
(1.5)
fissato - ovviamente - un vettore iniziale r0 (ad esempio il vettore e = (1, . . . , 1)T).
Il principale risultato relativo alla convergenza di questo algoritmo è il seguente. Teorema 1.3 (Iterazione di Sinkhorn-Knopp). Condizione necessaria e sufficiente affin-ché l’iterazione di Sinkhorn-Knopp converga ad un limite doppiamente stocastico è che A abbia supporto.
Se inoltre A ha supporto totale, il limite è della forma D1AD2.
Se A ha supporto che non è totale il limite può non essere di questa forma.
Proveremo questo teorema più avanti. Addentriamoci adesso nello studio delle rela-zioni che intercorrono tra le varie norela-zioni correlate alla distribuzione degli zeri all’interno di una matrice A non negativa. Vedremo come queste nozioni sono intimamente collegate alla possibilità di rendere A doppiamente stocastica nel senso che abbiamo specificato all’inizio del capitolo.
Enunciamo preliminarmente, senza darne dimostrazione, un importante risultato no-to in letteratura come teorema di Frobenius-König che in qualche modo caratterizza il supporto di A.
Teorema 1.4 (Frobenius-König). Una matrice quadrata A n × n contiene una sottoma-trice nulla r × s con r + s = n + 1 se e solo se ogni diagonale di A possiede un elemento nullo.
Se introduciamo il concetto di permanente di una matrice
perm(A) = X σ∈Sn n Y i=1 aiσ(i),
il teorema di Frobenius-König può essere enunciato nel seguente modo:
A contiene una sottomatrice nulla r × s con r + s = n + 1 ⇔ perm(A) = 0. Siamo ora in grado di provare un risultato che ci sarà utile successivamente ma comunque interessante di per sé.
Proposizione 1.1. Sia A ∈ Rn×n, A ≥ 0. A è completamente indecomponibile se e solo se le sue colonne possono essere permutate in modo da ottenere una matrice irriducibile con diagonale principale strettamente positiva.
Dimostrazione. Sia A completamente indecomponibile. A non contiene sottomatrici nulle di dimensioni s × n − s, pertanto, per il teorema di Frobenius-König, contiene una diago-nale positiva. È dunque possibile permutare le colonne di A in modo da portare questa diagonale in posizione principale. La matrice appena ottenuta rimane completamente indecomponibile e pertanto irriducibile.
Supponiamo ora che esistano P, Q matrici di permutazione tali che P AQ risulti irridu-cibile e con diagonale principale positiva. Poiché A è completamente indecomponibile se e solo se P AQ lo è possiamo assumere che A sia essa stessa irriducibile con diagonale positiva. Supponiamo per assurdo che A non sia completamente indecomponibile e siano P1, Q1 matrici di permutazione tali che
P1AQ1 =
A11 0
A21 A22
dove A11è una matrice r × r.
Scriviamo ora P1AQ1 = P1AP1T (P1Q1) = A0Q0, dove (ecco il motivo di questa
scrit-tura) A0 = P1AP1T ha ancora diagonale principale positiva avendo operato su A una
permutazione simultanea di righe e colonne. Segue allora che Q0= P1Q1 deve permutare
tra loro rispettivamente le prime r colonne e le ultime n − r colonne di A0, altrimenti in A0, la sottomatrice principale di testa di dimensione k avrebbe un’intera colonna di zeri e ciò inficerebbe la stretta positività della diagonale principale di A0. Ma allora anche A0 è della forma A0 =A 0 11 0 A021 A022
e ciò implica che A è riducibile, assurdo.
Vediamo adesso in che modo i concetti di supporto e indecomponibilità sono connessi con la stocasticità di una matrice non negativa. Premettiamo una definizione.
Definizione 1.5. Data A ∈ Rn×n, A ≥ 0, diremo che che A ha un pattern doppiamente stocastico se esiste una matrice S doppiamente stocastica con la proprietà che
Chiaramente se esistono D1, D2 diagonali positive tali che D1AD2 è doppiamente
stocastica allora A ha un pattern doppiamente stocastico. Sorprendentemente vale anche il viceversa: un primo passo in questa direzione è dato dal seguente teorema.
Teorema 1.5. Sia A ≥ 0 una matrice n × n non nulla. Le seguenti sono equivalenti: (i) A ha supporto totale.
(ii) A ha un pattern doppiamente stocastico.
(iii) A non può essere ridotta tramite permutazioni arbitrarie di righe e colonne nella forma
X 0 Y Z
(1.6) dove X è una matrice k × k con 0 < k < n ed Y 6= 0.
(iv) Esistono P, Q matrici di permutazione tali che P AQ è somma diretta di matrici completamente indecomponibili, ovvero
P AQ = k M i=1 Ai= A1 A2 . .. Ak
con Ai completamente indecomponibile ∀i = 1, . . . , k. Dimostrazione. Vediamo le varie implicazioni:
(i) ⇒ (ii) Sia aij un elemento non nullo di A. Per ipotesi aij appartiene ad una diagonale
positiva di A, ovvero esiste una matrice di permutazione P(ij) avente un 1 in posi-zione (i, j) e tale che le entrate occupate dagli elementi unitari corrispondano in A ad elementi non nulli. Detto t il numero di elementi non nulli di A osserviamo che
1 t
X
aij6=0
P(ij)
è una matrice doppiamente stocastica con lo stesso pattern di A.
(ii) ⇒ (iii) Sia S doppiamente stocastica con lo stesso pattern di A. Se (iii) non fosse soddi-sfatta esisterebbero P, Q matrici di permutazione tali che P SQ abbia la forma (1.6). La stocasticità viene preservata quando eseguiamo permutazioni di righe e colonne, pertanto se sommiamo gli elementi di X riga per riga otteniamo k. Se eseguiamo la stessa somma per colonne, essendo Y 6= 0 otteniamo una quantità strettamente minore di k e questo è assurdo.
(iii) ⇒ (iv) Se A è completamente indecomponibile la tesi è ovviamente verificata. Supponiamo che A sia decomponibile ed abbia supporto totale. A può allora essere ridotta tramite permutazioni arbitrarie delle sue righe e colonne nella forma
P AQ =X 0 Y Z
.
Per ipotesi esiste un elemento yij di Y non nullo. Il minore ottenuto eliminando
la riga e la colonna corrispondenti a yij contiene una sottomatrice nulla di ordine k × n − k e per il teorema di Frobenius-König non ha diagonali positive, assurdo. Pertanto Y deve essere identicamente nulla e P AQ assume la forma diagonale a blocchi:
P AQ =X 0 0 Z
.
Con lo stesso argomento si procede per induzione sulle sottomatrici X e Z fino ad ottenere una matrice diagonale a blocchi con tutti i blocchi completamente indecomponibili, il che conclude la dimostrazione.
(iv) ⇒ (i) Possiamo supporre che A sia già stata permutata in forma diagonale a blocchi con i blocchi completamente indecomponibili. È allora sufficiente provare che ogni blocco abbia supporto totale, ovvero che se M è una matrice completamente indecomponi-bile allora ha supporto totale. Supponiamo per assurdo che M non abbia supporto totale: esiste allora un elemento mij 6= 0 che non appartiene ad alcuna diagonale
positiva di M . Se consideriamo la sottomatrice N ottenuta da M rimuovendo la i-esima riga e la j-esima colonna, notiamo che N non ha diagonali positive (se ne avesse, estesa ad M , conterrebbe mij). Per il teorema di Frobenius-König esiste
allora una sottomatrice di N (e dunque di M ) di dimensione r × s con r + s = n avente tutte le entrate nulle. M risulta pertanto decomponibile, il che è assurdo.
Nella prossima sezione svilupperemo una teoria che ci sarà utile per provare in maniera piuttosto elegante il teorema di Sinkhorn-Knopp.
1.2
Teoria di Perron-Frobenius non lineare
Un noto teorema dovuto a Perron e Frobenius stabilisce che se A è una matrice non negativa, aperiodica ed irriducibile allora il raggio spettrale di A, ρ(A), è un autovalore semplice e ad esso corrisponde un autovettore con componenti strettamente positive. Il nostro obiettivo è quello di estendere questo teorema ad un particolare operatore non li-neare (associato ad una generica matrice non negativa A) che va sotto il nome di operatore di Menon. Introduciamo alcune notazioni:
¯
R = R ∪ {±∞} è l’insieme dei reali esteso con l’usuale topologia;
P = {x ∈ Rn: x ≥ 0} è l’insieme dei vettori reali a componenti non negative; P0= {x ∈ Rn: x > 0}
è l’insieme dei vettori reali a componenti strettamente positive; P∞=x ∈ ¯Rn: x ≥ 0
è l’insieme dei vettori ad entrate reali non negative (possibilmente infinite).
Dati due elementi x, y ∈ P∞diremo che x ≤ y se xi≤ yi ∀i = 1, . . . , n; analogamente
diremo che x < y se xi < yi ∀i = 1, . . . , n. Infine introduciamo per comodità la seguente
notazione:
x y⇐⇒ x ≤ y, ma x 6= y.def
Sia ora A ≥ 0 una matrice n × n. Con la convenzione che 10 = ∞, ∞1 = 0, ∞ + ∞ = ∞, 0 · ∞ = 0 e, se a > 0, a · ∞ = ∞ (dove con ∞ intenderemo sempre +∞), definiamo i seguenti operatori associati ad A:
U : P∞→ P∞
(U x)i= x−1i
che inverte tutte le componenti di un dato vettore; S : P∞→ P∞
S = U A
che data una matrice ed un vettore, calcola il prodotto riga per colonna e successivamente ne inverte le componenti;
T : P∞→ P∞
T = U ATU A
che data una matrice ed un vettore, calcola il prodotto riga per colonna, ne inverte le componenti ed itera lo stesso procedimento utilizzando la matrice trasposta.
In particolare vediamo come si comportano gli operatori S e T in componenti:
(Sx)i = n X j=1 aijxj −1
(T x)i= n X k=1 aki n X j=1 akjxj −1 −1
Se intendiamo l’operazione di inversione componente per componente possiamo visua-lizzare come agiscono i due operatori appena definiti tramite il seguente schema.
Sx
z }| {
x 7→ Ax 7→ (Ax)−1 7→ AT(Ax)−1 7→ (AT(Ax)−1)−1
| {z }
T x
.
T è detto operatore di Menon associato alla matrice A, in onore di M.V. Menon che ne indagò le proprietà proprio in vista dello studio del problema di scaling, benché egli si interessò in particolare a matrici strettamente positive e ne diede esempio di utilizzo solo nel caso 3 × 3.
Diamo ora alcune definizioni che ci permetteranno di trattare le proprietà spettrali dell’operatore T .
Definizione 1.6. Sia T : P∞→ P∞ un operatore.
• T è detto monotòno (su P∞) se
∀x, y ∈ P∞ x ≤ y ⇒ T x ≤ T y.
• T è detto strettamente monotòno (su P0) se
∀x, y ∈ P0 x y ⇒ T x T y ∧ ∃m ∈ N+: Tmx < Tmy
• T è detto omogeneo (su P) se
∀x ∈ P, ∀α ∈ R, α ≥ 0 T (αx) = αT (x).
Vedremo di seguito che le proprietà appena enunciate sono soddisfatte dall’operatore di Menon associato ad una certa classe di matrici.
Proposizione 1.2. Sia A ≥ 0 una matrice n × n irriducibile con diagonale principale positiva. Sia T l’operatore di Menon ad essa associato ed S definito come sopra. Valgono le seguenti:
(i) S e T sono continui su P∞;
(ii) S(P0) ⊆ P0, T (P0) ⊆ P0;
(iv) T è omogeneo su P;
(v) T è monotòno su P∞ e strettamente monotòno su P0.
Dimostrazione. Ricordiamo che 10 = ∞, ∞1 = 0, ∞ + ∞ = ∞, 0 · ∞ = 0 e, se a > 0. (i) Per le convenzioni operatoriali adottate su P∞segue che A, AT ed U sono operatori
continui su tale insieme. Pertanto le composizioni S = U A e T = U ATU A sono anch’esse continue su P∞.
(ii) Sia x ∈ P0. Essendo x > 0 ed aii> 0 ∀ i = 1, . . . , n segue che Ax > 0 e pertanto
Sx = U Ax ∈ P0. Allo stesso modo si vede che T x ∈ P0.
(iii) Sia x ∈ P. Ax ∈ P, pertanto (U Ax) > 0 (possibilmente con entrate infinite). Essendo aii> 0 si ha che ATU Ax > 0 e passando ai reciproci si ha U ATU Ax < ∞
ovvero T x ∈ P.
(iv) A ed AT essendo operatori lineari sono in particolare omogenei. Sia x ∈ P, α > 0.
Poiché U (αx) = α−1(U x) segue che T (αx) = α(T x). Si conclude osservando che naturalmente vale anche T 0 = 0.
(v) Se proviamo che T è strettamente monotòno su P0, essendo P0 denso in P∞ ed
essendo T continuo su P∞ si ha la tesi. Siano allora x, y ∈ P0, x y. Chiaramente
Ax ≤ Ay e in particolare (Ax)i < (Ay)i se e solo se esiste j tale che aji > 0 e
xj < yj. Abbiamo due possibilità: se x < y allora Ax < Ay (essendo aii > 0 per
ogni i = 1, . . . , n) e dunque U Ax < U Ay e T x < T y; se invece per qualche i si ha che xi = yi la situazione è più delicata e procediamo come segue.
Supponiamo dunque xi = yi per i = 1, . . . , r < n e xi < yi per i = r + 1, . . . , n
-dopo aver permutato allo stesso modo (e simultaneamente) righe e colonne di A. Osservando che risulta ancora aii> 0, segue che (Ax)i< (Ay)i per i = r + 1, . . . , n.
Poiché A è irriducibile non può contenere una sottomatrice nulla di dimensioni r × (n − r), pertanto esistono 1 ≤ h ≤ r, r + 1 ≤ k ≤ n tali che akh > 0 e
possiamo supporre, a meno di permutazioni del blocco relativo alle entrate nulle di x ed y, che sia h = r. Dunque (Ax)r< (Ay)r e (T x)i ≤ (T y)i per i = 1, . . . , r − 1,
(T x)i < (T y)i per i = r, . . . , n. In sostanza abbiamo guadagnato un indice per cui
vale la disuguaglianza stretta. Iterando lo stesso ragionamento un numero finito m di volte otteniamo Tmx < Tmy che era ciò che volevamo.
Avendo mostrato che l’operatore di Menon associato ad una matrice non negativa, irriducibile e con diagonale principale positiva è (in particolare) continuo e strettamente monotono su P0, occupiamoci di alcune proprietà che caratterizzano questa classe di
Definizione 1.7. Sia T : P → P, x ∈ P, x 6= 0. Definiamo Λ(x) := sup {λ : T x ≥ λx} .
Osservazione 1.3. Λ(x) può anche essere caratterizzata come segue:
Λ(x) := min (T x)i xi
: xi > 0
,
da cui segue che Λ(x) < ∞.
Lemma 1.1. Sia T : P → P un operatore continuo. Λ : P \ {0} è semicontinua superiormente.
Dimostrazione. Sia (xα) ⊂ P \ {0} una successione tale che xα → x ∈ P \ {0}. Vogliamo
provare che
λ := lim sup
xα→x Λ(x
α) ≤ Λ(x).
Esiste una sottosuccessione xαk tale che xαk → x e Λ(xαk) → λ. Per definizione T xαk−
Λ(xαk)xαk ≥ 0 e, passando al limite, T x − λx ≥ 0. Segue che λ ≤ Λ(x).
Lemma 1.2. Sia T : P → P continuo, omogeneo su P e strettamente monotono su P0.
Posto
ρ := sup {Λ(x) : x ∈ P \ {0}} , esiste u ∈ P \ {0} tale che Λ(u) = ρ e 0 < ρ < ∞.
Dimostrazione. Sia K = ( x ∈ P \ {0} : n X i=1 xi= 1 ) . Poiché T è omogeneo ρ = sup {Λ(x) : x ∈ K} ,
ed essendo K compatto e Λ semicontinua superiormente, il suo sup è raggiunto in un punto u ∈ K ⊂ P \ {0}. Proviamo infine che ρ > 0. Sia x > 0. Per ipotesi esiste m > 0 tale che Tmx = T (Tm−1x) > 0 pertanto, per λ > 0 abbastanza piccolo, T (Tm−1x) > λ(Tm−1x). Segue che ρ ≥ Λ(Tm−1x) > 0.
Proviamo ora il seguente teorema:
Teorema 1.6. Sia T : P → P continuo, omogeneo su P e strettamente monotono su P0. Se esiste u > 0 tale che ρ = Λ(u) allora:
• ρ è autovalore di T ed u è un autovettore ad esso corrispondente; • u è l’unico autovettore strettamente positivo di T .
Dimostrazione. Sia u > 0 tale che ρ = Λ(u). Si ha che T u ≥ ρu.
Supponiamo per assurdo che la disuguaglianza sia stretta. Per la stretta monotonia di T esisterebbe m > 0 tale che
Tm(T u) > Tm(ρu), ovvero
T (Tmu) > ρTmu e per ε > 0 abbastanza piccolo si avrebbe
T (Tmu) ≥ (ρ + ε)(Tmu).
Ma allora Λ(Tmu) > ρ, il che è assurdo e pertanto T u = ρu. Veniamo ora all’unicità. Supponiamo che esista v > 0 - che non sia un multiplo di u - tale che T v = σv. Esistono α = maxi ui vi , β = mini ui vi > 0 tali che βv < u < αv
e tali che per qualche j, βvj = uj e per qualche i, αvi = ui. Per la forte monotonia di T
esistono interi p, q > 0 tali che
σq(βvj) = Tq(βv) < Tqu = ρquj ⇒ σ < ρ,
σp(αvi) = Tp(αu) > Tpu = ρpui⇒ ρ < σ,
assurdo. Segue che v è un multiplo scalare di u e ciò conclude la dimostrazione.
Alla luce di questo teorema torniamo a considerare l’operatore di Menon. Il risultato principale che vorremo provare è che per matrici irriducibili con diagonale positiva esso ha 1 come autovalore. Premettiamo alcuni lemmi.
Lemma 1.3. Sia A ≥ 0 una matrice n × n irriducibile con diagonale principale positi-va. Sia T l’operatore di Menon ad essa associato ed Λ definito come sopra. Valgono le seguenti:
• Λ(x) ≤ 1 ∀x ∈ P0;
• Λ(x) ≤ n−1n ∀x ∈ P \ P0, x 6= 0
Dimostrazione. Dato x > 0 definiamo y = Sx, z = T x e le corrispondenti matrici diagonali X = D(x), Y = D(y), Z = D(z) dove D(·) è l’operatore definito all’inizio di questo capitolo. Osserviamo che per ogni i = 1, . . . , n
e dunque Y AX è stocastica per righe. Pertanto n = n X i,j=1 yiaijxj.
Analogamente per ogni i = 1, . . . , n
(ZATY e)i = (ZATy)i = zi(ATSx)i = (ATSx)−1i (ATSx)i = 1
e dunque ZAY è stocastica per colonne. Pertanto
n = n X i,j yiaijzj, ma allora n ≥ n X i,j yiaijxjΛ(x) = nΛ(x), da cui Λ(x) ≤ 1.
Per provare la seconda asserzione consideriamo x ∈ P \ P0, x 6= 0 e supponiamo, a meno di permutazioni simultanee selle righe e delle colonne di A, che sia xi = 0 per i = 1, . . . , r ed xi > 0 per i = r + 1, . . . , n. Poiché A è irriducibile esistono i, j con
1 ≤ i ≤ r e r + 1 ≤ j ≤ n tali che aij > 0. A meno di permutare nuovamente (e
simultaneamente) le prime r righe e colonne di A possiamo supporre che A sia della forma A11 A12 0 A21 A22 A23 A31 A32 A33
dove A11è q×q, A22è (r−q)×(r−q), 0 ≤ q < r indica il numero di righe di A con le ultime (n−r) componenti nulle e - questa la ragione dell’ultima permutazione effettuata - nessuna riga di A23 è identicamente nulla. Osserviamo infine che le permutazioni simultanee
conservano la stretta positività della diagonale principale e pertanto anche A33 non può possedere righe interamente nulle.
Una volta permutata A in questa forma poniamo y = Sx e osserviamo che yi < ∞ per i = q + 1, . . . , n. Infatti, per quanto detto sulle righe di A23 ed A33, ogni componente
(Ax)i per i > q sarà strettamente positiva.
Sia ora (xα)α∈N ⊂ P0 una successione tale che xα → x e poniamo yα = Sxα.
Analogamente a quanto visto nella prima parte della dimostrazione si ha
n − q = n X i=q+1 n X j=1 yαiaijxαj
e passando al limite sfruttando la continuità di S otteniamo n − q = n X i=q+1 n X j=1 yiaijxj.
Tuttavia poiché xj = 0 per j = 1, . . . , r e, per quanto detto poc’anzi, yi < ∞ per
i = q + 1, . . . , n alcuni termini della somma precedente sono nulli e possiamo semplificarla ottenendo n − q = n X i=q+1 n X j=r+1 yiaijxj. (1.7)
Sia ora z = T x. Avendo mostrato che T mappa P in sé si ha che zi < ∞ per i = 1, . . . , n.
Posto zα = T xα analogamente alla prima parte della dimostrazione otteniamo n − r = n X i=1 n X j=r+1 yiαaijzjα (1.8) e per la continuità di S e T n − r = n X i=1 n X j=r+1 yiaijzj. Combinando (1.7) e (1.8) si ha: n − r = n X i=1 n X j=r+1 yiaijzj ≥ n X i=1 n X j=r+1 yiaijxjΛ(x) = Λ(x)(n − q)
dove abbiamo utilizzato la disuguaglianza zi≥ Λ(x)xi. Segue
Λ(x) ≤ n − r n − q ≤ n − r n − r + 1 = 1 − 1 n − r + 1 ≤ 1 − 1 n = n − 1 n , ovvero la tesi.
Lemma 1.4. Sia A ≥ 0 una matrice n × n irriducibile con diagonale principale positiva. Siano T e Λ definiti come al solito. Se Λ realizza il suo sup ρ in un punto v > 0 allora ρ = 1 e v è l’unico autovettore di T strettamente positivo.
Dimostrazione. Alla luce del Teorema 1.6 ci basta provare che ρ = 1. Sia y = Sv, z = T v e definiamo come in precedenza V = D(v), Y = D(y), Z = D(z). Abbiamo già mostrato che Y AV è stocastica per righe e, poiché T v = ρv, si ha che
è stocastica per colonne per quanto già visto. Segue che n X i,j=1 yiaijvj = n = ρ n X i,j=1 yiaijvj
e pertanto ρ = 1 come volevamo.
Vediamo ora, prima di enunciare il teorema fondamentale di questa sezione, un ultimo lemma che non richiede l’irriducibilità della matrice A. A noi interesserà soltanto il caso irriducibile, ma la dimostrazione del caso riducibile ci guiderà nel provare il caso di nostro interesse.
Lemma 1.5. Sia Sia A ≥ 0 una matrice n × n con diagonale positiva. Siano T e Λ definiti come di consueto. Allora
sup {Λ(x) : x ∈ P0} ≥ 1.
Dimostrazione. Procediamo per induzione sulla dimensione di A. Se n = 1 la tesi è ovvia essendo T x = a11(a11x)−1
−1
= x. Supponiamo vera la tesi per m < n e dimostriamo che vale nel caso di matrici n × n. Consideriamo, come accennato in precedenza, due casi. • La matrice A è riducibile. Per definizione possiamo supporre che, a meno di
permutazioni simultanee di righe e colonne, A sia della forma A1 0
A21 A2
con A1 matrice m × m e A2 matrice n − m × n − m. Siano ora T1, S1 e T2, S2
gli operatori soliti relativi alle sottomatrici A1 e A2 rispettivamente ed in maniera analoga definiamo le corrispondenti funzioni Λ1 e Λ2.
Per ipotesi induttiva, fissato ε > 0 esistono elementi
x1= x11, . . . , x1m > 0 e x2 = x2m+1, . . . , x2n > 0
tali che Λ1(x1) > 1 − ε2 e Λ2(x2) > 1 −2ε. Vogliamo trovare un elemento ˜x tale che
Λ(˜x) > 1 − ε.
Consideriamo allora per δ > 0 i vettori ˙x = (δx1, x2) e ¨x = (x1, δ−1x2) = δ−1x e˙
osserviamo che per omogeneità si ha Λ ( ˙x) = Λ (¨x).
Consideriamo poi i vettori ¯x = (0, x2) e ¯x = (x¯ 1, ∞) e osserviamo che ¯x è arbitraria-¯ mente vicino a ¨x e analogamente ¯x è arbitrariamente vicino a ˙x a patto di scegliere δ abbastanza piccolo.
∀η > 0 ∃ δ > 0 : |¯x − ˙x|∞< η.
Essendo T continuo su P∞ segue che T ¯x sarà arbitrariamente vicino a T ¨¯ x e T ¯x
sarà arbitrariamente vicino a T ˙x. In particolare:
∀ε > 0 ∃ δ > 0 : (T ¯x)¯ i− (T ¨x)i< ε 2x 1 i ∀i = 1, . . . , m e ∀ε > 0 ∃ δ > 0 : (T ¯x)i− (T ˙x)i > −ε 2x 2 i ∀i = m + 1, . . . , n.
Ci basta pertanto dimostrare che (T ¯x)¯ i x1i > 1 − ε 2, ∀i = 1, . . . , m (1.9) e che (T ¯x)i x2i > 1 − ε 2, ∀i = m + 1, . . . , n. (1.10) Così facendo, infatti, avremmo
(T ¨x)i x1i = (T ¨x)i x1i − (T ¯x)¯ i x1i + (T ¯x)¯ i x1i > − ε 2+ 1 − ε 2 = 1 − ε, ∀i = 1, . . . , m e (T ˙x)i x2 i = (T ˙x)i x2 i −(T ¯x)i x2 i +(T ¯x)i x2 i > −ε 2+ 1 − ε 2 = 1 − ε, ∀i = m + 1, . . . , n. La (1.9) segue dal fatto che
T ¯x = (T¯ 1x1, ∞)
e per ipotesi induttiva
T1x1 ≥ Λ1(x1)x1 > 1 −ε 2 x1. Analogamente per provare la (1.10) calcoliamo
T ¯x = (0, T2x2)
e sfruttiamo l’ipotesi induttiva per ottenere
T2x2 ≥ Λ2(x2)x2 > 1 −ε 2 x2.
• La matrice A è irriducibile. Per il lemma precedente, che richiedeva l’ipotesi di irriducibilità, è sufficiente provare che il sup di Λ su P \ {0} è raggiunto in un punto
˙
x ∈ P0. Sia x ∈ P. Se mostriamo che esiste ˙x ∈ P0 tale che Λ( ˙x) ≥ Λx abbiamo
concluso. A meno di permutazioni simultanee di righe e colonne di A possiamo supporre xi = 0 per i = 1, . . . , m e xi > 0 per i = m + 1, . . . , n, chiamando per
comodità x2 = (xm+1, . . . , xn) > 0. Possiamo dunque partizionare A nel seguente
modo
A1 A12
A21 A2
similmente a quanto fatto nel caso riducibile, con la differenza che qui A12 non è
identicamente nulla.
Sia 0 < ε < n1. Con la notazione usata nel caso precedente si ha che per ipotesi induttiva esiste x1= (x11, . . . , x1m) > 0 tale che
Λ1(x1) > 1 − ε.
Sia ora δ > 0 e sia ˙x = (δx1, x2). Per la monotonia di T si ha T ˙x ≥ T x da cui (T ˙x)i ˙ xi ≥ (T x)i xi ≥ Λ(x) ∀i = m + 1, . . . , n. (1.11)
Quanto alle componenti 1 ≤ i ≤ m mostreremo che per δ sufficientemente piccolo vale anche
(T ˙x)i ˙ xi
> Λ(x) ∀i = 1, . . . , m. (1.12) Per il Lemma 1.3 sappiamo che Λ(x) ≤ 1 −n1, e avendo scelto ε < n1 ci basta provare che
(T ˙x)i ˙ xi
> 1 − ε ∀i = 1, . . . , m.
Con lo stesso argomento del caso precedente ci riduciamo a provare che (T ¯x)¯ i
x1i > 1 − ε, ∀i = 1, . . . , m dove, al solito, ¯x = (x¯ 1, ∞).
In questo caso notiamo che S ¯x = (y¯ 1, 0) con y1≤ S
1x1. Il fatto che il secondo blocco
sia identicamente nullo è dovuto al fatto che A2 non può avere righe interamente
nulle poiché si è supposta la stretta positività della diagonale principale di A. Segue allora che T ¯x = (z¯ 1, z2) con z1≥ T
1x1. Pertanto (T ¯x)¯ i x1 i ≥ T1x 1 i x1 i > 1 − ε ∀i = 1, . . . , m.
La (1.12) e la (1.11) ci dicono che ˙x è tale che Λ( ˙x) ≥ Λ(x) e dunque la tesi.
Veniamo ora al risultato principale di questa sezione.
Teorema 1.7 (Teorema di Perron-Frobenius non lineare). Sia A ≥ 0 una matrice n × n irriducibile con diagonale positiva. Sia T l’operatore di Menon associato ad A. Allora 1 è autovalore di T . Inoltre, su P, esiste un unico autovettore u ad esso relativo e si ha u > 0.
Dimostrazione. Siano al solito Λ e ρ definiti nel corso di questa sezione. Dal Lemma 1.2 otteniamo che esiste u ∈ P \ {0} tale che ρ = Λ(u). Dal Lemma 1.5 si ha che ρ ≥ 1 e se u avesse una componente nulla, per il Lemma 1.3 si avrebbe
Λ(u) ≤ n − 1 n < 1,
assurdo. Pertanto u > 0. Ma allora, per il Lemma 1.4, ρ = 1 ed u è l’unico autovettore di T in P0. Se esistesse un autovettore x di T in P \ P0, sempre per il Lemma 1.5, si
avrebbe necessariamente T x 6= x e pertanto non sarebbe relativo all’autovalore 1. Questo conclude la dimostrazione.
1.3
Teoremi di Sinkhorn-Knopp
Prima di dimostrare finalmente il Teorema 1.2 vediamo un risultato intermedio, una condizione sufficiente per l’esistenza di uno scaling doppiamente stocastico che sostan-zialmente è un’immediata generalizzazione del Teorema 1.1.
Teorema 1.8. Sia A una matrice n × n. Se A è completamente indecomponibile allo-ra esistono matrici diagonali positive D1, D2 tali che D1AD2 è doppiamente stocastica.
Inoltre D1, D2 sono uniche a meno di un fattore moltiplicativo.
Dimostrazione. Avendo mostrato (Proposizione 1.1) che una matrice completamente in-decomponibile è sostanzialmente equivalente ad una matrice irriducibile con diagonale po-sitiva, è sufficiente provare la tesi per una matrice siffatta. Sia x > 0 e siano D1 = D(Sx)
e D2 = D(x). Per quanto già visto, D1AD2 è doppiamente stocastica se e solo se T x = x,
dove T è l’operatore di Menon associato ad A. La tesi segue dal Teorema 1.7 osservando, per quanto riguarda l’unicità, che le matrici di scaling devono necessariamente avere la forma appena descritta, infatti
Diamo infine dimostrazione del Teorema 1.2 che generalizza il risultato precedente in-debolendo leggermente l’ipotesi di indecomponibilità. Alla luce del Teorema 1.5 possiamo sostituire la condizione - per A - di avere supporto totale con quella di essere (a meno di permutazioni) somma diretta di matrici completamente indecomponibili.
Dimostrazione. Siano P, Q tali che P AQ = Lk
i=1A(i), con tutte le A(i)
completamen-te indecomponibili. Dal teorema precedente sappiamo che esistono D(1)1 , . . . , D1(k) e D2(1), . . . , D(k)2 diagonali positive tali che D(i)1 A(i)D(i)2 è doppiamente stocastica.
Se consideriamo le somme dirette D1 =Lki=1D(i)1 e D2 =Lki=1D2(i) si vede facilmente
che anche D1P AQD2 è doppiamente stocastica. Ponendo
D01 = PTD1P e D20 = QTD2Q
otteniamo che
D01AD02e = PT D1P AQTD2 Qe = PT D1P AQTD2 e = PTe = e.
D10 e D02 sono le matrici di scaling cercate.
Viceversa supponiamo che esistano D1, D2 diagonali positive tali che S = D1AD2 sia
doppiamente stocastica. Per il ragionamento fatto alla fine del punto precedente possiamo supporre che, a seguito di una permutazione arbitraria delle righe e delle colonne di A, risulti S = S1 0 . . . 0 S21 S2 . . . 0 .. . ... . .. ... Sk1 Sk2 . . . Sk
dove ogni blocco diagonale è completamente indecomponibile (se S non è essa stessa completamente indecomponibile, la si può assumere partizionata nel modo solito e si procede per induzione sui blocchi diagonali). Con un ragionamento analogo a quello fatto nella dimostrazione del Teorema 1.5, essendo S doppiamente stocastica, detta r1 la dimensione di S1, si ha che la la somma dei suoi elementi, se calcolata per righe, risulta
uguale a r1, se calcolata per colonne risulta minore o uguale a r1. Segue che tutti i
blocchi S21, . . . , Sk1 devono essere nulli. Ragionando allo stesso modo sui restanti blocchi
diagonali otteniamo una scrittura di S della forma
S =
k
M
i=1
Si
con ciascuna Si completamente indecomponibile. È facile adesso risalire ad una scrittura analoga per A.
Algoritmo di Sinkhorn Knopp
Lo scopo di questo capitolo è duplice. Da un lato daremo prova della convergenza dell’algoritmo di Sinkhorn-Knopp già introdotto nel primo capitolo: le peculiarità della mappa di iterazione che descrive tale algoritmo ci suggerisce di introdurre una metrica rispetto alla quale essa risulti una contrazione. Dall’altro studieremo più da vicino l’al-goritmo per dare risultati sulla velocità di convergenza in particolare nel caso di matrici completamente indecomponibili.
2.1
Metrica proiettiva di Hilbert
Definizione 2.1 (Cono). Sia X uno spazio di Banach reale. Un sottoinsieme K ⊆ X si dice cono convesso positivo se:
• x, y ∈ K ⇒ x + y ∈ K. • x ∈ K, 0 ≤ λ ∈ R ⇒ λx ∈ K, • x ∈ K, −x ∈ K ⇒ x = 0.
D’ora in avanti, per cono intenderemo implicitamente un cono convesso positivo. Un cono K ⊆ X induce in modo naturale una relazione d’ordine parziale (≤K) su X
nel modo seguente:
x ≤K y ⇔ y − x ∈ K,
x <K y ⇔ y − x ∈ Int K.
Per non appesantire la notazione ometteremo il pedice e scriveremo semplicemente ≤ invece che ≤K fintanto che non ci saranno ambiguità.
Esempio 2.1. L’insieme dei vettori ad entrate reali non negative P = {x ∈ Rn: x ≥ 0}
già incontrato nel primo capitolo, è un esempio di cono sullo spazio Rn. L’ordine indotto da P secondo la definizione data poc’anzi coincide con quello che abbiamo utilizzato in precedenza. In particolare si ha x y ⇔ 0 6= y − x ∈ K.
Osservazione 2.1. Se richiediamo che il cono sia anche chiuso in X l’ordine da esso indotto risulta archimedeo, ovvero se nx ≤ y ∀n ∈ N allora x ≤ 0.
Diremo che due elementi x, y ∈ K sono confrontabili (e scriveremo x ∼K y) se esistono α, β > 0 tali che
αx ≤ y ≤ βx.
La relazione ∼K di confrontabilità è una relazione di equivalenza. Essa induce un parti-zionamento di K in insiemi disgiunti che chiameremo componenti. Nel caso semplice in cui K ⊂ R2 è il cono dei vettori non negativi, le componenti di K sono C0 = {0}, C1 =
{(x1, 0) : x1> 0}, C2 = {(0, x2) : x2> 0}, C3 = Int C. In generale si può mostrare che se
K è un cono chiuso con parte interna non vuota, Int K è sempre una componente di K. Inoltre, nel caso finito dimensionale, le componenti di K corrispondono agli interni relati-vi delle sue facce: ricordiamo che una faccia F di un insieme convesso C è un sottoinsieme di C tale che se αx + (1 − α)y ∈ F per qualche α ∈ (0, 1), x, y ∈ C allora x, y ∈ F , men-tre l’interno relativo di F è la sua parte interna come sottoinsieme del suo supporto affine.
Particolare interesse rivestono le mappe su un cono che ne preservano l’ordine. Definizione 2.2. Sia K un cono. Un’applicazione f : K → K è detta monotóna (cfr. Definizione 1.6) se per ogni x, y ∈ K con x ≤ y vale f (x) ≤ f (y).
Incontreremo anche mappe che invertono l’ordine.
Definizione 2.3. Sia K un cono. Un’applicazione f : K → K è detta antitóna se per ogni x, y ∈ K con x ≤ y vale f (x) ≥ f (y).
Definizione 2.4 (Metrica proiettiva di Hilbert). Sia K ⊆ X un cono. Dati x, y ∈ K \{0} confrontabili consideriamo le quantità:
M (x/y) = inf{λ ∈ R : x ≤ λy}, m(x/y) = sup{µ ∈ R : µy ≤ x}. La funzione
dH(x, y) = log
M (x/y) m(x/y)
è detta metrica proiettiva di Hilbert. Se x, y sono elementi di K \ {0} non confrontabili definiamo dH(x, y) = ∞.
Osservazione 2.2. Se K è chiuso gli estremi inferiori e superiori della Definizione 2.4 sono sempre raggiunti. In particolare m(x/y) è sempre un numero finito.
Lemma 2.1. La metrica proiettiva di Hilbert appena definita soddisfa le seguenti pro-prietà: (i) dH(x, y) ≥ 0 ∀x, y ∈ K; (ii) dH(x, y) = dH(y, x) ∀x, y ∈ K; (iii) dH(x, y) ≤ dH(x, z) + dH(z, y) ∀x, y, z ∈ K; (iv) dH(x, y) = dH(λx, µy) ∀x, y ∈ K, ∀λ, µ > 0.
Se inoltre K è chiuso in X si ha dH(x, y) = 0 se e solo se x = λy per qualche λ > 0. Dimostrazione.
(i) Per ogni 0 < α < m(x/y) e 0 < M (x/y) < β si ha αy ≤K x ≤K βy.
Segue che y ≤K(β/α)y e dunque β/α ≥ 1. Prendendo gli estremi superiore e inferiore si ottiene M (x/y)/m(x/y) ≥ 1 e passando ai logaritmi si ottiene la tesi.
(ii) Segue osservando che per definizione vale M (y/x) = m(x/y)−1 e dunque dH(x, y) = log (M (x/y)M (y/x)) = dH(y, x)
(iii) Per provare la disuguaglianza triangolare osserviamo che per ogni 0 < α < m(x/y) e 0 < γ < m(y/z) si ha αy ≤K x e γz ≤K y e dunque αγz ≤K x. Pertanto vale
m(x/z) ≥ m(x/y)m(y/z). In modo analogo si vede che M (x/z) ≤ M (x/y)M (y/z). Possiamo allora scrivere
M (x/z) m(x/z) ≤
M (x/y)M (y/z) m(x/y)m(y/z) e si conclude passando ai logaritmi.
(iv) Si vede facilmente che valgono
M (λx/µy) = λ
µM (x/y), m(λx/µy) = λ
µm(x/y) e la tesi segue immediatamente.
Sia C 6= {0} una componente di K. La restrizione di dH a C è una pseudometrica.
Se definiamo Σ = {x ∈ C : kxk = 1}, la restrizione di dH a Σ è a tutti gli effetti una metrica.
D’ora in avanti useremo il simbolo Σ sottintendendo il riferimento ad una data compo-nente di K.
Introduciamo infine una variante della metrica proiettiva di Hilbert, dovuta a A.C. Thompson [18].
Definizione 2.5 (Metrica di Thompson). Sia K ⊆ X un cono, x, y ∈ K \ {0} confron-tabili. La funzione
dT(x, y) = max{log M (x/y), log M (y/x)}
è detta metrica di Thompson. Come sopra definiamo dT(x, y) = ∞ se x, y ∈ K \ {0} non sono confrontabili.
Osservazione 2.3. Dalla dimostrazione del Lemma 2.1 si vede facilmente che dT è una metrica su ogni componente di C diversa da {0}.
Vogliamo mostrare che, sotto opportune ipotesi, la convergenza rispetto alle metriche di Thompson e di Hilbert (quest’ultima ristretta a Σ) implica la convergenza rispetto alla norma usuale. Premettiamo alcuni lemmi.
Lemma 2.2. Sia K ⊂ X un cono in uno spazio di Banach e supponiamo che la norma di X sia monotona (rispetto a K), ovvero:
∀x, y ∈ K, x ≤K y ⇒ kxk ≤ kyk.
Allora se x ≤K λy, y ≤Kλx, kxk ≤ m, kyk ≤ m si ha:
kx − yk ≤ 3m|λ − 1|. (2.1) Dimostrazione. Si ha x − y ≤K (λ − 1)y e y − x ≤K (λ − 1)x, pertanto esistono z, z0 ∈ K
tali che
x − y + z = (λ − 1)y, y − x + z0 = (λ − 1)x. Allora possiamo scrivere
kzk ≤ kz + z0k = k(λ − 1)x + (λ − 1)yk ≤ 2m|λ − 1| e dunque
kx − yk = kx − y + z − zk ≤ kx − y + zk + kzk ≤ 3m|λ − 1|.
Lemma 2.3. Sia K ⊂ X un cono in uno spazio di Banach e supponiamo che la norma di X sia monotona (rispetto a K). Vale
1
2dH(x, y) ≤ dT(x, y) ≤ dH(x, y) ∀x, y ∈ Σ. (2.2) Dimostrazione. Siano
α = m(x/y), β = M (x/y); per quanto visto si ha
dH(x, y) = log β α , dT(x, y) = log max β, 1 α .
Dati x, y ∈ Σ vale αy ≤K x ≤K βy e passando alle norme: α ≤ 1 ≤ β. Pertanto, da un lato 1 ≤ α1 ≤ βα ⇒ 0 ≤ log 1 α ≤ log β α
1 ≤ β ≤ βα ⇒ 0 ≤ log (β) ≤ logαβ ⇒ dT(x, y) ≤ dH(x, y); dall’altro • se β ≤ 1 α ⇒ β α ≤ 1 α2 ⇒ log β α ≤ 2 log 1 α • se 1α ≤ β ⇒ βα ≤ β2⇒ logβ α ≤ 2 log (β) e dunque in ogni caso vale
log β α ≤ 2 log max β,1 α ⇒ 1 2dH(x, y) ≤ dT(x, y).
Proposizione 2.1. Sia K ⊂ X un cono chiuso in uno spazio di Banach e supponiamo che la norma di X sia monotona (rispetto a K). Se x, y ∈ K e kxk ≤ m, kyk ≤ m allora kx − yk ≤ 3m[exp(dT(x, y)) − 1]; (2.3) se x, y ∈ Σ allora
kx − yk ≤ 3[exp(dH(x, y)) − 1]. (2.4) Dimostrazione. La prima disuguaglianza segue subito dalla (2.1) osservando che per de-finizione x ≤K [exp(dT(x, y))]y e y ≤K [exp(dT(x, y))]x. La seconda disuguaglianza
discende direttamente dalla prima tenendo presente la (2.2).
Vale anche una sorta di viceversa.
Proposizione 2.2. Sia K ⊂ X un cono in uno spazio di Banach. Supponiamo che Int K 6= ∅ e siano u ∈ Int K ed r > 0 tale che B(u, r) = {x : kx − uk < r} ⊂ K. Si ha:
dH(x, u) ≤ log
r + ku − xk r − ku − xk
∀x ∈ B(u, r).
Dimostrazione. Sia x ∈ B(u, r), x 6= u. Per ipotesi si ha che u ± w ∈ K se kwk ≤ r. Prendendo 0 < α < 1 tale che
α 1 − α
si ha che u − αx = (1 − α) u + α 1 − α (u − x) ∈ K; (2.6)
analogamente prendendo 0 < β < 1 tale che β β − 1 ku − xk = r (2.7) si ha che βx − u = (β − 1) u − β β − 1 (u − x) ∈ K (2.8)
Risolvendo la (2.5) e la (2.7) rispettivamente rispetto ad α e β e sfruttando le relazioni (2.6) e (2.8) otteniamo:
α = r
r + ku − xk ≤ m(u/x), β =
r
r − ku − xk ≥ M (u/x).
Si ha allora dH(x, u) ≤ logβαovvero la tesi.
Veniamo ora alle proprietà di completezza rispetto alle due metriche introdotte. Teorema 2.1. Sia K ⊆ X un cono in uno spazio di Banach reale e sia C una componente di K. Allora (C, dT) è uno spazio metrico completo.
Dimostrazione. Sia {xn} una successione di Cauchy in C rispetto a dT e definiamo αmn=
M (xn/xm). Dividiamo ora la dimostrazione in tre punti.
• La successione {xn} è limitata in norma. Essendo {xn} di Cauchy, esiste N tale che dT(xn, xm) < 1 per ogni n, m ≥ N , ovvero max{αmn, αnm} < e per ogni
n, m ≥ N . In particolare αnN < e per ogni n ≥ N e dunque xn≤K exN ≤K 3xN.
Per la monotonia della norma segue che kxnk ≤ 3kxNk e dunque la successione {kxnk} è limitata da R dove
R = max{kx1k, . . . , kxNk, 3kxNk}.
• La successione {xn} è di Cauchy in norma. Per ogni ε > 0 esiste δ tale che eδ ≤ 1 + ε
3R. Poiché {xn} è di Cauchy esiste un indice Nε tale che dT(xn, xm) ≤ δ
per ogni m, n ≥ Nε e dunque max{αmn, αnm} < 1 + 3Rε . In particolare xn ≤K
1 +3Rε xm e xm≤K 1 +3Rε xn e per il Lemma 2.2 kxn− xmk ≤ 3R 1 + ε 3R− 1 = ε ∀n, m ≥ Nε.
• La successione {xn} converge rispetto a dT a un elemento di C. Essendo
K un chiuso in un Banach è completo rispetto alla norma di X: segue che esiste un elemento u ∈ K tale che limn→∞kxn− uk = 0. Fissato ε > 0 si ha dT(xn, xm) ≤ ε
per m, n sufficientemente grandi e quindi ancora una volta xn ≤K eεxm e xm ≤K
eεxn sempre per m, n sufficientemente grandi.
Ma limm→∞kxm− uk = 0 ed essendo K chiuso segue che
xn≤K eεu, u ≤Keεxn (2.9)
per n sufficientemente grande. Osserviamo ora che dalla (2.9) segue che (sempre per n abbastanza grande) u ∈ C (essendo u ∼K xn) e che dT(xn, u) < ε. Per
l’arbitrarietà di ε ciò equivale a dire che {xn} converge a u rispetto a dT.
Teorema 2.2. Sia K ⊆ X un cono chiuso in uno spazio di Banach reale e sia C una componente di K, u ∈ C e sia Σ = {x ∈ C : kxk = 1}. Se la norma di X è monotona rispetto a K allora (Σ, dH) è uno spazio metrico completo.
Dimostrazione. Sia {xn} una successione di Cauchy in Σ rispetto a dH. Dalla (2.2)
segue che {xn} è di Cauchy rispetto a dT e per il Teorema 2.1 esiste y ∈ C tale che
dT(xn, y) → 0. Ancora dalla (2.2) deduciamo che vale dH(xn, y) → 0, pertanto ci resta
da mostrare che y ∈ Σ. Dalla Proposizione 2.1 si ha che kxn− yk → 0 e dunque possiamo
scrivere:
kyk = ky − xn+ xnk ≤ ky − xnk + kxnk = ky − xnk + 1 ⇒ kyk ≤ 1,
1 = kxnk = kxn− y + yk ≤ kxn− yk + kyk ⇒ kyk ≥ 1.
Combinando le ultime due disuguaglianze si ottiene la tesi.
Una prima motivazione all’introduzione della metrica proiettiva di Hilbert è data dalla seguente proposizione (ed in particolare dai due corollari che seguono).
Proposizione 2.3. Sia K ⊂ X un cono in uno spazio di Banach e sia f : K → K monotona e omogenea di grado r > 0. Allora valgono le seguenti:
M (f (x)/f (y)) ≤ M (x/y)r, m(x/y)r≤ m(f (x)/f (y)) ∀x, y ∈ K, x ∼K y.
Viceversa se f : K → K è antitona e omogenea di grado r < 0 vale: M (f (y)/f (x)) ≤ M (x/y)r, m(x/y)r≤ m(f (y)/f (x)) ∀x, y ∈ K, x ∼K y
Dimostrazione. Consideriamo il caso in cui f sia monotona e omogenea di grado positivo. Se x, y ∈ K con x ∼K y allora per ogni β > 0 tale che x ≤ βy si ha f (x) ≤ f (βy) = βrf (y). Pertanto M (f (x)/f (y)) ≤ βr per ogni β > M (x/y). Segue che M (f (x)/f (y)) ≤ M (x/y)r. La dimostrazione della seconda disuguaglianza è analoga.
Il caso speculare in cui f è antitona e omogenea di grado negativo segue ragionando allo stesso modo, osservando preliminarmente che se x ≤ βy si ha f (y) ≤ βrf (x).
Corollario 2.1. Sia K ⊂ X un cono in uno spazio di Banach e sia f : K → K monotona e omogenea di grado 1. Allora f è non espansiva rispetto a dH su ciascuna componente di K, ovvero:
dH(f (x), f (y)) ≤ dH(x, y) ∀x ∼Ky.
Dimostrazione. Segue immediatamente dalla Proposizione 2.3, dalla definizione della metrica dH e dalla monotonia del logaritmo.
Corollario 2.2. Sia K ⊂ X un cono in uno spazio di Banach e sia f : K → K monotona e omogenea di grado −1. Allora f è non espansiva rispetto a dH su ciascuna componente
di K.
Dimostrazione. Segue come sopra osservando che
dH(f (x), f (y)) = log M (x/y) m(x/y) = log M (y/x) m(y/x) = dH(f (y), f (x)).
Osservazione 2.4. Gli ultimi due corollari continuano a valere se al posto della metrica proiettiva dH consideriamo la metrica dT. La dimostrazione è ancora una volta una diretta applicazione della Proposizione 2.3.
Per il risultato principale che ci proponiamo di dimostrare in questa sezione sono essenziali le seguenti definizioni ed il successivo teorema che le mette in relazione. Definizione 2.6 (Diametro proiettivo). Sia K un cono in uno spazio di Banach X e sia L : X → X un’applicazione lineare tale che L(K) ⊆ K. Il diametro proiettivo di L (rispetto alla metrica dH) è definito come:
∆(L) = sup{dH(Lx, Ly) : x, y ∈ Int K}. (2.10)
Definizione 2.7 (Coefficiente di contrazione). Sia K un cono in uno spazio di Banach X e sia L : X → X un’applicazione lineare tale che L(K) ⊆ K. Il coefficiente di contrazione di L (rispetto alla metrica dH) è definito come:
Entrambe le quantità appena definite danno una misura dell’espansività di L e sono legate dal seguente risultato dovuto a Birkhoff.
Teorema 2.3 (Birkhoff). Sia K un cono chiuso in uno spazio di Banach X e sia L : X → X un’applicazione lineare tale che L(K) ⊆ K. Vale:
κ(L) = tanh 1 4∆(L)
.
Dimostrazione. La dimostrazione di questo teorema è elementare, benché piuttosto tec-nica e ne daremo soltanto uno schema. Dati x, y ∈ k con x ∼ky definiamo l’oscillazione di x su y come
osc(x/y) = M (x/y) − m(x/y)
e osserviamo che, per l’Osservazione 2.2 si ha sempre 0 < osc(x/y) < +∞. Questo non è essenziale ma snellisce la dimostrazione.
Definiamo inoltre il coefficiente di oscillazione di L:
N (L) = inf{λ : osc(Lx/Ly) ≤ λ osc(x/y) ∀x, y ∈ Int K}.
Ostrowski in [11] ha provato che N (L) ≤ κ(L); la disuguaglianza opposta è stata provata da Bushell in [4]. Pertanto è sufficiente provare che vale
N (L) = tanh 1 4∆(L)
.
Bauer in [2] ha mostrato che dalle proprietà di M (x/y) e m(x/y) segue facilmente che: osc(Lx/Ly) = osc(x/y) · ϕ(Ly1, Ly2)
dove si è posto
y1= x − m(x/y)y, y2= M (x/y)y − x
e
ϕ(u, v) = M (u/v)M (v/u) − 1 [M (u/v) + 1][M (v/u) + 1]. Si ha
ϕ(Lu, Lv) = M (Lu/Lv)M (Lv/Lu) − 1
M (Lu/Lv)M (Lv/Lu) + M (Lu/Lv) + M (Lv/Lu) + 1 ≤ M (Lu/Lv)M (Lv/Lu) − 1 [(M (Lu/Lv)M (Lv/Lu))12 + 1]2 = ϑ 1 2(Lu, Lv) − 1 ϑ12(Lu, Lv) + 1 (2.11)
dove si è usata la disuguaglianza tra media aritmetica e media geometrica e si è posto ϑ(x/y) = M (u/v)M (v/u). Osserviamo che per ogni α > 0 vale ϕ(αu, v) = ϕ(u, v) e che essendo
M (L(αu)/Lv) = αM (Lu/Lv), M (Lv, L(αu)) = 1
esiste ¯α tale che M (L( ¯αu)/Lv) = M (Lv, L( ¯αu)). Segue che la disuguaglianza (2.11) è in realtà un’uguaglianza e si ottiene
N (L) = supϑ 1 2(Lu, Lv) − 1 ϑ12(Lu, Lv) + 1 = ϑ 1 2(L) − 1 ϑ12(L) + 1 , (2.12)
dove ϑ(L) = sup ϑ(Lu, Lv). Per concludere notiamo che vale
ϑ(u, v) = exp(dH(u, v))
e dunque
ϑ(L) = exp(∆(L)). (2.13) Finalmente dalla (2.12) e dalla (2.13) segue
N (L) = exp( 1 2∆(L)) − 1 exp(12∆(L)) + 1 = tanh 1 4∆(L) .
2.2
Studio della convergenza
Abbiamo ora gli strumenti per studiare la convergenza dell’algoritmo di Sinkhorn-Knopp. Studieremo un caso leggermente più generale che si riconduce facilmente al nostro scopo.
Introduciamo un po’ di notazione che utilizzeremo nei prossimi enunciati. Qi, 1 ≤ i ≤ p
denoterà uno spazio di Haudorff compatto, Xi = C(Qi) lo spazio (di Banach) delle
funzioni continue a valori reali su Qied infine Ki⊆ Xi il cono delle funzioni non negative in Xi. Per semplicità supporremo che la norma di Xi sia monotona rispetto all’ordine
indotto da Ki. Diamo inoltre le seguenti definizioni. Introduciamo la mappa
Ui : Int Ki −→ Int Ki (2.14)
x(t) 7−→ x(t)−1 (2.15) nel modo seguente:
(Uix)(t) = x(t)−1=
1 x(t).
Notiamo che, essendo definita sulla parte interna di Ki, l’applicazione Ui risulta ben definita. Con ei∈ Xi indicheremo la funzione
che vale costantemente 1 sullo spazio Qi. Infine per ogni funzione fissata x ∈ Xi
introduciamo la mappa (lineare continua) di moltiplicazione Mx: Xi→ Xi
che agisce nel modo ovvio:
(Mx(y))(t) = x(t)y(t).
Ci chiediamo adesso se, fissati degli operatori lineari continui L : Xi → Xi+1, 1 ≤ i ≤ p
tali che Li(Int(Xi) ⊂ Int(Xi+1) con Xp+1 = X1 e Kp+1 = K1 esistano funzioni xi ∈
Int Ki, 1 ≤ i ≤ p e 0 < λ ∈ R tali che:
(Mxi+1LiMxi)(ei) = ei+1per 1 ≤ i < p; (2.16)
(Mx1LpMxp)(ep) = λe1. (2.17)
Il lemma seguente ci fornisce condizioni in tal senso. La notazione è quella appena introdotta.
Lemma 2.4. Definiamo le mappe gi : Int Ki → Int Ki+1, gi = Ui+1Li per 1 ≤ i ≤ p ed
f : Int K1 → Int K1, f = gpgp−1· · · g1 dove si è posto Up+1= U1 e Kp+1= K1. Esistono
xi, 1 ≤ i ≤ p e λ > 0 che soddisfano le equazioni (2.16) e (2.17) se e solo se f ha un
autovettore in Int K1 con relativo autovalore λ−1.
Dimostrazione. Siano xi e λ che soddisfano le equazioni (2.16) e (2.17). Dalla generica equazione (per 1 ≤ i < p)
(Mxi+1LiMxi)(ei) = ei+1,
applicando ad ambo i membri l’operatore Ui+1 e risolvendo rispetto a xi+1si ottiene xi+1= Ui+1Li(xi),
ovvero
xi+1= gi(xi) 1 ≤ i < p. (2.18)
Un ragionamento analogo permette di ottenere
λ−1x1 = gp(xp) (2.19)
e mettendo insieme le equazioni (2.18) e (2.19) si ha λ−1x1= f (x1),
ovvero x1 è un autovettore di f relativo all’autovalore λ−1. Viceversa supponiamo che f
abbia un autovalore µ > 0:
f (x) = µx
per qualche x ∈ Int K1. Ponendo x1 = x e xi+1 = gi(xi) per 1 ≤ i < p e λ = µ−1, le
Teorema 2.4. Supponiamo che Li : Xi → Xi siano operatori lineari continui per 1 ≤
i ≤ p e che Li(Int Ki) ⊂ Int Ki+1. Definiamo
∆(Li) = sup{di+1(Lix, Liy) : x, y ∈ Int Ki}
dove di è la metrica proiettiva di Hilbert su Int Ki. Supponiamo inoltre che esista j tale
che ∆(Lj) < ∞. Allora f ha un unico autovettore x1 ∈ Int K1 (a meno di multipli
scalari). Se x1 è scelto tale che kx1k = 1 allora per ogni z ∈ Int K1 si ha: lim
k→∞
fk(z)
kfk(z)k = x1. (2.20)
Dimostrazione. L’operatore Ui è antitono e omogeneo di grado −1, pertanto (per il
Corollario 2.2) si ha
di(Uix, Uiy) ≤ di(x, y) ∀x, y ∈ Int Ki. (2.21)
Analogamente l’operatore Li è monotono e omogeneo di grado 1, pertanto (per il Corol-lario 2.1) vale
di+1(Lix, Liy) ≤ di(x, y) ∀x, y ∈ Int Ki. (2.22)
Dall’ipotesi di limitatezza sul diametro dell’operatore Lj e dal Teorema di Birkhoff 2.3
deduciamo l’esistenza di una costante 0 ≤ C < 1 tale che
dj+1(Ljx, Ljy) ≤ Cdj(x, y) ∀x, y ∈ Int Kj. (2.23)
Combinando le disuguaglianze (2.21) - (2.23) otteniamo
d1(f (x), f (y)) ≤ Cd1(x, y) ∀x, y ∈ Int K1.
La mappa f risulta dunque una contrazione su Int K1 e vorremmo pertanto applicare il teorema del punto fisso di Banach. Tuttavia (K1, d1) non è a priori uno spazio metrico
completo (in realtà per quanto visto non è neppure uno spazio metrico). Abbiamo allora bisogno di un passo intermedio. Definiamo
Σ1 = {x ∈ Int K1 : kxk = 1}.
Dalla monotonia della norma sappiamo che (Σ1, d1) è uno spazio metrico completo e se
definiamo
g(z) = f (z) kf (z)k, la mappa g è tale che g(Int K1) ⊆ Σ1 e si ha:
d1(g(x), g(y)) ≤ Cd1(x, y) ∀x, y ∈ Int K1.
Segue, dal teorema delle contrazioni, che g ha un unico punto fisso x1 ∈ Σ1 e che per ogni
z ∈ Int K1 si ha:
lim
k→∞g
k(z) = x 1.
Resta da mostrare la convergenza delle iterate non normalizzate. Ciò è sempre vero nel caso in cui p sia pari (ricordiamo che p = 2 sarà il caso di nostro interesse). Descriviamo questo risultato nel seguente corollario.
Corollario 2.3. Nelle ipotesi del Teorema 2.4 supponiamo che p sia pari e f (x1) = x1.
Si ha che per ogni z ∈ Int K1 esiste 0 < λ(z) ∈ R tale che
lim
k→∞f
k(z) = λ(z)x 1.
Dimostrazione. Se p è pari f risulta essere monotona ed omogenea di grado 1. Dalla non espansività di f rispetto alla metrica dT (cfr. Osservazione 2.4) deduciamo che la successione βk = dT(fk(z), x1) è non crescente e non negativa. Ciò segue in particolare
dalla relazione f (x1) = x1. Pertanto βk ammette limite:
lim
k→∞βk= limk→∞dT(f k(z), x
1) = `. (2.24)
Se `=0 abbiamo concluso in quanto si ha fk(z) → x1 (ricordiamo che per la Proposizione
2.1 la convergenza rispetto a dT implica la convergenza in norma). Supponiamo dunque ` > 0. Dalla disuguaglianza triangolare si ha
dT fk(z), f k(z) kfk(z)k ≤ dT fk(z), x1 + dT x1, fk(z) kfk(z)k
e dunque dalla (2.20) e dalla (2.24) segue che:
lim k→∞dT fk(z), f k(z) kfk(z)k = `
D’altra parte per ogni v ∈ Int K, α > 0 vale
dT(v, αv) = | log(α)|. Segue che kfk(z)k −−−→ k→∞ m ∈ {e −` , e`}.
Possiamo supporre che per qualche sottosuccessione ki→ ∞ si abbia
lim
i→∞kf
ki(z)k = e` (2.25)
(altrimenti si avrebbe la convergenza a e−` e la dimostrazione sarebbe conclusa).
Vogliamo mostrare che se vale ciò la successione di partenza converge essa stessa a e`. A tal fine osserviamo che le relazioni (2.20) e (2.25) implicano che
lim
i→∞dT(f
ki(z), e`x
Essendo f (e`x1) = e`x1 ed essendo f non espansiva rispetto a dT segue che
dT(fq(z), e`u) ≤ dT(fki(z), e`x1) ∀q ≥ ki;
passando al limite su q (e su i) possiamo concludere che vale lim
q→∞f
q(z) = e`u.
Applichiamo ora i risultati appena descritti allo studio della convergenza dell’algorit-mo di Sinkhorn-Knopp.
• Innanzitutto è possibile vedere i vettori di Rncome funzioni (continue) sullo spazio
di Hausdorff compatto S = {1, 2, . . . , n} dotato della topologia discreta: x(t) = xt
al variare di t ∈ S.
• Gli operatori Mx inducono semplicemente i prodotti componente per componente: Mx(y) = (x1y1, x2y2, . . . , xnyn) ∀x, y ∈ Rn.
• Analogamente l’operatore U (definito sulla parte interna del cono P ⊂ Rn) agisce
invertendo ciascuna componente del vettore al quale è applicato: U (x) = x−11 , x−12 , . . . x−1n
∀x ∈ Rn
e, non a caso, la notazione coincide con quella usata nel Capitolo 1. • Infine il vettore e risulta essere il vettore con tutte le componenti unitarie.
Il problema di scaling si riduce pertanto alla risoluzione delle equazioni (2.16), (2.17) nel caso in cui p = 2, X1 = X2 = Rn, K1 = K2 = P e gli operatori lineari Li altro non sono
che la matrice A - che vorremmo rendere doppiamente stocastica - e la sua trasposta. In particolare nella nostra trattazione si ha L1 = A, L2 = AT. La funzione f , altro non è
che l’operatore T studiato nel primo capitolo e per il quale abbiamo mostrato l’esistenza si un punto fisso.
Osserviamo che il cono P ⊂ Rn gode di tutte le buone proprietà che sono alla ba-se dei risultati dimostrati fin ora. In particolare P risulta esba-sere un cono chiuso e la norma euclidea risulta essere monotona rispetto alla relazione d’ordine indotta da P. Inoltre, sia L : Rn → Rn sia un’applicazione lineare e sia A = (a
ij) la matrice ad essa
associatarispetto alla base canonica di Rn (e1, . . . , en). Supponiamo che A sia
L(Int P) = L(P0) ⊂ P0, ovvero Ax > 0 per ogni x ∈ P0. In particolare possiamo dare
una maggiorazione al diametro proiettivo di L nel modo seguente.
La metrica proiettiva di Hilbert su Rn ha una semplice espressione in funzione delle componenti: dH(u, v) = max i,j log uivj viuj dove u = (u1, . . . , un), v = (v1, . . . , vn) ∈ Rn.
Nel calcolo di ∆(L), per le proprietà proiettive di dH, possiamo ridurci a calcolare il sup nella formula (2.10) limitatamente ai vettori che abbiano norma 1 unitaria, ovvero gli x ∈ P0 tali che Pni=1xi = 1. Siano dunque u = Ax, v = Ay con x, y ∈ P0 e
kxk1 = kyk1 = 1. Si ha mi = mi n X h=1 xh≤ n X h=1 aihxh ≤ Mi n X h=1 xh= Mi ∀i = 1, . . . , n
dove Mi ed mi sono rispettivamente il massimo e il minimo degli elementi di A sulla riga
i-esima. Dunque ui =Pnh=1xh ed analogamente vi sono limitati. Pertanto abbiamo che:
∆(L) = sup{dH(Ax, Ay) : x, y ∈ P0, kxk1 = kyk1 = 1} ≤ max i,j log
MiMj
mimj
da cui segue che il diametro proiettivo di L è necessariamente finito.
Nel caso in cui A abbia supporto totale è possibile perturbare la matrice A per renderla strettamente positiva, applicare quanto visto sopra e mostrare (Teorema 7.2.5 in [8]) che al tendere del parametro perturbativo a 0 il punto fisso dell’operatore associato alla matrice perturbata tende al punto fisso dell’operatore associato alla matrice di partenza. L’esistenza di quest’ultimo, per matrici che hanno supporto totale, è stata provata nel Capitolo 1.
2.3
Velocità di convergenza
Al fine di studiare la velocità di convergenza dell’algoritmo di Sinkhorn-Knopp consi-dereremo in prima analisi il caso simmetrico. Se A è una matrice simmetrica le equazioni di scaling (1.4) assumono la forma
c = D(Ar)−1e, r = D(Ac)−1e. (2.26) Segue allora che possiamo supporre r = c e dunque sostanzialmente cercare un unico vettore x tale che:
Infatti, essendo i vettori di scaling unici a meno di moltiplicazione per costanti, si ha che se (r, c) ed (r0, c0) sono due coppie di vettori di scaling deve valere r = λr0 e c = λ1c0 per qualche λ > 0. Ma dalla simmetria delle equazioni (2.26) è ovvio che se la coppia (r, c) è una soluzione, allora anche la coppia (c, r) è una soluzione e deve esistere pertanto un λ > 0 tale che r = λc, c = 1 λr. Prendendo ¯r = ¯c = √r λ = c √
λ otteniamo otteniamo quanto voluto. Tenendo presente questa osservazione l’algoritmo di Sinkhorn-Knopp nel caso simmetrico assume la forma semplificata
xk+1= D(Axk)−1e (2.28)
o, in notazione funzionale
xk+1 = T xk (2.29)
dove T = U A (si veda la notazione adottata nella sezione 1.2). Come si evince dalla struttura della mappa di iterazione T , l’algoritmo di riscalamento applicato ad una ma-trice simmetrica risulta essere una sorta di variante dimezzata dell’algoritmo originario. Ciò è ancora più evidente se andiamo a considerare le iterate di ordine pari e di ordine dispari: un semplice confronto con l’iterazione intrecciata vista nel caso generale mostra che valgono le relazioni x2k = rk e x2k+1= ck+1. D’altra parte l’algoritmo di
Sinkhorn-Knopp per una matrice A - non necessariamente simmetrica - altro non è che l’iterazione (2.28) applicata alla matrice (simmetrica)
B = 0 A AT 0
.
Di fatti partendo da xk = [yk, zk]T ∈ R2n ed eseguendo un passo dell’iterazione (2.28)
otteniamo xk+1= yk+1 zk+1 = D Azk ATyk −1 e e = D(Azk) −1e D(ATy k)−1e e dunque yk+1= D(Azk)−1e = D(AD(ATyk−1)−1e)−1e (2.30)
zk+1 = D(ATyk)−1e = D(ATD(Azk−1)−1e)−1e. (2.31)
Osservando che dalle (1.5) si ottiene facilmente
ck= D(AD(ATck−1)−1e)−1e (2.32)
rk= D(ATD(Ark−1)−1e)−1e (2.33)
risulta chiaro che un passo dell’algoritmo di Sinkhorn-Knopp eseguito sulla matrice A equivale a due passi dell’algoritmo simmetrico (2.28) eseguito sulla matrice B.
Per essere ancora più espliciti osserviamo le prime 2k iterazioni ottenute dalla (2.28) con x0 = [e, e]T e e → ∗ c1 →r1 ∗ → ∗ c2 →r2 ∗ → ∗ c3 →r3 ∗ → · · · → ∗ ck →rk ∗ e con x0= [e, c1]T e c1 →r1 c1 →r1 c2 →r2 c2 →r2 c3 →r3 c3 →r3 c4 → · · · →rk ck → rk ck+1 .
È evidente che per ottenere la coppia (rk, ck) - che avremmo ottenuto dopo k passi
del-l’algoritmo di Sinkhorn-Knopp - necessitiamo di 2k passi della sua variante simmetrica applicata alla matrice B.
Abbiamo insistito su questo aspetto apparentemente tautologico in quanto ci sarà utile nello stabilire dei risultati sulla velocità di convergenza dell’algoritmo che stiamo studian-do. Considereremo infatti, come detto, il caso simmetrico e successivamente dedurremo un risultato analogo nel caso generale. Premettiamo alcuni lemmi.
Lemma 2.5. Sia A una matrice n × n simmetrica completamente indecomponibile e sia x∗ ∈ Rn l’unico vettore (a componenti strettamente positive) tale che P = D(x∗)AD(x∗)
sia doppiamente stocastica. Sia f (x) = D(Ax)−1e e sia J (x) la matrice Jacobiana di f . Si ha:
(i) J (x) = −D(Ax)−2A ∀x ∈ Rn, x > 0; (ii) J (αx∗) = α12D(x∗)P D(x∗)
−1
∀α ∈ R, α > 0.
Osservazione 2.5. Osserviamo preliminarmente che la funzione f definita nel lemma precedente altro non è che l’operatore T definito (nel caso simmetrico) dalla (2.29) e che il punto x∗ è ovviamente un punto fisso per T (e per f ).
Dimostrazione. (i) Si verifica osservando che
fi(x) = n X k=1 aikxk !−1 e dunque ∂fi ∂xj = −aij n X k=1 aikxk !−2 = − D(Ax)−2Aij
(ii) Essendo x∗ punto fisso per f vale D(Ax∗)−1e = x∗ e dunque D(Ax∗)x∗= e.
