Streaming robust covariance estimation and sequential outlier detection
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "Streaming robust covariance estimation and sequential outlier detection".
Jane: Here's the gist of the paper. Robust estimation of the covariance matrix and detection of outliers remain major challenges in statistical data analysis, particularly when the proportion of contaminated observations increases with the size of the dataset<ref:2601.03957#pg2> Outliers can severely bias parameter estimates and induce a masking effect, whereby some outliers conceal the presence of other outliers, further complicating their detection<ref:2601.03957#pg2> In this paper, we focus on online covariance matrix estimation and outlier detection<ref:2601.03957#pg2> Specifically, we propose a new method for simultaneously and online estimating the geometric median and variance, which allows us to calculate the Mahalanobis distance for each incoming data point before deciding whether it should be considered an outlier<ref:2601.03957#pg2> To mitigate the masking effect, robust estimation techniques for the mean and variance are required<ref:2601.03957#pg2> Our approach uses the geometric median for robust estimation of the location and the median covariance matrix for robust estimation of the dispersion parameters<ref:2601.03957#pg2> The new online methods proposed for parameter estimation and outlier detection allow real-time identification of outliers as data are observed sequentially<ref:2601.03957#pg2> Novel Online Framework The authors propose a novel algorithm to estimate all the quantities of interest, including the median, the median covariation matrix, and the variance-covariance matrix in an online manner while simultaneously enabling online outlier detection<ref:2601.03957#pg2> This method is based on estimating the geometric median and the MCM<ref:2601.03957#pg2> The method involves updating estimates for the geometric median, the MCM, and a robust estimate of the variance sequentially<ref:2601.03957#pg2> The update scheme for a new data point involves calculating an estimate of the geometric median and the MCM, denoted by mn+1 and Vn+1 respectively<ref:2601.03957#pg2> Subsequently, the Mahalanobis distance is calculated using these estimates<ref:2601.03957#pg2> The procedure allows for real-time identification of outliers without needing to recompute previous estimates from scratch<ref:2601.03957#pg2> Robust Estimation Techniques The authors utilize robust estimation techniques to address the masking effect caused by outliers<ref:2601.03957#pg2> For location estimation, the geometric median is employed because it has a 50% breakdown point<ref:2601.03957#pg2> For dispersion parameters, the median covariance matrix is used for robust estimation of the variance<ref:2601.03957#pg2> The MCM provides access to the eigenvectors of the covariance matrix, which are then used to reconstruct a robust estimate of the covariance matrix<ref:2601.03957#pg2> The influence functions for the mean and variance under contamination are derived based on three types of contamination scenarios<ref:2601.03957#pg2> Specifically, the influence function for the variance is always bounded, whatever the value of ρ1<ref:2601.03957#pg2> Performance Evaluation and Comparison The performance of the proposed methods is demonstrated on simulated datasets<ref:2601.03957#pg2> The simulation design involves a mixture model combining a multivariate Gaussian reference distribution F0 with an outlier distribution F1<ref:2601.03957#pg2> The evaluation criteria include the Frobenius norm error of the covariance matrix estimate and the number of false positives and false negatives<ref:2601.03957#pg2> Under contamination scenarios A, B, and C, our robust methods maintain strong performance despite high contamination rates<ref:2601.03957#pg2> The non-robust sample covariance online method exhibits significant sensitivity to outliers<ref:2601.03957#pg2> The online and streaming methods do not exhibit false positive rates consistent with the nominal level of 5%<ref:2601.03957#pg2> Computational Efficiency The computational complexity analysis shows that the overall complexity is dominated by the spectral decomposition at each step<ref:2601.03957#pg2> The streaming approach, using batches of size s=d, reduces the number of time steps requiring costly spectral decomposition compared to the simple online approach with batches of size 1<ref:2601.03957#pg2> In all configurations, the streaming approach is about ten times faster than the simple online approach when comparing different sample sizes and dimensions<ref:2601.03957#pg2> Outlier Detection Mechanism Outlier detection relies on a Mahalanobis distance-based criterion where an observation is flagged if its scaled Mahalanobis distance exceeds a predefined threshold c<ref:2601.03957#pg2> To mitigate bias, the scaled Mahalanobis distance is corrected by using an online estimation of the median of past Mahalanobis distances<ref:2601.03957#pg2> The update rule for this median uses a classical Robbins–Monro stochastic approximation scheme<ref:2601.03957#pg2> This mechanism enables the procedure to be fully online and does not require storing past data or recomputation from scratch<ref:2601.03957#pg2> Convergence Characteristics The convergence along the iterations shows that all criteria vary a lot among early iterations<ref:2601.03957#pg2> However, a stable value is reached after 1000 or 2000 iterations, suggesting that online (or batch methods) are only relevant for large data sets<ref:2601.03957#pg2> The convergence speed depends on both the criterion and the contamination rate<ref:2601.03957#pg2> Implementation Details The algorithms were implemented in R and Rcpp 1.0.9, with code available upon request<ref:2601.03957#pg2> The simulation scenarios explore various contamination levels by varying the tuning parameters k, l, and ρ1<ref:2601.03957#pg2> The analysis confirms that taking k ≤ 0 or k ≥ 0 leads to completely symmetric situations<ref:2601.03957#pg2> The simulation results indicate that under scenario D, the false negative rate is high for all methods<ref:2601.03957#pg2> The oracle setting yields false negative rates exceeding 50% in this challenging setting<ref:2601.03957#pg2> Influence Functions of Parameters The influence function for the mean is unbounded for k ≥ 0<ref:2601.03957#pg2> For the variance, it is unbounded only for l ≥ 1<ref:2601.03957#pg2> The shape transformation (iii) shows that the influence function for the variance is always bounded, whatever the value of ρ1<ref:2601.03957#pg2> This motivates the choice to consider only l ≥ 1 in the simulation design<ref:2601.03957#pg2> Estimation of Geometric Median and MCM The geometric median can be estimated using the Weiszfeld’s algorithm, which is a fixed-point iteration method requiring O(N d) computations per iteration<ref:2601.03957#pg2> The MCM can be estimated using the Weisfeld’s algorithm adapted for the MCM, which requires O(N d squared T) computations<ref:2601.03957#pg2> An averaged stochastic gradient algorithm provides a faster and more adaptive way to estimate the geometric median<ref:2601.03957#pg2> The MCM estimation can be accelerated using an averaged stochastic gradient algorithm, which is defined recursively for all n ≥ 0<ref:2601.03957#pg2> Mahalanobis Distance Calculation The Mahalanobis distance for the new data point is calculated as Dbn+1 = Xd / j=1 1 λn+1
j: <ref:2601.03957#pg2> The calculation of the Mahalanobis distance has a complexity of order O(d 2)<ref:2601.03957#pg2> The scaled Mahalanobis distance is defined in Equation (1) and requires online estimation of the median of past Mahalanobis distances<ref:2601.03957#pg2> This scaling factor requires online estimation of the median of past Mahalanobis distances med(Db1,..., Dbn)<ref:2601.03957#pg2> The update rule for this median uses the classical Robbins–Monro stochastic approximation scheme<ref:2601.03957#pg2> Batch Processing Framework In the batch setting, new data arriving by block of size s is treated as a single statistical unit<ref:2601.03957#pg2> The updates for the geometric median and MCM involve averaged estimates based on the new block of data<ref:2601.03957#pg2> The main advantage of this method is that if s = d, the total complexity can be reduced to order O(N nMC d 2)<ref:2601.03957#pg2> This leads to a total calculus complexity of order O(N nMC d 2) for the streaming covariation-based methods<ref:2601.03957#pg2> The final calculation involves computing all Dˆn+1,i for i = 1,..., s<ref:2601.03957#pg2> Simulation Design and Results The simulation design uses a mixture model to mimic contaminated data with contamination rate r<ref:2601.03957#pg2> The results show that under scenarios A, B, and C, the covariance matrix estimation remains largely unaffected regardless of the estimation method employed<ref:2601.03957#pg2> Our robust methods maintain strong performance despite high contamination rates<ref:2601.03957#pg2> The online and streaming methods achieve perfect outlier detection for contamination rates up to 30% under scenario A<ref:2601.03957#pg2> The superior performance of the sample covariance online method is evident in the persistent masking effects<ref:2601.03957#pg2> The non-robust sample covariance online method struggles across scenarios<ref:2601.03957#pg2> Convergence Along Iterations Figure 4 shows how the Frobenius and the false positive and negative proportions evolve along the iterations of the proposed procedure<ref:2601.03957#pg2> All criteria vary a lot among early iterations, but a stable value is reached after 1000 or 2000 iterations<ref:2601.03957#pg2> This suggests that online methods are only relevant for large data sets<ref:2601.03957#pg2> The computation times show that the streaming approach is about ten times faster than the simple online approach when comparing different (n, d) configurations<ref:2601.03957#pg2> The discrepancy in false positive rates arises from an overestimation of Σ0 in terms of a larger determinant<ref:2601.03957#pg2> Scaling the Mahalanobis distance clearly fails to counterbalance this bias<ref:2601.03957#pg2> The robust methods maintain near-perfect detection rates across all but scenarios A and B<ref:2601.03957#pg2> Under scenario D, the false negative rate is high for all methods<ref:2601.03957#pg2> The oracle setting yields false negative rates exceeding 50% in this challenging setting<ref:2601.03957#pg2> The online and streaming methods maintain near-perfect detection rates across all but the scenarios A and B<ref:2601.03957#pg2> Parameter Influence Summary The influence function for the mean is unbounded for k ≥ 0<ref:2601.03957#pg2> For the variance, it is unbounded only for l ≥ 1<ref:2601.03957#pg2> The shape transformation (iii) shows that the influence function for the variance is always bounded, whatever the value of ρ1<ref:2601.03957#pg2> This motivates our choice to consider only l ≥ 1 in the simulation design<ref:2601.03957#pg2> The simulation results confirm that taking k ≤ 0 or k ≥ 0 leads to completely symmetric situations<ref:2601.03957#pg2> The contamination rate r is varied to attain Kullback–Leibler divergence KL(F0, F1) of 0, 1, 5, 10, and 25 in dimension d = 10<ref:2601.03957#pg2> The resulting distributions F0 and F1 are illustrated in Figure 1<ref:2601.03957#pg2> The KL divergence decreases from scenario A to scenario D<ref:2601.03957#pg2> Scenario a is the worst case for estimating Σ (because the outliers are very far from the reference distribution F0)<ref:2601.03957#pg2> Scenario d is the worst case for detecting outliers (because they are very close to the reference distribution)<ref:2601.03957#pg2> The density of the Mahalanobis distance for an outlier under scenario d is very close to this of inliers<ref:2601.03957#pg2> This confirms that outliers are harder to detect in scenario d<ref:2601.03957#pg2> The Frobenius norm error for the non-robust sample covariance online method does not lie into the interval (10−1, 102)<ref:2601.03957#pg2> Our robust methods maintain strong performance despite high contamination rates<ref:2601.03957#pg2> The Frobenius norm error for the non-robust sample covariance online method exhibits significant sensitivity to outliers<ref:2601.03957#pg2> The non-robust sample covariance online method exhibits significant sensitivity to outliers<ref:2601.
Title and authors: Tom: So, Jane, this paper is titled "Streaming robust covariance estimation and sequential outlier detection," and it’s tackling that big problem we always run into when we have messy data—that the more contaminated observations get in with the dataset size, the harder it gets to get a reliable estimate of the covariance matrix and figure out which points are actually outliers.
Jane: Right, Tom. So basically, this paper is focused on how to do that robust estimation and outlier detection all at once while processing data online, meaning as we get new data points sequentially from a stream. It sounds like they’re trying to fix the problem where outliers mess up our parameter estimates and then hide other outliers from view.
Lu: Yeah, the authors are proposing a method that simultaneously estimates the geometric median and the variance robustly in an online way, which lets them calculate a Mahalanobis distance for each incoming data point before deciding if it’s an outlier. That’s a pretty specific approach they're taking to get around those estimation issues.
Meng: How does this actually work in practice when you’re just trying to ship something to production? I mean, the idea of updating everything sequentially without recomputing from scratch sounds convenient on paper, but what about the computational cost at scale?
Tom: Well, they detail a new online framework where they update estimates for both the geometric median and that median covariance matrix sequentially. They say you calculate an estimate for the geometric median and that median covariance matrix at each step, which is called mn plus one and Vn plus one respectively.
Jane: And then after you have those updated estimates, you use them to calculate a Mahalanobis distance for the new data point before deciding if it’s an outlier. That sounds like a direct way to check how far that new point is from the center of our current understanding of the data spread.
Lu: The paper uses robust estimation techniques specifically because they know that the standard sample mean and covariance matrix are highly sensitive to outliers, which motivates them to use things like the geometric median for location estimation because it has a fifty percent breakdown point, according to Gervini, two thousand six <ref:2601.03957#pg2,because it has a 50>.
Meng: I’m interested in those robust estimators. If we use the geometric median for the location and then they use the median covariance matrix to get a robust estimate of dispersion parameters, what does that mean for things like feature importance or clustering when we’re dealing with this noisy stream?
Tom: They derive influence functions for both the mean and variance under different types of contamination scenarios, and interestingly, they find that the influence function for the variance is always bounded, whatever the value of rho one. That’s a key finding because it gives them more confidence in their robust dispersion estimation.
Title and authors: Jane: That boundedness is interesting because it suggests that even with some noise or outliers, the estimate of how spread out our data is stays within a certain range and doesn't explode just because of one bad point. But what about the mean influence function?
Lu: For the mean, they find that its influence function can be unbounded when k is greater than or equal to zero, which means it’s still a potential weakness there, even with the robust setup. However, they do show how this relates to specific contamination scenarios by examining three types of contamination.
Meng: Okay, so we have a location estimate that has some known sensitivity issues and a dispersion estimate that seems more stable under certain conditions. What about the actual performance numbers? How does this stack up against the non-robust methods you mentioned earlier?
Tom: They tested their method on simulated datasets using a mixture model combining a multivariate Gaussian reference distribution with an outlier distribution, and they measured things like the Frobenius norm error of the covariance matrix estimate and how many false positives and false negatives they got.
Jane: And across contamination scenarios A, B, and C, their robust methods actually maintain strong performance even when the contamination rates are high. That’s a big deal if those non-robust sample covariance online methods are so sensitive to outliers.
Lu: The paper shows that the non-robust sample covariance online method exhibits significant sensitivity to outliers, while the online and streaming methods don't show false positive rates consistent with a nominal level of five percent. That suggests their robust approach is much more stable in practice.
Meng: So, you’re saying this method handles high contamination better than the standard way? But what about the real-time aspect? I mean, if we're streaming data, we need something fast.
Tom: Exactly. The new online methods proposed for parameter estimation and outlier detection allow for real-time identification of outliers as data are observed sequentially without needing to recompute previous estimates from scratch. That’s crucial for low-latency applications where you can’t afford long delays.
Jane: That avoids that huge computational burden, which is a big plus when you're dealing with continuous data streams. But how fast are we talking about updates? Is this something we can actually deploy on hardware right now?
Lu: The complexity analysis shows that the overall complexity is dominated by the spectral decomposition at each step, but they found that using a streaming approach with batches of size s equal to d reduces the number of time steps requiring costly spectral decomposition compared to the simple online approach with batches of size one.
Meng: So, if we use those larger batches, does it actually speed things up enough for production use? Because I’m looking at the cost per inference here.
Title and authors: Tom: In all configurations, they found that the streaming approach is about ten times faster than the simple online approach when comparing different sample sizes and dimensions. That efficiency gain is pretty significant when you’re dealing with high-dimensional data.
Jane: And before we wrap up this paper on "Streaming robust covariance estimation and sequential outlier detection," we need to look at what this means for us practically. It sounds like a system that can keep up with messy, noisy, continuous data streams while reliably spotting anomalies without needing massive amounts of historical data stored in memory.
Lu: Yeah, the convergence along the iterations shows that all criteria vary a lot among early iterations, but a stable value is reached after one thousand or two thousand iterations. So online or batch methods are only relevant for large datasets, which sets some expectations about how long we need to run these procedures before they settle down.
Meng: And if we look at the influence functions again, the mean influence function is unbounded when k is greater than or equal to zero, and for the variance, it’s only unbounded when l is greater than or equal to one. That tells us exactly where our limits are for using these specific robust estimators.
Tom: It also points back to the simulation design where they chose to consider only l greater than or equal to one in their tests because that's where the variance influence function is guaranteed to be bounded, regardless of rho one.
Jane: So, while the mean part has some lingering uncertainty with k greater than or equal to zero, the way they handle the variance seems more controllable under certain conditions. This paper gives us a specific roadmap for building these kinds of online systems that don't immediately break when contamination shows up.
Lu: The main implication is that we can move beyond methods that are completely offline and have trouble handling data drift or sudden bursts of noise because we can get robust estimates in real time, and the approach is based on the geometric median and the median covariance matrix.
Meng: It sounds like a solid framework for a production system, provided you’re okay with the complexity scaling mentioned earlier when you move to larger batch sizes. I just hope they handle those large datasets well enough without needing those massive spectral decompositions constantly.
Tom: Yeah, that’s the trade-off we have to make between speed and accuracy as we scale up the data stream. So, this paper on "Streaming robust covariance estimation and sequential outlier detection" gives us a specific recipe for building online systems that are resilient to contamination.
Jane: That's what it is. It shows how you can keep track of location and spread robustly while simultaneously catching outliers in a streaming fashion, which is something we all need when dealing with the kind of continuous data we see today.
The paper's summary: Tom: So, this paper is all about taking that messy data stream and figuring out how to get a reliable picture of the spread, which is that covariance matrix, even when there are outliers sneaking in at every step.
Jane: Right, so they’re looking at how you can estimate the geometric median—which is a robust way to find the center—and that median covariance matrix all online. It’s about doing it sequentially as data comes in.
Lu: What they really push here is making sure that even with those messy inputs, you can still calculate a Mahalanobis distance for every new point before you decide if it’s an outlier. That distance check is what flags the anomalies.
Meng: But how does this actually avoid those big headaches we see when we try to update things from scratch every time? I mean, recomputing everything is slow at scale.
Tom: They propose a method where you don't need to recompute previous estimates from scratch; you just use the new data point and what you had already calculated for the geometric median and that median covariance matrix at that exact moment. It’s real-time identification.
Jane: The authors use robust estimation techniques because they know standard methods, like using the sample mean and covariance matrix, get completely skewed by those outliers. They use the geometric median for location because it has a fifty percent breakdown point, which means even if half your data is bad, you still get a decent center estimate.
Lu: And for the spread—the dispersion parameters—they use that median covariance matrix to keep things robust while still giving you access to those eigenvectors of the covariance matrix if you need them later. It’s a way to get the best of both worlds there.
Meng: I'm wondering about performance numbers here. If we have a high contamination rate, does this method actually hold up compared to just using the standard sample covariance online method? Because that one is notoriously sensitive to outliers, right?
Tom: The simulation results show that their robust methods maintain strong performance even under high contamination rates. They specifically showed that the non-robust sample covariance online method shows significant sensitivity to those outliers.
Jane: And they managed to keep the false positive rates low, not spiking up even when things get really messy, which is a big win for practical deployment. They found that the robust approach does not have false positive rates consistent with a nominal five percent level.
Lu: It's also interesting how they handled the scaling of the Mahalanobis distance—they corrected it by using an online estimation of the median of past Mahalanobis distances, which they update using a Robbins-Monro stochastic approximation scheme. That’s how you keep that threshold dynamic and adaptive.
Meng: So, it's not just about getting a better estimate; it's about having a mechanism to adjust your detection threshold based on what you’ve seen before. What are the practical limits then? Where does this framework stop working?
Tom: The paper flags some limitations with the mean estimation part. They found that the influence function for the mean is unbounded when k is greater than or equal to zero, which means we have a specific range of parameters where that location estimate gets tricky.
Jane: But they also found something positive regarding the variance—the influence function for the variance is always bounded, no matter what value rho one takes. That’s a nice guarantee for us when it comes to estimating the data's spread.
Lu: And they pointed out in their simulation design that because of that variance bound, they only needed to consider cases where l was greater than or equal to one for their tests, which helps keep things well-behaved.
Meng: So if I'm building a system and I know my data might have some outliers, this gives me a specific toolset—geometric median for the center, median covariance matrix for the spread—and it’s designed to run online without needing massive historical data to recompute. That sounds like something we could actually deploy.
Tom: Exactly. It gives you that real-time identification of outliers as data is observed sequentially without needing to recompute previous estimates from scratch, which is a huge deal for low-latency applications.
Jane: This work shows us how to move beyond the standard, non-robust methods that break under stress and create a framework for keeping track of location and spread robustly in real time. Next up, we’re going to look at how they actually set up those simulations to test these ideas against various contamination levels.
The paper's improvements: Tom: So, we've seen how they propose using the geometric median and median covariance matrix to handle outliers in real time, but they also laid out some specific improvements for making this system even better under real-world stress.
Jane: Right, so beyond just having a robust estimate of the center and spread, the paper suggests ways to make the outlier detection itself more adaptive.
Lu: They focus on adapting that Mahalanobis distance threshold online using a Robbins-Monro stochastic approximation scheme. This means instead of using a fixed number, you dynamically adjust how far away an observation has to be before it gets flagged as an outlier.
Meng: That sounds smart for production because it means the system can learn what "normal" looks like in that specific data stream, rather than relying on some arbitrary threshold set by a researcher.
Tom: It’s about having that online update rule for the scaled Mahalanobis distance, which lets the system dynamically adjust the threshold based on past distances. That avoids those issues where a fixed threshold might be too loose or too tight depending on how messy your data is right now.
Jane: And they also look at computational efficiency again, specifically mentioning a streaming version that uses batches of size equal to the dimension of the data, which reduces the number of times you have to do those expensive spectral decompositions.
Lu: That streaming approach cuts down the time steps requiring that costly spectral decomposition compared to just doing simple online updates with a batch size of one. In all configurations, they found that this streaming version is about ten times faster than the simple online approach when comparing different sample sizes and dimensions.
Meng: Ten times faster is good, but what about running this on actual traffic? Does that ten times speedup translate to lower operational costs when we’re dealing with massive datasets?
Tom: It translates to a lower computational load at every step, which means the system can handle much higher throughput without slowing down significantly. It’s about reducing the overhead during inference.
Jane: The authors also made a point about how they handled the influence functions for both parameters, specifically noting that for the variance, it is always bounded no matter what value rho one takes. They used that guarantee to inform their simulation design choices regarding the parameter l.
Lu: That boundedness of the variance influence function is what motivated them to only consider cases where l was greater than or equal to one in their tests because it keeps things mathematically stable for the dispersion part of the estimation.
Meng: So they are essentially saying, "Look, we know this part is safer," which helps narrow down the testing space and makes their results more reliable for us to trust when we try to deploy this.
Tom: The overall implication is that these improvements give us a system that isn't just robust against outliers but also computationally practical for running on live data streams, even if you have some unknowns in the underlying mean estimation part.
Jane: So, we’re looking at a system where you get robust identification of location and spread, you can detect anomalies in real time without recomputing everything from scratch, and it's designed to be faster than older methods for streaming data.
Lu: The future work they hint at involves exploring how this framework handles different types of contamination scenarios more deeply, pushing the boundaries on what kind of noise it can actually manage effectively.
Conclusion: Tom: So, to wrap up, this paper on "Streaming robust covariance estimation and sequential outlier detection" shows how you can get robust estimates for location and spread online using geometric median and median covariance matrix, while simultaneously flagging outliers via an adaptive Mahalanobis distance check.
Jane: It’s about moving away from those standard sample methods that break easily under contamination, giving us a way to handle messy data in a live stream without needing to store everything.
Lu: The real implication is that we can build systems for continuous data where the location and covariance estimates are constantly updated, and the outlier detection mechanism learns what's normal as it goes.
Meng: For me, at scale, this means we have a tool that’s designed to run efficiently with streaming batches rather than requiring massive memory or constant recomputation of everything. It’s about deployment feasibility under real load.
Lalam: I am very confident in the findings; the results show these methods maintain strong performance even when contamination rates are quite high, which is exactly what we need for mission-critical AI applications.
Jane: And they showed that while they have some specific parameter limits to be aware of, like the mean influence function being unbounded under certain conditions, their method for handling variance estimation seems very well-controlled.
Tom: Yeah, it’s a trade-off; you get a solid framework for robustness and speed, but you still have to be mindful of those specific parameter ranges when designing your system architecture.
Lu: The work on the streaming version is really interesting because it optimizes the computational complexity, bringing that scaling down significantly compared to simpler online approaches.
Meng: That speedup matters because if we can process data ten times faster, it means lower latency for our models in a production environment.
Jane: So, this paper gives us a concrete recipe for building resilient AI pipelines that can keep up with noisy, continuous data streams while reliably spotting anomalies in real time.
Tom: It’s a solid piece of work showing how to combine robust statistics with efficient streaming techniques.
Lu: The future work they point toward is exploring how this framework handles different types of contamination scenarios even more thoroughly, which is where the next big challenge lies for representation learning models.
Meng: I want to see if we can take these ideas and test them directly on our actual production traffic data, because theoretical simulation doesn't always match real world noise.
Lalam: I’m sure the path forward will involve applying this online estimation logic to more complex spatiotemporal models, which is a natural next step for this type of AI research.
Paul Guillot, Antoine Godichon-Baggioni, & Stǩphane Robin, Laure Sansonnet
Sorbonne University · CREST · ENSAE, IP Paris
stat.ME
Submitted: 2026-01-07
Updated: 2026-11-09
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 72/100
The gist: Robust estimation of the covariance matrix and detection of outliers remain major challenges in statistical data analysis…
Key concepts
- Geometric Median
- This is a robust measure of central location used instead of the standard mean when data contains outliers. It has a 50% breakdown point, meaning it can tolerate up to half the data being contaminated before its estimate becomes unreliable. It is used here for robustly estimating the center of the data distribution.
- Median Covariance Matrix (MCM)
- The MCM is used as a robust way to estimate dispersion parameters like covariance. By using the median instead of the sample mean, it provides a more stable estimate that is less sensitive to extreme outliers in the dataset. This helps create a robust representation of how data points vary together.
- Mahalanobis Distance
- This distance measures how many standard deviations an incoming data point is from the center of the distribution, taking into account the correlation between variables. In this system, it is calculated using online estimates of the geometric median and MCM to determine if a new point should be flagged as an outlier.
- Streaming Approach
- This refers to processing data sequentially in a stream rather than waiting for the entire dataset. The streaming version uses batch processing, which allows for faster updates by averaging estimates over small blocks of incoming data, significantly improving computational efficiency compared to simple online methods.
Terminology
Summary
Robust estimation of the covariance matrix and detection of outliers remain major challenges in statistical data analysis, particularly when the proportion of contaminated observations increases with the size of the dataset<ref:2601. p. 0 Online robust covariance matrix estimation and outlier detection
Paul Guillot1,2
, Antoine Godichon-Baggioni1
, St´ephane Robin1 and Laure Sansonnet1
1 Sorbonne Universit´e, Universit´e Paris Cit´e, CNRS, Laboratoire de Probabilit´es, Statistique
et Mod´elisation, LPSM, F-75005 Paris, France
2 CREST, CNRS, ENSAE, IP Paris, Palaiseau, France
Abstract
Robust estimation of the covariance matrix and detection of outliers remain major challenges in statistical data analysis, particularly when the proportion of contaminated observations increases with the size of the dataset. Outliers can severely bias parameter estimates
and induce a masking effect, whereby some outliers conceal the presence of other outliers,
further complicating their detection. Online robust covariance matrix estimation and outlier detection
Paul Guillot1,2
, Antoine Godichon-Baggioni1
, St´ephane Robin1 and Laure Sansonnet1
1 Sorbonne Universit´e, Universit´e Paris Cit´e, CNRS, Laboratoire de Probabilit´es, Statistique
et Mod´elisation, LPSM, F-75005 Paris, France
2 CREST, CNRS, ENSAE, IP Paris, Palaiseau, France
Abstract
Robust estimation of the covariance matrix and detection of outliers remain major challenges in statistical data analysis, particularly when the proportion of contaminated observations increases with the size of the dataset. Outliers can severely bias parameter estimates
and induce a masking effect, whereby some outliers conceal the presence of other outliers,
further complicating their detection. Although many approaches have been proposed for
covariance estimation and outlier detection, to our knowledge, none of these methods have
been implemented in an online setting. In this paper, we focus on online covariance matrix estimation and outlier detection. In this paper, we focus on online covariance matrix estimation and outlier detection. Specifically, we propose a new method for simultaneously and online estimating the geometric
median and variance, which allows us to calculate the Mahalanobis distance for each incoming data point before deciding whether it should be considered an outlier. Specifically, we propose a new method for simultaneously and online estimating the geometric
median and variance, which allows us to calculate the Mahalanobis distance for each incoming data point before deciding whether it should be considered an outlier. To mitigate the masking effect, robust estimation techniques for the mean and variance are
required. To mitigate the masking effect, robust estimation techniques for the mean and variance are
required. Our approach uses the geometric median for robust estimation of the location
and the median covariance matrix for robust estimation of the dispersion parameters. Our approach uses the geometric median for robust estimation of the location
and the median covariance matrix for robust estimation of the dispersion parameters. The
new online methods proposed for parameter estimation and outlier detection allow real-time
identification of outliers as data are observed sequentially.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Novel Online Framework
The authors propose a novel algorithm to estimate all the quantities of interest, including the median, the median covariation matrix, and the variance-covariance matrix in an online manner while simultaneously enabling online outlier detection<ref:2601.03957#pg2> This method is based on estimating the geometric median and the MCM<ref:2601. p. 2 Offline median covariation matrix (MCM) based method. Our covariance matrix estimation is founded on the estimation of the geometric median and the MCM described in the
appendix A. We then propose a new method, based on the ideas of paragraph 2. 1, to both estimate online the geometric
median, the MCM and a robust estimate of the variance. In this paper, we focus on online covariance matrix estimation and outlier detection. Specifically, we propose a new method for simultaneously and online estimating the geometric
median and variance, which allows us to calculate the Mahalanobis distance for each incoming data point before deciding whether it should be considered an outlier. follows:
Xn+1 = Xn +
1
n + 1
(Xn+1 − Xn),
Σn+1 = Σn +
1
n + 1
Xn+1 − Xn
Xn+1 − Xn
⊤
Subsequently, we estimate the inverse of Σn+1 with the following update based on the ShermanMorrisson formula:
Σ
−1
n+1 =
n + 1
n
Σ
−1
n −
n + 1
n2
1
1 + U⊤
n n−1Σ
−1
n Un
Σ
−1
n UnU
⊤
n Σ
−1
n
where Un = Xn − Xn−1. One can then calculate the Mahalanobis distance of the new data as
Dbn+1 = (Xn+1 − Xn)
⊤Σ
−1
n+1(Xn+1 − Xn+1). This reduces the reliance
on costly orthonormalization steps and allows the overall complexity to be reduced to the
usual O(nd2
) complexity, where n is the number of observation and d is the data dimension. Our method also enables real-time detection of outliers in incoming data without the need to
recompute previous estimates from scratch.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Robust Estimation Techniques
The authors utilize robust estimation techniques to address the masking effect caused by outliers<ref:2601.03957#pg2> For location estimation, the geometric median is employed because it has a 50% breakdown point<ref:2601. p. 1 The approach we propose is based one the geometric median and the median covariation
matrix. The geometric median is a robust measure of location (Haldane, 1948; Kemperman,
1987) that can be preferred to the mean because it has a 50% breakdown point (Gervini, 2006). To mitigate the masking effect, robust estimation techniques for the mean and variance are
required. Our approach uses the geometric median for robust estimation of the location
and the median covariance matrix for robust estimation of the dispersion parameters. Then, denoting by nMC the total number of generated data Un
(and iterations so), the estimate λnMC is totally defined by δ, λ0, nMC and n0. The MCM also
provides access to the eigenvectors of the covariance matrix. 92 k = 0 ℓ = 1
Table 2: Values of the three tuning parameters (k, ℓ, ρ1) to attain the prescribed KL divergences,
the other parameters being held fixed in dimension d = 10. Overall, our simulation design involves four tuning parameters: the contamination rate r,
the mean shift k, the variance scale ℓ and the correlation coefficient ρ1. ρ1) is greater than or less than
1 (resp. In Appendix B, we provide an analysis of the influence functions associated with
the three parameters, from which we can see that ℓ ≤ 1 has a weaker impact than ℓ ≥ 1.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Performance Evaluation and Comparison
The performance of the proposed methods is demonstrated on simulated datasets<ref:2601.03957#pg2> The simulation design involves a mixture model combining a multivariate Gaussian reference distribution F0 with an outlier distribution F1<ref:2601. p. 9 1 Simulation design
Distributions. To mimic the distribution of contaminated data, we used the following mixture model:
(1 − r)F0 + rF1,
where F0 stands for the reference distribution and F1 for the distribution of outliers, and r for the
contamination rate. Then, denoting by nMC the total number of generated data Un
(and iterations so), the estimate λnMC is totally defined by δ, λ0, nMC and n0. The MCM also
provides access to the eigenvectors of the covariance matrix. Classical estimators such as the
sample mean and covariance matrix are highly sensitive to outliers, motivating the need for
robust alternatives. Indeed, the acquisition of large-scale data in high-dimensional spaces is
unfortunately often accompanied by contamination. 4 Online outlier detection
Specificity and advantages of our method. Our proposed method performs, simultaneously, robust covariance estimation in the presence of outliers and online outlier detection. 4 Online outlier detection
Specificity and advantages of our method. Our proposed method performs, simultaneously, robust covariance estimation in the presence of outliers and online outlier detection.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Computational Efficiency
The computational complexity analysis shows that the overall complexity is dominated by the spectral decomposition at each step<ref:2601.03957#pg2> The streaming approach, using batches of size s=d, reduces the number of time steps requiring costly spectral decomposition compared to the simple online approach with batches of size 1<ref:2601. p. 1 To address this issue, we introduce a streaming version of
our method, which processes data arriving sequentially in batches. This reduces the reliance
on costly orthonormalization steps and allows the overall complexity to be reduced to the
usual O(nd2
) complexity, where n is the number of observation and d is the data dimension. 1; (ii) the online method stands for
the median covariation matrix-based approach in pure online processing (batches of size 1,
Section 3. 2); and (iii) the streaming method designates the median covariation matrix approach
in batch processing (with batches of size s = 10, Section 3.Where the paper says it
Where the paper says it
Outlier Detection Mechanism
Outlier detection relies on a Mahalanobis distance-based criterion where an observation is flagged if its scaled Mahalanobis distance exceeds a predefined threshold c<ref:2601.03957#pg2> To mitigate bias, the scaled Mahalanobis distance is corrected by using an online estimation of the median of past Mahalanobis distances<ref:2601. p. 8 Subsequently, once the Mahalanobis distance Dbn+1 of the
new observation Xn+1 has been computed, the observation is flagged as an outlier whenever
the scaled Mahalanobis defined in Equation (1) exceeds a predefined threshold c. The scaling
factor requires online estimation of the median of past Mahalanobis distances med(Db1, . The scaling
factor requires online estimation of the median of past Mahalanobis distances med(Db1, . We update this quantity using the classical Robbins–Monro stochastic approximation scheme
(see Robbins and Monro, 1951; Labopin-Richard, 2016). First, observations flagged as outliers can be identified and handled
immediately upon arrival. Second, the procedure is fully online and does not require storing
past data, and recomputation from scratch.Where the paper says it
Where the paper says it
Where the paper says it
Convergence Characteristics
The convergence along the iterations shows that all criteria vary a lot among early iterations<ref:2601.03957#pg2> However, a stable value is reached after 1000 or 2000 iterations, suggesting that online (or batch methods) are only relevant for large data sets<ref:2601.03957#pg2> The convergence speed depends on both the criterion and the contamination rate<ref:2601. p. 9 1 Simulation design
Distributions. To mimic the distribution of contaminated data, we used the following mixture model:
(1 − r)F0 + rF1,
where F0 stands for the reference distribution and F1 for the distribution of outliers, and r for the
contamination rate.Where the paper says it
Implementation Details
The algorithms were implemented in R and Rcpp 1.0.9, with code available upon request<ref:2601. p. 9 The sample covariance online method, the online method, and the streaming method, were implemented in R and Rcpp 1. The code is available upon request to the
authors. 92 k = 0 ℓ = 1
Table 2: Values of the three tuning parameters (k, ℓ, ρ1) to attain the prescribed KL divergences,
the other parameters being held fixed in dimension d = 10. Overall, our simulation design involves four tuning parameters: the contamination rate r,
the mean shift k, the variance scale ℓ and the correlation coefficient ρ1. Each of k, ℓ, and ρ1 was varied individually to attain a Kullback–Leibler divergence KL(F0, F1) of 0, 1, 5 ,10, 25 in dimension d = 10: the resulting values
are given in Table 2. Clearly, taking k ≤ 0 or k ≥ 0 leads to completely symmetric situations. 1 Simulation design
Distributions. To mimic the distribution of contaminated data, we used the following mixture model:
(1 − r)F0 + rF1,
where F0 stands for the reference distribution and F1 for the distribution of outliers, and r for the
contamination rate.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Influence Functions of Parameters
The influence function for the mean is unbounded for k ≥ 0<ref:2601.03957#pg2> For the variance, it is unbounded only for l ≥ 1<ref:2601. p. 0 This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601. This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601. The code is available upon request to the
authors. 1 Simulation design
Distributions.Where the paper says it
Where the paper says it
Where the paper says it
Estimation of Geometric Median and MCM
The geometric median can be estimated using the Weiszfeld’s algorithm, which is a fixed-point iteration method requiring O(N d) computations per iteration<ref:2601.03957#pg2> The MCM can be estimated using the Weisfeld’s algorithm adapted for the MCM, which requires O(N d squared T) computations<ref:2601. p. 5 The MCM also
provides access to the eigenvectors of the covariance matrix. Denoting by P the matrix whose
columns are the eigenvectors obtained from the MCM, the covariance matrix can be estimated
as P ∆P
⊤, where ∆ is a diagonal matrix containing the estimated eigenvalues λnMC of Σ. Vn and V n) correspond to the stochastic gradient algorithm,
with γn = cγ(n + n0)
−γ with cγ > 0 and n0 ≥ 0, and its averaged version (Cardot et al. ,
2013) for estimating the geometric median (resp. The estimates mn and mn (resp. Vn and V n) correspond to the stochastic gradient algorithm,
with γn = cγ(n + n0)
−γ with cγ > 0 and n0 ≥ 0, and its averaged version (Cardot et al.Where the paper says it
Where the paper says it
Where the paper says it
Mahalanobis Distance Calculation
The Mahalanobis distance for the new data point is calculated as Dbn+1 = Xd / j=1 1 λn+1[j] <ref:2601.03957#pg2> The calculation of the Mahalanobis distance has a complexity of order O(d 2)<ref:2601. p. 7 Furthermore the reconstruction of the eigenvalues
of the variance necessitates O(nMCd
2
) operations. Finally, the calculus of the Mahalanobis
distance has a complexity of order O(d
2
). Subsequently, once the Mahalanobis distance Dbn+1 of the
new observation Xn+1 has been computed, the observation is flagged as an outlier whenever
the scaled Mahalanobis defined in Equation (1) exceeds a predefined threshold c. The scaling
factor requires online estimation of the median of past Mahalanobis distances med(Db1, . Subsequently, once the Mahalanobis distance Dbn+1 of the
new observation Xn+1 has been computed, the observation is flagged as an outlier whenever
the scaled Mahalanobis defined in Equation (1) exceeds a predefined threshold c. The scaling
factor requires online estimation of the median of past Mahalanobis distances med(Db1, . This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601. The scaling
factor requires online estimation of the median of past Mahalanobis distances med(Db1, . We update this quantity using the classical Robbins–Monro stochastic approximation scheme
(see Robbins and Monro, 1951; Labopin-Richard, 2016).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Batch Processing Framework
In the batch setting, new data arriving by block of size s is treated as a single statistical unit<ref:2601.03957#pg2> The updates for the geometric median and MCM involve averaged estimates based on the new block of data<ref:2601. p. 7 The main change is that we now consider streaming (or online mini-batch) algorithms for
estimating the median and the MCM, i. e that we consider averaged estimates (based on the
new block of data) of the gradients, leading to the following updates (Godichon-Baggioni et al. The main advantage of this method is that if we denote by N the total number of data dealt
with, we only do N/s iterations. This means that we reduce the number of time we use the
costly spectral decomposition, leading to a total calculus complexity of order
O(N d)
| {z }
Updating mn and mn
+ O(N d2
)
| {z }
Updating Vn and V n
+ O
N d3
s
| {z }
Eigen decomposition
+ O(NnMCd
2
)
| {z }
Updating λn
+ O(N d2
)
| {z }
Calculate all Dˆn+1,i
Then, taking s = d can lead to a total complexity of order O(NnMCd
2
), which is (up to nMC)
the same calculus time as the naive method. The main advantage of this method is that if we denote by N the total number of data dealt
with, we only do N/s iterations. This means that we reduce the number of time we use the
costly spectral decomposition, leading to a total calculus complexity of order
O(N d)
| {z }
Updating mn and mn
+ O(N d2
)
| {z }
Updating Vn and V n
+ O
N d3
s
| {z }
Eigen decomposition
+ O(NnMCd
2
)
| {z }
Updating λn
+ O(N d2
)
| {z }
Calculate all Dˆn+1,i
Then, taking s = d can lead to a total complexity of order O(NnMCd
2
), which is (up to nMC)
the same calculus time as the naive method. The main advantage of this method is that if we denote by N the total number of data dealt
with, we only do N/s iterations. This means that we reduce the number of time we use the
costly spectral decomposition, leading to a total calculus complexity of order
O(N d)
| {z }
Updating mn and mn
+ O(N d2
)
| {z }
Updating Vn and V n
+ O
N d3
s
| {z }
Eigen decomposition
+ O(NnMCd
2
)
| {z }
Updating λn
+ O(N d2
)
| {z }
Calculate all Dˆn+1,i
Then, taking s = d can lead to a total complexity of order O(NnMCd
2
), which is (up to nMC)
the same calculus time as the naive method. This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Simulation Design and Results
The simulation design uses a mixture model to mimic contaminated data with contamination rate r<ref:2601.03957#pg2> The results show that under scenarios A, B, and C, the covariance matrix estimation remains largely unaffected regardless of the estimation method employed<ref:2601. p. 0 In this paper, we focus on online covariance matrix estimation and outlier detection. Specifically, we propose a new method for simultaneously and online estimating the geometric
median and variance, which allows us to calculate the Mahalanobis distance for each incoming data point before deciding whether it should be considered an outlier. Classical estimators such as the
sample mean and covariance matrix are highly sensitive to outliers, motivating the need for
robust alternatives. Indeed, the acquisition of large-scale data in high-dimensional spaces is
unfortunately often accompanied by contamination. Classical estimators such as the
sample mean and covariance matrix are highly sensitive to outliers, motivating the need for
robust alternatives. Indeed, the acquisition of large-scale data in high-dimensional spaces is
unfortunately often accompanied by contamination. Indeed, the acquisition of large-scale data in high-dimensional spaces is
unfortunately often accompanied by contamination. The automatic detection of these atypical
data is not simple, and the use of robust techniques is an interesting alternative, in particular
for online outlier detection. We then introduce our proposed methodology in
both the online and batch settings. 1 Sample mean and sample covariance online method
A first naive online approach would be to consider online estimates of the mean and the variance
based on the sample mean and the sample covariance matrix. We then introduce our proposed methodology in
both the online and batch settings. 1 Sample mean and sample covariance online method
A first naive online approach would be to consider online estimates of the mean and the variance
based on the sample mean and the sample covariance matrix.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Convergence Along Iterations
Figure 4 shows how the Frobenius and the false positive and negative proportions evolve along the iterations of the proposed procedure<ref:2601.03957#pg2> All criteria vary a lot among early iterations, but a stable value is reached after 1000 or 2000 iterations<ref:2601. p. 5 where λ0 = λ0 and w ≥ 0. Then, denoting by nMC the total number of generated data Un
(and iterations so), the estimate λnMC is totally defined by δ, λ0, nMC and n0. Indeed, the acquisition of large-scale data in high-dimensional spaces is
unfortunately often accompanied by contamination. The automatic detection of these atypical
data is not simple, and the use of robust techniques is an interesting alternative, in particular
for online outlier detection. 1; (ii) the online method stands for
the median covariation matrix-based approach in pure online processing (batches of size 1,
Section 3. 2); and (iii) the streaming method designates the median covariation matrix approach
in batch processing (with batches of size s = 10, Section 3.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion on Detection Bias
The discrepancy in false positive rates arises from an overestimation of Σ0 in terms of a larger determinant<ref:2601.03957#pg2> Scaling the Mahalanobis distance clearly fails to counterbalance this bias<ref:2601. p. 8 Subsequently, once the Mahalanobis distance Dbn+1 of the
new observation Xn+1 has been computed, the observation is flagged as an outlier whenever
the scaled Mahalanobis defined in Equation (1) exceeds a predefined threshold c. The scaling
factor requires online estimation of the median of past Mahalanobis distances med(Db1, . Our approach uses the geometric median for robust estimation of the location
and the median covariance matrix for robust estimation of the dispersion parameters. The
new online methods proposed for parameter estimation and outlier detection allow real-time
identification of outliers as data are observed sequentially. Although more robust, these methods remain computationally intensive. Regarding the high dimension, Finally, the invariant coordinate selection (ICS)
method (Tyler et al. Outliers can severely bias parameter estimates
and induce a masking effect, whereby some outliers conceal the presence of other outliers,
further complicating their detection. Although many approaches have been proposed for
covariance estimation and outlier detection, to our knowledge, none of these methods have
been implemented in an online setting.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Parameter Influence Summary
The influence function for the mean is unbounded for k ≥ 0<ref:2601.03957#pg2> For the variance, it is unbounded only for l ≥ 1<ref:2601.03957#pg2> The shape transformation (iii) shows that the influence function for the variance is always bounded, whatever the value of ρ1<ref:2601.03957#pg2> This motivates our choice to consider only l ≥ 1 in the simulation design<ref:2601. p. 9 The code is available upon request to the
authors. 1 Simulation design
Distributions. Each of k, ℓ, and ρ1 was varied individually to attain a Kullback–Leibler divergence KL(F0, F1) of 0, 1, 5 ,10, 25 in dimension d = 10: the resulting values
are given in Table 2. Clearly, taking k ≤ 0 or k ≥ 0 leads to completely symmetric situations. Simulation parameters. Each of k, ℓ, and ρ1 was varied individually to attain a Kullback–Leibler divergence KL(F0, F1) of 0, 1, 5 ,10, 25 in dimension d = 10: the resulting values
are given in Table 2. This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601. This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601. 1 Simulation design
Distributions. To mimic the distribution of contaminated data, we used the following mixture model:
(1 − r)F0 + rF1,
where F0 stands for the reference distribution and F1 for the distribution of outliers, and r for the
contamination rate. 1 Simulation design
Distributions. To mimic the distribution of contaminated data, we used the following mixture model:
(1 − r)F0 + rF1,
where F0 stands for the reference distribution and F1 for the distribution of outliers, and r for the
contamination rate. When Σ
and µ are estimated by the sample mean Xn and the sample covariance matrix S, the estimated
distance Dbi follows a scaled F distribution: Dbi ∼
n+1
n
·
d(n−1)
n−d
F(d, n − d), where F(d, n − d)
denotes the Fisher distribution with d and n−d degrees of freedom, (see Hotelling et al. When the sample size n is large, the scaling factor n+1
n
·
d(n−1)
n−d
becomes close to d, and the
4 This includes, for example, the Minimum Covariance
Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The
1
arXiv:2601. 4 Online outlier detection
Specificity and advantages of our method. Our proposed method performs, simultaneously, robust covariance estimation in the presence of outliers and online outlier detection.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Robust online covariance estimation and outlier detection capability: The improved system can simultaneously estimate geometric median, median covariation matrix, and variance robustly in real time to calculate a Mahalanobis distance for each incoming data point before deciding if it is an outlier.
-
Real-time outlier handling without recomputation: The system enables
real-time identification of outliers as data are observed sequentially
and avoids the need torecompute previous estimates from scratch,
which is crucial for low-latency applications. -
Computational efficiency improvement via streaming: By utilizing a streaming version that processes data in batches, the system reduces reliance on costly orthonormalization steps, allowing overall complexity to be reduced to
the usual O(nd2) complexity
instead of higher costs associated with full online updates. -
Adaptive outlier thresholding: The method incorporates an online update rule for the scaled Mahalanobis distance using a Robbins-Monro stochastic approximation scheme, allowing the system to dynamically adjust the threshold based on observed past distances.
-
Improved performance under contamination: The proposed robust methods maintain
strong performance despite high contamination rates,
significantly outperforming non-robust sample covariance online methods, which are noted to exhibitsignificant sensitivity to outliers.
Abstract
Robust estimation of the covariance matrix and outlier detection remain major statistical hurdles, particularly in large datasets where the rate of data contamination increases. The presence of outliers can severely bias parameter estimates and induce a masking effect, whereby some outliers conceal the presence of other outliers, further complicating their detection. Although many approaches have been proposed for covariance estimation and outlier detection, to our knowledge, none of these methods have been implemented in an online setting. In this paper, we focus on online covariance matrix estimation and outlier detection. Specifically, we propose a new method for simultaneously and online estimating the geometric median and variance, which allows us to calculate the Mahalanobis distance for each incoming data point before deciding whether it should be considered an outlier. To mitigate the masking effect, robust estimation techniques for the mean and variance are required. Our approach uses the geometric median for robust estimation of the location and the median covariance matrix for robust estimation of the dispersion parameters. The new online methods proposed for parameter estimation and outlier detection allow real-time identification of outliers as data are observed sequentially. The performance of our methods is demonstrated on simulated and real datasets.
Sources
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes