Faster least squares approximation
From MaRDI portal
Publication:623334
DOI10.1007/s00211-010-0331-6zbMath1218.65037arXiv0710.1435MaRDI QIDQ623334
Publication date: 14 February 2011
Published in: Numerische Mathematik (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0710.1435
optimization; method of least squares; overdetermined system; QR decomposition; direct methods; accurate relative-error approximation; overconstrained least-squares problem; projection-based randomized algorithm; randomized Hadamard transform; sampling-based randomized algorithm
65F20: Numerical solutions to overdetermined systems, pseudoinverses
Related Items
Unnamed Item, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Simple backward error bounds for linear least-squares problems, Random design analysis of ridge regression, Two-subspace projection method for coherent overdetermined systems, Faster least squares approximation, Dense fast random projections and Lean Walsh transforms, Random projections for the nonnegative least-squares problem, Fast dimension reduction using Rademacher series on dual BCH codes, The Fast Cauchy Transform and Faster Robust Linear Regression, Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores, Randomized Iterative Methods for Linear Systems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster least squares approximation
- Sums of random Hermitian matrices and an inequality by Rudelson
- Matrix multiplication via arithmetic progressions
- Generalized inverses. Theory and applications.
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- A fast randomized algorithm for overdetermined linear least-squares regression
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- On variants of the Johnson–Lindenstrauss lemma
- Sampling from large matrices
- Sampling algorithms for l2 regression and applications
- A Fast Random Sampling Algorithm for Sparsifying Matrices
- Relative-Error $CUR$ Matrix Decompositions
- A generalization of the fast LUP matrix decomposition algorithm and applications
- Numerical linear algebra in the streaming model
- A fast and efficient algorithm for low-rank approximation of a matrix
- Spectral techniques applied to sparse random graphs
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Comparison of the Method of Averages with the Method of Least Squares
