Sketching as a tool for numerical linear algebra
From MaRDI portal
Abstract: This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties. Much of the expensive computation can then be performed on the smaller matrix, thereby accelerating the solution for the original problem. In this survey we consider least squares as well as robust regression problems, low rank approximation, and graph sparsification. We also discuss a number of variants of these problems. Finally, we discuss the limitations of sketching methods.
Recommendations
Cited in
(only showing first 100 items - show all)- On principal components regression, random projections, and column subsampling
- Gaussian random projections for Euclidean membership problems
- Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
- Increasing the accuracy of solving discrete ill-posed problems by the random projection method
- Dimensionality reduction of SDPs through sketching
- An improvement of the parameterized frequent directions algorithm
- Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing
- On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
- Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation
- Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten p-norms
- Robust high-dimensional factor models with applications to statistical machine learning
- Reduced-order modeling of deep neural networks
- An efficient randomized algorithm for computing the approximate Tucker decomposition
- Randomized signal processing with continuous frames
- On the theory of dynamic graph regression problem
- Manifold reconstruction and denoising from scattered data in high dimension
- Single-pass randomized QLP decomposition for low-rank approximation
- Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
- Private aggregation from fewer anonymous messages
- Pass-efficient methods for compression of high-dimensional turbulent flow data
- Spectral estimation from simulations via sketching
- Functional principal subspace sampling for large scale functional data analysis
- Community detection with a subsampled semidefinite program
- Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
- Randomized quaternion QLP decomposition for low-rank approximation
- An efficient algorithm for computing the approximate t-URV and its applications
- Nested aggregation of experts using inducing points for approximated Gaussian process regression
- Fast spectral analysis for approximate nearest neighbor search
- A sketched finite element method for elliptic models
- Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
- Adaptive iterative Hessian sketch via A-optimal subsampling
- Newton-type methods for non-convex optimization under inexact Hessian information
- Parameterized low-rank binary matrix approximation
- Sampling-based dimension reduction for subspace approximation with outliers
- Randomized algorithms for the low multilinear rank approximations of tensors
- A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
- A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
- Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
- Single-pass randomized algorithms for LU decomposition
- A consistency theorem for randomized singular value decomposition
- Randomized algorithms of maximum likelihood estimation with spatial autoregressive models for large-scale networks
- Numerically safe Gaussian elimination with no pivoting
- Far-field compression for fast kernel summation methods in high dimensions
- Random projections of linear and semidefinite problems with linear inequalities
- Tikhonov regularization and randomized GSVD
- Improved practical matrix sketching with guarantees
- A statistical perspective on randomized sketching for ordinary least-squares
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
- Randomized local model order reduction
- Approximating spectral clustering via sampling: a review
- Compressed and Penalized Linear Regression
- Sketches and computation – II: dynamic evaluation and applications
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Sketching and embedding are equivalent for norms
- Faster kernel ridge regression using sketching and preconditioning
- Randomized algorithms in numerical linear algebra
- Max-Plus Algebraic Statistical Leverage Scores
- Practical sketching algorithms for low-rank matrix approximation
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- A bootstrap method for error estimation in randomized matrix multiplication
- Robust frequent directions with application in online learning
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- On computationally tractable selection of experiments in measurement-constrained regression models
- A Practical Randomized CP Tensor Decomposition
- Nesterov's acceleration for approximate Newton
- Randomized sketching algorithms for low-memory dynamic optimization
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Numerical algorithms for high-performance computational science
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Approximate Newton methods
- Sharper bounds for regularized data fitting
- High probability frequency moment sketches
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Tight bounds for the subspace sketch problem with applications
- Tensor-structured sketching for constrained least squares
- Matrix rigidity and the ill-posedness of robust PCA and matrix completion
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Stochastic gradients for large-scale tensor decomposition
- Low-rank Tucker approximation of a tensor from streaming data
- Semi-Infinite Linear Regression and Its Applications
- Convexification with bounded gap for randomly projected quadratic optimization
- Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
- Querying a Matrix Through Matrix-Vector Products.
- Optimality of linear sketching under modular updates
- Sketched Newton-Raphson
- Practical leverage-based sampling for low-rank tensor decomposition
- Trading beams for bandwidth: imaging with randomized beamforming
- Fast regression with an \(\ell_{\infty}\) guarantee
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Hardness results for structured linear systems
- An investigation of Newton-sketch and subsampled Newton methods
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Structured random sketching for PDE inverse problems
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Stochastic sub-sampled Newton method with variance reduction
- Randomized Dynamic Mode Decomposition
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Streaming low-rank matrix approximation with an application to scientific simulation
This page was built for publication: Sketching as a tool for numerical linear algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2939794)
