Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was looking at some source code that was described as 'maintaining a moving average over the previous 10 minutes', and noticed it uses the exponential function. Now its been a while since my university study, and i didnt take as many numerical analysis type math topics as I wish I had (mostly vector calc and diff equations), but I cannot undertand how this algorithm works and I really would like to:

Geodesic g = new Geodesic(lat1, lon1, lat2, lon2);
double t = (cal.getTimeInMillis() - ts.getTimeInMillis()) / 1000.0D;
if (t > 0.0D)
{
    double s = 3600.0D * g.distance() / t;
    if ((0.0D != sog) && (0.0D != s))
    {
        double d = 1.0D - Math.exp(-t / 600.0D);
        sog = (d * s + (1.0D - d) * sog);
    }
    else
    {
        sog = s;
    }
}

Basically position is updated every minute or so, with some uncertainty in the exact time values between the actual updates, hence some averaging over time is needed, I just can't figure out how the 2 lines within the if() statement a acheive that.

The only link I can think of that may have relevance is that the 1st derivative of ln(x) is 1/x.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

The code can be abstracted as follows: we have a time series $S_t$ whose noisy values are observed at discrete samples of time. The averaging estimate used is $$\bar{S}_{t+1} = d_t S_t + (1-d_t) \bar{S}_t $$ This is a type of averaging called the exponential moving average. It is exponential because we can expand out the above expression recursively to obtain $$\bar{S}_{t+1} = d_t S_t + (1-d_t)d_{t-1} S_{t-1} + (1-d_t)(1-d_{t-1})d_{t-2} S_{t-2} + \dots $$ If we for a moment imagine that $d_t$ is a constant, we can see that past samples get weighed down by a factor that decreases exponentially. This is a useful feature to have in an averaging procedure where you want to give more weighting to your recent samples than to your older samples. The exponential weighting gradually forgets the past at a rate determined by the magnitude of $d_t$.

There is one more slight wiggle in your setup which is that the spacing between the samples is not necessarily uniform. Consider again the equation $\bar{S}_{t+1} = d_t S_t + (1-d_t) \bar{S}_t $. If the time interval $\Delta t$ between the last sample $S_{t-1}$ and the current sample $S_t$ is too large, we want to make sure that the past (i.e., $\bar{S}_t$) gets less weight, i.e., $d_t$ should be close to $1$ (since the series could have changed its behavior in the elapsed time $\Delta t$). $d_t$ could have been chosen using any arbitrary function that approaches $1$ as $t$ grows. In this case, the function chosen is $d_t = 1-e^{-\Delta t/t_0}$.

share|improve this answer
    
Also note that the code and my answer use $t$ in different senses. In the code, $t$ is the gap between samples. In the answer, $t$ is the absolute time at which we get the samples and $\Delta t$ is the time difference. –  Dinesh Feb 12 '11 at 9:38
    
Excellent thanks... –  user6969 Feb 13 '11 at 8:30
    
Actually, your fine explanation makes sense, however (an oversight in explaining the code by me) the value t is only the most recent time interval, ie ts = cal; is later executed, so then $d_t = 1-e^{-\Delta t/600}$ which would change the meaning as compared to your explanation yes? the /600 would provide something like 'per 10 minutes' though –  user6969 Feb 13 '11 at 11:49
    
@Aaron: I don't quite understand the first part of your comment. Can you elaborate? As far as the /600 is concerned, that steps from the physics of the problem. The $t_0$ I had in my explanation is kind of a "half-life" - you can choose whatever value you want based on your needs. –  Dinesh Feb 13 '11 at 18:26
    
Ah ok, i thought u meant t0 as in the time origin. –  user6969 Feb 18 '11 at 4:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.