Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Minimum distances of one vector to another

Subject: Minimum distances of one vector to another

From: Robert Kirdeikis

Date: 26 Jan, 2009 16:49:02

Message: 1 of 9

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.

Subject: Minimum distances of one vector to another

From: Walter Roberson

Date: 26 Jan, 2009 17:29:55

Message: 2 of 9

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)?

Subject: Minimum distances of one vector to another

From: Robert Kirdeikis

Date: 26 Jan, 2009 17:48:02

Message: 3 of 9

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

Subject: Minimum distances of one vector to another

From: nor ki

Date: 26 Jan, 2009 17:50:19

Message: 4 of 9

"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

Subject: Minimum distances of one vector to another

From: nor ki

Date: 26 Jan, 2009 17:55:03

Message: 5 of 9

"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

Subject: Minimum distances of one vector to another

From: Robert Kirdeikis

Date: 26 Jan, 2009 18:28:03

Message: 6 of 9

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

Subject: Minimum distances of one vector to another

From: ImageAnalyst

Date: 26 Jan, 2009 19:28:05

Message: 7 of 9

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

Subject: Minimum distances of one vector to another

From: us

Date: 26 Jan, 2009 19:39:01

Message: 8 of 9

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

Subject: Minimum distances of one vector to another

From: Roger Stafford

Date: 26 Jan, 2009 19:39:02

Message: 9 of 9

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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us