  Several recent randomized linear algebra algorithms rely upon fast dimension
reduction methods. A popular choice is the Subsampled Randomized Hadamard
Transform (SRHT). In this article, we address the efficacy, in the Frobenius
and spectral norms, of an SRHT-based low-rank matrix approximation technique
introduced by Woolfe, Liberty, Rohklin, and Tygert. We establish a slightly
better Frobenius norm error bound than currently available, and a much sharper
spectral norm error bound (in the presence of reasonable decay of the singular
values). Along the way, we produce several results on matrix operations with
SRHTs (such as approximate matrix multiplication) that may be of independent
interest. Our approach builds upon Tropp's in "Improved analysis of the
Subsampled Randomized Hadamard Transform".
