  We develop a fast algorithm for computing the "SVD-truncated" regularized
solution to the least-squares problem: $ \min_{\x} \TNorm{\matA \x - \b}. $ Let
$\matA_k$ of rank $k$ be the best rank $k$ matrix computed via the SVD of
$\matA$. Then, the SVD-truncated regularized solution is: $ \x_k =
\pinv{\matA}_k \b. $ If $\matA$ is $m \times n$, then, it takes $O(m n
\min\{m,n\})$ time to compute $\x_k $ using the SVD of \math{\matA}. We give an
approximation algorithm for \math{\x_k} which constructs a rank-\math{k}
approximation $\tilde{\matA}_{k}$ and computes $ \tilde{\x}_{k} =
\pinv{\tilde\matA}_{k} \b$ in roughly $O(\nnz(\matA) k \log n)$ time. Our
algorithm uses a randomized variant of the subspace iteration. We show that,
with high probability: $ \TNorm{\matA \tilde{\x}_{k} - \b} \approx \TNorm{\matA
\x_k - \b}$ and $\TNorm{\x_k - \tilde\x_k} \approx 0. $
