Name
Abstract | ||
|---|---|---|
We develop a fast algorithm for computing the “SVD-truncated” regularized solution to the least-squares problem: minx ∥Ax - b∥2. Let Ak of rank k be the best rank k matrix computed via the SVD of A. Then, the SVD-truncated regularized solution is: xk = Ak†b. If A is m × n, then, it takes O(mnmin{m, n}) time to compute xk using the SVD of A. We give an approximation algorithm for xk which constructs a rank k approximation Ãk and computes x̃k = Ãk† in roughly O(nnz(A)k log n) time. Our algorithm uses a randomized variant of the subspace iteration method. We show that, with high probability: ∥Ax̃k - b∥2 ≈ ∥Axk - b∥2 and ∥xk - x̃k∥2 ≈ 0. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ISIT.2014.6875047 | Information Theory |
Keywords | Field | DocType |
approximation theory,iterative methods,least squares approximations,regression analysis,singular value decomposition,SVD-truncated regularized solution,approximation algorithm,least-squares problem,rank k approximation,rank k matrix,subspace iteration method | Least squares,Singular value decomposition,Approximation algorithm,Discrete mathematics,Combinatorics,Minimax approximation algorithm,Low-rank approximation,Non-linear least squares,Total least squares,Linear least squares,Mathematics | Conference |
Citations | PageRank | References |
8 | 0.54 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Boutsidis | 1 | 610 | 33.37 |
| Malik Magdon-Ismail | 2 | 914 | 104.34 |