CODEWITHSUNDEEP
ralgorithmconvolution
ny439
ny439

Reputation: 23

How to convolve a vector with itself n times

Suppose I have a vector x which I want to convolve with itself n times. What is the good way to do this in R?

Suppose that we already have a function conv(u,v) that convolves two vectors.

I can do this:

autoconv<-function(x,n){
    r<-1;
    for(i in 1:n){
        r<-conv(r,x);
    }
    return(r);
}

is there a more efficient way?

Upvotes: 2

Views: 1631

Answers (2)

G. Grothendieck
G. Grothendieck

Reputation: 269684

Take the Fast Fourier Transform (fft) of x, raise it to the kth power and take the inverse fft. Then compare that to performing convolutions of k copies of x. No packages are used.

# set up test data
set.seed(123)
k <- 3 # no of vectors to convolve
n <- 32 # length of x
x <- rnorm(n)

# method 1 using fft and inverse fft
yy <- Re(fft(fft(x)^k, inverse = TRUE) / n)

# method 2 using repeated convolutions
y <- x
if (k >= 2) for(i in 2:k) y <- convolve(x, y, FALSE)

# check that the two methods give the same result
all.equal(y, yy)
## TRUE

Upvotes: 4

Museful
Museful

Reputation: 6959

autoconv <- function(x, n){
    if(n == 0){
        return(1)
    } else if(n == 1){
        return(x)
    } else {
        i <- 2
        xi <- conv(x,x)
        while(n %% i != 0){
            i <- i + 1
            xi <- conv(xi,x)
        }
        return(autoconv(xi,n/i))
    }
}

This will call conv() once for each prime factor of n, rather than n times.

Upvotes: 1

Related Questions