Multiple pass moving average filter

I'm working with a multiple pass moving average filter.  I would like
to communicate with someone who is using or very familiar with
methods of treating the ends and reducing lag via assumption of
missing values, etc.

Alternatively any comments or referral to sources on this issue
would be highly appreciated.

edwards wrote:

> I'm working with a multiple pass moving average filter.

You can include the multiple passes into your filter (via multiple
self-convolution of the filter kernel), and then apply only one single
pass. OTOH, this doesn't allow you to filter as many passes as are
required until the filtered signal satisfies some criterion.

> I would like
> to communicate with someone who is using or very familiar with
> methods of treating the ends and reducing lag via assumption of
> missing values, etc.
>
> Alternatively any comments or referral to sources on this issue
> would be highly appreciated.

Perhaps you have to describe your application in more detail. You can,
for example, modify your moving average filter to have minimum phase
response given some magntiude response to improve the "promptness". Or
is your application aimed at extrapolation?

Regards,
Andor

> > I'm working with a multiple pass moving average filter.

Thank you for your response.

> You can include the multiple passes into your filter (via multiple
> self-convolution of the filter kernel), and then apply only one single
> pass. OTOH, this doesn't allow you to filter as many passes as are
> required until the filtered signal satisfies some criterion.

I'm using an odd number so that I always have a center points and
I'm using 3 passes to reduce more noise from the data.  My
application is a form of graduation -- where my data is probabilities.

I have searched various methods used in actuarial science and have
not seen much useful for real time data involving time sensitive risk
as opposed to historical data.  I use the same programming language
as many actuaries and have tested several methods used within the
field that are slower and not as effective as simple and exponential
smoothing.

Your suggestion of including the multiple passes into your filter (via
multiple self-convolution of the filter kernel) sounds very
interesting.
How would I do that?

> > I would like
> > to communicate with someone who is using or very familiar with
> > methods of treating the ends and reducing lag via assumption of
> > missing values, etc.
> >
> > Alternatively any comments or referral to sources on this issue
> > would be highly appreciated.

I have augmented an existing multiple moving average method to
suit my purpose.  It is fast and provides desirable historical results.
Adjustments will have to be made to treatment of the ends and
how I sequentially select the middle point to improve real time
results.  I am not a dsp person so this raises several questions
in my mine about the reliability of mulitiple mov ave filters.

Therefore I tried to replicate the results with simple exponential
smoothing.  I found that my testing all coefficients on over a
100 samples with 450 elements each that it would allow me
to obtain a 93 percent correlation with the multiple moving average
filter.  Still the standard deviation in using multiple moving average
was significantly better and the modification I made to it produced
much more "effective promptness".

I do not need to extrapolate the probabilites.  I need to communicate
with someone with which I can proof my modification and/or revise
them so the final design is consistent with sound dsp theory and usage.

Your comment below is exactly the tasks I'm seeking to complete
and verify that it is done correctly.

> Perhaps you have to describe your application in more detail. You can,
> for example, modify your moving average filter to have minimum phase
> response given some magntiude response to improve the "promptness". Or
> is your application aimed at extrapolation?
> 
> Regards,
> Andor

On 18 Aug 2006 18:33:24 -0700, edwards2107@comcast.net wrote:

>I'm working with a multiple pass moving average filter.  I would like
>to communicate with someone who is using or very familiar with
>methods of treating the ends and reducing lag via assumption of
>missing values, etc.
>
>Alternatively any comments or referral to sources on this issue
>would be highly appreciated.

Newbie: That would be like the sinc3 filters used in industrial ADCs
(CIC?)?

Tony (remove the "_" to reply by email)

Newport wrote:
> > > I'm working with a multiple pass moving average filter.
>
> Thank you for your response.
>
> > You can include the multiple passes into your filter (via multiple
> > self-convolution of the filter kernel), and then apply only one single
> > pass. OTOH, this doesn't allow you to filter as many passes as are
> > required until the filtered signal satisfies some criterion.
>
> I'm using an odd number so that I always have a center points and
> I'm using 3 passes to reduce more noise from the data.  My
> application is a form of graduation -- where my data is probabilities.

Interesting. I guess this poses special limitations on the "filter
type". I enclose this in quoation marks, because if the probability
space is finite, you cannot actually process your distribution with a
filter because convolution increases the length of the sequence. For
example, you have a distribution on the numbers {1, 2, 3}. FIR
filtering via convolution will, in general also return non-zero values
for {4, 5, ... N-4}, where N is the length of the filter kernel.
Truncating the output to the space {1, 2, 3} is not linear convolution.

>
> I have searched various methods used in actuarial science and have
> not seen much useful for real time data involving time sensitive risk
> as opposed to historical data.  I use the same programming language
> as many actuaries and have tested several methods used within the
> field that are slower and not as effective as simple and exponential
> smoothing.

