# Faster SVD-Truncated Least-Squares Regression

arXiv: https://arxiv.org/abs/1401.0417 · HTML: https://mlsanity.com/paper/1401.0417/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jan 2014.

## Built on by (most cited first, 1 of 1)

- [An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition](https://mlsanity.com/paper/2503.02386/) (2025)

## Abstract (arXiv)

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.