Welford's Online Algorithm for Mean and Variance on Microcontrollers
Implement the ArdentZScore struct and update function to compute running mean and variance on microcontrollers without storing all samples, and use EWMA drift detection for slow changes.
Implement the ArdentZScore struct and update function in your MCU code to compute running mean and variance without storing all samples.
Summary
Welford's algorithm computes mean and variance in a single pass, using only three values, making it ideal for microcontrollers with limited RAM. The ArdentZScore struct stores count, mean, M2, threshold_sigma, min_samples, and window_size, totaling 24 bytes. The update function increments count, calculates delta and delta2, updates mean and M2, and checks min_samples before computing variance and standard deviation. It returns a boolean indicating whether the z‑score exceeds the configured threshold, avoiding negative variance by using Welford's method. The article also introduces an EWMA drift detector with fast and slow alphas to catch slow drifts that z‑score misses. The EWMA struct holds ewma_fast, ewma_slow, alpha_fast, alpha_slow, threshold, and count, and updates them with exponential smoothing. The drift detector returns true when the difference between fast and slow EWMA exceeds the threshold, providing a complementary anomaly detection. These lightweight algorithms enable stable statistical monitoring on devices with only 320 KB of RAM.
Key changes
- Uses three running values (count, mean, M2) to maintain mean and variance.
- Update step calculates delta and delta2, updates mean and M2, and checks min_samples before computing variance.
- Computes variance as M2/(count-1) and standard deviation as sqrt(variance).
- Returns z‑score > threshold_sigma, avoiding negative variance via Welford's method.
- Provides EWMA drift detection with fast and slow alphas to catch slow drifts.
- EWMA struct holds ewma_fast, ewma_slow, alpha_fast, alpha_slow, threshold, and count.
- Drift detector returns true when |ewma_fast - ewma_slow| exceeds threshold.