Thread Subject: euclidean distance

Hi everyone!
Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???

for i=1:size(A,1);
    for k=1:size(B,1);
Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
    end
end

Thank you in advance!!!!

First I would advise to preallocate the resulting matrix like

Eucl_Ideal=zeros(size(A,1),size(B,1));

in advance to the for loop.

Regards,
Stefan


"kudrah " <elzarogia@yahoo.gr> wrote in message <h2dp5l$p98$1@fred.mathworks.com>...
> Hi everyone!
> Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???
>
> for i=1:size(A,1);
> for k=1:size(B,1);
> Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
> end
> end
>
> Thank you in advance!!!!

"kudrah " <elzarogia@yahoo.gr> wrote in message <h2dp5l$p98$1@fred.mathworks.com>...
> Hi everyone!
> Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???
>
> for i=1:size(A,1);
> for k=1:size(B,1);
> Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
> end
> end
>
> Thank you in advance!!!!

This matrix will take roughly 300 megabytes to store.
This is one reason why it takes forever. A bigger reason
for the slowness is that you failed to preallocate the
memory.

Finally, you might convert to single precision to store
the distances, so this might work best:

D = bsxfun(@times,single(A(:,1)),single(B(:,1)).');
D = D + bsxfun(@times,single(A(:,2)),single(B(:,2)).');
D = D + bsxfun(@times,single(A(:,3)),single(B(:,3)).');
D = sqrt(D);

HTH,
John

kudrah wrote:
> Hi everyone!
> Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???
>
> for i=1:size(A,1);
> for k=1:size(B,1);
> Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
> end
> end

As others have said, preallocate the result. Also:

Because of the way data is stored in MATLAB, your loops are in the wrong order -- you want to have the row index in Eucl_Ideal varying fastest or you will be accessing memory very non-sequentially.

But most likely, you want to loop over 1:3 within 1:2000, and sum the squared diffs for each dimension of each point in B to all points in A, vectorized. This is essentially what John suggested with BSXFUN (though I think those ought to be @minus's, wrapped in .^2's). Here's an "unrolled loop" version.

Eucl_Ideal = zeros(size(A,1),size(B,1));
for i = 1:size(B,1);
    Eucl_Ideal(:,i) = sqrt((A(:,1)-B(i,1)).^2 + (A(:,2)-B(i,2)).^2 + (A(:,3)-B(i,3)).^2);
end

There's a good deal that can be learned about memory access and vectorization from this example. Hope this helps.

Hi peter,
Thank you very much.
Your solution was very helpful to me in my situation (except that I have 150 dimensions instead of 3 !).
In my situation, I just need the index (of point) of B which is nearest to each point in B. Instead of finding the pairwise distance and using min command, can I bypass this laborious calculation of calculating Euclidean distance to directly arrive at the indices.


regards,
ramana
 
> But most likely, you want to loop over 1:3 within 1:2000, and sum the squared diffs for each dimension of each point in B to all points in A, vectorized. This is essentially what John suggested with BSXFUN (though I think those ought to be @minus's, wrapped in .^2's). Here's an "unrolled loop" version.
>
> Eucl_Ideal = zeros(size(A,1),size(B,1));
> for i = 1:size(B,1);
> Eucl_Ideal(:,i) = sqrt((A(:,1)-B(i,1)).^2 + (A(:,2)-B(i,2)).^2 + (A(:,3)-B(i,3)).^2);
> end
>
> There's a good deal that can be learned about memory access and vectorization from this example. Hope this helps.