• randomized algorithm
• matrix approximation
• low rank matrix
• singular value decomposition

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.