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)- Sub-sampled Newton methods
- A sketched finite element method for elliptic models
- _p row sampling by Lewis weights
- Single pass spectral sparsification in dynamic streams
- Core-sets: updated survey
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- Weighted SGD for _p regression with randomized preconditioning
- Constructing linear-sized spectral sparsification in almost-linear time
- Randomized algorithms in numerical linear algebra
- Max-Plus Algebraic Statistical Leverage Scores
- Second-order stochastic optimization for machine learning in linear time
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Density independent algorithms for sparsifying k-step random walks
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Rigidity of random subgraphs and eigenvalues of stiffness matrices
- Real-valued embeddings and sketches for fast distance and similarity estimation
- The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
- Online row sampling
- Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Minimum cost flow in the CONGEST model
- 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
- Imaging of atmospheric dispersion processes with differential absorption lidar
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Quantum speedups for linear programming via interior point methods
- Online Lewis weight sampling
- Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
- Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- Accelerated double-sketching subspace Newton
- Adaptive power method: eigenvector estimation from sampled data
- Leverage score sampling for faster accelerated regression and ERM
- A very sketchy talk (invited talk)
- Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
- Sampling based succinct matrix approximation
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)
