Random sampling for estimating the performance of fast summations

View/ Open
Date
2010-10-18Author
Srinivasan, Balaji Vasan
Duraiswami, Ramani
Metadata
Show full item recordAbstract
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.