performance - 没有 for 循环的求和 - MATLAB

Question

我有 2 个矩阵:V 是方阵 MxM，K 是 MxN。调用跨行维度 x 和跨列维度 t，我需要计算 K 两个维度的积分(即总和) V 的 t 移位版本，答案是移位的函数(几乎像卷积，见下文)。总和由以下表达式定义，其中 _{} 表示总和索引，并假定零填充超出限制的元素:

S(t) = sum_{x,tau}[V(x,t+tau) * K(x,tau)]

我设法用一个循环在 t 维度上完成(矢量化 x 维度):

% some toy matrices
V = rand(50,50);
K = rand(50,10);
[M N] = size(K);

S = zeros(1, M);            
for t = 1 : N
  S(1,1:end-t+1) = S(1,1:end-t+1) + sum(bsxfun(@times, V(:,t:end),  K(:,t)),1);                
end 

我有类似的表达式，我设法在没有 for 循环的情况下使用 conv2 和\或单个维度的镜像(翻转)的组合对其进行评估。但是我看不出在这种情况下如何避免 for 循环(尽管看起来与卷积相似)。

Answer 1

矢量化步骤

1] 针对 K 中的所有列对 V 中的所有列执行 sum(bsxfun(@times, V(:,t:end), K(:,t)),1)矩阵乘法 -

sum_mults = V.'*K

这将为我们提供一个二维数组，其中每一列代表每次迭代时的 sum(bsxfun(@times,.. 操作。

2] 步骤 1 为我们提供了所有可能的求和，并且要求和的值在迭代中未在同一行中对齐，因此我们需要在沿行求和之前做更多的工作。剩下的工作是关于获得一个升级版本。同样，您可以使用带有上下三角 bool 掩码的 bool 索引。最后，我们对每一行求和以获得最终输出。所以，这部分代码看起来像这样 -

valid_mask = tril(true(size(sum_mults)));
sum_mults_shifted = zeros(size(sum_mults));
sum_mults_shifted(flipud(valid_mask)) = sum_mults(valid_mask);
out = sum(sum_mults_shifted,2);

---

运行时测试 -

%// Inputs
V = rand(1000,1000);
K = rand(1000,200);

disp('--------------------- With original loopy approach')
tic
[M N] = size(K);
S = zeros(1, M);
for t = 1 : N
    S(1,1:end-t+1) = S(1,1:end-t+1) + sum(bsxfun(@times, V(:,t:end),  K(:,t)),1);
end
toc

disp('--------------------- With proposed vectorized approach')
tic
sum_mults = V.'*K; %//'
valid_mask = tril(true(size(sum_mults)));
sum_mults_shifted = zeros(size(sum_mults));
sum_mults_shifted(flipud(valid_mask)) = sum_mults(valid_mask);
out = sum(sum_mults_shifted,2);
toc

输出-

--------------------- With original loopy approach
Elapsed time is 2.696773 seconds.
--------------------- With proposed vectorized approach
Elapsed time is 0.044144 seconds.