Sketch-FORCE: Sub-quadratic Streaming Robust Covariance Estimation for Extreme Dimensions

Abstract Streaming covariance estimation is a foundational primitive in real-time high-dimensional data analysis, underlying applications ranging from Internet-of-Things (IoT) sensor networks to high-throughput single-cell genomics. In these settings, data streams are often subject to arbitrary contamination by outliers and heavy-tailed noise, while being bounded by strict computational and memory constraints. Although robust scale estimation methods offer protection against extreme marginal outliers, they require storing a full $p \times p$ covariance matrix, leading to an insurmountable $O(p^2)$ memory wall as the dimension $p$ scales beyond tens of thousands. In this paper, we present \textbf{Sketch-FORCE}, a sub-quadratic, robust streaming covariance estimator that breaks this memory barrier. Sketch-FORCE decouples robust scale tracking from global covariance updating by combining Piecewise-Parabolic ($P^2$) quantile trackers with Frequent Directions (FD) matrix sketching. By dynamically Winsorizing incoming observations based on running medians and scales (using either Interquartile Range or Median Absolute Deviation) and streaming these trimmed vectors into an FD sketch, we maintain an active low-rank representation using only $O(pk)$ memory, where $k \ll p$ is the sketch rank. SVD-based shrinkage is executed in $O(k^2 p)$ time whenever the sketch fills, completely bypassing $O(p^2)$ storage and computation. We analyze the theoretical trade-off of this approach, specifically the ``imputation bias'' introduced by trimming in cross-covariance terms versus the contamination bias it prevents. Empirically, we demonstrate that Sketch-FORCE scales to dimensions up to $p=10{,}000$ using highly efficient throughput, while outperforming vanilla sketching under heavy-tailed contamination and matching the subspace accuracy of full $O(p^2)$ robust methods. We show its downstream utility on the real-world KDD Cup 99 network intrusion dataset, confirming its practical relevance for real-time edge environments. Furthermore, we subject the algorithm to an adversarial stress test, illustrating its theoretical vulnerability to structural outliers that evade marginal bounds but distort joint correlation, establishing the boundary conditions of marginal robust sketching.