Avoiding unnecessary for loops

How do I do this without the loops in a few lines?

S = zeros(100,100);

sig = 0.05;

for i = 1:100

      for j = 1:100

          S(i,j) = exp(-norm(D(i,:)-D(j,:),'fro')/sig);
      end
  end

[Deepayan Bhadra]

@Walter Roberson, did you make any comment on this?

[Jos (10584)]

Note that S will be symmetric with zeros on the diagonal, as norm(x) = norm(-x), so you can let j run from i+1 to 100 to save time.

Since norm is not vectorized it is hard to get rid of the for-loops at all.

Answer 1

[Jan]

These are a few lines already. The mos expensive is the exp call, so you save the most time with using the symmetry (as mentioned by Jos already):

S = zeros(100,100);
sig = 0.05;
for i = 1:100
   for j = i+1:100
      S(i,j) = exp(-norm(D(i,:) - D(j,:)) / sig);
      S(j,i) = S(i,j);
   end
end

You can try if it is faster to replace norm by:

for i = 1:100
   v = D(i, :);
   for j = i+1:100
      w = v - D(j, :);
      S(i,j) = exp(-sqrt(w * w.') / sig);
      S(j,i) = S(i,j);
   end
end

Operating on columns is faster than on rows:

DT = D.';
for i = 1:100
   v = DT(:, i);
   for j = i+1:100
      w = v - DT(:, j);
      S(i,j) = exp(-sqrt(w.' * w) / sig);
      S(j,i) = S(i,j);
   end
end

Please post the timings you get.

[Deepayan Bhadra]

The thing is later, I use i and j going up to 10,000 each. As you can imagine, this is nightmarishly time-consuming if I use for loops. My course instructor forbids the use of loops and wants us to think our way out. Still scratching my head around this. I think repmat() is an option.

[Jan]

If you ask for the optimizing of code, provide the real dimensions of the problem, because this is essential. If you have 10'000 vectors, creating the temporary arrays by repmat can fill your RAM and let the code run incredibly slow.

The long time needed for the processing is not caused by the loops, if you avoid repeated calculations. Therefore the advice of your instructor to vectorize is important, but not necessarily the best method.

Nevertheless, if the goal is, that you find a vectorized loop-free way by your own, please post, what you have tried so far and ask a specific question. The forum should not solve your homework.

[Deepayan Bhadra]

data: 100x2. D = pdist(data), Z = squareform(D), S = exp(-Z/sig). This accomplishes the exact thing as the for loop. I appreciate your inputs but let's not jump to conclusions about intentions of different MATLAB users on the forum.

[Jan]

In pdist you find exactly the same loops as in the suggested code, but S = exp(-Z/sig) does not use the symmetry of the input, such that almost the double number of expensive exp() calls are performed. Therefore I assume, that this "loop free" code is not less "nightmarishly time-consuming". I'm interested in the timings you get, especially for the larger matrices with 10'000 vectors.

I did not draw any conclusions about intentions of anybody. I'm convinced, that the forum should not solve homework. That's all. But discussions about homework are very useful for the forum and the students.