A Fast Random Sampling Algorithm for Sparsifying Matrices

DOI10.1007/11830924_26MaRDI QIDQ3595390zbMATH OpenOpenAlexFDO

Authors Elad Hazan, Satyen Kale, Sanjeev Arora

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11830924_26

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Sampling based succinct matrix approximation
• A fast randomized algorithm for the approximation of matrices
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Computing sparse approximations deterministically

Cited in

(21)

• Uniform sampling for matrix approximation
• A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• A fast randomized algorithm for computing an approximate null space
• Frequent directions: simple and deterministic matrix sketching
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• A compact sparse matrix representation using random hash functions
• Robust frequent directions with application in online learning
• Sampling and multilevel coarsening algorithms for fast matrix approximations.
• Comparison of matrix norm sparsification
• Sampling based succinct matrix approximation
• scientific article; zbMATH DE number 7008333 (Why is no real title available?)
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Compression of sparse matrices by blocked Rice coding
• Core-elements for large-scale least squares estimation
• Fast algorithm for the multiplication of a row vector by a randomly selected matrixA
• Recovering PCA and sparse PCA via hybrid-(_1,_2) sparse sampling of data elements
• Universal matrix sparsifiers and fast deterministic algorithms for linear algebra
• Compressing Rank-Structured Matrices via Randomized Sampling
• Faster least squares approximation
• ReliefE: feature ranking in high-dimensional spaces via manifold embeddings

This page was built for publication: A Fast Random Sampling Algorithm for Sparsifying Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3595390)