Randomized Single-View Algorithms for Low-Rank Matrix Approximation
This paper develops a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semideniteness, and they can produce approximations with a user-specied 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 computer experiments.
TYUC16-Randomized-Single-Pass-arXiv.pdf
Preprint
openaccess
4.42 MB
Adobe PDF
1d45296cbd78ba78c12a5ee7157344c9
Code.zip
openaccess
60.85 KB
ZIP
c4127f5c8552e13423fcde89eef4b2c0