Summing without a for loop - MATLAB

Question

I have 2 matrices: V , which is square MxM and K , which is MxN. By invoking a measurement along rows x and dimension of columns t , I need to evaluate the integral (i.e. the sum) over both measurements K times, when the t-shifted version of V , the answer is a shift function (almost like a convolution, see below). The sum is defined by the following expression, where _{} denotes the summation indices, and zero addition of elements outside the limits is accepted:

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

I manage to do this with a single loop, in size t (vectorized dimension x ):

 % some toy matrices V = rand(50,50); K = rand(50,10); [MN] = 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 

I have similar expressions that I was able to evaluate without a for loop, using a combination of conv2 and \ or mirroring (clicking) a single dimension. However, I don’t see how to avoid the for loop in this case (despite the resemblance to convolution).

Answer 1

Vectorization Steps

1] Execute sum(bsxfun(@times, V(:,t:end), K(:,t)),1) for all columns in V for all columns in K with matrix multiplication -

 sum_mults = V.'*K 

This will give us a 2D array with each column representing the operation sum(bsxfun(@times,.. at each iteration.

2] Step 1 gave us all the possible amounts, as well as the values ​​that need to be summed, do not align in the same line by iteration, so we need to do a little more work before summing the lines. The rest of the work involves getting a shifted version. To do this, you can use logical indexing with an upper and lower triangular boolean mask. Finally, we summarize each line for final output. So this piece of code will look like this -

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

---

Runtime Tests -

 %// Inputs V = rand(1000,1000); K = rand(1000,200); disp('--------------------- With original loopy approach') tic [MN] = 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 

Exit -

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

Answer 2

It might be a hoax (using arrayfun instead of a for loop), but I believe this expression gives you what you want:

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