快速计算`dot(a(n:end), b(1:end-n))`

Question

假设我们有两个值 a 和 b 的一维数组，它们的长度都为 N。我想创建一个新数组 c 这样 c(n)=dot(a(n:N), b(1:N-n+1)) 我当然可以使用一个简单的循环来做到这一点：

for n=1:N
    c(n)=dot(a(n:N), b(1:N-n+1));
end

但鉴于这是一个类似于卷积的简单操作，我想知道是否有更有效的方法来执行此操作（使用 Matlab）。

Answer 1

这是一个有趣的问题！

我假设 a 和 b 是相同长度的列向量。让我们考虑一个简单的例子：

a = [9;10;2;10;7];
b = [1;3;6;10;10];
% yields:
c = [221;146;74;31;7];

现在让我们看看计算这些向量的卷积时会发生什么：

>> conv(a,b)
ans =
     9
    37
    86
   166
   239
   201
   162
   170
    70

>> conv2(a, b.')
ans =
     9    27    54    90    90
    10    30    60   100   100
     2     6    12    20    20
    10    30    60   100   100
     7    21    42    70    70

我们注意到 c 是 conv2 结果的下对角线上元素的总和。为了更清楚地显示，我们将转置以获得与 c:

中的值相同顺序的对角线

>> triu(conv2(a.', b))
ans =
     9    10     2    10     7
     0    30     6    30    21
     0     0    12    60    42
     0     0     0   100    70
     0     0     0     0    70

所以现在它变成了对矩阵的对角线求和的问题，这是 a more common problem 现有的解决方案，例如 Andrei Bobrov 的这个解决方案：

C = conv2(a.', b);
p = sum( spdiags(C, 0:size(C,2)-1) ).'; % This gives the same result as the loop.

Answer 2

使用一维卷积的解决方案conv:

out = conv(a, flip(b));
c = out(ceil(numel(out)/2):end);

在 conv 中，第一个向量乘以第二个向量的反向版本，因此我们需要计算 a 的卷积以及翻转的 b 和 trim 不必要的部分。

快速计算`dot(a(n:end), b(1:end-n))`

Quickly compute `dot(a(n:end), b(1:end-n))`

algorithm

matlab

vector

convolution

numerical-methods