A fast convolution method applicable to convolving a signal (indicative of an
n-dimensional
pattern, where n is greater than or equal to two) with a smooth kernel that can
be approximated by a separated-spline kernel, and a system configured to perform
such method using software or signal processing circuitry. Unlike Fourier-based
convolution methods which require on the order of N log N arithmetic operations
for a signal of length N, the method of the invention requires only on the order
of N arithmetic operations to do so. Unlike wavelet-based convolution approximations
(which typically also require more arithmetic operations than are required in accordance
with the invention to convolve the same signal), the method of the invention is
exact for convolution kernels which are spline kernels.
