Streaming robust covariance estimation and sequential outlier detection

arXiv:2601.03957 · stat.ME · Submitted 2026-01-07 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

03957#pg2> In this paper, we focus on online covariance matrix estimation and outlier detection<ref:2601. p. 0
Where the paper says it

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.

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. p. 0
Where the paper says it

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.

03957#pg2> To mitigate the masking effect, robust estimation techniques for the mean and variance are required<ref:2601. p. 0
Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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. p. 2

Where the paper says it

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.

03957#pg2> The method involves updating estimates for the geometric median, the MCM, and a robust estimate of the variance sequentially<ref:2601. p. 6
Where the paper says it

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.

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. p. 0
Where the paper says it

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.

03957#pg2> Subsequently, the Mahalanobis distance is calculated using these estimates<ref:2601. p. 6
Where the paper says it

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).

03957#pg2> The procedure allows for real-time identification of outliers without needing to recompute previous estimates from scratch<ref:2601. p. 1
Where the paper says it

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.

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. p. 1

Where the paper says it

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).

03957#pg2> For dispersion parameters, the median covariance matrix is used for robust estimation of the variance<ref:2601. p. 0
Where the paper says it

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.

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. p. 5
Where the paper says it

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.

03957#pg2> The influence functions for the mean and variance under contamination are derived based on three types of contamination scenarios<ref:2601. p. 9
Where the paper says it

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.

03957#pg2> Specifically, the influence function for the variance is always bounded, whatever the value of ρ1<ref:2601. p. 9
Where the paper says it

ρ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.

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. p. 9

Where the paper says it

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.

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. p. 5
Where the paper says it

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.

03957#pg2> Under contamination scenarios A, B, and C, our robust methods maintain strong performance despite high contamination rates<ref:2601. p. 0
Where the paper says it

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.

03957#pg2> The non-robust sample covariance online method exhibits significant sensitivity to outliers<ref:2601. p. 8
Where the paper says it

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.

p. 8
Where the paper says it

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.

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. p. 1

Where the paper says it

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.

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. p. 8
Where the paper says it

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.

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. p. 8

Where the paper says it

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, .

03957#pg2> The update rule for this median uses a classical Robbins–Monro stochastic approximation scheme<ref:2601. p. 8
Where the paper says it

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).

03957#pg2> This mechanism enables the procedure to be fully online and does not require storing past data or recomputation from scratch<ref:2601. p. 8
Where the paper says it

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.

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. p. 9

Where the paper says it

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.

03957#pg2>

Implementation Details

The algorithms were implemented in R and Rcpp 1.0.9, with code available upon request<ref:2601. p. 9

Where the paper says it

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.

03957#pg2> The simulation scenarios explore various contamination levels by varying the tuning parameters k, l, and ρ1<ref:2601. p. 9
Where the paper says it

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.

03957#pg2> The analysis confirms that taking k ≤ 0 or k ≥ 0 leads to completely symmetric situations<ref:2601. p. 9
Where the paper says it

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.

03957#pg2> The simulation results indicate that under scenario D, the false negative rate is high for all methods<ref:2601. p. 9
Where the paper says it

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.

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. p. 0

Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv:2601.

p. 0
Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv: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. p. 9
Where the paper says it

The code is available upon request to the authors. 1 Simulation design Distributions.

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. p. 5

Where the paper says it

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 Σ.

03957#pg2> An averaged stochastic gradient algorithm provides a faster and more adaptive way to estimate the geometric median<ref:2601. p. 6
Where the paper says it

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.

03957#pg2> The MCM estimation can be accelerated using an averaged stochastic gradient algorithm, which is defined recursively for all n ≥ 0<ref:2601. p. 6
Where the paper says it

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.

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. p. 7

Where the paper says it

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 ).

03957#pg2> The scaled Mahalanobis distance is defined in Equation (1) and requires online estimation of the median of past Mahalanobis distances<ref:2601. p. 8
Where the paper says it

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, .

