Sketching as a Tool for Numerical Linear Algebra

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.

fixed minor errors/typos in section 4.3, e.g., Fact 6 and its propagation, clarified when Lemma 4.2 can be applied, typos in section 4.2.3 (G should be applied on the left), other typos throughout

References in corpus (13)

• Fast approximation of matrix coherence and statistical leverage
• Randomized algorithms for matrices and data
• Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
• Estimates of moments and tails of Gaussian chaoses
• Optimal approximate matrix product in terms of stable rank
• Optimal CUR Matrix Decompositions
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• A Sparse Johnson--Lindenstrauss Transform
• Moments of the Gaussian Chaos
• Faster Least Squares Approximation
• On the Sensitivity of Shape Fitting Problems
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Using a Non-Commutative Bernstein Bound to Approximate Some Matrix Algorithms in the Spectral Norm

Cited by in corpus (104)

• Fast Resampling of 3D Point Clouds via Graphs
• A Practical Randomized CP Tensor Decomposition
• Practical sketching algorithms for low-rank matrix approximation
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Greedy Sampling of Graph Signals
• Quantum-inspired algorithms in practice
• Randomized Dynamic Mode Decomposition
• Optical Reservoir Computing using multiple light scattering for chaotic systems prediction
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Compressed Dynamic Mode Decomposition for Background Modeling
• Online Censoring for Large-Scale Regressions with Application to Streaming Big Data
• Sub-sampled Newton Methods with Non-uniform Sampling
• Training Data Influence Analysis and Estimation: A Survey
• Adaptive Cost-sensitive Online Classification
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Sketched Subspace Clustering
• OverSketch: Approximate Matrix Multiplication for the Cloud
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Uncertainty-biased molecular dynamics for learning uniformly accurate interatomic potentials
• An improved quantum-inspired algorithm for linear regression
• Randomized Local Model Order Reduction
• Stochastic Gradients for Large-Scale Tensor Decomposition
• Numerical Reconstruction in Magnetic Particle Imaging
• Efficient Inverted Indexes for Approximate Retrieval over Learned Sparse Representations
• Tensor-reduced atomic density representations
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• CPGD: Cadzow Plug-and-Play Gradient Descent for Generalised FRI
• On the Complexity of Robust PCA and ${\ell }_1$-norm Low-Rank Matrix Approximation
• FREDE: Anytime Graph Embeddings
• Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation
• Asymptotic Analysis of Sampling Estimators for Randomized Numerical Linear Algebra Algorithms
• Data Sketching for Large-Scale Kalman Filtering
• Ultra-Fast Accurate AoA Estimation via Automotive Massive-MIMO Radar
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• On the Complexity of Inner Product Similarity Join
• BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees
• A literature survey of matrix methods for data science
• Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets
• Stochastic Variance Reduction Methods for Saddle-Point Problems
• Guarantees for the Kronecker Fast Johnson-Lindenstrauss Transform Using a Coherence and Sampling Argument
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Structural-constrained Methods for the Identification of Unobservable False Data Injection Attacks in Power Systems
• Every Byte Matters: Traffic Analysis of Bluetooth Wearable Devices
• Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data
• Improved Analyses of the Randomized Power Method and Block Lanczos Method
• Dimensionality reduction of SDPs through sketching
• Integrating multiple random sketches for singular value decomposition
• Faster SGD Using Sketched Conditioning
• Sublinear Time Spectral Density Estimation
• Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition
• Bridging Dense and Sparse Maximum Inner Product Search
• Randomized block Gram-Schmidt process for solution of linear systems and eigenvalue problems
• A Fast Frequent Directions Algorithm for Low Rank Approximation
• A Fast Randomized Algorithm for Computing an Approximate Null Space
• Spectral Clustering via the Power Method -- Provably
• Randomized low-rank approximation for symmetric indefinite matrices
• Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
• Efficient error and variance estimation for randomized matrix computations
• A Sketched Finite Element Method for Elliptic Models
• A Random Matrix Theoretical Approach to Early Event Detection Using Experimental Data
• Approximating Hamiltonian dynamics with the Nyström method
• Fourier-sparse interpolation without a frequency gap
• Improved Differentially Private Euclidean Distance Approximation
• Manifold Reconstruction and Denoising from Scattered Data in High Dimension via a Generalization of $L_1$-Median
• On Recoverability of Randomly Compressed Tensors with Low CP Rank
• Approximation in the extended functional tensor train format
• A Distance-preserving Matrix Sketch
• Optimal Matrix Sketching over Sliding Windows
• Modewise Johnson-Lindenstrauss Embeddings for Nuclear Many-Body Theory
• Solving Ridge Regression using Sketched Preconditioned SVRG
• Revisiting Sub-sampled Newton Methods
• Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation
• Low rank approximation and decomposition of large matrices using error correcting codes
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Random Projection using Random Quantum Circuits
• Randomized linear algebra for model reduction. Part II: minimal residual methods and dictionary-based approximation
• Linear Discriminant Analysis with the Randomized Kaczmarz Method
• pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores
• Spectral estimation from simulations via sketching
• Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
• Effective sketching methods for value function approximation
• Compressed and Penalized Linear Regression
• Estimating leverage scores via rank revealing methods and randomization
• Analysis of Randomized Householder-Cholesky QR Factorization with Multisketching
• Adjusting Leverage Scores by Row Weighting: A Practical Approach to Coherent Matrix Completion
• Construction of Hierarchically Semi-Separable matrix Representation using Adaptive Johnson-Lindenstrauss Sketching
• Quadrature Sampling of Parametric Models with Bi-fidelity Boosting
• Unique reconstruction for discretized inverse problems: a random sketching approach via subsampling
• Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting
• Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation
• Optimal Sketching Bounds for Sparse Linear Regression
• Accurate principal component analysis via a few iterations of alternating least squares
• Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
• Convexification with bounded gap for randomly projected quadratic optimization
• Learning-Augmented Sketches for Hessians
• Two-level Nyström--Schur preconditioner for sparse symmetric positive definite matrices
• Regularized ERM on random subspaces
• Operator-Based Generalization Bound for Deep Learning: Insights on Multi-Task Learning
• Tensorization of neural networks for improved privacy and interpretability
• A geometric view of Biodiversity: scaling to metagenomics
• A general error analysis for randomized low-rank approximation methods
• One-Pass Sparsified Gaussian Mixtures
• Dictionary-based model reduction for state estimation
• Massive MIMO as a Big Data System: Random Matrix Models and Testbed