Random sampling for estimating the performance of fast summations

Thumbnail Image
Files
CS-TR-4969.pdf(56.99 KB)
No. of downloads: 601
Publication or External Link
Date
2010-10-18
Authors
Srinivasan, Balaji Vasan
Duraiswami, Ramani
Advisor
Citation
DRUM DOI
Abstract
Summation of functions of N source points evaluated at M target points occurs commonly in many applications. To scale these approaches for large datasets, many fast algorithms have been proposed. In this technical report, we propose a Chernoff bound based efficient approach to test the performance of a fast summation algorithms providing a probabilistic accuracy. We further validate and use our approach in separate comparisons.
Notes
Rights