Exponentially discounted running average: a computer implementation

40 Views Asked by At

I need to write a computer algorithm that calculates the following exponentially discounted running average \begin{equation} \hat{u}(t) = \lambda \int_0^t u(s) \exp{\left[-\lambda(t - s)\right]} ds\,, \end{equation} where $u(t)$ is an arbitrary function evolving with time $t$, and $\lambda$ is a parameter that represents the "memory" of the average.

I have two problems: first, I need to convert this formula into a discrete sum (my time steps $\Delta t$ are discretised), second, I would like to obtain an incremental update rule as \begin{equation} \hat{u}(t) \leftarrow \hat{u}(t+\Delta t) \end{equation} so that I do not have to keep track of all the past evolution of the function $u(t)$, but only of the previous time step.

1

There are 1 best solutions below

2
On BEST ANSWER

Indeed, fix a time step $\Delta t > 0$ and define $u[n] = u(n\Delta t)$ and $\hat{u}[n] = \hat{u}(n\Delta t)$, respectively. Then

\begin{align*} \hat{u}[n] &= \lambda \int_{0}^{n\Delta t} u(s) \exp(-\lambda(n\Delta t-s)) \, \mathrm{d}s \\ &= \lambda e^{-n\lambda \Delta t} \int_{0}^{n\Delta t} u(s) e^{\lambda s} \, \mathrm{d}s, \end{align*}

and so,

\begin{align*} \hat{u}[n+1] - e^{-\lambda \Delta t} \hat{u}[n] &= \lambda e^{-(n+1)\lambda \Delta t} \int_{n\Delta t}^{(n+1)\Delta t} u(s) e^{\lambda s} \, \mathrm{d}s \\ &\approx \lambda e^{-(n+1)\lambda \Delta t} \int_{n\Delta t}^{(n+1)\Delta t} u[n+1] e^{\lambda s} \, \mathrm{d}s \\ &= (1 - e^{-\lambda \Delta t}) u[n+1]. \end{align*}

So it follows that, with $\mu = 1 - e^{-\lambda \Delta t} \approx \lambda \Delta t$, we get the approximate update rule

$$ \hat{u}[n+1] \approx (1 - \mu) \hat{u}[n] + \mu u[n+1], \tag{*} $$

which is exactly the recurrence relation @Jeroen Boschma mentioned in the comment.


Addendum. Here is another derivation. By the Leibniz's integral rule,

\begin{align*} \frac{\mathrm{d}}{\mathrm{d}t} \hat{u}(t) &= \lambda u(t) e^{-\lambda(t-t)} + \lambda \int_{0}^{t} u(s)(-\lambda)e^{-\lambda(t-s)} \, \mathrm{d}s \\ &= \lambda u(t) - \lambda \hat{u}(t). \end{align*}

Replacing the derivative $\frac{\mathrm{d}}{\mathrm{d}t} \hat{u}(t)$ by $\frac{\hat{u}(t+\Delta t) - \hat{u}(t)}{\Delta t}$, we get

$$ \frac{\hat{u}(t+\Delta t) - \hat{u}(t)}{\Delta t} \approx \lambda u(t) - \lambda \hat{u}(t), $$

or equivalently,

$$ \hat{u}(t+\Delta t) \approx (1 - \lambda \Delta t) \hat{u}(t) + (\lambda \Delta t) u(t). $$

Considering only the time steps that are integer multiples of $\Delta t$, this yields a recurrence relation that is identical to $\text{(*)}$ up to the approximations $1 - e^{-\lambda \Delta t} \approx \lambda \Delta t$ and $u(t) \approx u(t+\Delta t)$.