Thread Subject: Row normalize a matrix

How do I normalize a large sparse matrix so that every row
sums to one?

The following code runs awfully slowly:
for i = 1:numrows
  rowsum = sum(S(i, :));
  S(i, :) = S(i, :)*1/rowsum;
end

In article <fk483l$r06$1@fred.mathworks.com>, "John Smith" <spamalot@jhu.edu> wrote:

> How do I normalize a large sparse matrix so that every row
> sums to one?
>
> The following code runs awfully slowly:
> for i = 1:numrows
> rowsum = sum(S(i, :));
> S(i, :) = S(i, :)*1/rowsum;
> end

This will work, and be reasonably fast.

S = spdiags(1./sum(S,2),0,numrows,numrows)*S;

Of course, if there are zero rows then a
row normalization will fail.

John


--
The best material model of a cat is another, or preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.
Anonymous

John D'Errico <woodchips@rochester.rr.com> wrote in message
<woodchips-DF20B0.19363216122007@news.rochester.rr.com>...
> In article <fk483l$r06$1@fred.mathworks.com>, "John Smith"
<spamalot@jhu.edu> wrote:
>
> > How do I normalize a large sparse matrix so that every row
> > sums to one?
> >
> > The following code runs awfully slowly:
> > for i = 1:numrows
> > rowsum = sum(S(i, :));
> > S(i, :) = S(i, :)*1/rowsum;
> > end
>
> This will work, and be reasonably fast.
>
> S = spdiags(1./sum(S,2),0,numrows,numrows)*S;
>
> Of course, if there are zero rows then a
> row normalization will fail.
>
> John
>
>
> --
> The best material model of a cat is another, or preferably
the same, cat.
> A. Rosenblueth, Philosophy of Science, 1945
>
> Those who can't laugh at themselves leave the job to others.
> Anonymous

This is safer (this works if S has any rows for which
sum(S,2) is denormal, for example, whereas John's example
would give Nans):

S = spdiags (sum (S,2), 0, numrows, numrows) \ S ;

(backslash to the rescue ;-)

You might want

S = spdiags (sum (abs(S),2), 0, numrows, numrows) \ S

instead.

Thanks! Both solutions worked for my data but I am sticking
with Tim's solution for the reason he points out.

Compared to the original code segment, both solutions were
amazingly fast.

"Tim Davis" <davis@cise.ufl.edu> wrote in message
<fk5spt$1c9$1@fred.mathworks.com>...
> John D'Errico <woodchips@rochester.rr.com> wrote in message
> <woodchips-DF20B0.19363216122007@news.rochester.rr.com>...
> > In article <fk483l$r06$1@fred.mathworks.com>, "John Smith"
> <spamalot@jhu.edu> wrote:
> >
> > > How do I normalize a large sparse matrix so that every row
> > > sums to one?
> > >
> > > The following code runs awfully slowly:
> > > for i = 1:numrows
> > > rowsum = sum(S(i, :));
> > > S(i, :) = S(i, :)*1/rowsum;
> > > end
> >
> > This will work, and be reasonably fast.
> >
> > S = spdiags(1./sum(S,2),0,numrows,numrows)*S;
> >
> > Of course, if there are zero rows then a
> > row normalization will fail.
> >
> > John
> >
> >
> > --
> > The best material model of a cat is another, or preferably
> the same, cat.
> > A. Rosenblueth, Philosophy of Science, 1945
> >
> > Those who can't laugh at themselves leave the job to others.
> > Anonymous
>
> This is safer (this works if S has any rows for which
> sum(S,2) is denormal, for example, whereas John's example
> would give Nans):
>
> S = spdiags (sum (S,2), 0, numrows, numrows) \ S ;
>
> (backslash to the rescue ;-)
>
> You might want
>
> S = spdiags (sum (abs(S),2), 0, numrows, numrows) \ S
>
> instead.

Tim,

but your method returns NaNs in rows in S where sum(S,2) is
zero,too. For large matrices this gives me an "out of
memory". Hence, I use to standardize rows by

S = spdiags(spfun(@(x) 1./x,sum(M,2)),0,numrows,numcols)*S;

which may be efficient when there are many rows that sum to
zero.



"Tim Davis" <davis@cise.ufl.edu> wrote in message
<fk5spt$1c9$1@fred.mathworks.com>...
> John D'Errico <woodchips@rochester.rr.com> wrote in message
> <woodchips-DF20B0.19363216122007@news.rochester.rr.com>...
> > In article <fk483l$r06$1@fred.mathworks.com>, "John Smith"
> <spamalot@jhu.edu> wrote:
> >
> > > How do I normalize a large sparse matrix so that every row
> > > sums to one?
> > >
> > > The following code runs awfully slowly:
> > > for i = 1:numrows
> > > rowsum = sum(S(i, :));
> > > S(i, :) = S(i, :)*1/rowsum;
> > > end
> >
> > This will work, and be reasonably fast.
> >
> > S = spdiags(1./sum(S,2),0,numrows,numrows)*S;
> >
> > Of course, if there are zero rows then a
> > row normalization will fail.
> >
> > John
> >
> >
> > --
> > The best material model of a cat is another, or preferably
> the same, cat.
> > A. Rosenblueth, Philosophy of Science, 1945
> >
> > Those who can't laugh at themselves leave the job to others.
> > Anonymous
>
> This is safer (this works if S has any rows for which
> sum(S,2) is denormal, for example, whereas John's example
> would give Nans):
>
> S = spdiags (sum (S,2), 0, numrows, numrows) \ S ;
>
> (backslash to the rescue ;-)
>
> You might want
>
> S = spdiags (sum (abs(S),2), 0, numrows, numrows) \ S
>
> instead.