論文の概要: Concentration of polynomial random matrices via Efron-Stein inequalities
- arxiv url: http://arxiv.org/abs/2209.02655v1
- Date: Tue, 6 Sep 2022 17:12:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-07 15:46:41.564123
- Title: Concentration of polynomial random matrices via Efron-Stein inequalities
- Title（参考訳）: Efron-Stein不等式による多項式ランダム行列の濃度
- Authors: Goutham Rajendran, Madhur Tulsiani
- Abstract要約: 多くの応用において、変数がスカラーであるランダム行列を解析する必要がある。
パウリン・マッキー=トロップによって開発された行列 Efron-Stein の不等式に基づいて、そのような境界を得るための一般的な枠組みを提案する。
トレースパワー法を非自明に応用したJonesら[FOCS 2021]が最近取得した"スパースグラフ行列"のバウンダリを導出する。
- 参考スコア（独自算出の注目度）: 0.3451964963586458
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Analyzing concentration of large random matrices is a common task in a wide
variety of fields. Given independent random variables, many tools are available
to analyze random matrices whose entries are linear in the variables, e.g. the
matrix-Bernstein inequality. However, in many applications, we need to analyze
random matrices whose entries are polynomials in the variables. These arise
naturally in the analysis of spectral algorithms, e.g., Hopkins et al. [STOC
2016], Moitra-Wein [STOC 2019]; and in lower bounds for semidefinite programs
based on the Sum of Squares hierarchy, e.g. Barak et al. [FOCS 2016], Jones et
al. [FOCS 2021]. In this work, we present a general framework to obtain such
bounds, based on the matrix Efron-Stein inequalities developed by
Paulin-Mackey-Tropp [Annals of Probability 2016]. The Efron-Stein inequality
bounds the norm of a random matrix by the norm of another simpler (but still
random) matrix, which we view as arising by "differentiating" the starting
matrix. By recursively differentiating, our framework reduces the main task to
analyzing far simpler matrices. For Rademacher variables, these simpler
matrices are in fact deterministic and hence, analyzing them is far easier. For
general non-Rademacher variables, the task reduces to scalar concentration,
which is much easier. Moreover, in the setting of polynomial matrices, our
results generalize the work of Paulin-Mackey-Tropp. Using our basic framework,
we recover known bounds in the literature for simple "tensor networks" and
"dense graph matrices". Using our general framework, we derive bounds for
"sparse graph matrices", which were obtained only recently by Jones et al.
[FOCS 2021] using a nontrivial application of the trace power method, and was a
core component in their work. We expect our framework to be helpful for other
applications involving concentration phenomena for nonlinear random matrices.
- Abstract（参考訳）: 大きなランダム行列の濃度を分析することは、様々な分野において一般的な課題である。
独立な確率変数が与えられた場合、多くのツールは、行列-ベルンシュタイン不等式のような変数の成分が線型であるランダム行列を解析することができる。
しかし、多くの応用において、変数の成分が多項式であるランダム行列を解析する必要がある。
これらは、例えばホプキンス等、スペクトルアルゴリズムの解析において自然に発生する。
[STOC 2016], Moitra-Wein [STOC 2019], そして半定値プログラムの下位境界では、例えば Barak などである。
FOCS 2016], Jones et al.
【focs 2021】
本研究では、Paulin-Mackey-Tropp が開発した行列 Efron-Stein の不等式(Annals of Probability 2016)に基づいて、そのような境界を得るための一般的な枠組みを提案する。
Efron-Steinの不等式は、他のより単純な(しかしまだランダムな)行列のノルムによってランダム行列のノルムを束縛する。
再帰的に微分することで、我々のフレームワークは、はるかに単純な行列を解析する主なタスクを減らします。
ラデマッハ変数の場合、これらの単純な行列は実際決定論的であり、したがって解析はずっと容易である。
一般の非ラデマッハ変数の場合、タスクはスカラー濃度に還元されるが、これははるかに容易である。
さらに,多項式行列の設定において,ポーリン・マッキートロップの研究を一般化した。
基本フレームワークを用いて、単純な「テンソルネットワーク」と「密度グラフ行列」の文献における既知の境界を復元する。
一般的なフレームワークを使って、jones氏らによって最近取得された"疎グラフ行列"の境界を導出します。
[FOCS 2021] トレースパワー方式の非自明な応用を用い, 作業のコアコンポーネントとなった。
我々は,非線形ランダム行列に対する集中現象を含む他の応用に有効なフレームワークを期待する。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Nonlinear Random Matrices and Applications to the Sum of Squares
Hierarchy [0.0]
非線形ランダム行列の理論における新しいツールを開発する。
平均ケース問題における正方形階層のサム性能について検討する。
論文 参考訳（メタデータ） (2023-02-09T06:52:03Z) - An Equivalence Principle for the Spectrum of Random Inner-Product Kernel
Matrices with Polynomial Scalings [21.727073594338297]
この研究は、機械学習と統計学の応用によって動機付けられている。
スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。
我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
論文 参考訳（メタデータ） (2022-05-12T18:50:21Z) - Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra [6.338178373376447]
本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。
我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
論文 参考訳（メタデータ） (2022-01-27T05:24:02Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z) - On Random Matrices Arising in Deep Neural Networks: General I.I.D. Case [0.0]
本研究では, ニューラルネットワーク解析に係わる無作為行列の積の特異値分布について検討した。
我々は、[22] の結果を一般化するために、[22] の確率行列理論のテクニックの、より簡潔な別のバージョンを使用します。
論文 参考訳（メタデータ） (2020-11-20T14:39:24Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
論文 参考訳（メタデータ） (2020-06-24T19:33:49Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。