• Algoritmo di Sinkhorn Knopp
• bilanciamento
• matrici
• PageRank
• RAS method
• scaling
• tecniche di accelerazione

Se una matrice quadrata non negativa A possiede un numero sufficiente di elementi non nulli, essa può essere bilanciata: esistono cioè matrici diagonali D_1 e D_2, con entrate diagonali strettamente positive, tali che P=D_1AD_2 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 matrice 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 ammette 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 R^n - il cui punto fisso, se esiste, fornirà una soluzione del problema. A tal fine svilupperemo una teoria di Perron-Frobenius non lineare 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 R^n, rispetto alla quale la mappa di iterazione T risulta essere una contrazione. Un'applicazione del teorema del punto fisso di Banach concluderà la dimostrazione della convergenza.
Discuteremo quindi alcuni risultati circa la velocità di convergenza dell'algoritmo appena descritto: sotto 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 matrici quasi decomponibili di grandi dimensioni. Matrici 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 convergenza quadratico di gran lunga preferibile alla convergenza lineare dell'algoritmo di Sinkhorn-Knopp.