If I remember correctly, exponential smoothing is a first order IIR
lowpass filter of the type

y_n = alpha y_{n-1} + beta x_n,   alpha + beta = 1,

where x_n is the input and y_n the output sequence. To comment on its
effectivity for smoothing, one would need to know the application.
There is nothing special about this filter which would make it stand
out in a class of filters (except its ease of implementation).

>
> Your suggestion of including the multiple passes into your filter (via
> multiple self-convolution of the filter kernel) sounds very
> interesting.
> How would I do that?

Simple, just use the fact that convolution is associative. For example,
if your input data is x_n and your finite filter kernel is h (the
moving average filter) , then

h * (h * (h * x_n) ) ) = (h * h * h) * x_n,

where * denotes the convolution operator. If H is the frequency
resposne of h, then multiple convolution with h just means that you
take powers in the frequency domain, ie.

 (h * h * h) * x_n    < = > H^3 X,

where X is the Fourier transformed of x_n. Iterated convolution is
usually an inefficient way to design filters. You can get the
performance of H^3 with less filter taps. A similar techniques called
filter sharpening is to apply 3 H^2 - 2 H^3, which improves both
stopband and passband ripple. This was, for exmaple, discussed here:

http://groups.google.com/group/comp.dsp/browse_frm/thread/87fbcc126c66fef6/063924123abe3460?#063924123abe3460

An example of iterated convolution: if h is the linear average, ie h =
1/m [1  1 .... 1] (m entries), then the z-transform H of h is equal to

H(z) = (1 - z^m) / (1 - z),

which means that the frequency response has m-1 zeros, spaced at the
m-th unit roots not equal to 1. Such a filter is good for removing
periodic signals with period Fs / m and no DC content, where Fs is the
sampling frequency. Repeated application of h will increase the order
of the zeros, effectively making this a lowpass filter with stopband
starting from Fs / m. It is however a very poor design for such a
lowpass filter, because the passband is not very flat - for the same
filter order, you can get much better performance. Hence iteration, or
sharpening, or not widely used for signal processing (at least where I
come from).
>
> > > I would like
> > > to communicate with someone who is using or very familiar with
> > > methods of treating the ends and reducing lag via assumption of
> > > missing values, etc.
> > >
> > > Alternatively any comments or referral to sources on this issue
> > > would be highly appreciated.
>
> I have augmented an existing multiple moving average method to
> suit my purpose.  It is fast and provides desirable historical results.
> Adjustments will have to be made to treatment of the ends and
> how I sequentially select the middle point to improve real time
> results.  I am not a dsp person so this raises several questions
> in my mine about the reliability of mulitiple mov ave filters.
>
> Therefore I tried to replicate the results with simple exponential
> smoothing.  I found that my testing all coefficients on over a
> 100 samples with 450 elements each that it would allow me
> to obtain a 93 percent correlation with the multiple moving average
> filter.  Still the standard deviation in using multiple moving average
> was significantly better and the modification I made to it produced
> much more "effective promptness".
>
> I do not need to extrapolate the probabilites.  I need to communicate
> with someone with which I can proof my modification and/or revise
> them so the final design is consistent with sound dsp theory and usage.
>
> Your comment below is exactly the tasks I'm seeking to complete
> and verify that it is done correctly.

You can, for example, read about transforming linear-phase filters
(such as the simple linear average) to minimum-phase filters here:

http://www.dspguru.com/howto/tech/minph.htm

Another option is some DSP book, an incomplete list thereof you can
find here:

http://www.dspguru.com/info/books/favor.htm

FWIW,
Andor

Thanks for your response.

I looked up info and sinc3 filters and what I've seen appears to be
implemented with dsp hardware.  I'm totally open to any solution
that I can use that will work as well as multi-pass moving average
as long as it works fast in real time.

Are there other methods equivalent to the sinc3 that can be
implemented with software?  Since I'm looking for a way to do
aggressive smoothing of probabilities in real time along with
getting fast response to jumps that may occur -- a computer
program would appear to be much simple and easier to use than
hardware.

However, I will follow up on any source you provide that might help
lead to a solution if you can break down the benefits in terms
someone outside the dsp field can understand.


Tony wrote:
> On 18 Aug 2006 18:33:24 -0700, edwards2107@comcast.net wrote:
>
> >I'm working with a multiple pass moving average filter.  I would like
> >to communicate with someone who is using or very familiar with
> >methods of treating the ends and reducing lag via assumption of
> >missing values, etc.
> >
> >Alternatively any comments or referral to sources on this issue
> >would be highly appreciated.
>
> Newbie: That would be like the sinc3 filters used in industrial ADCs
> (CIC?)?
> 
> Tony (remove the "_" to reply by email)

