Max / Min of sparse matrices

4 次查看（过去 30 天）
Edward Umpfenbach
Edward Umpfenbach 2012-4-12
评论： Hesameddin KHosravi 2019-2-18
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.

请先登录，再回答此问题。

采纳的回答

Richard Brown
Richard Brown 2012-4-12
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 个评论
显示 3更早的评论
Oleg Komarov
Oleg Komarov 2012-4-13
Nice solution.
Also,this was a good question!
Oleg Komarov
Oleg Komarov 2012-4-13
Nice solution.
Also,this was a good question!

请先登录，再进行评论。

更多回答（3 个）

Richard Brown
Richard Brown 2012-4-12
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 个评论
显示 1更早的评论
Richard Brown
Richard Brown 2012-4-12
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 2012-4-12
Oh, and if you can get rid of the isempty condition, then that will help a little

请先登录，再进行评论。

Geoff
Geoff 2012-4-12
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 个评论
Hesameddin KHosravi
Hesameddin KHosravi 2019-2-18
Thank you so much, this function wrorks for me but how can I get index of minimal array?

请先登录，再进行评论。

Oleg Komarov
Oleg Komarov 2012-4-12
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 个评论
显示 2更早的评论
Oleg Komarov
Oleg Komarov 2012-4-13
@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 2012-4-13
I like this approach - it will certainly be faster.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Data Distribution Plots 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by