# Median absolute deviation outlier detection for new data points

I have been reading this article for outlier detection and the method proposed works really well when applied over my data set. However, it would be great if i could run outlier check for new data points without recomputing median and MAD every time due to resource constraints.

Would it be theoretically justifiable to use pre-computed value of MAD and median to detect if an unseen point is an outlier while periodically updating these values ?

• Sure. That said their are many algorithm to update the median/mad (instead of recomputed them from scratch) each time a new datum is added. Updating a mad/median has O(1) complexity, so they come essentially for free marginal cost. Aug 7, 2018 at 20:13
• Hm i am unaware of such algorithm, the best i could find has O(logN). Perhaps you could show how to do this ? Basically i need a rolling median behavior where oldest points are deleted first.
– John
Aug 8, 2018 at 7:49
• ah, sorry, I got confused. You are correct the complexity of updating the median is O(logN) and not O(1). So if O(logN) is too high a cost, sure, not updating the median is the next cheapest thing. Aug 8, 2018 at 9:39
• you could write an answer with a simple yes, i would accept it. I wasn't sure if it is ok to do this.
– John
Aug 8, 2018 at 10:03
• I am not sure it is the best solution tho. What I would do is I would sample a random set of $M$ observations from the past and use that to compute a running median at cost $O(\log M)$. I would chose $M$ such that I could afford $O(\log M)$. In this way I would get two pairs of mads/medians: one from the fixed set of observations you already use and a second one from the running ones (based on $M$ observations). The final outlyingness of an incoming datum $y$ would be the maximum outlyingness of $y$ wrt to both sets pairs of mad/medians. Aug 8, 2018 at 10:10