Decomposizione CUR per una migliore analisi dei dati

Le tecniche comunemente utilizzate nell'analisi dei dati permettono di esprimere grandi matrici di dati in termini di un insieme di alcuni vettori ortogonali detti componenti principali. Solitamente questi vettori, essendo combinazioni lineari delle colonne e delle righe della matrice, risultano difficili da interpretare in termini del processo da cui provengono i dati. In questa tesi viene presentata e studiata la decomposizione CUR che permette di rappresentare la matrice in termini di alcune righe e/o colonne della matrice stessa. Tale proprietà rende più facile l'interpretazione dei risultati in termini dei dati di partenza. In particolare vengono presentati due algoritmi randomizzati per il campionamento delle righe/colonne della matrice e per la costruzione delle matrici della decomposizione. La tecnica utilizzata per il campionamento è una particolare strategia chiamata "subspace sampling" che permette di dimostrare l'esistenza di garanzie di tipo probabilistico per l'errore della decomposizione. Infine vengono presentati i risultati della riduzione delle informazioni di un dataset, proveniente da una directory web, ottenuta mediante la decomposizione CUR.