%0 Conference Paper %1 DBLP:conf/approx/AroraHK06 %A Arora, Sanjeev %A Hazan, Elad %A Kale, Satyen %B APPROX-RANDOM %D 2006 %E D\'ıaz, Josep %E Jansen, Klaus %E Rolim, José D. P. %E Zwick, Uri %I Springer %K eigenvalues sparsification %P 272-279 %R 10.1007/11830924_26 %T A Fast Random Sampling Algorithm for Sparsifying Matrices %V 4110 %X 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. %@ 3-540-38044-2

@inproceedings{DBLP:conf/approx/AroraHK06, 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. }, added-at = {2011-04-23T21:06:26.000+0200}, author = {Arora, Sanjeev and Hazan, Elad and Kale, Satyen}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/2f615cfa21f3b6a83fe01d099c0484022/ytyoun}, booktitle = {APPROX-RANDOM}, crossref = {DBLP:conf/approx/2006}, doi = {10.1007/11830924_26}, editor = {D\'{\i}az, Josep and Jansen, Klaus and Rolim, Jos{\'e} D. P. and Zwick, Uri}, interhash = {dca569ceeb18cc5f3477e9b6331691cc}, intrahash = {f615cfa21f3b6a83fe01d099c0484022}, isbn = {3-540-38044-2}, keywords = {eigenvalues sparsification}, pages = {272-279}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2016-06-14T13:50:02.000+0200}, title = {A Fast Random Sampling Algorithm for Sparsifying Matrices}, volume = 4110, year = 2006 }