Thread Subject: Simple matrix manipulation question

Hi all,

Suppose I have a n x k matrix A and a n x 1 column vector b. b contains integers between 1 and k. I want to produce a n x 1 column vector c, which is defined by c(i) = min {A(i,1),A(i,2),...,A(i,b(i)}. This would be easy with loops, but I want code which will run as fast as possible (the matrices are large, and the operation will be performed many times).

To clarify, if b were (k,...,k)' then c would contain the minimum elements in each row of A.

Maybe it's just early in the morning but I have trouble understanding what you want.
Is c(i) given by
c(i) = min([A(i,1),A(i,2),...,A(i,k),A(i,b(i))]) ??
because this would just be the minimum value in the row.
What exactly are the ... representing?

Ok, I see what you want now
c(i) = min( A(1:b(i)) );

Right, but that method involves looping over each i. Is there a way to do this without loops?

"Darren Rowland" <darrenjremovethisrowland@hotmail.com> wrote in message <h3m1dc$5gs$1@fred.mathworks.com>...
> Ok, I see what you want now
> c(i) = min( A(1:b(i)) );

On Jul 16, 9:13 am, "jcurr Curran" <johncurra...@yahoo.com> wrote:
> Right, but that method involves looping over each i. Is there a way to do this without loops?
>
> "Darren Rowland" <darrenjremovethisrowl...@hotmail.com> wrote in message <h3m1dc$5g...@fred.mathworks.com>...
> > Ok, I see what you want now
> > c(i) = min( A(1:b(i)) );

A = magic(10);
b = [1:10]';
c = min(A(b,:)')';

c =

     1
     7
     4
     3
     2
    17
     5
     6
    10
    11

How about that one?
-Nathan

"jcurr Curran" <johncurran20@yahoo.com> wrote in message <h3njiu$8m6$1@fred.mathworks.com>...
> Right, but that method involves looping over each i. Is there a way to do this without loops?
>
> "Darren Rowland" <darrenjremovethisrowland@hotmail.com> wrote in message <h3m1dc$5gs$1@fred.mathworks.com>...
> > Ok, I see what you want now
> > c(i) = min( A(1:b(i)) );

If I understand correctly, this should work:

z = meshgrid(1:k)>repmat(b',1,k); % use this to mask off the unwanted values with inf
A(z) = inf;
min(A,[],2);

I didn't check for timing, a loop might be faster.

This computes the minimum element in each row of A, it's not quite what I was looking for.

Nathan <ngreco32@gmail.com> wrote in message <f83d9ae3-79bf-4717-be07-cb7ac76d00a1@12g2000pri.googlegroups.com>...
> On Jul 16, 9:13?am, "jcurr Curran" <johncurra...@yahoo.com> wrote:
> > Right, but that method involves looping over each i. Is there a way to do this without loops?
> >
> > "Darren Rowland" <darrenjremovethisrowl...@hotmail.com> wrote in message <h3m1dc$5g...@fred.mathworks.com>...
> > > Ok, I see what you want now
> > > c(i) = min( A(1:b(i)) );
>
> A = magic(10);
> b = [1:10]';
> c = min(A(b,:)')';
>
> c =
>
> 1
> 7
> 4
> 3
> 2
> 17
> 5
> 6
> 10
> 11
>
> How about that one?
> -Nathan

"jcurr Curran" <johncurran20@yahoo.com> wrote in message <h3lt89$b6e$1@fred.mathworks.com>...
> Hi all,
>
> Suppose I have a n x k matrix A and a n x 1 column vector b. b contains integers between 1 and k. I want to produce a n x 1 column vector c, which is defined by c(i) = min {A(i,1),A(i,2),...,A(i,b(i)}. This would be easy with loops, but I want code which will run as fast as possible (the matrices are large, and the operation will be performed many times).

Vectorized code MAY NOT NECESSARILY run as fast as code with loops, especially for large matricies.

>
> To clarify, if b were (k,...,k)' then c would contain the minimum elements in each row of A.

On Jul 16, 10:15 am, "jcurr Curran" <johncurra...@yahoo.com> wrote:
> This computes the minimum element in each row of A, it's not quite what I was looking for.

Ah, I get what you mean now.
I haven't been able to come up with anything other than loops for this
problem.
What is so bad about having a loop anyways? It's not that slow.
How big is your matrix A?
With a basic for loop
for i = 1:size(A,1)
c(i) = min(A(i,1:b(i)));
end

computation times aren't too bad...
-Nathan

http://www.mathworks.com/matlabcentral/newsreader/view_thread/256123#665287

"jcurr Curran" <johncurran20@yahoo.com> wrote in message <h3lt89$b6e$1@fred.mathworks.com>...
> Hi all,
>
> Suppose I have a n x k matrix A and a n x 1 column vector b. b contains integers between 1 and k. I want to produce a n x 1 column vector c, which is defined by c(i) = min {A(i,1),A(i,2),...,A(i,b(i)}. This would be easy with loops, but I want code which will run as fast as possible (the matrices are large, and the operation will be performed many times).
-------

Another option


Amod=A;
Amod( bsxfun(@lt,b,(1:k)) )=nan;
c=min(Amod,[],2);

>
>
> Amod=A;
> Amod( bsxfun(@lt,b,(1:k)) )=nan;
> c=min(Amod,[],2);

A remark: When it's possible use alternative number other than NaN. Operation with NaN is usually much slowest. In this specific thread, use Inf.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h3o2o3$7g4$1@fred.mathworks.com>...
> >
> >
> > Amod=A;
> > Amod( bsxfun(@lt,b,(1:k)) )=nan;
> > c=min(Amod,[],2);
>
> A remark: When it's possible use alternative number other than NaN. Operation with NaN is usually much slowest. In this specific thread, use Inf.
------

I'd be curious to know why this is true in this case. Surely min() bails out as soon as it sees either an Inf or a Nan. Is there a reason it takes longer to recognize a Nan than an Inf?

I can see no difference in speed (nan vs. inf), but Matt's solution is incomplete as I understand the problem.


% Data
N = 1200;
A = round(rand(N)*20);
B = randperm(N);

% obvious engine.
tic
for ii = N:-1:1
   C(ii,1) = min(A(ii,1:B(ii))); % OP wants column vector.
end
toc

% faster engine for this data.
tic
for ii = N:-1:1
    m = A(ii);
    for jj = 1:B(ii)
        if A(ii,jj)<m
            m = A(ii,jj);
        end
    end
   C2(ii,1) = m;
end
toc

% Unfinished(?) engine.
tic
Amod = A;
Amod( bsxfun(@lt,B,(1:N)) ) = nan;
c = min(Amod,[],2);
toc

whos
isequal(C,C2) % Yes
isequal(C,c) % No

"Matt Fig" <spamanon@yahoo.com> wrote in message <h3o54v$hc9$1@fred.mathworks.com>...
> I can see no difference in speed (nan vs. inf), but Matt's solution is incomplete as I understand the problem.
>
>
> % Data
> N = 1200;
> A = round(rand(N)*20);
> B = randperm(N);

It's because randperm() produces a row vector, whereas I assume B is a column vector (as did the OP). When you insert

B=B(:);

all 3 methods come into agreement.

On Jul 16, 2:13 pm, "Matt Fig" <spama...@yahoo.com> wrote:
> I can see no difference in speed (nan vs. inf), but Matt's solution is incomplete as I understand the problem.
>
> % Data
> N = 1200;
> A = round(rand(N)*20);
> B = randperm(N);
>
> % obvious engine.
> tic
> for ii = N:-1:1
>    C(ii,1) = min(A(ii,1:B(ii)));  % OP wants column vector.
> end
> toc
>
> % faster engine for this data.
> tic
> for ii = N:-1:1
>     m = A(ii);
>     for jj = 1:B(ii)
>         if A(ii,jj)<m
>             m = A(ii,jj);
>         end
>     end
>    C2(ii,1) = m;
> end
> toc
>
> % Unfinished(?) engine.
> tic
> Amod = A;
> Amod( bsxfun(@lt,B,(1:N)) ) = nan;
> c = min(Amod,[],2);
> toc
>
> whos
> isequal(C,C2)  % Yes
> isequal(C,c)  % No

The last engine does work. B is supposed to be nx1, not 1xn
: )
But yeah, your for loop is faster than the obvious one.
-Nathan

It's not the first time I observe much slower operation on NaN, and I did very careful timing in various development of codes. I know that by default Matlab NaN is a "quiet" NaN (as opposed) to signaled. So in principle it does not trigger any floating point handler. So I don't have any explanation.

Bruno

n = 1000;
k = 1000;
A = rand(n,k);
b = ceil(k*rand(n,1));

tic
Amod=A;
Amod( bsxfun(@lt,b,(1:k)) )=inf;
c2=min(Amod,[],2);
toc % Elapsed time is 0.028898 seconds.
clear Amod c1

tic
Amod=A;
Amod( bsxfun(@lt,b,(1:k)) )=nan;
c1=min(Amod,[],2);
toc % Elapsed time is 0.119306 seconds.

% Bruno

"Matt " <xys@whatever.com> wrote in message <h3o5v5$d8c$1@fred.mathworks.com>...

> It's because randperm() produces a row vector, whereas I assume B is a column vector (as did the OP). When you insert
>
> B=B(:);
>
> all 3 methods come into agreement.

(or B = randperm(N)';)

D'oh. My stupid oversight. Sorry Matt.

"Matt " <xys@whatever.com> wrote in message <h3o5v5$d8c$1@fred.mathworks.com>...
> "Matt Fig" <spamanon@yahoo.com> wrote in message <h3o54v$hc9$1@fred.mathworks.com>...
> > I can see no difference in speed (nan vs. inf), but Matt's solution is incomplete as I understand the problem.
> >
> >
> > % Data
> > N = 1200;
> > A = round(rand(N)*20);
> > B = randperm(N);
>
> It's because randperm() produces a row vector, whereas I assume B is a column vector (as did the OP). When you insert
>
> B=B(:);
>
> all 3 methods come into agreement.

This also probably explains why you see no significant difference between nan's and inf's in my version. With B a row vector, Amod gets truncated to an Nx1 vector. It inadvertently reduces the complexity of the min() operation by a factor of N.

I definitely see a significant speed-up, when using Infs as Bruno suggested:


%data
k=2000;
A=rand(k); b=randperm(k)';

tic;
 
 Amod=A;
 Amod( bsxfun(@lt,b,(1:k)) )=nan;
 c=min(Amod,[],2);

 toc;
%Elapsed time is 0.708845 seconds.

 tic;
 
 Amod=A;
 Amod( bsxfun(@lt,b,(1:k)) )=inf;
 c=min(Amod,[],2);

 toc;
%Elapsed time is 0.236525 seconds.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h3o6ae$6rr$1@fred.mathworks.com>...
> It's not the first time I observe much slower operation on NaN, and I did very careful timing in various development of codes. I know that by default Matlab NaN is a "quiet" NaN (as opposed) to signaled. So in principle it does not trigger any floating point handler. So I don't have any explanation.


Now that people have corrected my error (thanks all :-)) I DO see the speed difference too. I have no reason for this either, but it is good to know for future reference.

"Matt Fig" <spamanon@yahoo.com> wrote in message <h3o6c9$ag5$1@fred.mathworks.com>...
> "Matt " <xys@whatever.com> wrote in message <h3o5v5$d8c$1@fred.mathworks.com>...
>
> > It's because randperm() produces a row vector, whereas I assume B is a column vector (as did the OP). When you insert
> >
> > B=B(:);
> >
> > all 3 methods come into agreement.
>
> (or B = randperm(N)';)
>
> D'oh. My stupid oversight. Sorry Matt.

Well, it's all moot. The obvious engine is the fastest, even in the most pessimistic case where B(:)=N.