Hi Andor,

Thanks for the useful information in your detailed reply.  I will use
the sources you provided to gain more details on your suggestions.

Andor wrote:
> Newport wrote:
> > > > I'm working with a multiple pass moving average filter.
> >
> > Thank you for your response.
> >
> > > You can include the multiple passes into your filter (via multiple
> > > self-convolution of the filter kernel), and then apply only one single
> > > pass. OTOH, this doesn't allow you to filter as many passes as are
> > > required until the filtered signal satisfies some criterion.
> >
> > I'm using an odd number so that I always have a center points and
> > I'm using 3 passes to reduce more noise from the data.  My
> > application is a form of graduation -- where my data is probabilities.
>
> Interesting. I guess this poses special limitations on the "filter
> type". I enclose this in quoation marks, because if the probability
> space is finite, you cannot actually process your distribution with a
> filter because convolution increases the length of the sequence. For
> example, you have a distribution on the numbers {1, 2, 3}. FIR
> filtering via convolution will, in general also return non-zero values
> for {4, 5, ... N-4}, where N is the length of the filter kernel.
> Truncating the output to the space {1, 2, 3} is not linear convolution.
>
> >
> > I have searched various methods used in actuarial science and have
> > not seen much useful for real time data involving time sensitive risk
> > as opposed to historical data.  I use the same programming language
> > as many actuaries and have tested several methods used within the
> > field that are slower and not as effective as simple and exponential
> > smoothing.
>
> If I remember correctly, exponential smoothing is a first order IIR
> lowpass filter of the type
>
> y_n = alpha y_{n-1} + beta x_n,   alpha + beta = 1,
>
> where x_n is the input and y_n the output sequence. To comment on its
> effectivity for smoothing, one would need to know the application.
> There is nothing special about this filter which would make it stand
> out in a class of filters (except its ease of implementation).
>
> >
> > Your suggestion of including the multiple passes into your filter (via
> > multiple self-convolution of the filter kernel) sounds very
> > interesting.
> > How would I do that?
>
> Simple, just use the fact that convolution is associative. For example,
> if your input data is x_n and your finite filter kernel is h (the
> moving average filter) , then
>
> h * (h * (h * x_n) ) ) = (h * h * h) * x_n,
>
> where * denotes the convolution operator. If H is the frequency
> resposne of h, then multiple convolution with h just means that you
> take powers in the frequency domain, ie.
>
>  (h * h * h) * x_n    < = > H^3 X,
>
> where X is the Fourier transformed of x_n. Iterated convolution is
> usually an inefficient way to design filters. You can get the
> performance of H^3 with less filter taps. A similar techniques called
> filter sharpening is to apply 3 H^2 - 2 H^3, which improves both
> stopband and passband ripple. This was, for exmaple, discussed here:
>
> http://groups.google.com/group/comp.dsp/browse_frm/thread/87fbcc126c66fef6/063924123abe3460?#063924123abe3460
>
> An example of iterated convolution: if h is the linear average, ie h =
> 1/m [1  1 .... 1] (m entries), then the z-transform H of h is equal to
>
> H(z) = (1 - z^m) / (1 - z),
>
> which means that the frequency response has m-1 zeros, spaced at the
> m-th unit roots not equal to 1. Such a filter is good for removing
> periodic signals with period Fs / m and no DC content, where Fs is the
> sampling frequency. Repeated application of h will increase the order
> of the zeros, effectively making this a lowpass filter with stopband
> starting from Fs / m. It is however a very poor design for such a
> lowpass filter, because the passband is not very flat - for the same
> filter order, you can get much better performance. Hence iteration, or
> sharpening, or not widely used for signal processing (at least where I
> come from).
> >
> > > > I would like
> > > > to communicate with someone who is using or very familiar with
> > > > methods of treating the ends and reducing lag via assumption of
> > > > missing values, etc.
> > > >
> > > > Alternatively any comments or referral to sources on this issue
> > > > would be highly appreciated.
> >
> > I have augmented an existing multiple moving average method to
> > suit my purpose.  It is fast and provides desirable historical results.
> > Adjustments will have to be made to treatment of the ends and
> > how I sequentially select the middle point to improve real time
> > results.  I am not a dsp person so this raises several questions
> > in my mine about the reliability of mulitiple mov ave filters.
> >
> > Therefore I tried to replicate the results with simple exponential
> > smoothing.  I found that my testing all coefficients on over a
> > 100 samples with 450 elements each that it would allow me
> > to obtain a 93 percent correlation with the multiple moving average
> > filter.  Still the standard deviation in using multiple moving average
> > was significantly better and the modification I made to it produced
> > much more "effective promptness".
> >
> > I do not need to extrapolate the probabilites.  I need to communicate
> > with someone with which I can proof my modification and/or revise
> > them so the final design is consistent with sound dsp theory and usage.
> >
> > Your comment below is exactly the tasks I'm seeking to complete
> > and verify that it is done correctly.
>
> You can, for example, read about transforming linear-phase filters
> (such as the simple linear average) to minimum-phase filters here:
>
> http://www.dspguru.com/howto/tech/minph.htm
>
> Another option is some DSP book, an incomplete list thereof you can
> find here:
> 
> http://www.dspguru.com/info/books/favor.htm
> 
> FWIW,
> Andor

