Manipulation of matrix addition and multiplication.

Hello Friends,

I have the following:

A = [1 2 3; 4  5 6; 7 8 9];
B = [10 11 12; 13 14 15];

[N1, D1] = size(A);
[N2, D2] = size(B);

A_sq = sum(A.^2, 2);
B_sq = sum(B.^2, 2)';
D = A_sq(:,ones(1,N2)) + B_sq(ones(1,N1),:) - 2.*(A*B');

where D is N1 x D1 matrix.

I want to write expression for D in one single step, i.e., something like this (this is for illustration purpose, but it should compute the same Euclidean distance as the code above):

D = sum(X - C).^2;

I will appreciate any advise.

[the cyclist]

Here is a more streamlined version of your code. It is not particularly more elegant, except for the use of bsxfun to eliminate the need for some intermediate variables.

A = [1 2 3;
     4 5 6;
     7 8 9];

B = [10 11 12;
     13 14 15];

D = bsxfun(@plus,sum(A.^2, 2),sum(B'.^2, 1))  - 2.*(A*B');

[the cyclist]

Also, this equivalent formulation seems closer to your prototype formula, but I still don't quite see a simpler set of matrix operations to get you there:

D = bsxfun(@plus,diag(A*A'),diag(B*B')')  - 2.*(A*B')

(I think this version is likely more computationally intensive, but somewhat more elegant.)

[James Tursa]

How is this different from this earlier post which was already answered?

http://www.mathworks.com/matlabcentral/answers/299781-rewriting-a-vector-addition-and-multiplication

Answer 1

[Matt J]

 Bp=permute(B,[3,2,1]);

 D=reshape(   sum(bsxfun(@minus, A, Bp).^2,2))    , N1,N2);

[hello_world]

Does it work for any N1 x D1 and N2 x D2 matrices where D1 = D2, but N1 ~= N2?

[Matt J]

If you don't know whether it works, it means you didn't try it ;)

However, note the edit to my Answer, which uses reshape instead of squeeze. I think it will make the solution quite general.

[the cyclist]

I did not thoroughly test this, but I feel like permuting again would be a better option than reshaping, and it avoids the need to do the size check:

Bp =permute(B,[3,2,1]);
D = permute(sum(bsxfun(@minus, A, Bp).^2,2),[1 3 2]);

[Matt J]

Well... permutes are expensive as compared to reshapes. I was seeking to minimize them. It is possible to do this entirely without permutes/transposes if the OP had organized the 3x1 vectors in matrix columns instead of matrix rows.

[the cyclist]

I repmat'ed his matrices to make them pretty huge, and found nearly identical timing for the reshape algorithm and the permute algorithm.

Interestingly, my original solution (in the comments)

D = bsxfun(@plus,sum(A.^2, 2),sum(B'.^2, 1))  - 2.*(A*B');

absolutely crushed both of these in timing.

So, as always, best to try to solve the problem (multiple ways if possible!), and then do optimization.