Fast convolution and Fast Fourier Transform under interval and fuzzy uncertainty

作者：Liu, Guoqing; Kreinovich, Vladik^*

来源：Journal of Computer and System Sciences, 2010, 76(1): 63-76.

DOI：10.1016/j.jcss.2009.05.006

• Convolution
• Fourier transform
• Interval uncertainty
• Fuzzy uncertainty

Convolution y(t) = integral a(t - s) . x(s)ds is one of the main techniques in digital signal processing. A straightforward computation of the convolution y(t) requires O(n(2)) steps, where n is the number of observations x(t(0)), ..., x(t(n-1)). It is well known that by using the Fast Fourier Transform (FFT) algorithm. we can compute convolution much faster, with computation time O (n . log(n)).
In practice, we only know the signal x(t) and the function a(t) with uncertainty. Sometimes, we know them with interval uncertainty, i.e., we know intervals [(x) under bar (t), (x) over bar (t)] and [(a) under bar (t), (a) over bar (t)] that contain the actual (unknown) functions x(t) and a(t). In such situations, it is desirable, for every t, to compute the range [(y) under bar (t), (y) over bar (t)] of possible values of y(t). Of course, it is possible to use straightforward interval computations to compute this range, i.e., replace every computational step in FFT by the corresponding operations of interval arithmetic. However, the resulting enclosure is too wide. In this paper, we show how to provide asymptotically accurate ranges for y(t) in time O(n . log(n)).
We also explain how to use these new algorithms to compute the convolution (and the Fourier transform) under fuzzy uncertainty.

• 出版日期2010-2
• 单位南京工业大学