Faster least squares approximation

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

zbMATH Keywords

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

Mathematics Subject Classification ID

65F20: Numerical solutions to overdetermined systems, pseudoinverses

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Faster Kernel Ridge Regression Using Sketching and Preconditioning, A Practical Randomized CP Tensor Decomposition, On b-bit min-wise hashing for large-scale regression and classification with sparse data, On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Optimal Subsampling for Large Sample Logistic Regression, Sampled Tikhonov regularization for large linear inverse problems, Estimating Leverage Scores via Rank Revealing Methods and Randomization, Unnamed Item, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, Optimal Sampling for Generalized Linear Models Under Measurement Constraints, Unnamed Item, Semi-Infinite Linear Regression and Its Applications, Sharper Bounds for Regularized Data Fitting, Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition, An investigation of Newton-Sketch and subsampled Newton methods, Structured Random Sketching for PDE Inverse Problems, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, Information-Based Optimal Subdata Selection for Big Data Linear Regression, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces, Sketching for Principal Component Regression, Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning, Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators With Massive Data, Zeroth-order optimization with orthogonal random directions, Optimal subsampling for large‐sample quantile regression with massive data, Distributed penalized modal regression for massive data, M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions, Sketched approximation of regularized canonical correlation analysis, Model constraints independent optimal subsampling probabilities for softmax regression, Generalized linear models for massive data via doubly-sketching, Optimal subsampling algorithms for composite quantile regression in massive data, Subsampling in longitudinal models, Random projections for Bayesian regression, Simple backward error bounds for linear least-squares problems, Random design analysis of ridge regression, Two-subspace projection method for coherent overdetermined systems, Fast quantum algorithms for least squares regression and statistic leverage scores, Dimensionality reduction with subgaussian matrices: a unified theory, Faster least squares approximation, Dense fast random projections and Lean Walsh transforms, Proximal algorithms and temporal difference methods for solving fixed point problems, High-dimensional model recovery from random sketched data by exploring intrinsic sparsity, Random projections for the nonnegative least-squares problem, Fast dimension reduction using Rademacher series on dual BCH codes, Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition, Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten \(p\)-norms, Model-robust subdata selection for big data, Optimal subsampling for composite quantile regression in big data, Optimal subsampling for least absolute relative error estimators with massive data, Subdata selection algorithm for linear model discrimination, Functional principal subspace sampling for large scale functional data analysis, Principal eigenvector localization and centrality in networks: revisited, A two-stage optimal subsampling estimation for missing data problems with large-scale data, Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration, Inversion-free subsampling Newton's method for large sample logistic regression, Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format, Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem, Surface temperature monitoring in liver procurement via functional variance change-point analysis, Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument, Adaptive iterative Hessian sketch via \(A\)-optimal subsampling, Sublinear update time randomized algorithms for dynamic graph regression, A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems, On the perturbation of an \(L^2\)-orthogonal projection, On the perturbation of the Moore-Penrose inverse of a matrix, Far-field compression for fast kernel summation methods in high dimensions, Structural conditions for projection-cost preservation via randomized matrix multiplication, Optimal subsampling for softmax regression, Stochastic boundary methods of fundamental solutions for solving PDEs, The Fast Cauchy Transform and Faster Robust Linear Regression, Frequent Directions: Simple and Deterministic Matrix Sketching, Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence, General Error Estimates for the Longstaff–Schwartz Least-Squares Monte Carlo Algorithm, Compressed and Penalized Linear Regression, Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores, Randomized Iterative Methods for Linear Systems

Uses Software

Blendenpik

Cites Work