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 essere 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 stret-
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.