R: Fast Convolution

convolve {base}

R Documentation

Fast Convolution

Description

Use the Fast Fourier Transform to compute the several kinds of convolutions of two sequences.

Usage

convolve(x, y, conj = TRUE, type = c("circular", "open", "filter"))

Arguments

x, y

numeric sequences of the same length to be convolved.

conj

logical; if TRUE, take the complex conjugate before back-transforming (default, and used for usual convolution).

type

character; one of "circular", "open", "filter" (beginning of word is ok). For circular, the two sequences are treated as circular, i.e., periodic.

For open and filter, the sequences are padded with 0s (from left and right) first; "filter" returns a the middle sub-vector of "open", namely, the result of running a weighted mean of x with weights y.

Details

The Fast Fourier Transform, fft, is used for efficiency.

The input sequences x and y must have the same length if circular = TRUE).

Value

If r <- convolve(x,y, conj=TRUE, type) and n <- length(x), then

r_k = \sum_{i=1}^n x_i y_{k-i}

for k = 1,\dots,n.

If type == "circular", then y_{j} = y_{n+j} for j < 0.

References

Brillinger, D. R. (1981). Time Series: Data Analysis and Theory, Second Edition. San Francisco: Holden-Day.

Examples

x <- c(0,0,0,100,0,0,0)
y <- c(0,0,1, 2 ,1,0,0)/4
zapsmall(convolve(x,y))		#  *NOT* what you first thought..
zapsmall(convolve(x, y[3:5], type="f")) # rather
x <- rnorm(50);y <- rnorm(50)
all(convolve(x,y), convolve(y,x))
all(convolve(x,y, conj = FALSE), rev(convolve(y,x)))

n <- length(x <- -20:24)
y <- (x-10)^2/1000 + rnorm(x)/8

Han <- function(y) # Hanning
       convolve(y, c(1,2,1)/4, type = "filter")

plot(x,y, main="Using  convolve(.) for Hanning filters")
lines(x[-c(1  , n)      ], Han(y), col="red")
lines(x[-c(1:2, (n-1):n)], Han(Han(y)), lwd=2, col="dark blue")

[Package base version 0.64.2 ]