Fugu-MT 論文翻訳(概要): A Fast and Accurate Approach for Covariance Matrix Construction

論文の概要: A Fast and Accurate Approach for Covariance Matrix Construction

arxiv url: http://arxiv.org/abs/2511.08223v1
Date: Wed, 12 Nov 2025 01:47:30 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-12 20:17:03.701859
Title: A Fast and Accurate Approach for Covariance Matrix Construction
Title（参考訳）: 共分散行列構築のための高速かつ高精度な手法
Authors: Felix Reichel,
Abstract要約: Reichel (2025) は、バリアンスを $mathrmBariance(x)=frac1n(n-1)sum_ij(x_i-x_j)2$ と定義した。これを共分散行列に拡張するには、$mathrmCov(X)=frac1n-1!left(Xtop X-frac1n,s,stopright)$ with $s=Xtop mathbf1
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: Reichel (2025) は、バリアンスを $\mathrm{Bariance}(x)=\frac{1}{n(n-1)}\sum_{i<j}(x_i-x_j)^2$ と定義した。これを共分散行列に拡張し、$\mathrm{Cov}(X)=\frac{1}{n-1}\! X^\top X-\frac{1}{n}\,s\,s^\top\right)$ with $s=X^\top \mathbf{1}_n$ は対微分形式と代数的に同一であるが、明示的な中心化を避ける。計算は1つの$p\times p$外行列積と1つの減算に還元される。 Pythonの実証的なベンチマークでは、非BLASでチューニングされた設定でnumpy.covよりも明らかにランタイムが向上している。 RXTX (Rybin et. al) のようなより高速なGramルーチンを$XX^\top$で実行すると、総コストはさらに削減される。

関連論文リスト

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs [0.12289361708127876]
単純かつ効果的なリジェクションサンプリングに基づくアプローチで,$k$-$mathttmeans$++ を高速化する。最初のメソッドは $tildeO(mathttnnz (mathcalX) + beta k2d)$ で実行されます。第2の手法は,計算コストと解品質の新たなトレードオフを示す。
論文参考訳（メタデータ） (2025-02-04T08:05:34Z)
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文参考訳（メタデータ） (2024-08-16T02:33:07Z)
Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文参考訳（メタデータ） (2023-12-14T12:53:34Z)
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文参考訳（メタデータ） (2023-11-03T14:56:24Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文参考訳（メタデータ） (2022-09-30T04:15:44Z)
List-Decodable Covariance Estimation [1.9290392443571387]
共分散推定アルゴリズムを初めて提案する。この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
論文参考訳（メタデータ） (2022-06-22T09:38:06Z)
Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
関数 $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)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文参考訳（メタデータ） (2021-09-06T14:21:43Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)
Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文参考訳（メタデータ） (2020-04-16T22:57:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。