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.
%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
}