Newport wrote:
> Thanks for your response.
> 
> I looked up info and sinc3 filters and what I've seen appears to be
> implemented with dsp hardware.  I'm totally open to any solution
> that I can use that will work as well as multi-pass moving average
> as long as it works fast in real time.
> 
> Are there other methods equivalent to the sinc3 that can be
> implemented with software?  Since I'm looking for a way to do
> aggressive smoothing of probabilities in real time along with
> getting fast response to jumps that may occur -- a computer
> program would appear to be much simple and easier to use than
> hardware.
> 
> However, I will follow up on any source you provide that might help
> lead to a solution if you can break down the benefits in terms
> someone outside the dsp field can understand.
> 
> 
> Tony wrote:
> 
>>On 18 Aug 2006 18:33:24 -0700, edwards2107@comcast.net wrote:
>>
>>
>>>I'm working with a multiple pass moving average filter.  I would like
>>>to communicate with someone who is using or very familiar with
>>>methods of treating the ends and reducing lag via assumption of
>>>missing values, etc.
>>>
>>>Alternatively any comments or referral to sources on this issue
>>>would be highly appreciated.
>>
>>Newbie: That would be like the sinc3 filters used in industrial ADCs
>>(CIC?)?
>>
>>Tony (remove the "_" to reply by email)
> 
> 

The moving average filter is also known as a boxcar filter: all the 
coefficients are unity.  When you do multiple passes, it is the same as 
passing the data through 3 consecutive boxcar filters.  Knowing that, 
you can convolve the impulse responses of the boxcar filters to arrive 
at a single filter that does the same thing.  Convolution is basically 
sliding one filter's coefficients past the other and computing the sum 
of products for each alignment.

If your moving average is 5 samples, the response is [1 1 1 1 1]
convolving that with itself gives you the response of two passes, which 
would be
[1 2 3 4 5 4 3 2 1],
and the convolving that again with {1 1 1 1 1 ] yields an FIR filter 
with coefficients:
[1 3 6 10 15 18 19 18 15 10 6 3 1]

the software implementation the would perform the convolution of that 
filter with the most recent 13 samples:

y(k) = sum( x(k)*filt(k) ) for k=0 to 12.

Ray Andraka <ray@andraka.com> wrote in news:jaKGg.5726$SZ3.1767@dukeread04:

> If your moving average is 5 samples, the response is [1 1 1 1 1]


actually, [1 1 1 1 1]/5, otherwise you'll end up with a gain of 15 with 
three passes.

-- 
Scott
Reverse name to reply

Newport wrote:

>>>I'm working with a multiple pass moving average filter.
> 
> 
> Thank you for your response.
> 
> 
-- snip --
> 
> I have searched various methods used in actuarial science and have
> not seen much useful for real time data involving time sensitive risk
> as opposed to historical data.
-- snip --

Am I correct in my assumption that you are coming at this from the 
actuarial world, rather than the signals and systems world?

If you are trying to estimate some constant value whose measurement is 
corrupted by noise, or the state of some variable whose evolution is 
driven by a random process (and whose measurement is corrupted by 
noise), then you may want to investigate Kalman filtering.  If you can 
state your problem in terms of linear systems evolving in response to 
Gaussian random variables, and if your cost functions are quadratic, 
then you can find closed-form optimal solutions in the Kalman filter.

Given that it's been around for nearly 50 years now, there are 
extensions to the Kalman filter to take care of cases where the random 
processes aren't Gaussian, the cost functions aren't quadratic, or the 
systems aren't linear.

Kalman filter theory isn't easy, but it can save you a lot of fumbling 
in the dark testing half-baked filtering attempts*.

I'm currently reading Dan Simon's "Optimal State Estimation: Kalman, 
H-infinity, and Nonlinear Approaches", John Wiley & Sons, 2006.  It 
seems like a good text to me -- it matches what I know of detection & 
estimation theory, it presents all the necessary math, but it does so 
with an eye toward _using_ the math rather than just playing with all 
the pretty notation.  I recommend it highly.

* On the other hand, if you have exactly one problem to solve and a 
half-baked filter will get you close enough you can optimize for design 
time and just go for it.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google?  See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html