Faster least squares approximation

DOI10.1007/S00211-010-0331-6zbMATH Open1218.65037arXiv0710.1435OpenAlexW2007399394MaRDI QIDQ623334FDOQ623334

Sumit K. Garg

Publication date: 14 February 2011

Published in: Numerische Mathematik (Search for Journal in Brave)

Abstract: Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets $n$ be the number of constraints and $d$ be the number of variables, with $nggd$. Then, existing exact methods find a solution vector in $O(n{d}^2)$ time. We present two randomized algorithms that provide very accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard Transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if $n$ is sufficiently larger than $d$, the approximate solution can be computed in $O(ndlogd)$ time.

Full work available at URL: https://arxiv.org/abs/0710.1435

zbMATH Keywords

optimizationdirect methodsQR decompositionoverdetermined systemmethod of least squaresaccurate relative-error approximationoverconstrained least-squares problemprojection-based randomized algorithmrandomized Hadamard transformsampling-based randomized algorithm

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sampling algorithms for l₂ regression and applications
• Relative-Error $CUR$ Matrix Decompositions
• Title not available (Why is that?)
• Numerical linear algebra in the streaming model
• Faster least squares approximation
• Generalized inverses. Theory and applications.
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• On variants of the Johnson–Lindenstrauss lemma
• Sums of random Hermitian matrices and an inequality by Rudelson
• Spectral techniques applied to sparse random graphs
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• A fast randomized algorithm for overdetermined linear least-squares regression
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Sampling from large matrices
• A Fast Random Sampling Algorithm for Sparsifying Matrices
• Title not available (Why is that?)
• A fast and efficient algorithm for low-rank approximation of a matrix
• Comparison of the Method of Averages with the Method of Least Squares

Cited In (only showing first 100 items - show all)

• Sublinear update time randomized algorithms for dynamic graph regression
• Fast dimension reduction using Rademacher series on dual BCH codes
• Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
• Optimal subsampling for softmax regression
• Distributed penalized modal regression for massive data
• Sketching for Principal Component Regression
• Subdata selection algorithm for linear model discrimination
• Stochastic boundary methods of fundamental solutions for solving PDEs
• Randomized Iterative Methods for Linear Systems
• Dimensionality reduction with subgaussian matrices: a unified theory
• Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models
• Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition
• Title not available (Why is that?)
• On the perturbation of an \(L^2\)-orthogonal projection
• Functional principal subspace sampling for large scale functional data analysis
• Zeroth-order optimization with orthogonal random directions
• Fast iterative methods for least squares estimations
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores
• Principal eigenvector localization and centrality in networks: revisited
• A two-stage optimal subsampling estimation for missing data problems with large-scale data
• Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten \(p\)-norms
• Random design analysis of ridge regression
• Frequent directions: simple and deterministic matrix sketching
• The fast Cauchy transform and faster robust linear regression
• Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
• Faster Kernel Ridge Regression Using Sketching and Preconditioning
• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
• Inversion-free subsampling Newton's method for large sample logistic regression
• Surface temperature monitoring in liver procurement via functional variance change-point analysis
• Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators With Massive Data
• A Practical Randomized CP Tensor Decomposition
• Title not available (Why is that?)
• Preconditioners for Krylov subspace methods: An overview
• Optimal subsampling for least absolute relative error estimators with massive data
• Subsampling in longitudinal models
• Information-Based Optimal Subdata Selection for Big Data Linear Regression
• Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views
• On the perturbation of the Moore-Penrose inverse of a matrix
• Optimal Sampling for Generalized Linear Models Under Measurement Constraints
• Two-subspace projection method for coherent overdetermined systems
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• On b-bit min-wise hashing for large-scale regression and classification with sparse data
• Fast least squares approximation using tensor products of functions and linear forms
• Model-robust subdata selection for big data
• High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
• Title not available (Why is that?)
• An investigation of Newton-Sketch and subsampled Newton methods
• Title not available (Why is that?)
• Random projections for Bayesian regression
• Fast quantum algorithms for least squares regression and statistic leverage scores
• Title not available (Why is that?)
• An Efficient Algorithm for the Classical Least Squares Approximation
• Sketched approximation of regularized canonical correlation analysis
• Optimal Subsampling for Large Sample Logistic Regression
• Adaptive iterative Hessian sketch via \(A\)-optimal subsampling
• Dense fast random projections and Lean Walsh transforms
• Title not available (Why is that?)
• Faster least squares approximation
• Simple backward error bounds for linear least-squares problems
• A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
• Generalized linear models for massive data via doubly-sketching
• Optimal subsampling for composite quantile regression in big data
• Proximal algorithms and temporal difference methods for solving fixed point problems
• Random projections for the nonnegative least-squares problem
• Random reordering in SOR-type methods
• A random sampling algorithm for fully-connected tensor network decomposition with applications
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Fast and accurate randomized algorithms for linear systems and eigenvalue problems
• Deterministic subsampling for logistic regression with massive data
• Leveraging for big data regression
• Far-field compression for fast kernel summation methods in high dimensions
• Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition
• Admissible subspaces and the subspace iteration method
• Robust optimal subsampling based on weighted asymmetric least squares
• Robust and efficient subsampling algorithms for massive data logistic regression
• Structured Random Sketching for PDE Inverse Problems
• Optimal subsampling for large‐sample quantile regression with massive data
• Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning
• Optimal Poisson subsampling for softmax regression
• Title not available (Why is that?)
• Sampled Tikhonov regularization for large linear inverse problems
• Title not available (Why is that?)
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
• Distributed subsampling for multiplicative regression
• Title not available (Why is that?)
• Optimal subsampling algorithms for composite quantile regression in massive data
• On the inversion-free Newton's method and its applications
• Parameter estimation of linear mixed effects model based on online update
• A literature survey of matrix methods for data science
• A selective review on statistical methods for massive data computation: distributed computing, subsampling, and minibatch techniques
• A Subsampling Method for Regression Problems Based on Minimum Energy Criterion
• Density Regression with Conditional Support Points
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Subsampling and Jackknifing: A Practically Convenient Solution for Large Data Analysis With Limited Computational Resources
• Unweighted estimation based on optimal sample under measurement constraints
• Model constraints independent optimal subsampling probabilities for softmax regression

Uses Software

• Blendenpik

   Recommendations

• A fast randomized algorithm for overdetermined linear least-squares regression 👍 👎
• Fast least squares approximation using tensor products of functions and linear forms 👍 👎
• A Fast Randomized Algorithm for Orthogonal Projection 👍 👎
• A fast and efficient algorithm for low-rank approximation of a matrix 👍 👎
• Random projections for the nonnegative least-squares problem 👍 👎

This page was built for publication: Faster least squares approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623334)