logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11252020-134007


Tipo di tesi
Tesi di laurea magistrale
Autore
PANDOLFI, MARILENA
URN
etd-11252020-134007
Titolo
Randomized methods for low-rank approximation of matrices
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Robol, Leonardo
relatore Prof. Bini, Dario Andrea
Parole chiave
  • low rank matrix
  • matrix approximation
  • randomized algorithm
  • singular value decomposition
Data inizio appello
18/12/2020
Consultabilità
Completa
Riassunto
Matrices of huge size and low rank are encountered in applications from the real world where large scale problems are involved. Due to the extremely large size, this kind of matrices cannot be fully stored in the fast memory of a computer so that mass storage devices, having a low access speed, must be used. An alternative way is to represent these matrices, possibly in an approximate way, as product of "thin" matrices, i.e., matrices where at least one dimension takes very small values. The search for such factorizations has received much interest in the last decade.

Some classical rank-revealing decompositions, like the Singular Value Decomposition or the QR decomposition, are very helpful in the case of matrices of moderate size, but they are almost unusable for their computational cost, in the case of large scale problems.

A different approach relies on randomized methods. The key idea is to generate a number of Gaussian random vectors close to the numerical rank of the matrix, to multiply them by the given matrix and obtain with a high probability a basis of the range of the matrix. Relying on this approach enables to design effective methods for estimating the numerical rank of large matrices, for determining compressed representations, and for designing rank revealing factorizations. The effectiveness of this approach is related to the possibility to compute the matrix-vector product with a low computational cost as in the case of sparse matrices.

The thesis deals with the theoretical and the computational aspects of this problem. Some applications are shown.
File