On estimating the large entries of a convolution

Authors
Citation
Mj. Atallah, On estimating the large entries of a convolution, IEEE COMPUT, 50(3), 2001, pp. 193-196
Citations number
9
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON COMPUTERS
ISSN journal
00189340 → ACNP
Volume
50
Issue
3
Year of publication
2001
Pages
193 - 196
Database
ISI
SICI code
0018-9340(200103)50:3<193:OETLEO>2.0.ZU;2-O
Abstract
We give a Monte Carlo algorithm that computes an unbiased estimate of the c onvolution of two vectors. The variance of our estimate is small for entrie s of the convolution that are large; this corresponds to the situation in w hich convolution is used in pattern matching or template matching, where on e is only interested in the largest entries of the resulting convolution ve ctor. Experiments performed with our algorithm confirm the theory and sugge st that, in contexts where one cares about only the large entries in the co nvolution, the algorithm can be a faster alternative to performing an FFT-b ased convolution.