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)そのうちx1のx2は M 行 1 列のベクトルです。

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)(matrix) であり、他の部分は単なる 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、一部の計算結果を再利用できます。