L’algoritmo di Orthogonal Rank-One Matrix Pursuit per il completamento matriciale

Il completamento di matrici a basso rango è stato applicato con successo in un'ampia gamma di applicazioni di machine learning, come il filtraggio collaborativo e il ripristino di immagini. Il problema consiste nel trovare una matrice con rango minimo che abbia gli stessi elementi non nulli di una matrice di partenza parzialmente osservata. Tuttavia, molti algoritmi esistenti e già noti non sono adatti per problemi di grandi dimensioni, poiché richiedono il calcolo della decomposizione ai valori singolari completa. In questo elaborato, viene descritto un algoritmo efficiente per il completamento delle matrici. L'idea è di estendere il noto Orthogonal Matching Pursuit dal caso vettoriale al caso matriciale. Ad ogni iterazione, viene determinata una base di matrici di rango uno, generata dalla coppia di vettori singolari principali del residuo dell'approssimazione corrente e vengono aggiornati i coefficienti per tutte le matrici di rango uno ottenute fino all'iterazione attuale. Questo algoritmo risulta più efficiente poiché richiede il calcolo della sola prima coppia di vettori singolari, evitando la decomposizione completa ai valori singolari. Successivamente viene descritto un secondo algoritmo più economico in termini di memoria, rendendo l'algoritmo proposto efficace anche per matrici di grandi dimensioni. Viene infine dimostrata la convergenza lineare dei due algoritmi proposti. Infine l’algoritmo descritto viene applicato su numerosi dataset di dimensioni diverse. I risultati mostrano che l’algoritmo descritto è molto più efficiente rispetto agli algoritmi di completamento matriciale già noti, ottenendo al contempo prestazioni di previsione simili o migliori.