Max / Min of sparse matrices

I previously asked this question:

http://www.mathworks.com/matlabcentral/answers/35224-max-min-of-nonzero-rows-cols

It was answered perfectly, except now I realize that I need to deal with a sparse matrix. If I set the zero elements to be NaN, I run out of memory. So the question is, how to find the row and column max and min of a sparse matrix, excluding the zero elements. Creating a full matrix is not an option. Any help would be appreciated.

[Edward Umpfenbach]

Anyone? I'm pretty stuck without this.

Answer 1

[Richard Brown]

EDIT There was a mistake in the markers line and the s= line, fixed now.

OK, here's an accelerated version. What made my previous answer slower was the S(I == i) line, this is pretty wasteful. Vectorisation sometimes hurts you rather than helping, this is one of those cases.

So, here goes. Again, I'll just focus on the rows and assume that it is possible for a row to be all zeros.

First, define a test matrix

A = sprand(50000, 60000, 1/20000);

Preallocate the rowMin and rowMax vectors

[m,n] = size(A);
rowMin = nan(m, 1);
rowMax = nan(m, 1);

Find all the NZ entries ;) and sort them by row index

[I,J,S] = find(A);
[I,K] = sort(I);
S = S(K);

Now we need to find where the index changes, diff is great for this. Just got to be careful with how you pad the left hand end. I also add in an extra entry to mark the final entry (saves unnecessary calls to end).

markers = [find([1; diff(I)]); numel(I)+1];

Pull out the identified rows, (end-1) makes sure that we don't get the final row twice.

iRows = I(markers(1:end-1));

The loop ought to be faster now:

for i = 1:numel(iRows)
  s = S(markers(i):(markers(i+1)-1));
  rowMin(iRows(i)) = min(s);
  rowMax(iRows(i)) = max(s);
end

This completes in 0.2 seconds on my laptop ...

[Edward Umpfenbach]

This works great. Very fast. Thank you very much!

[Oleg Komarov]

This solution gives wrong results:

A =

(8,1) 0.3740

(6,2) 0.8893

(3,3) 0.2660

(7,3) 0.8853

(9,3) 0.0842

(7,5) 0.0074

(10,5) 0.4687

(5,6) 0.7478

(7,6) 0.2866

(7,8) 0.5423

rowMin =

NaN

NaN

0.2660

NaN

0.7478

0.8853

0.0074

0.0842

0.0842

0.4687

[Richard Brown]

@Oleg, thanks- fixed now

[Oleg Komarov]

Nice solution.

Also,this was a good question!

[Oleg Komarov]

Nice solution.

Also,this was a good question!

Answer 2

[Richard Brown]

Can't do this one quite so cutely :)

Try this (for rows), you can do the same thing for columns with a trivial modification

[m,n] = size(A);
rowMin = zeros(m, 1);
rowMax = zeros(m, 1);

[I,J,S] = find(A)
for i = 1:m
  s = S(I == i);
  % you may need this condition, depending on your matrix
  if ~isempty(s)
    rowMin(i) = min(s);
    rowMax(i) = max(s);
  end
end

[Edward Umpfenbach]

I greatly appreciate your answer, but I was hoping to do this without a for loop. My matrix is 60,000 by 50,000, so I need this to be as fast as possible.

[Richard Brown]

Have you tried it? for loops are not as bad as you might think - your performance will depend on the sparsity of your matrix

[Richard Brown]

Oh, and if you can get rid of the isempty condition, then that will help a little

Answer 3

[Geoff]

Here is a solution for rows (similar for columns)...

If you know that every row contains at least one non-zero value, you can do this:

rmax = arrayfun( @(row) full(max( A(row, A(row,:)~=0) )), 1:size(A,1) );
rmin = arrayfun( @(row) full(min( A(row, A(row,:)~=0) )), 1:size(A,1) );

If a row can be empty, you will need to do:

rmax = arrayfun( @(row) blahblah, 1:size(A,1), 'UniformOutput', false );
rmin = likewise

In that case your rmax, rmin will be cell arrays. You possibly want to turn the empty cells into NaNs and get the whole thing back as a vector:

rmax( cellfun(@(c) isempty(c), rmax) ) = {NaN};
rmin( cellfun(@(c) isempty(c), rmin) ) = {NaN};
rmax = cell2mat(rmax);
rmin = cell2mat(rmin);

[Hesameddin KHosravi]

Thank you so much, this function wrorks for me but how can I get index of minimal array?

Answer 4

[Oleg Komarov]

For the max you should not have any problems:

% Find the max (along columns)
[mmax,Imax]   = max(A,[],2);
[rmax,~,mmax] = find(mmax);
cmax          = Imax(rmax);

% Similarly, find the max along rows
[mmax,Imax]   = max(A);
[~,cmax,mmax] = find(mmax);
rmax          = Imax(cmax);

In case of all positive numbers, to find the min, e.g. along columns, you can take the negative of A and shift the numbers by the maximum you found before:

% Take negative and shift to positive 
[nnzr,nnzc] = find(A);
B = -A + sparse(nnzr,nnzc,max(mmax),m, n);

% Now find the MIN which involves taking the max (along columns)
[mmin,Imin]   = max(B,[],2);
[rmin,~,mmin] = find(mmin);
cmin          = Imin(rmin);

% Shift back and retake negative
mmin          = -(mmin - max(mmax));

WARNING: you may have the same numbers for min and max because it's the only one.

NOTE: if you have negative numbers as well, then using simply max and min wors fine.

Elapsed time is 0.029157 seconds.

[Richard Brown]

Assuming the max > 0 ...

[Edward Umpfenbach]

Yeah, the question was mostly about the min. Thanks, though.

[Oleg Komarov]

@Edward: I wrote a full example on how to retrieve the min.

@Richard: if max < 0, then the min is trivial and the max involves the shifting procedure.

In case you numbers are on the domain [-,+] then it's trivial to take max and min.

[Richard Brown]

I like this approach - it will certainly be faster.