Faster SVD-Truncated Least-Squares Regression

We develop a fast algorithm for computing the "SVD-truncated" regularized solution to the least-squares problem: minx TNormmatA x - b. Let matAk of rank k be the best rank k matrix computed via the SVD of matA. Then, the SVD-truncated regularized solution is: xk = pinvmatAk b. If matA is m × n, then, it takes O(m n minm,n) time to compute xk using the SVD of mathmatA. We give an approximation algorithm for mathxk which constructs a rank-mathk approximation tildematAk and computes tildexk = pinvtildematAk 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: TNormmatA tildexk - b ≈ TNormmatA xk - b and TNormxk - tildexk ≈ 0.