On Estimating the Large Entries of a Convolution

Get BibTex-formatted data

Author

Mikhail J. Atallah

Tech report number

CERIAS TR 2001-08

Entry type

article

Abstract

We give a Monte Carlo algorithm that computes an unbiased estimate of the convolution of two vectors. The variance of our estimate is small for entries of the convolution that are large; this corresponds to the situation in which convolution is used in pattern matching or template matching, where one is only interested in the largest entries of the resulting convolution vector. Experiments performed with our algorithm confirm the theory and suggest that, in contexts where one cares about only the large entries in the convolution, the algorithm can be a faster alternative to performing an FFT-based convolution.

Date

2001

URL

http://ieeexplore.ieee.org/sta ... p?tp=&arnumber=910811

Institution

CERIAS

Journal

IEEE Trans. on Computers

Key alpha

atallah

Number

Pages

193-196

Publisher

IEEE Trans. on Computers

Volume

Affiliation

Purdue University

Publication Date

1970-01-01

Subject

none

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ atallah,
	title = "On Estimating the Large Entries of a Convolution",
	author = "Mikhail J. Atallah",
	year = "2001",
	institution = "CERIAS",
	journal = "IEEE Trans. on Computers",
	number = "3",
	pages = "193-196",
	publisher = "IEEE Trans. on Computers",
	volume = "50",
	abstract = "We give a Monte Carlo algorithm that computes an unbiased estimate of the convolution of two vectors. The variance of our estimate is small for entries of the convolution that are large; this corresponds to the situation in which convolution is used in pattern matching or template matching, where one is only interested in the largest entries of the resulting convolution vector. Experiments performed with our algorithm confirm the theory and suggest that, in contexts where one cares about only the large entries in the convolution, the algorithm can be a faster alternative to performing an FFT-based convolution.",
	affiliation = "Purdue University",
	subject = "none",
	url = "http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=910811",
}