A Fast and Accurate Approach for Covariance Matrix Construction

• URL: http://arxiv.org/abs/2511.08223v1
• Date: Wed, 12 Nov 2025 01:47:30 GMT
• Title: A Fast and Accurate Approach for Covariance Matrix Construction
• Authors: Felix Reichel,
• Abstract summary: Reichel (2025) defined the Bariance as $mathrmBariance(x)=frac1n(n-1)sum_ij(x_i-x_j)2$.<n>We extend this to the covariance matrix by showing that $mathrmCov(X)=frac1n-1!left(Xtop X-frac1n,s,stopright)$ with $s=Xtop mathbf1
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Reichel (2025) defined the Bariance as $\mathrm{Bariance}(x)=\frac{1}{n(n-1)}\sum_{i<j}(x_i-x_j)^2$, which admits an $O(n)$ reformulation using scalar sums. We extend this to the covariance matrix by showing that $\mathrm{Cov}(X)=\frac{1}{n-1}\!\left(X^\top X-\frac{1}{n}\,s\,s^\top\right)$ with $s=X^\top \mathbf{1}_n$ is algebraically identical to the pairwise-difference form yet avoids explicit centering. Computation reduces to a single $p\times p$ outer matrix product and one subtraction. Empirical benchmarks in Python show clear runtime gains over numpy.cov in non-BLAS-tuned settings. Faster Gram routines such as RXTX (Rybin et. al) for $XX^\top$ further reduce total cost.

Related papers

• Lasso and Partially-Rotated Designs [2.28438857884398]
  We introduce a new $textitsemirandom$ family of designs for which the RE constant with respect to the secret is bounded away from zero.<n>Our results imply that Lasso achieves prediction error $O(k log d / lambda_min n)$ with high probability.
  arXiv  Detail & Related papers  (2025-05-16T10:25:08Z)
• A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs [0.12289361708127876]
  We present a simple and effective rejection sampling based approach for speeding up $k$-$mathttmeans$++.<n>Our first method runs in time $tildeO(mathttnnz (mathcalX) + beta k2d)$ while still being $O(log k )$ competitive in expectation.<n>Our second method presents a new trade-off between computational cost and solution quality.
  arXiv  Detail & Related papers  (2025-02-04T08:05:34Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Efficient $1$-bit tensor approximations [1.104960878651584]
  Our algorithm yields efficient signed cut decompositions in $20$ lines of pseudocode. We approximate the weight matrices in the open textitMistral-7B-v0.1 Large Language Model to a $50%$ spatial compression.
  arXiv  Detail & Related papers  (2024-10-02T17:56:32Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  We show that our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. In particular, our algorithm has an $tilde O(n2)$ when $k=O(n0.729)$. Our main algorithm can be viewed as a randomized block coordinate descent method.
  arXiv  Detail & Related papers  (2023-12-14T12:53:34Z)
• Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products [9.661328973620531]
  Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting. We give novel reductions from the Strong Exponential Time Hypothesis (SETH) that rely on lower bounding the leverage scores of flat sparse vectors. Since our low rank algorithms rely on matrix-vectors, our lower bounds extend to show that computing $f(UV)W$, for even a small matrix $W$, requires $Omega(n2-o(1))$ time.
  arXiv  Detail & Related papers  (2023-11-03T14:56:24Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• List-Decodable Covariance Estimation [1.9290392443571387]
  We give the first time algorithm for emphlist-decodable covariance estimation. Our result implies the first-time emphexact algorithm for list-decodable linear regression and subspace recovery.
  arXiv  Detail & Related papers  (2022-06-22T09:38:06Z)
• The Complexity of Dynamic Least-Squares Regression [11.815510373329337]
  complexity of dynamic least-squares regression. Goal is to maintain an $epsilon-approximate solution to $min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin.
  arXiv  Detail & Related papers  (2022-01-01T18:36:17Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $nOmega(1)$ number of columns. We show that under certain minimal and realistic distributional settings, it is possible to obtain a $(k/epsilon)$-approximation with a nearly linear running time and poly$(k/epsilon)+O(klog n)$ columns. This is the first algorithm of any kind for achieving a $(k/epsilon)$-approximation for entrywise
  arXiv  Detail & Related papers  (2020-04-16T22:57:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.