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

(22)

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

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)