### 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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a |

Publisher | Springer Verlag |

Pages | 272-279 |

Number of pages | 8 |

ISBN (Print) | 3540380442, 9783540380443 |

DOIs | |

State | Published - Jan 1 2006 |

Event | 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, Spain Duration: Aug 28 2006 → Aug 30 2006 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 4110 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 |
---|---|

Country | Spain |

City | Barcelona |

Period | 8/28/06 → 8/30/06 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'A fast random sampling algorithm for sparsifying matrices'. Together they form a unique fingerprint.

## Cite this

Arora, S., Hazan, E., & Kale, S. (2006). A fast random sampling algorithm for sparsifying matrices. In

*Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a*(pp. 272-279). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4110 LNCS). Springer Verlag. https://doi.org/10.1007/11830924_26