Uniform Sampling for Matrix Approximation

DOI10.1145/2688073.2688113zbMath1365.65108arXiv1408.5099OpenAlexW2963098024MaRDI QIDQ2989029

Cameron Musco, Christopher Musco, Richard Peng, Michael B. Cohen, Aaron Sidford, Yin Tat Lee

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.5099

zbMATH Keywords

regressionmatrix samplingrandomized numerical linear algebraleverage scores

Mathematics Subject Classification ID

Related Items (20)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ A sketched finite element method for elliptic models ⋮ Unnamed Item ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Randomized algorithms in numerical linear algebra ⋮ Max-Plus Algebraic Statistical Leverage Scores ⋮ Minimum cost flow in the CONGEST model ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Core-Sets: Updated Survey ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ Sub-sampled Newton methods ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Unnamed Item ⋮ Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition

This page was built for publication: Uniform Sampling for Matrix Approximation