Practical Sketching Algorithms For Low-Rank Matrix Approximation

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.


Published in:
Siam Journal On Matrix Analysis And Applications, 38, 4, 1454-1485
Year:
2017
Publisher:
Philadelphia, Society for Industrial and Applied Mathematics
ISSN:
0895-4798
Keywords:
Laboratories:




 Record created 2018-01-15, last modified 2018-12-03


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)