arXiv 30 Apr 2026 · Statistics — Computation
arXiv:2605.00247 · PDF · DOI · OpenAlex · Extracted main text
We place three algorithms for computing the unbiased sample covariance matrix in streaming and distributed settings on a common algebraic, numerical, and statistical foundation. The Gram algorithm, derived from the variance reformulation, maintains the running cross-product matrix $G_t = \sum_{i=1}^t x_i x_i^\top$ and the column-sum vector $s_t = \sum_{i=1}^t x_i$, yielding the unbiased covariance estimator $S_t = (t-1)^{-1}(G_t - t^{-1}s_t s_t^\top)$ in $O(p^2)$ time per update. The Welford algorithm propagates a running mean $m_t$ and outer-product corrections $M_t$, with updates $m_t = m_{t-1} + (x_t - m_{t-1})/t$ and $M_t = M_{t-1} + (x_t - m_{t-1})(x_t - m_t)^\top$, achieving the same asymptotic cost with improved numerical stability under large data shifts. The Chan-Golub-LeVeque algorithm supports block-parallel merging through the exact identity $M = M_A + M_B + \frac{n_A n_B}{n_A+n_B}(m_B - m_A)(m_B - m_A)^\top$, making it the natural choice for distributed and map-reduce architectures. All three algorithms produce the same estimator $S_t = M_t/(t-1)$ in exact arithmetic, although their finite-precision behavior differs markedly. Beyond runtime and numerical comparisons, we introduce a conformal prediction framework for streaming covariance estimation that yields finite-sample, distribution-free confidence sets $C_{t,jk}$ for each entry $S_{t,jk}$ of the covariance matrix at any step $t$ of the data stream. Experiments confirm that the Gram algorithm is fastest for batch computation, Welford is uniquely robust to catastrophic cancellation under large mean shifts, CGL is optimal for distributed settings, and conformal intervals achieve the nominal coverage level across all three algorithms.
appendix boundary found by none_found · 100% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Chan, T. F., Golub, G. H., and LeVeque, R. J (1979) Updating formulae and a pairwise algorithm for computing sample variances | 1.000 | 5 | 4 | 100% |
| 2 | Reichel, F (2025) High-Performance Variance-–Covariance Matrix Construction Using an Uncentered Gram Formulation, Forthcoming in self | 0.928 | 4 | 4 | 100% |
| 3 | Vovk, V., Gammerman, A., and Shafer, G (2005) Algorithmic Learning in a Random World | 0.928 | 4 | 3 | 100% |
| 4 | Higham, N. J (2002) Accuracy and Stability of Numerical Algorithms | 0.737 | 3 | 2 | 100% |
| 5 | Angelopoulos, A. N. and Bates, S (2023) Conformal prediction: A gentle introduction | 0.644 | 2 | 2 | 100% |
| 6 | Welford, B. P (1962) Note on a method for calculating corrected sums of squares and products | 0.644 | 2 | 2 | 100% |
| 7 | Newey, W. K. and West, K. D (1987) A simple, positive semi-definite, heteroskedasticity and autocorrelation consistent covariance matrix | 0.405 | 1 | 1 | 100% |
| 8 | Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A (2002) Inductive confidence machines for regression | 0.405 | 1 | 1 | 100% |
| 9 | White, H (1980) A heteroskedasticity-consistent covariance matrix estimator and a direct test for heteroskedasticity | 0.405 | 1 | 1 | 100% |
Showing the top 9 of 9 scored citations.