Saved in:
| Main Author: | |
|---|---|
| Format: | Recurso digital |
| Language: | |
| Published: |
Zenodo
2026
|
| Online Access: | https://doi.org/10.5281/zenodo.19931686 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866901578116497408 |
|---|---|
| author | Reichel, Felix |
| author_facet | Reichel, Felix |
| contents | <div class="page"> <div class="layoutArea"> <div class="column"> <div class="page"> <div class="layoutArea"> <div class="column"> <p>Three algorithms for computing the unbiased sample covariance matrix in a streaming or distributed setting are placed on a unified algebraic, numerical, and statistical foundation. The Gram algorithm, derived from the bariance reformulation of Reichel [8], maintains the running cross-product matrix and column-sum vector , yielding the unbiased covariance in ( ^2) per update. The Welford algorithm [10] propagates a running mean and outer-product corrections, achieving the same asymptotic cost with provably better numerical stability under large data shifts. The Chan-Golub- LeVeque (CGL) algorithm [2] supports block parallel merging via an exact combination formula, making it the natural choice for distributed and map- reduce architectures. All three produce the same estimator in exact arithmetic; 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 for each entry of the covariance matrix at any step 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.</p> </div> </div> </div> </div> </div> </div> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19931686 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | 2B or Not 2B: A Tale of Three Algorithms for Streaming: Covariance Estimation after Welford and Chan–Golub–LeVeque Reichel, Felix <div class="page"> <div class="layoutArea"> <div class="column"> <div class="page"> <div class="layoutArea"> <div class="column"> <p>Three algorithms for computing the unbiased sample covariance matrix in a streaming or distributed setting are placed on a unified algebraic, numerical, and statistical foundation. The Gram algorithm, derived from the bariance reformulation of Reichel [8], maintains the running cross-product matrix and column-sum vector , yielding the unbiased covariance in ( ^2) per update. The Welford algorithm [10] propagates a running mean and outer-product corrections, achieving the same asymptotic cost with provably better numerical stability under large data shifts. The Chan-Golub- LeVeque (CGL) algorithm [2] supports block parallel merging via an exact combination formula, making it the natural choice for distributed and map- reduce architectures. All three produce the same estimator in exact arithmetic; 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 for each entry of the covariance matrix at any step 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.</p> </div> </div> </div> </div> </div> </div> |
| title | 2B or Not 2B: A Tale of Three Algorithms for Streaming: Covariance Estimation after Welford and Chan–Golub–LeVeque |
| url | https://doi.org/10.5281/zenodo.19931686 |