Uniform sampling for matrix approximation
From MaRDI portal
Abstract: Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances. We take a fresh look at uniform sampling by examining what information it does preserve. Specifically, we show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, it is enough to compute a better approximation. This observation leads to simple iterative row sampling algorithms for matrix approximation that run in input-sparsity time and preserve row structure and sparsity at all intermediate steps. In addition to an improved understanding of uniform sampling, our main proof introduces a structural result of independent interest: we show that every matrix can be made to have low coherence by reweighting a small subset of its rows.
Recommendations
Cited in
(36)- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Rigidity of random subgraphs and eigenvalues of stiffness matrices
- Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- _p row sampling by Lewis weights
- Single pass spectral sparsification in dynamic streams
- Sub-sampled Newton methods
- Constructing linear-sized spectral sparsification in almost-linear time
- Accelerated double-sketching subspace Newton
- Minimum cost flow in the CONGEST model
- Second-order stochastic optimization for machine learning in linear time
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- Weighted SGD for _p regression with randomized preconditioning
- Imaging of atmospheric dispersion processes with differential absorption lidar
- Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
- Adaptive power method: eigenvector estimation from sampled data
- Leverage score sampling for faster accelerated regression and ERM
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Online row sampling
- The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
- Sampling based succinct matrix approximation
- A very sketchy talk (invited talk)
- Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Quantum speedups for linear programming via interior point methods
- Online Lewis weight sampling
- A sketched finite element method for elliptic models
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Density independent algorithms for sparsifying k-step random walks
- Max-Plus Algebraic Statistical Leverage Scores
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Core-sets: updated survey
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- Randomized algorithms in numerical linear algebra
- A novel approach for estimating blood flow dynamics factors of eccentric stenotic arteries based on ML
- Real-time sensor selection for time-varying networks with guaranteed performance
This page was built for publication: Uniform sampling for matrix approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989029)
