Optimize matlab for loop for big data

Question

I want to calculate the Euclidean distance between two images using the Hyperbolic Tangent (Sigmoid) kernel. Please follow this link where I have discussed the same problem using Gaussian Kernel in detail.

If x=(i,j) & y=(i1,j1) are any two pixels in our image then for hyperbolic tangent kernel, my H(x,y) will be defined as: H(i,j) = tanh(alpha*(x'*y) + c) where alpha and c are parameters and x' is the transpose of x. Parameter alpha can be taken as 1/N where N is my image dimension(8192 x 200 in my case) and c can take any value according to the problem. More detailed description about Hyperbolic Tangent kernel can be found here.

To achieve my goal & keeping the running time under consideration, I have written the below MATLAB script.

gray1=zeros(8192,200);
gray2=zeros(8192,200);

s1 = 8192;
s2 = 200;

alpha = s1*s2;

perms = combvec(1:s2,1:s1);
perms = [perms(2,:);perms(1,:)]';
perms1 = perms;

gray1(4096,100) = 10;
gray2(10,100) = 10;
img_diff = gray1 - gray2;

display('Calculation of Sigmoid Kernel started');

for i = 1:length(perms1)
    kernel = sum(bsxfun(@times,perms,perms1(i,:))');
    kernel1 = tanh((1/alpha)*kernel + 1)';
    g_temp(i) = img_diff(:)'*kernel1;
end

temp = g_temp*img_diff(:);
ans = sqrt(temp);

In spite of my all efforts I couldn't vectorize it further so as to decrease its running cost. Currently, it is taking around 29 hours to complete which is too much for me as I want to run it for various different images. I want to give it a completely vectorized form using intrinsic MATLAB functions as it was done by @dan-man in the case of Gaussian Kernel. With his help the Gaussian Version was taking 1-2 secs to complete. I tried my best to use the same conv2fft function in this case also but it seems difficult to find a way to achieve that.

Can someone please help me to remove that one extra for loop so as to get the running cost of algorithm in the same proportion as that of the Gaussian version of same problem.

Thanks in advance.

@Ander Yeah..I have profiled it. Its taking around 50 secs for only 780 iterations. Therefore for 1638400 iterations it will take around 29 hours. — nagarwal, Aug 04 '16 at 15:31
Profiling os useful to learn which lines take tame, not the total time. You want to pinpoint what takes longer — Ander Biguri, Aug 04 '16 at 15:32
As far as I understand, all the other lines are taking normal time to execute since for 1 iteration the algorithm is taking around 0.065 secs which is considerable. — nagarwal, Aug 04 '16 at 15:56
Please find the profiler summary [here](https://drive.google.com/file/d/0B5IqMPhxh5b5N2FVWUpIdHg5Y00/view). — nagarwal, Aug 05 '16 at 07:49
None of the lines seem to be taking too much time, You are just computing too many things. — Ander Biguri, Aug 05 '16 at 08:14
That's what I stated earlier. None of the lines seems to be taking much time. It's just that I want to repeat some steps for 1638400 pixels (the for loop) so that's why it is taking time as long as 29 hours. Now can you suggest me a better solution to this problem so as to decrease the running time. — nagarwal, Aug 05 '16 at 08:31
Yes, you didn't really show the whole profiler. the line with `bsxfun` takes 58% of the time — Ander Biguri, Aug 05 '16 at 08:35
Though I can share the whole profile results but it would be best if you could please copy and run this script on any of your local system. Can you please do that? — nagarwal, Aug 05 '16 at 08:50

score 1 · Answer 1 · edited May 23 '17 at 12:14

1

Get rid of the nasty loop with matrix-multiplication -

g_temp = img_diff(:).'*tanh((1/alpha)*(perms*perms.')+1)

edited May 23 '17 at 12:14

Community

1
1

answered Aug 04 '16 at 14:56

Divakar

218,885
19
262
358

I'm sorry but this cannot be done since `perms*perms.'` will create a huge matrix of size 1638400 x 1638400 which is not possible for MATLAB to create because of the memory constraints. – nagarwal Aug 04 '16 at 15:53

score 1 · Answer 2 · answered Aug 05 '16 at 08:52

1

With my times in my PC for just 50 iterations, the code takes 2.07s

Just changing the bsxfun line to

kernel = sum(bsxfun(@times,perms,perms1(i,:)),2)';

as the warning suggests you can get it to 1.65s

~~If you use the Neural Network toolbox and substitute tanh by tansig , the time goes to 1.44s~~

If you write your own tanhas

kernel1= (2./(1+exp(-2.*((1/alpha)*kernel + 1)))-1)';

the time goes to 1.28s

Just these changes would mean improvement from 29h to 18h

And remember to preallocate!

g_temp=zeros(length(perms1),1);

answered Aug 05 '16 at 08:52

Ander Biguri

35,140
11
74
120

That's appreciable but not the improvement which I want. I would like to tell you again that I want to iterate it for several different images (~5000) and thus want the running cost to be brought down to seconds, like the one done by @dan-man in the case of Gaussian kernel. – nagarwal Aug 05 '16 at 09:06
Thanks for such an rude and offensive comment. I already reported it. Life tip: Sometimes you can solve the things, sometimes you cannot. You cannot provide a 'no existence' certificate for problem's solution if you cannot do it. Meanwhile stackoverflow is platform to discuss and solve things which once seemed impossible, not involving in claptrap with some egoistic guys. – nagarwal Aug 05 '16 at 10:06
@nagarwal the comment wasn't mean to be rude at all. Understand I have a lot of things to do and I write this things really quick. The questions there were meant to say exactly what they say and the tip was a real one. – Ander Biguri Aug 05 '16 at 10:08
Still, coming back to the problem: have you tried Dans approach with your new kernel? – Ander Biguri Aug 05 '16 at 10:09
1

Trying that only. Though Dan's approach works absolutely well for other kernels involving `L2` norm of `(x-y)`, but I'm yet to find a way to achieve that for inner product of `x` & `y`. In Dan's approach, he made use of successive overlapping entries for the distance matrix(G) obtained for distances (L2 norm) between say (1,1) with rest all, (1,2) with rest all etc. and thus he used convolution theroem to get a nice 8192x200 matrix (g) which best represents our desired product (img_diff(:)' * G). But in case of dot product, it seems difficult to make use of any such fact but still trying. – nagarwal Aug 05 '16 at 11:16
@nagarwal yeah that's what I meant with "maybe that approach is not possible". The properties of the gaussian kernel are not shared with the `tanh` so you my not be able todo the fft trick. I don;t have any idea how solve this, I'll leave just here my computational improvement, I hope you find a better way. Good luck. – Ander Biguri Aug 05 '16 at 11:19
Okay. No problem. Anyways thanks a lot for your computational efforts. – nagarwal Aug 05 '16 at 11:26

Optimize matlab for loop for big data

2 Answers2