論文の概要: Stochastic trace estimation with tensor train random vectors
- arxiv url: http://arxiv.org/abs/2606.15679v1
- Date: Sun, 14 Jun 2026 08:55:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-16 16:21:33.791079
- Title: Stochastic trace estimation with tensor train random vectors
- Title（参考訳）: テンソルトレインランダムベクトルを用いた確率的トレース推定
- Abstract要約: 本研究は、ガウス確率テンソルトレインベクトルをトレース推定のための構造的代替物として研究する。
テンソルトレインランクの適切な選択により、ランダムテンソルトレインベクトルは、ジラード-ハッチンソン推定器の次元非依存保証を回復する。
特に、テンソルトレインの階数$r geq d-1の中央値の変種は、古典ガウス推定器と同じ精度と失敗確率$$に依存する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic trace estimation is a standard tool for approximating the trace of a large-scale matrix available only through matrix-vector products. However, in tensor-structured settings, unstructured Gaussian or Rademacher test vectors may be prohibitively expensive to store and compute with, while cheaper rank-one tensor-product vectors can require sample complexities that grow exponentially with the tensor order. This work studies Gaussian random tensor train vectors as a structured alternative for stochastic trace estimation. We show that, with a suitable choice of the tensor train rank, random tensor train vectors recover dimension-independent guarantees for the Girard--Hutchinson estimator. In particular, a median-of-means variant with tensor train rank $r \geq d-1$ achieves the same dependence on the accuracy $\varepsilon$ and failure probability $δ$ as the classical estimator based on unstructured Gaussian vectors. We further prove an oblivious subspace injection result for sketches formed from independent Gaussian random tensor train vectors: tensor train rank $r\geq d-1$ and $\mathcal{O}(\varepsilon^{-2}(k+\log(1/δ)))$ samples suffice for a $k$-dimensional target subspace. Finally, we investigate the use of such sketches within the Nyström++ framework. We show that the resulting estimator can achieve the desired $\mathcal{O}(\varepsilon^{-1})$ sample complexity under an additional spectral-tail condition. These results provide clarififcation on both the potential and the limitations of random tensor train vectors in stochastic trace estimation.
- Abstract（参考訳）: 確率的トレース推定は,行列ベクトル生成物のみで利用可能な大規模行列のトレースを近似するための標準ツールである。
しかし、テンソル構造では、非構造ガウスあるいはラデマッハテストベクトルは保存と計算が禁じられるが、より安価なランク1のテンソル積ベクトルはテンソル次数で指数関数的に増加するサンプル複素数を必要とする。
本研究は確率的トレース推定のための構造的代替としてガウスランダムテンソルトレインベクトルについて研究する。
テンソルトレインランクの適切な選択により、ランダムテンソルトレインベクトルは、ジラード-ハッチンソン推定器の次元非依存保証を回復する。
特に、テンソルトレイン階数 $r \geq d-1$ の中間平均変種は、非構造ガウスベクトルに基づく古典的推定量として$\varepsilon$ と失敗確率 $δ$ の精度に依存する。
さらに、独立ガウスのランダムなテンソルトレインベクトルから生成されるスケッチに対して、不要な部分空間注入結果が証明される:tensor train rank $r\geq d-1$ and $\mathcal{O}(\varepsilon^{-2}(k+\log(1/δ))$ $k$次元のターゲット部分空間に対するサンプルサフィス。
最後に、Nyström++フレームワーク内でのこのようなスケッチの使用について検討する。
得られた推定器は、追加のスペクトルテール条件下で所望の$\mathcal{O}(\varepsilon^{-1})$サンプル複雑性が得られることを示す。
これらの結果は確率的トレース推定におけるランダムなテンソルトレインベクトルのポテンシャルと制限の両方にクリフレーションを与える。
関連論文リスト
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Dimension reduction with structure-aware quantum circuits for hybrid machine learning [0.0]
ベクトルのシュミット分解は特異値分解(SVD)をベクトル形式で記述するものとして理解することができる。
我々は、$k$の値で設計された量子回路が、データセット全体の縮小形式表現を近似できることを示した。
論文 参考訳（メタデータ） (2025-07-31T17:18:43Z) - On the Accuracy of Hotelling-Type Asymmetric Tensor Deflation: A Random
Tensor Analysis [14.809070996761013]
ホテルリング型テンソルデフレレーションはノイズの存在下で研究されている。
我々は,デフレ手順の各ステップにおいて,推定特異値と推定および真の特異ベクトルのアライメントを解析的に特徴付ける。
論文 参考訳（メタデータ） (2023-10-28T14:40:10Z) - Decomposable Sparse Tensor on Tensor Regression [1.370633147306388]
テンソル回帰のスパースローランクテンソルを考えると、予測子 $mathcalX$ とレスポンス $mathcalY$ はどちらも高次元テンソルである。
本稿では,契約部と生成部から構成されるステージワイド探索に基づく高速解を提案する。
論文 参考訳（メタデータ） (2022-12-09T18:16:41Z) - On the Accuracy of Hotelling-Type Tensor Deflation: A Random Tensor
Analysis [16.28927188636617]
階数-$r$ の $sum_i=1r beta_i A_i + W$ の非対称スパイクモデルを考える。
本研究では, ホテルリング型デフレに関する研究を行った。
論文 参考訳（メタデータ） (2022-11-16T16:01:56Z) - Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor
Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。
テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。
さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2022-07-15T11:55:09Z) - When Random Tensors meet Random Matrices [50.568841545067144]
本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。
検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
論文 参考訳（メタデータ） (2021-12-23T04:05:01Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。
以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
論文 参考訳（メタデータ） (2020-10-22T00:32:12Z) - GO Hessian for Expectation-Based Objectives [73.06986780804269]
GOグラデーションは、最近予測に基づく目的に対して$mathbbE_q_boldsymboldsymboldsymbolgamma(boldsymboly) [f(boldsymboly)]$として提案された。
GO勾配に基づいて、$mathbbE_q_boldsymboldsymboldsymbolgamma(boldsymboly) [f(boldsymboly)]$ an unbiased low-variance Hessian estimator, named GO Hessian を示す。
論文 参考訳（メタデータ） (2020-06-16T02:20:41Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。