成对L2距离计算的优化 [英] optimization of pairwise L2 distance computations

问题描述

我需要帮助优化这个循环。 matrix_1 是一个（ n x 2）int矩阵和 matrix_2 是（ m x 2）， m & n very。

  index_j = 1; 
 for index_k = 1：size（Matrix_1,1）
 for index_l = 1：size（Matrix_2,1）
 M2_Index_Dist（index_j，:) = [index_l，sqrt（bsxfun（@plus ，总和（Matrix_1（index_k，：）^ 2,2），和（Matrix_2（index_l，：）^ 2,2。） '） -  2 *（Matrix_1（index_k，：）* Matrix_2（index_l，:)' ））]; 
 index_j = index_j + 1; 
 end 
 end 
  

我需要 M2_Index_Dist > matrix_2 的索引提供一个（（n * m） x 2）第一列和第二列的距离。

输出示例：

  M2_Index_Dist = [1，5.465 
 2，56.52 
 3，6.21 
 1,35.3 
 2，56.52 
 3，0 
 1， 43.5 
 2 9.3 
 3 236.1 $ b $ 1,8.2 
 56.52 $ b $ 3 5.582 
 code $ pre 
 
解决方案 
以下是如何在公式中应用 bsxfun  c $ c> || AB || = sqrt（|| A || ^ 2 + || B || ^ 2  -  2 * A * B））：
 
 
  d = real（sqrt（bsxfun（@plus，dot（Matrix_1，Matrix_1,2），... 
 bsxfun（@minus，dot （Matrix_2，Matrix_2,2）。，2 * Matrix _1 * Matrix_2））））。。; 
  
如果您更改对矩阵的解释，则可以避免最终转置。 
 $ b 
注意：不应该有任何复杂的值来处理 real ，但是如果出现非常小的差异，可能会导致很小的值
 $ b 
 
 
 
编辑：如果没有点 ：
 
 
  d = sqrt（bsxfun（@plus，sum（Matrix_1。* Matrix_1,2），... 
 bsxfun（@minus，sum（Matrix_2。* Matrix_2,2）'，2 * Matrix_1 * Matrix_2。'）））。 
  
或者只需一次调用 bsxfun ： 
 
 $ $ $ $ $ c $ d $ sq $（bsxfun（@plus，sum（Matrix_1。* Matrix_1,2），sum（Matrix_2。* Matrix_2， 2）'）... 
  -  2 * Matrix_1 * Matrix_2。'）。'; 
  

注意：最后一个操作顺序给出了相同的结果，而不是错误<$ c





$ b $编辑2：复制<$ c $ 2> ndgrid（1：size（Matrix_2,1），1：ndgrid（1：size（Matrix_2,1），1：大小（Matrix_2,1））;
M2_Index_Dist = [II（:) d（:)];

I need help optimizing this loop. matrix_1 is a (nx 2) int matrix and matrix_2 is a (m x 2), m & n very.

index_j = 1;
for index_k = 1:size(Matrix_1,1)
    for index_l = 1:size(Matrix_2,1)
        M2_Index_Dist(index_j,:) = [index_l, sqrt(bsxfun(@plus,sum(Matrix_1(index_k,:).^2,2),sum(Matrix_2(index_l,:).^2,2)')-2*(Matrix_1(index_k,:)*Matrix_2(index_l,:)'))];
        index_j = index_j + 1;
    end
 end

I need M2_Index_Dist to provide a ((n*m) x 2) matrix with the index of matrix_2 in the first column and the distance in the second column.

Output example:

M2_Index_Dist = [ 1, 5.465
                  2, 56.52
                  3, 6.21
                  1, 35.3
                  2, 56.52
                  3, 0
                  1, 43.5
                  2, 9.3
                  3, 236.1
                  1, 8.2
                  2, 56.52
                  3, 5.582]

解决方案

Here's how to apply bsxfun with your formula (||A-B|| = sqrt(||A||^2 + ||B||^2 - 2*A*B)):

d = real(sqrt(bsxfun(@plus, dot(Matrix_1,Matrix_1,2), ...
    bsxfun(@minus, dot(Matrix_2,Matrix_2,2).', 2 * Matrix_1*Matrix_2.')))).';

You can avoid the final transpose if you change your interpretation of the matrix.

Note: There shouldn't be any complex values to handle with real but it's there in case of very small differences that may lead to tiny negative numbers.

---

Edit: It may be faster without dot:

d = sqrt(bsxfun(@plus, sum(Matrix_1.*Matrix_1,2), ...
    bsxfun(@minus, sum(Matrix_2.*Matrix_2,2)', 2 * Matrix_1*Matrix_2.'))).';

Or with just one call to bsxfun:

d = sqrt(bsxfun(@plus, sum(Matrix_1.*Matrix_1,2), sum(Matrix_2.*Matrix_2,2)') ...
    - 2 * Matrix_1*Matrix_2.').';

Note: This last order of operations gives identical results to you, rather than with an error ~1e-14.

---

Edit 2: To replicate M2_Index_Dist:

II = ndgrid(1:size(Matrix_2,1),1:size(Matrix_2,1));
M2_Index_Dist = [II(:) d(:)];

这篇关于成对L2距离计算的优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！