How can I perform matrix operation efficiently?

I have an array X(n,m) where m<<n and n can be very large. First, I want to create a 3-d array of dimension (m,m,n) such that each mxm matrix in the nth location is the outer product of the n-th m-dimensional row in the original X- array.

Then I want to form a weighted sum all the mxm arrays where the weights are the elements of another n-dimensional array, Y(n).

result=zeros(m);
for i=1:n
   result = result +  Y(i) * X(i,:)' * X(i,:);
end

I could do this in the loop, but I think it would be slow when n is very large, compared to if there were a way to do all this with some matrix operation functions in MATLAB.

[per isakson]

"I think it would be slow when n is very large" . Did you make a test?

[dpb]

Needs to preallocate the full 3D array, however, and store into it; otherwise it'll be the classic case of reallocation and memory thrashing as he adds planes.

That said, I'd think it likely to be reasonably-decent performing. The alternatives seem to be accumarray and the like which are basically loops themselves...

[Dan Gianotti]

Hah! This is exactly the question I was about to ask (presumably implementing some version of the EM algorithm?)!

Did you determine if Roger's loop or James's vectorized version was faster?

Answer 1

[Roger Stafford]

If m is much smaller than n and assuming Y is a column vector, try this:

 R = zeros(m);
 TX = X';
 for ix = 1:m
   R(:,ix) = TX*(X(:,ix).*Y); % <-- R is 'result'
 end

[Ranjan Sonalkar]

Thanks. Very nice. I was doing a loop on n (10000). I changed it to your code to loop on m (3) and this part of the code ran 600 times faster.

Answer 2

[James Tursa]

This is vectorized, but it creates potentially large intermediate arrays, so I don't know if it will be any faster than your simple loop. Strictly from a memory use perspective, the simple loop is better.

XT = X';
XTc = reshape(XT,m,1,n);
XTr = reshape(XT,1,m,n);
XTX = bsxfun(@times,XTc,XTr);
Yn = reshape(Y,1,1,n);
YXTX = bsxfun(@times,Yn,XTX);
result = sum(YXTX,3);