Normalize rows a sparse matrix to sum to one in matlab
Alec Jacobson
May 20, 2013
I surprisingly found a bottleneck in my matlab program to be how I was normalizing rows of a sparse adjacency matrix. I was doing this using bsxfun:
A = bsxfun(@rdivide,A,sum(A,2));
This matlab forum lists a few other ways. I compared them with this script using the timeit function:
a1 = @() bsxfun(@rdivide,A,sum(A,2));
a2 = @() spdiags (sum (A,2), 0, size(A,1), size(A,1)) \ A ;
a3 = @() spdiags (1./sum (A,2), 0, size(A,1), size(A,1)) * A ;
% A is 10000x10000 with roughly 6 nnz per row
timeit(a1)
% 0.32 seconds
timeit(a2)
% 0.0023 seconds
timeit(a3)
% 0.0016 seconds
So I'm going with:
A = spdiags (1./sum (A,2), 0, size(A,1), size(A,1)) * A ;
Update: This observation is not valid if A is dense. The same methods above perform differently:
% A = rand(10000,10000);
timeit(a1)
% 0.49 seconds
timeit(a2)
% 1.02 seconds
timeit(a3)
% 0.72 seconds
Looks like bsxfun is still the best bet for dense matrices.