03957#pg2> This scaling factor requires online estimation of the median of past Mahalanobis distances med(Db1,. p. 8
Where the paper says it

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, .

.., Dbn)<ref:2601. p. 0
Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv:2601.

03957#pg2> The update rule for this median uses the classical Robbins–Monro stochastic approximation scheme<ref:2601. p. 8
Where the paper says it

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).

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. p. 7

Where the paper says it

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.

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. p. 8
Where the paper says it

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.

03957#pg2> This leads to a total calculus complexity of order O(N nMC d 2) for the streaming covariation-based methods<ref:2601. p. 8
Where the paper says it

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.

03957#pg2> The final calculation involves computing all Dˆn+1,i for i = 1,. p. 8
Where the paper says it

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.

.., s<ref:2601. p. 0
Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv: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. p. 0

Where the paper says it

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.

03957#pg2> Our robust methods maintain strong performance despite high contamination rates<ref:2601. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

03957#pg2> The online and streaming methods achieve perfect outlier detection for contamination rates up to 30% under scenario A<ref:2601. p. 0
Where the paper says it

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.

03957#pg2> The superior performance of the sample covariance online method is evident in the persistent masking effects<ref:2601. p. 5
Where the paper says it

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.

03957#pg2> The non-robust sample covariance online method struggles across scenarios<ref:2601. p. 5
Where the paper says it

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.

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. p. 5

Where the paper says it

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.

03957#pg2> This suggests that online methods are only relevant for large data sets<ref:2601. p. 0
Where the paper says it

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.

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. p. 8
Where the paper says it

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.

03957#pg2>

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

Where the paper says it

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, .

03957#pg2> The robust methods maintain near-perfect detection rates across all but scenarios A and B<ref:2601. p. 0
Where the paper says it

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.

03957#pg2> Under scenario D, the false negative rate is high for all methods<ref:2601. p. 3
Where the paper says it

Although more robust, these methods remain computationally intensive. Regarding the high dimension, Finally, the invariant coordinate selection (ICS) method (Tyler et al.

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. p. 0
Where the paper says it

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.

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. p. 9

Where the paper says it

The code is available upon request to the authors. 1 Simulation design Distributions.

03957#pg2> The simulation results confirm that taking k ≤ 0 or k ≥ 0 leads to completely symmetric situations<ref:2601. p. 9
Where the paper says it

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.

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. p. 9
Where the paper says it

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.

03957#pg2> The resulting distributions F0 and F1 are illustrated in Figure 1<ref:2601. p. 0
Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv:2601.

03957#pg2> The KL divergence decreases from scenario A to scenario D<ref:2601. p. 0
Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv:2601.

03957#pg2> Scenario a is the worst case for estimating Σ (because the outliers are very far from the reference distribution F0)<ref:2601. p. 9
Where the paper says it

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.

03957#pg2> Scenario d is the worst case for detecting outliers (because they are very close to the reference distribution)<ref:2601. p. 9
Where the paper says it

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.

03957#pg2> The density of the Mahalanobis distance for an outlier under scenario d is very close to this of inliers<ref:2601. p. 3
Where the paper says it

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

03957#pg2> This confirms that outliers are harder to detect in scenario d<ref:2601. p. 0
Where the paper says it

This includes, for example, the Minimum Covariance Determinant (MCD: Rousseeuw, 1985) or shrinkage approaches (Ledoit and Wolf, 2004). The 1 arXiv: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. p. 8
Where the paper says it

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.

03957#pg2> The non-robust sample covariance online method exhibits significant sensitivity to outliers<ref:2601.

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

  1. 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.

  2. Real-time outlier handling without recomputation: The system enables real-time identification of outliers as data are observed sequentially and avoids the need to recompute previous estimates from scratch, which is crucial for low-latency applications.

  3. 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.

  4. 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.

  5. 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 exhibit significant 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