convolve: Convolution of Sequences via FFT

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; partially matched to "circular", "open", "filter". 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 the middle sub-vector of "open", namely, the result of running a weighted mean of x with weights y.

Value

If r <- convolve(x, y, type = "open") and n <- length(x), m <- length(y), then $r_{k} = \sum_{i} x_{k - m + i} y_{i}$ where the sum is over all valid indices $i$ , for $k = 1, \dots, n + m - 1$ .

If type == "circular", $n = m$ is required, and the above is true for $i, k = 1, \dots, n$ when $x_{j} := x_{n + j}$ for $j < 1$ .

Details

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

The input sequences x and y must have the same length if circular is true.

Note that the usual definition of convolution of two sequences x and y is given by convolve(x, rev(y), type = "o").

References

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

Examples

Run this code

# NOT RUN {
require(graphics)

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)
# Circular convolution *has* this symmetry:
all.equal(convolve(x, y, conj = FALSE), rev(convolve(rev(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")
# }

Run the code above in your browser using DataLab

Last chance! 50% off unlimited learning