Find row-wise minima in sparse matrix

Question

I would like to get the minimum nonzero values per row in a sparse matrix. Solutions I found for dense matrices suggested masking out the zero values by setting them to NaN or Inf. However, this obviously doesn't work for sparse matrices.

Ideally, I should get a column vector of all the row-wise minima, as I would get with

minValues = min( A, [], 2);

Except, obviously, using min leaves me with an all-zeros column vector due to the sparsity. Is there a solution using find?

Answer 1

This is perfect for accumarray. Consider the following sparse matrix,

vals = [3 1 1 9 7 4 10 1];  % got this from randi(10,1,8)
S = sparse([1 3 4 4 5 5 7 9],[2 2 3 6 7 8 8 11],vals);

Get the minimum value for each row, assuming 0 for empty elements:

[ii,jj] = find(S);
rowMinVals = accumarray(ii,nonzeros(S),[],@min)

Note that rows 4 and 5 of rowMinVals, which are the only two rows of S with multiple nonzero values are equal to the min of the row:

rowMinVals =
     3
     0
     1
     1 % min([1 9]
     4 % min([7 4]
     0
    10
     0
     1

If the last row(s) of your sparse matrix do not contain any non-zeros, but you want your min row value output to reflect that you have numRows, for example, change theaccumarray command as follows,

rowMinVals = accumarray(ii,nonzeros(S),[numRows 1],@min).

Also, perhaps you also want to avoid including the default 0 in the output. One way to handle that is to set the fillval input argument to NaN:

rowMinVals = accumarray(ii,nonzeros(S),[numRows 1],@min,NaN)

rowMinVals =

     3
   NaN
     1
     1
     4
   NaN
    10
   NaN
     1
   NaN
   NaN
   NaN

Or you can keep using a sparse matrix with the fifth input argument, issparse:

>> rowMinVals = accumarray(ii,nonzeros(S),[],@min,[],true)
    rowMinVals =
   (1,1)        3
   (3,1)        1
   (4,1)        1
   (5,1)        4
   (7,1)       10
   (9,1)        1