How to compute a fast outer product between two matrices, in Matlab?

Question

I have two n-by-m matrices, A and B. I want to create a new matrix C which is something like:

for i = 1:n
    C = C + outerProduct(A(i,:), B(i,:));
end

i.e. C is a matrix of size m x m, the sum of all outer products of the rows of A and B.

Is there a fast way to do it without a for loop (given that for loops are notoriously slow in Matlab)?

Solution 1

The operation you are performing (the sum of the row outer products) is equivalent to the multiplication of a transposed version of A with B:

C = A.'*B;

You can see this using the following example:

>> mat = magic(5);  %# A sample 5-by-5 matrix
>> A = mat(1:4,:);  %# Create a 4-by-5 matrix
>> B = mat(2:5,:);  %# Create another 4-by-5 matrix

>> C = zeros(5);  %# Initialize C to be 5-by-5
>> for i = 1:4, C = C + A(i,:).'*B(i,:); end;  %'# Calculate C as you are now

>> isequal(C, A.'*B)  %'# Test for equality with the shorter solution

ans =

     1  %# Equal!

Solution 2

Have you profiled your for loop code and found it to be too slow? If not, do it before you spend too much time agonizing over the loop penalty.

Your for loop is not particularly bad because you loop only n times but do O(n*m) work each loop. Since you're doing a lot of work each iteration, the loop penalty doesn't hit as hard. The really bad situations are nested loops, e.g. if you calculated the outer products with nested for loops too.

Solution 3

Perhaps I am misunderstanding, but I believe what you are looking for is

C = A*B';

Comments

[kloop]

No, that wouldn't be it -- this uses the inner product for each cell.

[Nzbuu]

$C_{ij} = \sum_k A_{ki} B_{kj} = \sum_k A^T_{ik} B_{kj} = A^T * B$

[gnovice]

That would produce an n-by-n result, not an m-by-m result.

[nbro]

For loops are very discouraged when working with Matlab. It's a "standard" rule of thumb, not just in Matlab, but in all programming languages which are used in numerical computing and related fields. If you can "vectorize" your operations, some optimizations can be performed and your code can run e.g. on the GPU more efficiently.