Pizzo, Lisa
(2024)
L’algoritmo di Orthogonal Rank-One Matrix Pursuit per il completamento matriciale.
[Laurea], Università di Bologna, Corso di Studio in
Matematica [L-DM270]
Documenti full-text disponibili:
![[img]](http://amslaurea.unibo.it/style/images/fileicons/application_pdf.png) |
Documento PDF (Thesis)
Disponibile con Licenza: Salvo eventuali più ampie autorizzazioni dell'autore, la tesi può essere liberamente consultata e può essere effettuato il salvataggio e la stampa di una copia per fini strettamente personali di studio, di ricerca e di insegnamento, con espresso divieto di qualunque utilizzo direttamente o indirettamente commerciale. Ogni altro diritto sul materiale è riservato
Download (590kB)
|
Abstract
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.
Abstract
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.
Tipologia del documento
Tesi di laurea
(Laurea)
Autore della tesi
Pizzo, Lisa
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
Completamento matriciale,Rango basso,Scomposizione in valori singolari,Matrici sparse,Ripristino di immagini
Data di discussione della Tesi
28 Giugno 2024
URI
Altri metadati
Tipologia del documento
Tesi di laurea
(NON SPECIFICATO)
Autore della tesi
Pizzo, Lisa
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
Completamento matriciale,Rango basso,Scomposizione in valori singolari,Matrici sparse,Ripristino di immagini
Data di discussione della Tesi
28 Giugno 2024
URI
Statistica sui download
Gestione del documento: