MATLAB Central Newsreader - vectorize finding upper envelope of vector

vectorize finding upper envelope of vector

ashipyard — Thu, 13 Mar 2008 18:30:21 -0400

I hope someone can help me vectorize some code.

I have a vector a. I want to return the upper envelope of a,
based on its original sort order.

E.g.

if a = [2 3 4 2 7 5 8]

I would want to return: [2 3 4 4 7 7 8].

Clearly this is very easy in a for loop.

for i=2:length(a)
  if (a(i)<a(i-1))
    a(i)=a(i-1);
  end
end

However, I can't think of an easy way to vectorize this.
Looping is slow when the length of a is large.

Thank you for your help

Re: vectorize finding upper envelope of vector

Yuri Geshelin — Thu, 13 Mar 2008 19:31:57 -0400

Re: vectorize finding upper envelope of vector

ashipyard — Thu, 13 Mar 2008 21:29:02 -0400

"Yuri Geshelin" <geshelin@hotmail.com> wrote in message
<frbvfd$bj4$1@fred.mathworks.com>...
> ifi = find(diff(a)<0)
> a(ifi+1)=a(ifi)
>

Thanks for your reply, however this doesn't work how I want.
Perhaps I didn't explain my problem clearly enough.

I would like each element to be the highest from all
previous elements.

So, if if

a=[1 2 3 4 3 2 3 5]

then I would like this to become

[1 2 3 4 4 4 4 5].

Using the code you provided, this would yield

[1 2 3 4 4 3 3 5] which isn't what I after.

Re: vectorize finding upper envelope of vector

Dan Haeg — Thu, 13 Mar 2008 22:58:01 -0400

"ashipyard " <andrewshipyard@hush.com> wrote in message
<frc6au$ehp$1@fred.mathworks.com>...
> "Yuri Geshelin" <geshelin@hotmail.com> wrote in message
> <frbvfd$bj4$1@fred.mathworks.com>...
> > ifi = find(diff(a)<0)
> > a(ifi+1)=a(ifi)
> >
>
> Thanks for your reply, however this doesn't work how I want.
> Perhaps I didn't explain my problem clearly enough.
>
> I would like each element to be the highest from all
> previous elements.
>
> So, if if
>
> a=[1 2 3 4 3 2 3 5]
>
> then I would like this to become
>
> [1 2 3 4 4 4 4 5].
>
> Using the code you provided, this would yield
>
> [1 2 3 4 4 3 3 5] which isn't what I after.

this may run fast enough.

a=[1 2 3 4 3 2 3 5]
ifi = find(diff(a)<0)
while ~isempty(ifi)
a(ifi+1)=a(ifi)
ifi = find(diff(a)<0)
end

Re: vectorize finding upper envelope of vector

Roger Stafford — Thu, 13 Mar 2008 23:07:02 -0400

"ashipyard " <andrewshipyard@hush.com> wrote in message <frbrrt$n43
$1@fred.mathworks.com>...
> I hope someone can help me vectorize some code.
>
> I have a vector a. I want to return the upper envelope of a,
> based on its original sort order.
>
> E.g.
>
> if a = [2 3 4 2 7 5 8]
>
> I would want to return: [2 3 4 4 7 7 8].
>
> Clearly this is very easy in a for loop.
>
> for i=2:length(a)
> if (a(i)<a(i-1))
> a(i)=a(i-1);
> end
> end
>
> However, I can't think of an easy way to vectorize this.
> Looping is slow when the length of a is large.
>
> Thank you for your help
----------
  What you are asking for is a "cumulative" maximum function. I have seen
this question arise many times on this newsgroup and each time no-one
seems to have been able to come up with a good vectorized solution.
Furthermore, even if someone did manage to stumble across some magical
combination of such things as cumsums, diffs, and whatnot, that would
accomplish the task, it is highly likely that, at least on the newer matlab
versions, it would take far longer to execute than doing it your for-loop way.

  I strongly suspect that it would be comparatively easy for Mathworks, if they
thought it was worthwhile, to devise a fast cumulative maximum function at
the low level coding which is available to them and which would execute with
the same speed as 'sum', 'find', etc., but until and unless they do, you may
have to be content with the for-loop method. There is no disgrace in using a
for-loop. It is a highly essential construct in the matlab language.

  Remember, each of the so-called vectorized operations is accomplished in
the same way it would be done in a for-loop or the like, one step at a time.
To do 'sum', the computer adds the first number to the second, then adds
their sum to the third, then that sum to the fourth one, etc., just as a for-loop
would do. However, doing this at low level coding can eliminate a certain
amount of overhead that is associated with for-loop indexing executed at a
higher language level.

Roger Stafford

Re: vectorize finding upper envelope of vector

Jos — Fri, 14 Mar 2008 15:47:01 -0400

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <frcc2m$h6i$1@fred.mathworks.com>...
> "ashipyard " <andrewshipyard@hush.com> wrote in message
<frbrrt$n43
> $1@fred.mathworks.com>...
> > I hope someone can help me vectorize some code.
> >
> > I have a vector a. I want to return the upper envelope of a,
> > based on its original sort order.
> >
> > E.g.
> >
> > if a = [2 3 4 2 7 5 8]
> >
> > I would want to return: [2 3 4 4 7 7 8].
> >
> > Clearly this is very easy in a for loop.
> >
> > for i=2:length(a)
> > if (a(i)<a(i-1))
> > a(i)=a(i-1);
> > end
> > end
> >
> > However, I can't think of an easy way to vectorize this.
> > Looping is slow when the length of a is large.
> >
> > Thank you for your help
> ----------
> What you are asking for is a "cumulative" maximum
function. I have seen
> this question arise many times on this newsgroup and each
time no-one
> seems to have been able to come up with a good vectorized
solution.
> Furthermore, even if someone did manage to stumble across
some magical
> combination of such things as cumsums, diffs, and whatnot,
that would
> accomplish the task, it is highly likely that, at least on
the newer matlab
> versions, it would take far longer to execute than doing
it your for-loop way.
>
> I strongly suspect that it would be comparatively easy
for Mathworks, if they
> thought it was worthwhile, to devise a fast cumulative
maximum function at
> the low level coding which is available to them and which
would execute with
> the same speed as 'sum', 'find', etc., but until and
unless they do, you may
> have to be content with the for-loop method. There is no
disgrace in using a
> for-loop. It is a highly essential construct in the
matlab language.
>
> Remember, each of the so-called vectorized operations is
accomplished in
> the same way it would be done in a for-loop or the like,
one step at a time.
> To do 'sum', the computer adds the first number to the
second, then adds
> their sum to the third, then that sum to the fourth one,
etc., just as a for-loop
> would do. However, doing this at low level coding can
eliminate a certain
> amount of overhead that is associated with for-loop
indexing executed at a
> higher language level.
>
> Roger Stafford
>
>

A one-line vectorized cumulative maximum function:

  a = [2 3 4 2 7 5 8] % row vector
  CMA = max(triu(toeplitz(a)))

  % -> CMA = 2 3 4 4 7 7 8

which, however(!), will create an intermediate (numel(A).^2)
matrix that may cause memory troubles for long vectors.

SLIDEFUN on the File Exchange may be of interest to you as
well (shameful self promotion ...).

hth
Jos

Re: vectorize finding upper envelope of vector

Arthur G — Fri, 14 Mar 2008 15:59:33 -0400

On 2008-03-14 11:47:01 -0400, "Jos " <DELjos@jasenDEL.nl> said:
> A one-line vectorized cumulative maximum function:
>
> a = [2 3 4 2 7 5 8] % row vector
> CMA = max(triu(toeplitz(a)))
>
> % -> CMA = 2 3 4 4 7 7 8
>
> which, however(!), will create an intermediate (numel(A).^2)
> matrix that may cause memory troubles for long vectors.

Another caveat: the above one-liner won't work if the vector starts
with any negative numbers.

Re: vectorize finding upper envelope of vector

Roger Stafford — Fri, 14 Mar 2008 17:29:02 -0400

"Jos " <DELjos@jasenDEL.nl> wrote in message <fre6ll$p28
$1@fred.mathworks.com>...
> A one-line vectorized cumulative maximum function:
>
> a = [2 3 4 2 7 5 8] % row vector
> CMA = max(triu(toeplitz(a)))
>
> % -> CMA = 2 3 4 4 7 7 8
>
> which, however(!), will create an intermediate (numel(A).^2)
> matrix that may cause memory troubles for long vectors.
>
> SLIDEFUN on the File Exchange may be of interest to you as
> well (shameful self promotion ...).
>
> hth
> Jos
-------
Thanks Jos. I stand corrected. I should have done more thorough searching
before making my claim.

However, I do worry about its execution speed since it is an order n^2
algorithm rather than the order n of the OP's for-loop method. On my
ancient matlab version it runs about three times as long as the for-loop, even
for a 32-element vector.

Roger Stafford

Re: vectorize finding upper envelope of vector

Roger Stafford — Fri, 14 Mar 2008 19:13:03 -0400

Arthur G <gorramfreak+news@gmail.com> wrote in message <47daa0e5$0
$307$b45e6eb0@senator-bedfellow.mit.edu>...
> On 2008-03-14 11:47:01 -0400, "Jos " <DELjos@jasenDEL.nl> said:
> > A one-line vectorized cumulative maximum function:
> >
> > a = [2 3 4 2 7 5 8] % row vector
> > CMA = max(triu(toeplitz(a)))
> >
> > % -> CMA = 2 3 4 4 7 7 8
> >
> > which, however(!), will create an intermediate (numel(A).^2)
> > matrix that may cause memory troubles for long vectors.
>
> Another caveat: the above one-liner won't work if the vector starts
> with any negative numbers.
-------
Jos could easily correct for that with:

CMA = max(toeplitz(repmat(a(1),size(a)),a))

Roger Stafford