Decomposizione CUR e applicazioni

Nell’ambito dell’analisi dati è spesso necessario fare uso di grandi matrici per descrivere un dataset. In molti casi, per poterlo analizzare, risulta utile approssimare la matrice dei dati come prodotto di altre matrici. A tale fine, la Decomposizione in Valori Singolari (SVD) è una decomposizione ampiamente utilizzata, in quanto consente di ottenere la migliore approssimazione di un certo rango della matrice. Nonostante le proprietà di ottimalità, le matrici che si ottengono da tale decomposizione non risultano particolarmente significative in funzione dei dati e risulta perciò difficile utilizzarle direttamente per dedurre informazioni sul dataset. Per superare questo limite, abbiamo introdotto la Decomposizione CUR, un particolare tipo di decomposizione di rango basso, in cui la matrice di partenza viene espressa in funzione solo di alcune righe e colonne della matrice stessa. Essendo costruite a partire da alcuni dati effettivi della matrice, individuati attraverso la tecnica del Subspace Sampling, le matrici ottenute da questa decomposizione consentono di poter fare considerazioni sull’intero dataset. In questa tesi viene descritto l’algoritmo per la costruzione delle matrici di tale decomposizione e vengono messe in evidenza le garanzie sull’errore relativo dell’approssimazione ottenuta. Infine, viene presentata l’applicazione della Decomposizione CUR ad un dataset reale contenente i risultati delle votazioni dei giudici della Corte Suprema degli Stati Uniti e vengono analizzati e discussi i risultati ottenuti.