論文の概要: Lower bounds for trace estimation via Block Krylov and other methods
- arxiv url: http://arxiv.org/abs/2506.22701v1
- Date: Sat, 28 Jun 2025 00:41:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-01 21:27:53.520011
- Title: Lower bounds for trace estimation via Block Krylov and other methods
- Title（参考訳）: Block Krylovと他の手法によるトレース推定のための下界
- Authors: Shi Jie Yu,
- Abstract要約: 我々は,Hutchinson法とBlock Krylov法を併用した手法について検討した。
関数に対してクリロフステップがいくつ必要かという理論上界を導出する。
また、トレース推定に必要なクエリ数の制限も低くする。
- 参考スコア（独自算出の注目度）: 2.365973885231265
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies theoretical lower bounds for estimating the trace of a matrix function, $\text{tr}(f(A))$, focusing on methods that use Hutchinson's method along with Block Krylov techniques. These methods work by approximating matrix-vector products like $f(A)V$ using a Block Krylov subspace. This is closely related to approximating functions with polynomials. We derive theoretical upper bounds on how many Krylov steps are needed for functions such as $A^{-1/2}$ and $A^{-1}$ by analyzing the upper bounds from the polynomial approximation of their scalar equivalent. In addition, we also develop lower limits on the number of queries needed for trace estimation, specifically for $\text{tr}(W^{-p})$ where $W$ is a Wishart matrix. Our study clarifies the connection between the number of steps in Block Krylov methods and the degree of the polynomial used for approximation. This links the total cost of trace estimation to basic limits in polynomial approximation and how much information is needed for the computation.
- Abstract（参考訳）: 本稿では,Hutchinson法とBlock Krylov法を併用した手法に着目し,行列関数のトレースを推定するための理論的下界,$\text{tr}(f(A))$について検討する。
これらの手法は、ブロック・クリロフ部分空間を用いて$f(A)V$のような行列ベクトル積を近似することで機能する。
これは多項式の近似関数と密接に関連している。
A^{-1/2}$ や $A^{-1}$ のような関数に対して、そのスカラー同値の多項式近似から上界を解析することによって、クリロフステップがいくつ必要かの理論上界を導出する。
さらに、トレース推定に必要なクエリ数、具体的には$\text{tr}(W^{-p})$に対して$W$はウィッシュアート行列である。
本研究は,ブロック・クリロフ法におけるステップ数と近似に用いる多項式の次数との関連性を明らかにする。
これは、トレース推定の総コストと多項式近似の基本的な限界と、計算に必要な情報量とを関連付ける。
関連論文リスト
- Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。
分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文 参考訳（メタデータ） (2025-04-29T15:56:48Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Infinite quantum signal processing [0.6808803980072229]
量子信号処理(QSP)は、次数$d$の真のスカラーを表す。
QSPは多種多様なポリノミカル関数を表現できることを示す。
解析の結果,対象関数の正則性と因子の減衰特性との間には,驚くべき関連性があることが判明した。
論文 参考訳（メタデータ） (2022-09-21T07:50:26Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Practical Quasi-Newton Methods for Training Deep Neural Networks [12.48022619079224]
トレーニングにおいて、勾配の$n$の変数と成分の数は、しばしば数千万の順序のものであり、ヘッセン元は$n2$要素を持つ。
ブロック対角行列によりヘッセンを近似し、勾配とヘッセンの構造を用いてこれらのブロックをさらに近似する。
DNNにおけるヘシアンの不確定かつ高度に可変な性質のため、BFGSとL-BFGSの近似の上限と下限を有界に保つための新しい減衰法も提案する。
論文 参考訳（メタデータ） (2020-06-16T02:27:12Z) - Fourier Sparse Leverage Scores and Approximate Kernel Learning [29.104055676527913]
我々はガウス測度とラプラス測度の両方の下でフーリエ関数のレバレッジスコアに新しい明示的な上限を証明した。
私たちの限界は、機械学習における2つの重要な応用によって動機付けられています。
論文 参考訳（メタデータ） (2020-06-12T17:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。