r - 有没有办法通过避免循环来计算以下指定的矩阵？在 R 或 Matlab 中

Question

我有一个 N×M 矩阵X，我需要计算一个 N×N 矩阵Y：

Y[i, j] = sum((X[i,] - X[j,]) ^ 2)   0 <= i,j <= N

现在，我必须使用嵌套循环来处理 O(n ² )。我想知道是否有更好的方法，比如使用矩阵运算。

更一般地说，sum(....)可以是一个函数，其中fun(x1,x 2)是M×1 向量。x1x2

Answer 1

您可以使用expand.grid来获取可能对的 data.frame：

X <- matrix(sample(1:5, 50, replace=TRUE), nrow=10)

row.ind <- expand.grid(1:dim(X)[1], 1:dim(X)[2])

然后apply沿着每一对使用一个函数：

myfun <- function(n) {
  sum((X[row.ind[n, 1],] - X[row.ind[n, 2],])^2)
}

Y <- matrix(unlist(lapply(1:nrow(row.ind), myfun)), byrow=TRUE, nrow=nrow(X))


> Y
      [,1] [,2] [,3] [,4] [,5]
 [1,]    0   28   15   31   41
 [2,]   31   28   33   30   33
 [3,]   28    0   15    7   19
 [4,]   33   30   19   34   11
 [5,]   15   15    0   12   22
 [6,]   10   19   10   21   20
 [7,]   31    7   12    0    4
 [8,]   16   17   16   13    2
 [9,]   41   19   22    4    0
[10,]   14   11   28    9    2
> 

我敢打赌有更好的方法，但它是星期五，我累了！

Answer 2

(x[i]-x[j])^2 = x[i]² - 2*x[i]*x[j] + x[j]²

而不是中间部分只是矩阵乘法-2*X*tran(X)（矩阵），其他部分只是 vetrors，你必须在每个元素上运行它

这有 O(n^2.7) 或任何矩阵乘法复杂度

伪代码：

vec=sum(X,rows).^2
Y=X * tran(X) * -2 
for index [i,j] in Y:
   Y[i,j] =  Y[i,j] + vec[i]+vec[y]

Answer 3

在 MATLAB 中，对于您的具体f情况，您可以这样做：

Y = pdist(X).^2;

对于非“作弊”版本，请尝试以下方法（MATLAB）：

[N, M] = size(X);
f = @(u, v) sum((u-v).^2);
helpf = @(i, j) f(X(i, :), X(j, :))
Y = arrayfun(helpf, meshgrid(1:N, 1:N), meshgrid(1:N, 1:N)');

使用特定功能有更有效的方法，sum(...)但您的问题说您想要通用功能的通用方法f。通常，此操作将是每个向量对操作复杂度的 O(n^2) 倍，因为这就是需要完成的操作数。如果f是特殊形式，一些计算的结果可以重复使用。