如何将向量与自身进行 n 次卷积

Question

假设我有一个向量 x，我想将它与自身进行 n 次卷积。在 R 中执行此操作的好方法是什么？

假设我们已经有一个函数 conv(u,v) 对两个向量进行卷积。

我能做到：

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

有没有更高效的方法？

Answer 1

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))
    }
}

这将为 n 的每个质因数调用一次 conv()，而不是 n 次。

Answer 2

取x的快速傅里叶变换(fft)，将其提高到k次方，然后取逆fft。然后将其与执行 k 份 x 的卷积进行比较。没有使用包。

# 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

如何将向量与自身进行 n 次卷积

How to convolve a vector with itself n times

r

algorithm

convolution