Speed-efficient classification for complex vectors in MATLAB

Question

I am trying to optimize this piece of code and get rid of the nested loop implemented. I am finding difficulties in applying a matrix to pdist function

For example, 1+j // -1+j // -1+j // -1-j are the initial points and i am trying to detect 0.5+0.7j to with point it belong by min distance approach .
any help is appreciated

function result = minDisDetector( newPoints, InitialPoints)
result = [];
for i=1:length(newPoints)
    minDistance = Inf;
    for j=1:length(InitialPoints)

        X = [real(newPoints(i)) imag(newPoints(i));real(InitialPoints(j)) imag(InitialPoints(j))];
        d = pdist(X,'euclidean');

        if d < minDistance
            minDistance = d;
            index = j;
        end
    end
    result = [result; InitialPoints(index)]; 
end     
end

Answer 1

You can use efficient euclidean distance calculation as listed in Speed-efficient classification in Matlab for a vectorized solution -

%// Setup the input vectors of real and imaginary into Mx2 & Nx2 arrays
A = [real(InitialPoints) imag(InitialPoints)];
Bt = [real(newPoints).' ; imag(newPoints).'];

%// Calculate squared euclidean distances. This is one of the vectorized
%// variations of performing efficient euclidean distance calculation using 
%// matrix multiplication linked earlier in this post.
dists = [A.^2 ones(size(A)) -2*A ]*[ones(size(Bt)) ; Bt.^2 ; Bt];

%// Find min index for each Bt & extract corresponding elements from InitialPoints
[~,min_idx] = min(dists,[],1);
result_vectorized = InitialPoints(min_idx);

---

Quick runtime tests with newPoints as 400 x 1 & InitialPoints as 1000 x 1:

-------------------- With Original Approach
Elapsed time is 1.299187 seconds.
-------------------- With Proposed Approach
Elapsed time is 0.000263 seconds.

Answer 2

The solution is very simple. However you do need my cartprod.m function to generate a cartesian product.

First generate random complex data for each variable.

newPoints = exp(i * pi * rand(4,1));
InitialPoints = exp(i * pi * rand(100,1));

Generate the cartesian product of newPoints and InitialPoints using cartprod.

C = cartprod(newPoints,InitialPoints);

The difference of column 1 and column 2 is the distance in complex numbers. Then abs will find the magnitude of the distance.

A = abs( C(:,1) - C(:,2) );

Since the cartesian product is generated so that it permutates newPoints variables first like this:

 1     1
 2     1
 3     1
 4     1
 1     2
 2     2
 ...

We need to reshape it and get the minimum using min to find the minimum distance. We need the transpose to find the min for each newPoints. Otherwise without the transpose, we will get the min for each InitialPoints.

[m,i] = min( reshape( D, length(newPoints) , [] )' );

m gives you the min, while i gives you the indices. If you need to get the minimum initialPoints, just use:

result = initialPoints( mod(b-1,length(initialPoints) + 1 );

Answer 3

It is possible to eliminate the nested loop by introducing element-wise operations using the euclidean norm for calculating the distance as shown below.

    result = zeros(1,length(newPoints)); % initialize result vector
    for i=1:length(newPoints)
        dist = abs(newPoints(i)-InitialPoints); %calculate distances
        [value, index] =  min(dist);
        result(i) = InitialPoints(index);
    end