MATLAB vectorization: computing a neighborhood matrix
matlab, matrix, performance, vector, vectorization
Solution
Approach #1
`bsxfun` based approach -
out = bsxfun(@minus,X,X').^2 + bsxfun(@minus,Y,Y').^2 < radius^2
out(1:n+1:end)= 0
Approach #2
`Distance matrix calculation using matrix-multiplication` based approach (possibly faster) -
A = [X(:) Y(:)]
A_t = A.'; %//'
out = [-2*A A.^2 ones(n,3)]*[A_t ; ones(3,n) ; A_t.^2] < radius^2
out(1:n+1:end)= 0
Approach #3
With `pdist` and `squareform` -
A = [X(:) Y(:)]
out = squareform(pdist(A))<radius
out(1:n+1:end)= 0
Approach #4
You can use `pdist` as with the previous approach, but avoid `squareform` with some logical indexing to get the final output of neighbourhood matrix as shown below -
A = [X(:) Y(:)]
dists = pdist(A)< radius
mask_lower = bsxfun(@gt,[1:n]',1:n) %//'
%// OR tril(true(n),-1)
mask_upper = bsxfun(@lt,[1:n]',1:n) %//'
%// OR mask_upper = triu(true(n),1)
%// OR mask_upper = ~mask_lower; mask_upper(1:n+1:end) = false;
out = zeros(n)
out(mask_lower) = dists
out_t = out' %//'
out(mask_upper) = out_t(mask_upper)
Note: As one can see, for the all above mentioned approaches, we are using pre-allocation for the output. A fast way to pre-allocate would be with `out(n,n) = 0` and is based upon `this wonderful blog on undocumented MATLAB`. This should really speed up those approaches!
Problem
Given two vectors `X` and `Y` of length `n`, representing points on the plane, and a neighborhood radius `rad`, is there a vectorized way to compute the neighborhood matrix of the points? In other words, can the following (painfully slow for large `n`) loop be vectorized: ``` neighborhood_mat = zeros(n, n); for i = 1 : n for j = 1 : i - 1 dist = norm([X(j) - X(i), Y(j) - Y(i)]); if (dist < radius) neighborhood_mat(i, j) = 1; neighborhood_mat(j, i) = 1; end end end ```