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. Sfrut-
D(Ax∗) = D(x∗)−1 ed in generale D(A(αx∗)) = αD(x∗)−1.
Possiamo allora scrivere
J (αx∗) = −D (A(αx∗))−2A = − αD(x)−1 −2 A = − 1 α2D(x∗) 2A = − 1 α2D(x∗) [D(x∗)AD(x∗)] D(x∗) −1 = − 1 α2D(x∗)P D(x∗) −1
Abbiamo sottolineato in precedenza due aspetti: da un lato che l’algoritmo di Sinkhorn- Knopp (sotto le opportune ipotesi) converge in generale ad un multiplo scalare (positivo) del punto fisso della mappa di iterazione; dall’altro che nel caso simmetrico ci proponiamo di trovare un unico vettore x∗ che soddisfi la relazione di scaling (2.27). Quest’ultimo
aspetto merita una precisazione. In generale non possiamo aspettarci che la variante sim- metrica dell’algoritmo di Sinkhorn-Knopp converga a x∗, il che significa che non possiamo
aspettarci che le successioni ck e rk convergano allo stesso limite. Più ragionevolmente
accadrà che i due limiti saranno diversi ma proporzionali tra loro e che la successione fk(x) oscillerà tra questi due valori.
Tenendo conto di ciò, per valutare la velocità di convergenza dell’algoritmo, andremo a studiare soltanto una delle due sottosuccessioni convergenti (ck o rk) e dunque ci con- centreremo sugli effetti di due iterazioni di f alla volta (ovvero di f2), in particolare nei pressi di un opportuno multiplo scalare del punto fisso.
Lemma 2.6. Sia A una matrice simmetrica completamente indecomponibile e sia x∗
l’unico vettore (a componenti strettamente positive) tale che P = D(x∗)AD(x∗) sia dop-
piamente stocastica. Sia f (x) = D(Ax)−1e e sia α > 0. Esiste una norma k · k su Rn tale che se kˆx − αx∗k < ε allora
min
v∈Vkf
2(ˆx) − vk ≤ |λ
2|2ε + o(ε) (2.34)
dove λ2 è il secondo autovalore più grande in modulo di P e V è la retta generata da x∗.
Dimostrazione. Dato ε > 0 sia ˆx = αx∗+ d con kdk ≤ ε (dedurremo in seguito la norma
opportuna da usare). Per semplicità definiamo D = D(x∗) e J = J (x∗) e osserviamo che
si ha
f (αx∗) = D(A(αx∗))−1e = 1
αD(x∗)e = x∗
α e dunque f2(αx∗) = αx∗. Possiamo ora sviluppare nel modo seguente:
f2(ˆx) = f (f (αx∗) + J (αx∗)d + o(kdk))
= f2(αx∗) + J (f (αx∗))[J (αx∗)d + o(kdk)] + o(kdk)
= f2(αx∗) + J (x∗/α)J (αx∗)d + o(kdk)
= αx∗+ (−α2DP D−1)(−α−2DP D−1)d + o(kdk)
Osserviamo ora che il raggio spettrale di P (e dunque quello di J ) è uguale a 1: questo può essere visto come una conseguenza del teorema di Perron-Frobenius oppure direttamente osservando che P e = e, dunque 1 è autovalore; d’altra parte la norma 1 di una matrice doppiamente stocastica, essendo il massimo della somma fatta sulle righe, è chiaramente uguale a 1 ed il raggio spettrale è sempre minore di essa. Pertanto non possiamo diretta- mente passare alle norme e concludere che kf2(ˆx)−vk < kˆx−vk. Possiamo però sfruttare l’ipotesi che A sia completamente indecomponibile. Infatti questa proprietà è ovviamen- te ereditata da P che risulta pertanto essere primitiva (e irriducibile): dal teorema di Perron-Frobenius segue che il suo raggio spettrale ρ(P ) = 1 è un autovalore semplice ed è in particolare l’unico autovalore di modulo 1. Per similitudine la stessa conclusione vale per J e dalla relazione deduciamo che x∗ è un autovettore corrispondente all’autovalore
1.
Eseguiamo adesso un’operazione, detta deflazione di Wielandt, che ci permette di ottene- re una matrice J0che ha lo stesso spettro di J eccetto l’autovalore (semplice) 1. Poniamo
y = x∗/(xT∗x∗) e definiamo
J0 = J − x∗yT.
Notiamo che J0x∗ = J x∗− x∗ = 0 e che in generale se λ 6= 1 è un autovalore di J relativo
all’autovettore sinistro z vale
zTJ0 = zTJ − zTx∗yT = λzT.
Pertanto gli spettri di J0 e di J (e dunque di P ) coincidono a meno dell’autovalore 1 che
in J0 è rimpiazzato dall’autovalore 0. In simboli
λ(J0) = (λ(J ) \ {1}) ∪ {0} = {λ2, . . . , λn, 0}
dove λ2 è il secondo autovettore più grande in modulo di J .
Dunque possiamo scrivere:
f2(ˆx) = αx∗+ (J0+ x∗yT)2d + o(ε)
= αx∗+ (J02+ x∗yTx∗yT + x∗yTJ0+ J0x∗yT)d + o(ε)
= αx∗+ (J02+ x∗yT + x∗yTJ0)d + o(ε)
= αx∗+ J02d + x∗yT(I + J0)d + o(ε)
= J02d + (α + yT(I + J0)d)x∗+ o(ε).
Per concludere osserviamo che, data una matrice B e fissato ε > 0, esiste sempre una nor- ma matriciale indotta (da una norma vettoriale) per cui valga kBk ≤ ρ(B)+ε. Scegliendo la nostra norma tale che
kJ0k ≤ ρ(J0) + ε = λ2+ ε
e ponendo
v = (α + yT(I + J0)d)x∗
Il lemma precedente ci dice sostanzialmente che, se ci troviamo a distanza minore di ε dalla retta generata dal punto fisso, ogni due iterazioni della mappa f tale distanza decrescerà di un fattore |λ2|2 al primo ordine in ε. Poiché nelle nostre ipotesi l’algoritmo
di Sinkhorn-Knopp converge possiamo concludere che nel caso simmetrico la convergenza è lineare ed è governata dal secondo autovalore più grande in modulo della matrice P . Il prossimo risultato descrive in maniera più precisa queste considerazioni.
Teorema 2.5. Sia A una matrice simmetrica completamente indecomponibile e sia x∗
l’unico vettore (a componenti strettamente positive) tale che P = D(x∗)AD(x∗) sia dop-
piamente stocastica. Sia {xk} la successione delle iterate prodotte dalla (2.28) con x0= e.
Per ogni ε > 0 esistono successioni limitate {αk} e {dk} ed un indice K ∈ N tale che per ogni k ≥ K si ha
xk = αkx∗+ dk (2.35)
con kdkk ≤ ε ed inoltre
kdk+2k ≤ |λ2|2kdkk + o(kdkk). (2.36) Dimostrazione. La (2.35) segue dalla convergenza dell’algoritmo di Sinkhorn-Knopp (la limitatezza di αkè una condizione necessaria alla convergenza). La (2.36) discende invece dalla dimostrazione del Lemma 2.6.
Passiamo ora al caso generale in cui la matrice A non è necessariamente simmetrica. Come visto, in questo caso l’algoritmo di Sinkhorn-Knopp risulta equivalente alla sua variante simmetrica applicata alla matrice
B = 0 A AT 0
.
Tuttavia non possiamo applicare direttamente il teorema precedente in quanto la matrice B non risulta più essere completamente indecomponibile (a causa dei blocchi nulli sulla diagonale). Sappiamo però che se A è completamente indecomponibile, l’algoritmo stan- dard applicato ad A converge ed esistono pertanto vettori r∗, c∗tali che P = D(r∗)AD(c∗)
è doppiamente stocastica. Ma allora il vettore [r∗, c∗]T ∈ R2n è tale che
Dr∗ c∗ 0 A AT 0 Dr∗ c∗ = 0 D(r∗)AD(c∗) D(c∗)ATD(r∗) 0 = 0 P PT 0
dove l’ultima matrice a blocchi, che chiameremo Q, è doppiamente stocastica per co- struzione. Segue che [r∗, c∗]T è un punto fisso per la mappa f (x) = D(Bx)−1e e, per
quanto visto sopra, la sua matrice Jacobiana in questo punto è simile a Q. Come sopra, essendo A completamente indecomponibile, anche P e PT lo sono. Ma allora anche P PT è completamente indecomponibile e dunque primitiva ed essendo doppiamente stocastica il suo raggio spettrale ρ(P PT) = 1 è un autovalore semplice. Osserviamo ora che vale la seguente relazione insiemistica
λ(Q) = ± q
dove con λ(·) e σ(·) abbiamo indicato rispettivamente l’insieme degli autovalori e quello dei valori singolari. In particolare Q ha due autovalori di modulo 1 e gli autovettori di J ad essi relativi sono v1 = [r∗, c∗]T e v2 = [r∗, −c∗]T. Operiamo nuovamente un processo
di (doppia) deflazione per rimuovere gli autovalori indesiderati e definiamo J0 = J − v1yT1 − v2y2T
dove abbiamo posto y1 = n1U (v1) e y2 = −1nU (v2). Ricordiamo che l’operatore U agisce
sui vettori invertendone le componenti e osserviamo che y1 e y2 altro non sono che gli
autovettori sinistri di J (opportunamente normalizzati) relativi agli autovalori 1 e −1 rispettivamente. È immediato verificare che vale J0v1 = J v2 = 0. Possiamo allora
procedere come nel Lemma 2.6 e concludere che se ˆx è della forma ˆx = αv1 + d con
kdk < ε allora f2(ˆx) = J02d + (α + yT1(I + J0)d)v1+ o(ε) e di conseguenza min v∈Vkf 2(ˆx) − vk ≤ σ2 2ε + o(ε) (2.37)
dove V è il sottospazio generato dal punto fisso v1 = [r∗, c∗]T e σ2 è il secondo più grande
valore singolare di P . Abbiamo ora gli strumenti per enunciare il risultato piu’ impor- tante di questa sezione. Ricordando le considerazioni fatte all’inizio di questa sezione, detta {xk} la successione delle iterate prodotte dalla variante simmetrica dell’algoritmo di Sinkhorn-Knopp applicato alla matrice a blocchi B e dette {ck} ed {rk} le successioni delle iterate prodotte dall’algoritmo standard applicato ad A, possiamo identificare (ed in effetti lo abbiamo già fatto) rk con il blocco superiore del vettore x2ke ckcon il blocco in- feriore del vettore x2k−1. Sfruttando la (2.37), analogamente a quanto fatto nel Teorema 2.5, otteniamo che per k sufficientemente grande si ha:
krk+1− r∗k ≤ σ22krk− r∗k kck+1− c∗k ≤ σ22kck− c∗k.
Unendo le due disuguaglianze possiamo enunciare il seguente teorema.
Teorema 2.6. Sia A una matrice completamente indecomponibile. L’algoritmo di Sinkhorn- Knopp converge linearmente ad una coppia (r∗, c∗) tale che che P = D(r∗)AD(c∗) è
doppiamente stocastica. Inoltre esiste un indice K ∈ N tale che per ogni k ≥ K si ha rk+1 ck+1 −r∗ c∗ ≤ σ22 rk ck −r∗ c∗
dove σ2 è il secondo più grande valore singolare di P . In particolare la velocità di
convergenza è governata da σ2.
Per concludere questa sezione notiamo che in generale, come detto, l’algoritmo di Sinkhorn-Knopp converge per matrici a supporto totale. Dal Teorema 1.5 sappiamo però
che se A ha supporto totale allora è a meno di permutazioni somma diretta di matrici completamente indecomponibili, ovvero esistono P, Q matrici di permutazione tali che
P AQ = A1 A2 . .. Ak (2.38)
dove ciascuna Ai è completamente indecomponibile.
Osserviamo ora comportamento dell’algoritmo di Sinkhorn-Knopp non è influenzato dalle permutazioni di righe e colonne, infatti se P, Q sono matrici di permutazione ed r, c sono tali che D(r)(P AQ)D(c) è doppiamente stocastica, segue immediatamente che
PTD(r)(P AQ)D(c)QT = D(r)AD(c)
è doppiamente stocastica. Pertanto possiamo assumere che A sia già nella forma (2.38) e osservare che applicare l’algoritmo su A è equivalente ad applicarlo separatamente ad ogni blocco diagonale. Relativamente a ciascun blocco l’algoritmo convergerà ad una matrice doppiamente stocastica Pi con un tasso di convergenza locale maggiorato da
σ22(Pi); possiamo pertanto concludere che il tasso di convergenza totale sarà maggiorato
Tecniche di accelerazione
In questo capitolo presenteremo un metodo nuovo, non presente in letteratura, per risolvere il problema di bilanciamento. Il metodo che proponiamo si comporta molto bene in termini di velocità di convergenza, in particolare se applicato a matrici quasi decomponibili di grandi dimensioni: su di esse l’algoritmo di Sinkhorn-Knopp converge molto lentamente e risulta pertanto poco pratico. Seguirà una sezione dedicata ai risultati numerici che evidenzieranno le proprietà di convergenza dei metodi analizzati.
3.1
Una tecnica di accelerazione
Come abbiamo visto nella sezione 2.2 l’algoritmo di Sinkhorn-Knopp (Algoritmo 1) converge linearmente. Ciò può risultare particolarmente svantaggioso in alcuni casi, in particolare quando il secondo valore singolare di P è molto vicino ad 1. In questi casi, per matrici di grandi dimensioni, l’algoritmo si rivela del tutto improponibile. Ci proponiamo dunque di formulare un algoritmo che si comporti bene anche in questi casi difficili da trattare con l’algoritmo standard.
Consideriamo una matrice A ∈ Rn×n scalabile, ovvero una matrice per cui l’algoritmo di Sinkhorn-Knopp converga. Sia T l’operatore di Menon associato ad A: ricordiamo che l’algoritmo di Sinkhorn-Knopp è equivalente ad un’iterazione di punto fisso per la mappa T . Sia ora J (x) la matrice Jacobiana di T valutata nel punto x ∈ Rn, x > 0; nel capitolo precedente abbiamo analizzato il suo ruolo nelle proprietà di convergenaq dell’algoritmo. Cerchiamo adesso un’espressione esplicita per J (x). Per chiarezza espositiva indichiamo con Jf(x) la matrice Jacobiana della funzione f nel punto x, dunque per il momento la
nostra J (x) sarà denotata JT(x). Una semplice applicazione della derivazione di funzioni
composte mostra che vale:
JT(x) = JU ATU A(x) = JU(ATU Ax) · JAT(U Ax) · JU(Ax) · JA(x).
Algoritmo 1 Algoritmo di Sinkhorn-Knopp
1 function SK(A, τ );
Input : A ∈ Rn×n scalabile, τ > 0 soglia di tolleranza Output: x tale che T x = x
2 Seleziona x0 ∈ Rn, x > 0 3 for k = 1, 2, . . . do 4 y = T (xk−1) 5 xk = y/kyk2 6 if kT xk− xkk2 < τ then 7 stop 8 end 9 end 10 return xk
Notiamo adesso che fissato y ∈ Rn, y > 0 si ha:
JU(y) = − 1 y2 1 1 y2 2 . .. 1 y2 n = − diag−2(y).
Immediato è anche il calcolo della matrice Jacobiana associata ad A ed AT. Essendo (Ay)i =Pnj=1aijyj si ha ovviamente ∂(Ay)i/∂yj = aij e dunque
JA(y) = A, JAT(y) = AT.
Mettendo insieme i pezzi otteniamo la scrittura seguente:
JT(x) = diag2(T x)ATdiag2(Sx)A (3.1)
nella quale abbiamo osservato che
diag−2(y) = diag2(U y) ed abbiamo richiamato la definizione dell’operatore S = U A.
Proposizione 3.1. Sia A ∈ Rn×n una matrice scalabile e sia T l’operatore di Menon ad essa associato. Sia x∗ > 0 un punto fisso per T , la cui esistenza è garantita dall’ipotesi
Dimostrazione. Sia x ∈ Rn, x > 0. Si ha
JT(x) · x = diag2(T x)ATdiag2(Sx)Ax
= diag2(T x)ATSx = diag−2(ATSx)(ATSx) = diag−1(ATSx)e = diag(U ATU Ax)e = T x
Pertanto, se x∗ è punto fisso per T vale
JT(x∗) · x∗ = T x∗ = x∗
ovvero la tesi.
Dalla dimostrazione della Proposizione 3.1 deduciamo un’interessante proprietà. L’al- goritmo di Sinkhorn-Knopp è infatti equivalente alla seguente iterazione:
xk+1 = J (xk)xk (3.2)
in cui abbiamo omesso il pedice T nella Jacobiana. Non essendoci pericolo di ambiguità utilizzeremo questa notazione anche nel seguito della trattazione.
Naturalmente l’iterazione (3.2) non aggiunge nulla di nuovo, anzi risulta numerica- mente più onerosa se ci proponiamo di formare ad ogni passo la matrice J (xk). Osservia-
mo però che il secondo membro della (3.2) è sostanzialmente un passo del metodo delle potenze (Algoritmo 2) applicato alla matrice J (xk).
Questa procedura converge, com’è noto, all’autovettore dominante della matrice cui è applicato. L’idea è allora quella di introdurre un’iterazione interna in cui eseguiamo l’in- tero metodo delle potenze per calcolare un’approssimazione dell’autovettore dominante di J (xk) ed utilizzare quest’ultima come nuova iterata. Il metodo che ne risulta (Algoritmo
3) può essere sintetizzato - e di fatto generalizzato - dalla seguente relazione:
λmax(J (xk))xk+1 = J (xk)xk+1 (3.3)
in cui con λmax(J (xk)) abbiamo indicato l’autovalore di modulo massimo della matrice
Jacobiana calcolata in xk.
Intuitivamente, se nella (3.2) supponiamo che xk ≈ xk+p per p > 0, possiamo immaginare che valga una relazione del tipo
xk+p ≈ Jp(xk)xk (3.4)
in cui xk+p è ottenuto a seguito di p iterazioni del metodo delle potenze sulla matrice J (xk). La (3.4) esprime quanto detto in precedenza, ovvero che, come nuova approssi-
Algoritmo 2 Metodo delle potenze
1 function PowerMethod(A, τ );
Input : A ∈ Rn×n, τ > 0 soglia di tolleranza Output: (λ, x) autocoppia dominante di A
2 Seleziona x0 ∈ Rn, kx0k2 = 1 3 for k = 1, 2, . . . do 4 y = Axk−1 5 xk = y/kyk2 6 λk= xTky 7 if ky − λkxkk2 < τ then 8 stop 9 end 10 end 11 return (λk, xk) Algoritmo 3 1 function PowerSK(A, τ1, τ2);
Input : A ∈ Rn×n scalabile, τ1, τ2 > 0 soglie di tolleranza
Output: x tale che T x = x
2 Seleziona x0 ∈ Rn, x > 0 3 for k = 1, 2, . . . do 4 xk = PowerMethod(J (xk−1), τ1) 5 if kT xk− xkk2 < τ2 then 6 stop 7 end 8 end 9 return xk
1 1.5 2 2.5 3 3.5 4 Numero di iterazioni 10-16 10-14 10-12 10-10 10-8 10-6 10-4 10-2 100 102 104 Errore Algoritmo di SK SK con metodo delle potenze
Figura 3.1: Andamento dell’errore per SK e PowerSK con τ, τ1, τ2 = 10−8 applicati ad una matrice A > 0 di
dimensione n = 104. L’errore è rappresentato in scala logaritmica.
Jacobiana che formiamo al passo k-esimo. Possiamo sperare in questo modo di accelerare la convergenza dell’algoritmo di Sinkhorn-Knopp.
La (3.3) è un’equazione implicita che si presta ad essere risolta mediante un qualsivo- glia algoritmo per il calcolo di autovettori: il metodo delle potenze che ha ispirato questo metodo è probabilmente il più semplice da implementare.
Sperimentalmente (Figura 3.1) l’errore decresce quadraticamente ad ogni iterazione del ciclo for (istruzioni 3-8, Algoritmo 3).
Quanto al tempo di esecuzione possiamo osservare in Figura 3.2 come l’algoritmo standard di Sinkhorn-Knopp, nel caso di matrici strettamente positive, converga più velocemente dell’Algoritmo 3 di un fattore κ ≈ 2.47. Ciò può apparire controintuitivo: a fronte di una riduzione quadratica dell’errore assistiamo ad un aumento, seppur contenuto, del tempo di esecuzione. Questo fenomeno è dovuto al fatto che benché siano necessari pochi passi dell’iterazione esterna per garantire un’ottima approssimazione del punto fisso di T , possono essere necessarie diverse iterazioni del metodo delle potenze per avere un’approssimazione altrettanto buona dell’autovettore dominante di J (xk).
Un primo approccio per ovviare a questo inconveniente potrebbe essere quello di au- mentare la soglia di tolleranza richiesta dal metodo delle potenze, o equivalentemente limitare il numero di iterazioni di quest’ultimo. Tuttavia si osserva che, nel caso stret- tamente positivo, la scelta migliore in termini di tempo di esecuzione sarebbe quella di eseguire un solo passo del metodo delle potenze e ci ricondurremmo pertanto all’algoritmo standard nella forma (3.2).
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 dim(A) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Tempo di esecuzione Algoritmo di SK SK con metodo delle potenze
Figura 3.2: Tempo di esecuzione (in secondi) per SK e PowerSK applicati a matrici strettamente positive di dimensione n = k · 102per k = 1, . . . , 100. Si è posto τ, τ
1, τ2= 10−8.
Un secondo approccio potrebbe essere quello di accelerare l’algoritmo per il calcolo dell’autovettore dominante di J (xk): noi seguiremo questa strada e mostreremo che, per una particolare classe di matrici, il miglioramento che otteniamo è sostanziale.