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 ?

  • $\begingroup$ 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. $\endgroup$
    – user603
    Aug 7, 2018 at 20:13
  • $\begingroup$ 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. $\endgroup$
    – John
    Aug 8, 2018 at 7:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – user603
    Aug 8, 2018 at 9:39
  • $\begingroup$ you could write an answer with a simple yes, i would accept it. I wasn't sure if it is ok to do this. $\endgroup$
    – John
    Aug 8, 2018 at 10:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – user603
    Aug 8, 2018 at 10:10


Your Answer

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