如何矢量化从矢量中找出最近的点

Question

BigList = rand(20, 3)
LittleList = rand(5, 3)

我想为大列表中的每一行找到小列表中的"最近"行,由欧几里德范数定义(即k = 3维度中相应值之间的平方距离之和).

我可以看到如何使用两个循环来做到这一点,但似乎应该有一个更好的方法来使用内置矩阵操作来做到这一点.

Answer 1

正确的方法当然是使用最近邻搜索算法.
但是,如果您的维度不是太高而且您的数据集不是很大,那么您只需使用bsxfun:

d = bsxfun( @minus, permute( bigList, [1 3 2] ), permute( littleList, [3 1 2] ) ); %//diff in third dimension
d = sum( d.^2, 3 ); %// sq euclidean distance
[minDist minIdx] = min( d, [], 2 );

除了这里提出的矩阵乘法方法之外,还有另一个没有循环的矩阵乘法

nb = sum( bigList.^2, 2 ); %// norm of bigList's items
nl = sum( littleList.^2, 2 ); %// norm of littleList's items
d = bsxfun( @sum, nb, nl.' ) - 2 * bigList * littleList'; %// all the distances

这种方法背后的观察是欧几里德距离(L2范数)

|| a - b ||^2 = ||a||^2 + ||b||^2 - 2<a,b> 

随着<a,b>是两个向量的点积.