Thread Subject:

Minimum distances of one vector to another

Hi, i have a program that collapses a sphere onto a body, the program works well but my next step is finding the furthest point away from the body to determine the error. the method i got in there is

    j=2562
    win=zeros(m,1);
    for j=1:m
        win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
    end
    max(win)

where sdata is a 2562X3 matrix and data is a 52000X3 matrix. This program finds the minimum for every row of sdata and stores it in win then finds the maximum distance away from the body. This works okay but the for loop slows down my program by quite a bit and i am looking for suggestions on how to make my program more efficient. Any help would be appreciated and thanks in advance.

Robert Kirdeikis wrote:
> Hi, i have a program that collapses a sphere onto a body, the program works well but my next
> step is finding the furthest point away from the body to determine the error. the method i
> got in there is
 
> j=2562
> win=zeros(m,1);
> for j=1:m
> win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
> end
> max(win)
 
> where sdata is a 2562X3 matrix and data is a 52000X3 matrix. This program finds the
> minimum for every row of sdata and stores it in win then finds the maximum distance
> away from the body. This works okay but the for loop slows down my program by quite a
> bit and i am looking for suggestions on how to make my program more efficient.

Some small tweaking that might add up:

min(sqrt(X(j))) is sqrt(min(X(j)))

max(sqrt(min(X)) is sqrt(max(min(X))

Thus you can eliminate all of the sqrt() calls except for one last trivial one.

--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

Ive fixed the square root to perform the rooting outside the loop and it has saved a bit of time. Thank you for the suggestion. I am still looking for a built in matlab function or a matrix way to get rid of the for loop which is the main time consumer to find all the minimum distances in 3d of each point on my sdata vector to a point or surface made from my data vector

"Robert Kirdeikis" <kirdeiki@ualberta.ca> wrote in message <glkphu$6v$1@fred.mathworks.com>...
> Hi, i have a program that collapses a sphere onto a body, the program works well but my next step is finding the furthest point away from the body to determine the error. the method i got in there is
>
> j=2562
> win=zeros(m,1);
> for j=1:m
> win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
> end
> max(win)
>
> where sdata is a 2562X3 matrix and data is a 52000X3 matrix. This program finds the minimum for every row of sdata and stores it in win then finds the maximum distance away from the body. This works okay but the for loop slows down my program by quite a bit and i am looking for suggestions on how to make my program more efficient. Any help would be appreciated and thanks in advance.

Hi Robert,

bsxfun seems to allocate memory on order to calculate then with two matrices of equal size.
My test :
clc
A = magic(1000);
m = mean(A);
tic
for n = 1:20
    AA = bsxfun(@minus, A, m);
end
toc

tic
for n = 1:20
    for n = size(m, 2):-1:1
        AA2(:,n) = A(:,n)- m(n);
    end
end
toc

if you loop twice this should prevent unnecessary allocation

 j=2562
win=zeros(m,1);
for j=1:m

    win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
end
max(win)

gives
Elapsed time is 0.196413 seconds.
Elapsed time is 0.123616 seconds.

with Walters hint this looks rather like

 j=2562
win=zeros(m,1);
for j=1:m
    for n = size(sdata,2):-1:1
        tmp(n) = data-sdata(j,n);
    end
    win(j) = min(sum(tmp.^2));
    
% win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
end

sqrt(max(win))

hth kinor

"Robert Kirdeikis" <kirdeiki@ualberta.ca> wrote in message <glkphu$6v$1@fred.mathworks.com>...
> Hi, i have a program that collapses a sphere onto a body, the program works well but my next step is finding the furthest point away from the body to determine the error. the method i got in there is
>
> j=2562
> win=zeros(m,1);
> for j=1:m
> win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
> end
> max(win)
>
> where sdata is a 2562X3 matrix and data is a 52000X3 matrix. This program finds the minimum for every row of sdata and stores it in win then finds the maximum distance away from the body. This works okay but the for loop slows down my program by quite a bit and i am looking for suggestions on how to make my program more efficient. Any help would be appreciated and thanks in advance.

Hi Robert,

bsxfun seems to allocate memory on order to calculate then with two matrices of equal size.
My test :
clc
A = magic(1000);
m = mean(A);
tic
for n = 1:20
    AA = bsxfun(@minus, A, m);
end
toc

tic
for n = 1:20
    for n = size(m, 2):-1:1
        AA2(:,n) = A(:,n)- m(n);
    end
end
toc

if you loop twice this should prevent unnecessary allocation

 j=2562
win=zeros(m,1);
for j=1:m

    win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
end
max(win)

gives
Elapsed time is 0.196413 seconds.
Elapsed time is 0.123616 seconds.

with Walters hint this looks rather like

 j=2562
win=zeros(m,1);
for j=1:m
    for n = size(sdata,2):-1:1
        tmp(n) = data-sdata(j,n);
    end
    win(j) = min(sum(tmp.^2));
    
% win(j)=min(sqrt(sum(bsxfun(@minus,data,sdata(j,:)).^2,2)));
end

sqrt(max(win))

hth kinor

Thank you hth kinor, the time required to run the loop went down from tElapsed=6.186647 seconds to tElapsed=5.004199 seconds on a smaller iteration loop i used to test it. If anybody has any more ideas on how to shave off some computation time, id appreciate hearing your ideas

Robert:
I can't figure out why you're taking the square root. If you want to
find the closest or farthest distance, simply searching on the
distance squared will do it. No need to take the square root until
the search is done. I'm surprised no one else mentioned it -- am I
incorrect here?
Regards,
ImageAnalyst

ImageAnalyst
> No need to take the square root until the search is done.
> I'm surprised no one else mentioned it -- am I
> incorrect here...

yes, walter (first reply) has mentioned this about 2hrs ago...

:-)
us

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <1fa8fad2-d4a8-4ae2-a74d-d4c4cb1e827d@r36g2000prf.googlegroups.com>...
> Robert:
> I can't figure out why you're taking the square root. If you want to
> find the closest or farthest distance, simply searching on the
> distance squared will do it. No need to take the square root until
> the search is done. I'm surprised no one else mentioned it -- am I
> incorrect here?
> Regards,
> ImageAnalyst

  Walter already mentioned that in this thread.

Roger Stafford