View article

We introduce a randomized procedure that, given an m×n matrix A and a positive integer k, approximates A with a matrix Z of rank k. The algorithm relies on applying a structured l×m random matrix R to each column of A, where l is an integer near to, but greater than, k. The structure of R allows us to apply it to an arbitrary m×1 vector at a cost proportional to mlog(l); the resulting procedure can construct a rank-k approximation Z from the entries of A at a cost proportional to mnlog(k)+l²(m+n). We prove several bounds on the accuracy of the algorithm; one such bound guarantees that the spectral norm ‖A−Z‖ of the discrepancy between A and Z is of the same order as max{m,n} times the (k+1)st greatest singular value σ_k+1 of A, with small probability of large deviations. In contrast, the classical pivoted “QR” decomposition algorithms (such as Gram–Schmidt or Householder) require at least kmn floating-point …