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)- Approximate Newton methods
- Fast spectral analysis for approximate nearest neighbor search
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Hardness results for structured linear systems
- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
- RCLUPPr: a new randomized CholeskyQR with LU preconditioning
- Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization
- librla: Randomized Linear Algebra Library
- Query lower bounds for log-concave sampling
- A block-randomized stochastic method with importance sampling for CP tensor decomposition
- Householder QR factorization with randomization for column pivoting (HQRRP)
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- A random sampling algorithm for fully-connected tensor network decomposition with applications
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- An efficient algorithm for computing the approximate t-URV and its applications
- Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
- Single-pass randomized QLP decomposition for low-rank approximation
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Matrix sketching for supervised classification with imbalanced classes
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
- Optimal sampling designs for multidimensional streaming time series with application to power grid sensor data
- GMRES with randomized sketching and deflated restarting
- Querying a Matrix Through Matrix-Vector Products.
- Optimality of linear sketching under modular updates
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- Preconditioner design via Bregman divergences
- Stochastic gradients for large-scale tensor decomposition
- Data-adaptive binary classifiers in high dimensions using random partitioning
- Truncated LSQR for matrix least squares problems
- Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
- Far-field compression for fast kernel summation methods in high dimensions
- A guide to stochastic optimisation for large-scale inverse problems
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- On principal components regression, random projections, and column subsampling
- A generalized Nyström method with subspace iteration for low-rank approximations of large-scale nonsymmetric matrices
- An improvement of the parameterized frequent directions algorithm
- scientific article; zbMATH DE number 7758314 (Why is no real title available?)
- Private aggregation from fewer anonymous messages
- Accelerated double-sketching subspace Newton
- Polynomial preconditioning for the action of the matrix square root and inverse square root
- Kernel Approximation on Algebraic Varieties
- Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Randomized low-rank approximations beyond Gaussian random matrices
- Improved practical matrix sketching with guarantees
- Minimum cost flow in the CONGEST model
- Admissible subspaces and the subspace iteration method
- Global optimization using random embeddings
- Surrogate-based autotuning for randomized sketching algorithms in regression problems
- A bootstrap method for error estimation in randomized matrix multiplication
- Contour Integral Methods for Nonlinear Eigenvalue Problems: A Systems Theoretic Approach
- Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
- Construction of hierarchically semiseparable matrix representation using adaptive Johnson-Lindenstrauss sketching
- Randomized numerical linear algebra: Foundations and algorithms
- A statistical perspective on randomized sketching for ordinary least-squares
- Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
- An investigation of Newton-sketch and subsampled Newton methods
- Algorithm-agnostic low-rank approximation of operator monotone matrix functions
- Pass-efficient methods for compression of high-dimensional turbulent flow data
- Unique reconstruction for discretized inverse problems: a random sketching approach via subsampling
- Random projections for linear programming: an improved retrieval phase
- Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
- Low-Rank Binary Matrix Approximation in Column-Sum Norm.
- Randomized algorithms for the computation of multilinear rank-(_1,_2,_3) approximations
- Fast Metric Embedding into the Hamming Cube
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Efficient Error and Variance Estimation for Randomized Matrix Computations
- Sharper bounds for regularized data fitting
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Sketched and truncated polynomial Krylov subspace methods: matrix Sylvester equations
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Approximation in the extended functional tensor train format
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- Generative modeling via tree tensor network states
- \texttt{FedPower}: privacy-preserving distributed eigenspace estimation
- Approximating spectral clustering via sampling: a review
- Fast regression with an \(\ell_{\infty}\) guarantee
- How robust are linear sketches to adaptive inputs?
- Randomized Block Adaptive Linear System Solvers
- Accurate low-rank approximations via a few iterations of alternating least squares
- A sketch-and-select Arnoldi process
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Gaussian random projections for Euclidean membership problems
- Approximate F₂-Sketching of Valuation Functions
- Spectral estimation from simulations via sketching
- Functional principal subspace sampling for large scale functional data analysis
- Two-sided randomized algorithms for approximate \(K\)-term t-SVD
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- A fast randomized algorithm for computing an approximate null space
- Randomized block Gram-Schmidt process for the solution of linear systems and eigenvalue problems
- Randomized algorithms for symmetric nonnegative matrix factorization
- A class of sparse Johnson-Lindenstrauss transforms and analysis of their extreme singular values
- Randomized signal processing with continuous frames
- Numerical algorithms for high-performance computational science
- Randomized algorithms of maximum likelihood estimation with spatial autoregressive models for large-scale networks
- Random projections of linear and semidefinite problems with linear inequalities
- Convexification with bounded gap for randomly projected quadratic optimization
- MaSk-LMM: a matrix sketching framework for linear mixed models in association studies
- Numerically safe Gaussian elimination with no pivoting
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)
