論文の概要: Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
- arxiv url: http://arxiv.org/abs/2609.18577v1
- Date: Wed, 16 Sep 2026 12:37:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:53.800231
- Title: Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
- Title（参考訳）: Recursive TensorSketchによる低ランダムビットによる高精度トレース推定
- Abstract要約: 本稿では,matrix-vector 製品クエリを通じてのみアクセス可能な mathbbRdptimes dp$ の暗黙行列 $mathbfA のトレースを推定する問題を考える。
textitHutchinson trace estimator% citeGirard 1987algorithme, article-Hutchinson is a classical sketching method for this problem。
- 参考スコア（独自算出の注目度）: 7.212776727737758
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of estimating the trace of an implicit matrix $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries. The \textit{Hutchinson trace estimator}% ~\cite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{(i)}}^T \mathbf{A} \mathbf{z}^{(i)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$, and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and (ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$. Generating one query vector $\mathbf{z}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(md^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in $\mathbb{R}^{d^p}$ is constructed as the Kronecker product of $p$ random vectors in $\mathbb{R}^d$, requiring $O(mpd)$ random bits for $m$ query vectors. The estimator of~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} is unbiased; however, its variance grows exponentially with $p$. In this work, we address this limitation by proposing a sketching-based estimator that requires $O\!\big(p (d + m)\log m\big)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.
- Abstract（参考訳）: 暗黙行列 $\mathbf{A} \in \mathbb{R}^{d^p\times d^p}$ のトレースを推定する問題を考える。
The \textit{Hutchinson trace estimator}% ~\cite{Girard 1987algorithme, article-hutchinson} is a classical sketching method for this problem。
その推定子 $H_{m}(\mathbf{A}) = \frac{1}{m} \sum_{i=1}^{m} {\mathbf{z}^{
(i)}}^T \mathbf{A} \mathbf{z}^{
(i)}, \quad \text{where } \ {\mathbf{z}^{
(i)}}\in \mathbb{R}^{d^p}$, $z^{
(i)}_j \in {N}(0, 1), j\in [d^p]$ は以下の保証を満たす。
(i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and
(ii) $\mathrm{Var}[H_{m}(\mathbf{A})]=\frac{2}{m}||\mathbf{A}||_F^2$。
1つのクエリベクトル $\mathbf{z}^{ を生成する
(i)}$は$O(d^p)$ランダムビットを必要とするので、$m$クエリは$O(md^p)$ランダムビットを必要とする。
Meyer et al ~\cite{meyer2025 Hutchinsonsestimatorbadkroneckertraceestimation} による最近の研究は、$\mathbb{R}^{d^p}$の各クエリベクトルが$\mathbb{R}^d$のランダムベクトルのKronecker積として構成され、$m$のクエリベクトルに対して$O(mpd)$ランダムビットを必要とするハッチンソントレース推定器の変種を提案する。
~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} の推定量は不偏であるが、その分散は$p$で指数関数的に増加する。
本研究では,$O\!を必要とするスケッチベースの推定器を提案することで,この制限に対処する。
\big(p (d + m)\log m\big)$ ランダムビットは、トレースの偏りのない推定値となり、同時に$p$で多項式的に成長する分散境界を達成する。
関連論文リスト
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。
ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-11-11T03:43:52Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
我々は分散アルゴリズムを解析し、$N$クライアント上で低ランク行列の分解を計算する。
グローバルな$mathbfV$ in $mathbbRd times r$をすべてのクライアントに共通とし、ローカルな$mathbfUi$ in $mathbbRn_itimes r$を得る。
論文 参考訳（メタデータ） (2024-09-13T12:28:42Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳（メタデータ） (2023-10-02T16:44:47Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - 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) - Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。
点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
論文 参考訳（メタデータ） (2021-05-11T02:29:33Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。