Sommation sans une boucle - MATLAB

Question

J'ai 2 matrices: V qui est carré MxM, et K qui est MxN. Appelant la dimension entre les lignes x et la dimension entre les colonnes t, j'ai besoin d'évaluer l'intégrale (somme) sur les deux dimensions de K fois une version t-décalée de V, la réponse étant une fonction du décalage (presque comme une convolution, voir ci-dessous). La somme est définie par l'expression suivante, où _{} désigne les indices de sommation, et un zéro-padding d'éléments hors-limites est supposé:

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

je réussi à le faire avec une seule boucle, sur t dimension (vectorisation la x dimension):

% 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 

J'ai des expressions semblables que je réussi à évaluer sans boucle, en utilisant une combinaison de conv2 et \ ou en miroir (retournement) d'une seule dimension. Cependant, je ne vois pas comment éviter une boucle for dans ce cas (malgré la ressemblance apparente à la convolution).

Answer 1

Étapes pour vectorisation

1] Perform sum(bsxfun(@times, V(:,t:end), K(:,t)),1) pour tous colonnes en V contre toutes les colonnes en K avec multiplication matricielle -

sum_mults = V.'*K 

Cela nous donnerait un tableau 2D avec chaque colonne représentant sum(bsxfun(@times,.. opération à chaque itération. 2] L'étape 1 nous a donné toutes les sommations possibles et les valeurs à additionner ne sont pas alignées dans la même rangée à travers les itérations, nous devons donc faire un peu plus de travail avant de faire la somme des lignes. Le reste du travail consiste à obtenir une version décalée. Pour le même, vous pouvez utiliser l'indexation booléenne avec un masque booléen triangulaire supérieur et inférieur. Enfin, nous somme le long de chaque ligne pour la sortie finale. Ainsi, cette partie du code ressemblerait donc -

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

---

essais d'exécution -

%// 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 

Sortie -

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

Answer 2

Cela pourrait être la tricherie (à l'aide arrayfun au lieu d'une boucle for) mais je crois que cette expression vous donne ce que vous voulez:

S = arrayfun(@(t) sum(sum(V(:,(t+1):(t+N)) .* K)), 1:(M-N), 'UniformOutput', true)