Max / Min of sparse matrices

29 views (last 30 days)
I previously asked this question:
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.
  1 Comment
Edward Umpfenbach
Edward Umpfenbach on 12 Apr 2012
Anyone? I'm pretty stuck without this.

Sign in to comment.

Accepted Answer

Richard Brown
Richard Brown on 12 Apr 2012
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 ...
  5 Comments
Oleg Komarov
Oleg Komarov on 13 Apr 2012
Nice solution.
Also,this was a good question!
Oleg Komarov
Oleg Komarov on 13 Apr 2012
Nice solution.
Also,this was a good question!

Sign in to comment.

More Answers (3)

Richard Brown
Richard Brown on 12 Apr 2012
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
  3 Comments
Richard Brown
Richard Brown on 12 Apr 2012
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
Richard Brown on 12 Apr 2012
Oh, and if you can get rid of the isempty condition, then that will help a little

Sign in to comment.


Geoff
Geoff on 12 Apr 2012
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);
  1 Comment
Hesameddin KHosravi
Hesameddin KHosravi on 18 Feb 2019
Thank you so much, this function wrorks for me but how can I get index of minimal array?

Sign in to comment.


Oleg Komarov
Oleg Komarov on 12 Apr 2012
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.
  4 Comments
Oleg Komarov
Oleg Komarov on 13 Apr 2012
@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
Richard Brown on 13 Apr 2012
I like this approach - it will certainly be faster.

Sign in to comment.

Categories

Find more on Creating and Concatenating Matrices in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!