Re:Median and Mad Revisited with an Online Estimator
by Lemaxoxo on Thursday April 09, 2020 @08:55AM
(#22822050)
Would you happen the memory complexity of this algorithm? I maintain an online machine learning library written in Python, called creme, where we implement online statistics. We have a generic onine algorithm for estimating quantiles, and so a specific algorithm for estimating medians would be welcome. I'm always on the lookout for such online algorithms.
[ Parent
| on HN ]
Re:Median and Mad Revisited with an Online Estimator
by AnthonyLloyd on Thursday April 09, 2020 @09:09AM
(#22822152)
It's a fixed memory size but gets released when you move into the recursive part. Increasing the fixed part will give you a better starting estimate.
See here for quantiles: https://stackoverflow.com/questions/1058813/on-line-iterator...
The P^2 algorithm used in creme is interesting. For the median it would give a 2 sided median deviation. Maybe this could be changed slightly to be symmetric and give Median and MAD. I'll look into.