7 views (last 30 days)

I have 2 matrices, both of them are feature matrices, M1 is 9216x26310, M2 is 9216x34000. each column represents 9216x1 represents one feature for a particular image, in this case 26310 images for the M1, 34000 for M2. I want to speed up the time for it to calculate euclidean distance, my current code takes average 1.3 secs or 1.4 secs per calculation.

tic;

for idx = 1:Number_of_Test_Images

for TrnIdx = 1 : Number_of_Train_Images

E_distance(TrnIdx) = sqrt(sum(abs((ftest(:,idx)-ftrain(:,TrnIdx)).^2)));

end

%

%[smallest_value, Idx_smallest] = min(E_distance);

%

Esimate_Test_labels(idx,1) = TrnLabels(Idx_smallest,1);

toc;

end

even if I replace the nested for loop with this

[smallest_value,Idx_smallest] = min(sum(abs(bsxfun(@minus,ftest(:,idx),ftrain))));

it still takes roughly the same time, although this one doesn't calculate sqrt.

Is there other way to speed this up to about 0.2 secs per calculation?

I have a i7 6700k CPU sadly no Nvidia GPU, owning AMD GPU. Else I can use gpuarray to speed things up.

Any ideas guys?

Both matrices are type double, I've tried to use sparse double on the my original code, my computer hangs every time after it reaches maximum memory usage, had to restart. and Sparse double matrices actually takes longer to compute.

Update! I've tried convert both matrices into single precision, and it runs faster, average of 0.63 secs per calculation by using the formula below, which runs the fastest compare to others.

I still need it to run faster, preferably under 0.2 secs if that's possible.

for TrnIdx = 1 : Number_of_Train_Images

E_distance(TrnIdx) = norm(ftest(:,idx)-ftrain(:,TrnIdx));

end

% runs averagely of 0.63secs which is the best at the moment, after converting both matrices from double to single, double runs at 1.05secs

Ahmet Cecen
on 30 Dec 2016

If you have the stats & ML toolbox:

NS = createns(M1'); % Create Search Object for The Train Set

Idx = knnsearch(NS,M2'); % Search Nearest Element of M1 for Each Element in M2

This should be lightning fast compared to your original code, probably would take around 20-30 minutes for the entire task. If you run out of memory, chunk the test matrix into smaller groups, and provide that as input, instead of looping over them one-by-one with i.

Ahmet Cecen
on 31 Dec 2016

Are you sure you are using the Tranpose matrices? Each row should be an image, each column a dimension.

This works for me without any error.

Here:

A = rand(9216,26310);

>> B = rand(9216,10);

>> tic;NS = createns(A');toc;

Elapsed time is 1.410517 seconds.

>> tic; Idx = knnsearch(NS,B'); toc;

Elapsed time is 1.992841 seconds.

>> Idx

Idx =

15172

22166

1461

17563

6626

16701

12601

10224

16658

15376

Your code results:

tic;

for idx = 1:10

for TrnIdx = 1 : 26310

E_distance(TrnIdx) = sqrt(sum(abs((B(:,idx)-A(:,TrnIdx)).^2)));

end

[smallest_value, Idx_smallest] = min(E_distance);

YourMethodIDX(idx) = Idx_smallest;

end

toc;

Elapsed time is 11.048696 seconds.

YourMethodIDX'

ans =

15172

22166

1461

17563

6626

16701

12601

10224

16658

15376

Note that while the speed improvement here is marginal, it will be Orders of Magnitude faster if you input your entire matrix.

Matt J
on 30 Dec 2016

Edited: Matt J
on 30 Dec 2016

E_distance = DNorm2( bsxfun(@minus,ftest(:,idx),ftrain) ,1) ; %Equation (*)

You could also try parallelizing the outer loop with parfor and maybe even the computation of E_distance as well (break ftrain into smaller parallel chunks and perform pieces of Equation (*) above on different workers).

Finally, if ftest and ftrain are type double, you might try moving to type single.

Matt J
on 31 Dec 2016

No, it's usually not a big problem. Tech support might be able to help you with the installation.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 14 Comments

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417107

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417107

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417110

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417110

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417139

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417139

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417159

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417159

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417164

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417164

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417165

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417165

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417173

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417173

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417203

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417203

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417257

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417257

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417259

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417259

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417260

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417260

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417262

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417262

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417263

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417263

## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417266

⋮## Direct link to this comment

https://es.mathworks.com/matlabcentral/answers/318619-speed-up-matrix-subtraction-for-euclidean-distance-calculation#comment_417266

Sign in to comment.