Find first element in each row greater than a given element from another matrix.

Suppose I have 2 matrices of different dimensions. Say

A=[2 3 5 7; 
   1 4 8 9; 
   3 4 9 7]

and

B=[2;
   8;
  11]

then I want each element from each row of B compared with corresponding row of A and then get an output as follows:

C=[3;
   9;
   0]

i.e take 2 from B and look for the first element in first row of A which is greater than it. then take 8 from B and look for first element in second row of A which is greater than it. In third row since there was no element in A greater than 11, it should return zero. Is there a way I can do this without using loop? I would like to get this done through vectorization. Many thanks!

[dpb]

Nothing trivial comes to mind...the difficulty of the special case for no element is one problem in generalizing a vectorized solution (altho if start by C=zeros(size(B)); then if could find a decent way to return the first location by row where the test does succeed could populate those positions. But, find doesn't have a 'first' option that works except for the entire set, not by the search dimension and otomh nothing strikes that would be better than just the straight-forward loop in all likelihood.

[Sandeep]

If it helps, I am pasting below the code using for loop to get the desired result. Since the dimensions of array in my actual problem is very high, I prefer to have a vectorized solution.

for i=1:4
  for j=1:4
      if A(i,j)>B(i)
          C(i)=A(i,j);
          break;
      else
          C(i)=0;
      end
  end

end

Answer 1

[Star Strider]

I tried to come up with a vectorised solution but could not.

My non-vectorised solution:

A=[2 3 5 7; 1 4 8 9; 3 4 9 7];
B=[2; 8; 11];
C = zeros(size(B));
for k1 = 1:size(B,1)
    T = min(A(k1,(find(A(k1,:) > B(k1)))));
    if ~isempty(T)
        C(k1) = T;
    end
end

The ‘C’ (result) vector is the output of the script.

It produces:

C =

       3
       9
       0

A vectorised solution is not always more efficient than a loop. This one is a bit more efficient than your posted solution (it eliminates one loop and vectorises the comparison step), so it will speed things up a bit.

[Sandeep]

Thank you Star Strider!

[Star Strider]

My pleasure!

[Nico]

Correct me if I'm wrong, but I believe this finds the smallest number in a row of A that is bigger than the corresponding entry in B (and the original question was to find the FIRST number in a row of A). I only ask this because I have a similar problem and wish to find the first entry (i.e. row number) of a column below the diagonal that is smaller than the diagonal element of that matrix. However I have an indexing issue.

n=4;
degrees = [3 0 0 0; 2 1 0 0; 2 0 1 0; 2 0 0 1];
vi = zeros(n,n);
vi(1,:) = degrees(1,:);
for j = 1:n-1
    vi(j+1,:) = degrees(j+(find(degrees(j+1:end,j) < vi(j,j)))(1),:)
end

I want a vectorized comparison as in the solution above, but I want the first number that is less than the diagonal so (I think) I should just take the first element of my comparison vector. However I run into the double set of parantheses indexing problem. Is there a way to do this without having to create a local variable that saves the comparison vector? My actual problem is quite large so I'd rather not use the memory if I don't have to.

Answer 2

[Alfonso Nieto-Castanon]

Something like this would also work:

 cond = bsxfun(@gt,A,B);
 [ok,idx] = max(cond,[],2);
 C = ok.*A((1:numel(idx))'+numel(idx)*(idx-1));

EDIT: to clarify, 'max' returns the index to the first occurrence when there is more than one maximal element

[Cedric]

The multiplication by ok to get the 0 is neat!

[Giovanni Ciriani]

bsxfun can be replaced by the simpler cond = A>B

and the indexing calculation can be replaced by sub2ind

[ok, idx] = max(A>B, [], 2);
C = ok .* A(sub2ind(size(A), 1:rows(A), idx'))'

[Cedric]

Yes but only since 2016b support automatic expansion. Back in 2014, it was not the case!