4
$\begingroup$

I wish to calculate the running mean absolute deviation (MAD) without storing the previous n data points. This calculation is for a continuous stream of data, i.e. infinite length. I am trying to calculated the running MAD for a window of samples of size n but without storing the last n points. In other words

$MAD_k=MAD_{k-1}+f(u_k)$

where k is the index of the current sample, and $u_k$ is the current data point in a sequence. Is there a way to get an exact or approximate measure of the MAD using this approach? I currently calculate the exponentially-weighted moving average like this.

$\endgroup$
5
  • 1
    $\begingroup$ Mean or Median AD? MAD is usually defined with the median. $\endgroup$ Commented Jan 29, 2021 at 8:44
  • $\begingroup$ Preferably the mean, but the median may also be of use. In this case, an approximate measure of the deviation is sufficient. $\endgroup$
    – mr_js
    Commented Jan 29, 2021 at 9:26
  • $\begingroup$ Can you store some statistics about past data, aside from $MAD_{k-1}$? $\endgroup$ Commented Jan 29, 2021 at 10:07
  • $\begingroup$ Absolute deviation with respect to what? Mean, median, or something else? The usual "MAD" is the median absolute deviation from the median.. In that case, the solution is to use an online quantile algorithm. Otherwise, you need a combination of such an algorithm and a running mean (or running whatever). Please clarify. $\endgroup$
    – whuber
    Commented Jan 29, 2021 at 16:18
  • 2
    $\begingroup$ Mean absolute deviation with respect to the mean. I am using an exponentially-weighted moving average $\endgroup$
    – mr_js
    Commented Jan 29, 2021 at 17:37

1 Answer 1

4
$\begingroup$

There is no (useful) exact recursion, but there is an approximate one

Since your comment specified that you prefer to use the MAD around the mean, I will proceed for that case. Given an observed sample vector $\mathbf{x}_n$ this form of the the MAD statistic is:

$$\text{MAD}(\mathbf{x}_n) \equiv \frac{1}{n} \sum_{i=1}^n |x_i - \bar{x}_n|.$$

If we define the values $s_{n:i} \equiv |x_i - \bar{x}_{n}|$ we can write $\text{MAD}(\mathbf{x}_n) = \frac{1}{n} \sum_{i=1}^n s_{n:i}$. We also define the corresponding ordered values $0 \leqslant s_{n:(1)} \leqslant \cdots \leqslant s_{n:(n)}$ and the quantity:

$$r_n \equiv \sum_{i=1}^n \mathbb{I} \Big( |x_{n+1} - \bar{x}_{n}| > (n+1) |x_i - \bar{x}_{n}| \Big).$$

Using these statistics we can write the next value of the MAD statistic as:

$$\begin{align} \text{MAD}(\mathbf{x}_{n+1}) &= \frac{1}{n+1} \sum_{i=1}^{n+1} |x_i - \bar{x}_{n+1}| \\[6pt] &= \frac{1}{n+1} \sum_{i=1}^{n+1} \Bigg| x_i - \frac{n \bar{x}_{n} + x_{n+1}}{n+1} \Bigg| \\[6pt] &= \frac{1}{n+1} \sum_{i=1}^{n+1} \Bigg| x_i + \frac{1}{n+1} \cdot \bar{x}_{n} - \frac{1}{n+1} \cdot \bar{x}_{n} - \frac{n \bar{x}_{n} + x_{n+1}}{n+1} \Bigg| \\[6pt] &= \frac{1}{n+1} \sum_{i=1}^{n+1} \Bigg| (x_i - \bar{x}_{n}) - \frac{1}{n+1} \cdot (x_{n+1} - \bar{x}_n) \Bigg| \\[6pt] &=\quad \frac{1}{n+1} \sum_{i=1}^{n+1} \Bigg( |x_i - \bar{x}_{n}| - \frac{1}{n+1} \cdot |x_{n+1} - \bar{x}_{n}| \Bigg) \\[6pt] &\quad + \frac{2}{n+1} \sum_{i=1}^{r_n} \Bigg( \frac{1}{n+1} \cdot |x_{n+1} - \bar{x}_{n}| - s_{n:(i)} \Bigg) \\[6pt] &=\quad \frac{n}{n+1} \cdot \Bigg[ \text{MAD}(\mathbf{x}_{n}) + \frac{1}{n+1} \cdot |x_{n+1} - \bar{x}_{n}| \Bigg] \\[6pt] &\quad + \frac{2}{n+1} \sum_{i=1}^{r_n} \Bigg( \frac{1}{n+1} \cdot |x_{n+1} - \bar{x}_{n}| - s_{n:(i)} \Bigg). \\[6pt] \end{align}$$

This is an exact recursion, but it requires you to keep track of at least as many statistics as the number of sample values, so it is no more parsimonious than keeping track of the whole sample and computing the MAD statistic from scratch.


An approximate recursion: When $n$ is large it is likely that $r_n$ is small, so we may approximate this equation by assuming that the last term is zero. This gives the approximate recursion:

$$\text{MAD}(\mathbf{x}_{n+1}) \approx \frac{n}{n+1} \cdot \Bigg[ \text{MAD}(\mathbf{x}_{n}) + \frac{1}{n+1} \cdot |x_{n+1} - \bar{x}_{n}| \Bigg].$$

This gives you a simple approximating recursive equation that requires you to keep track of the sample mean and the MAD statistic at each iteration. Of course, the recursion is not exact, since it is possible that $r_n > 0$, and in this case there is an additional positive term in the MAD recursion that is ignored in the approximation.

Unfortunately there is no exact recursion that accounts for this that does not require you to keep track of all the values. If you are looking for something that is better than the above approximation, but less onerous than keeping track of all the values in the sample, you could choose some modest upper bound $R$ for $r_n$ (e.g., an upper bound $R=2,3$, etc.) and keep track of the minimum deveiations for the mean up to that order. This would allow you to keep track of a few of the order statistics $s_{n:(1)} \leqslant \cdots \leqslant s_{n:(R)}$ up to the upper bound which would allow you to approximate using the first few terms in the last summation in the recursion. Using this method it is possible to get an approximate recursion that is quite accurate when $n$ is large.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.