Keeping k largest values in each column of a sparse matrix

Hi everyone,

I am trying to implement an algorithm that involves a pruning of a large sparse matrix. The pruning scheme should keep the k largest values (all nonzero values are positive) in each column of the sparse matrix M.

My current solution is:

function Mp = pruning(M,k)

[i,j,v] = find(M);
t = sortrows([i j v],[2 -3]);

dzero = cumsum([0;diff(t(:,2))]==0);
dz = [1;diff(t(:,2))]>0;

dd = dzero.*dz;
for r = 2:numel(dd); 
    dd(r) = max(dd([r-1 r])); 
end;

I = (dzero-dd+1) <= k;
Mp = sparse(t(I,1),t(I,2),t(I,3),size(M,1),size(M,2));

Do you have better solutions (that avoid the loop)?

Thanks, W.

[Wolfgang Schwanghart]

since nobody answered, I'll just give it another try...

Answer 1

[Andrei Bobrov]

k = triu(bsxfun(@minus,dd,dd'));
pl = sum(k<0)+1==1:numel(dd);
m = dd(pl);
dd = m(cumsum(pl));

[Wolfgang Schwanghart]

thanks andrei, but this seems to generate a large and perhaps non-sparse matrix k. Basically, the question is, how to get from e.g. here

dd = [1 0 0 0 4 0 0 0 7 0 8 0 0 10 0 0 0 0]';

to there

dd2 = [1 1 1 1 4 4 4 4 7 7 8 8 8 10 10 10 10 10]';

Regards, W.

[Sean de Wolski]

values always ascending?

[Sean de Wolski]

with a zero between them?

[Andrei Bobrov]

k = find(dd);

dd = dd(k(cumsum(dd~=0)));

[Wolfgang Schwanghart]

@Sean de: yes

[Wolfgang Schwanghart]

Hi Andrei! Thanks! That's a nice solution.

[Sean de Wolski]

That is nice Andrei!

[Andrei Bobrov]

Thanks, friends!