efficient matrix completion via randomization

In questa tesi viene introdotto il problema del completamento di matrici, con alcuni esempi di applicazioni reali. Tra i possibili metodi utilizzati per risolvere il problema, ci concentriamo sulla sogliatura dei valori singolari, spiegandone l’algoritmo e discutendone una possibile implementazione. Evidenziamo le proprietà utili e presentiamo i risultati che ne garantiscono la convergenza. Successivamente, l’algoritmo viene testato numericamente per mostrarne i punti di forza e metterne in luce eventuali limiti. Per migliorare alcuni aspetti dell’SVT (principalmente velocità e gestione della memoria), introduciamo la decomposizione ai valori singolari randomizzata. Questa decomposizione è più rapida di quella standard, a costo di introdurre elementi casuali. Il metodo viene quindi utilizzato in una versione modificata dell’algoritmo SVT, con alcune tecniche che permettono di mantenere la precisione necessaria a garantire la convergenza. L’algoritmo risultante viene testato numericamente confrontandolo con il metodo standard. Mostriamo inoltre come l’algoritmo si comporta in applicazioni reali e come sia possibile ottenere un notevole incremento in velocità mantenendo l’accuratezza dell’SVT classico. Infine, vengono descritti brevemente gli algoritmi randomizzati per comprendere come funziona la randomizzazione nell’aritmetica a precisione finita. In particolare, ci concentriamo sulla generazione casuale in MATLAB, sia per distribuzioni uniformi che gaussiane, ricorrenti nell’algoritmo di SVD randomizzata.