@inproceedings{b3e3843b145641a4b7775cefccdce116,
title = "A fast random sampling algorithm for sparsifying matrices",
abstract = "We describe a simple random-sampling based procedure for producing sparse matrix approximations. Our procedure and analysis are extremely simple: the analysis uses nothing more than the Chernoff-Hoeffding bounds. Despite the simplicity, the approximation is comparable and sometimes better than previous work. Our algorithm computes the sparse matrix approximation in a single pass over the data. Further, most of the entries in the output matrix are quantized, and can be succinctly represented by a bit vector, thus leading to much savings in space.",
author = "Sanjeev Arora and Elad Hazan and Satyen Kale",
year = "2006",
doi = "10.1007/11830924_26",
language = "English (US)",
isbn = "3540380442",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "272--279",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a",
address = "Germany",
note = "9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 ; Conference date: 28-08-2006 Through 30-08-2006",
}