@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",

month = jan,

day = "1",

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",

}