論文の概要: A random matrix model for random approximate $t$-designs
- arxiv url: http://arxiv.org/abs/2210.07872v3
- Date: Tue, 16 Apr 2024 12:22:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 03:10:06.486174
- Title: A random matrix model for random approximate $t$-designs
- Title（参考訳）: ランダム近似$t$-designに対するランダム行列モデル
- Authors: Piotr Dulian, Adam Sawicki,
- Abstract要約: 任意の$t$に対して$delta(nu_mathcalS,t)$の確率分布を記述するためにランダム行列モデルを提案する。
我々のモデルはいわゆるスペクトルギャップ予想を満足していること、すなわち、$sup が $tinmathbbZ_+$ であること、すなわち $sup が $tinmathbbZ_+delta(k)=delta(t)$ であることを示す。
- 参考スコア（独自算出の注目度）: 1.534667887016089
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For a Haar random set $\mathcal{S}\subset U(d)$ of quantum gates we consider the uniform measure $\nu_\mathcal{S}$ whose support is given by $\mathcal{S}$. The measure $\nu_\mathcal{S}$ can be regarded as a $\delta(\nu_\mathcal{S},t)$-approximate $t$-design, $t\in\mathbb{Z}_+$. We propose a random matrix model that aims to describe the probability distribution of $\delta(\nu_\mathcal{S},t)$ for any $t$. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by $t$. We prove that, the operator norm of this matrix, $\delta({t})$, is the random variable to which $\sqrt{|\mathcal{S}|}\delta(\nu_\mathcal{S},t)$ converges in distribution when the number of elements in $\mathcal{S}$ grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities $\mathbb{P}(\delta(t)>2+\epsilon)$, for any $\epsilon>0$. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability $1$ there is $t\in\mathbb{Z}_+$ such that $\sup_{k\in\mathbb{Z}_{+}}\delta(k)=\delta(t)$. Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of $\mathcal{S}$. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities $\mathbb{P}(\sqrt{\mathcal{S}}\delta(\nu_\mathcal{S},t)>2+\epsilon)$ are bounded from above by the tail probabilities $\mathbb{P}(\delta(t)>2+\epsilon)$ of our random matrix model. In particular our conjecture implies that a Haar random set $\mathcal{S}\subset U(d)$ satisfies the spectral gap conjecture with the probability $1$.
- Abstract（参考訳）: ハール確率集合 $\mathcal{S}\subset U(d)$ に対して、一様測度 $\nu_\mathcal{S}$ を考える。
測度 $\nu_\mathcal{S}$ は $\delta(\nu_\mathcal{S},t)$-approximate $t$-design, $t\in\mathbb{Z}_+$ とみなすことができる。
任意の$t$に対して$\delta(\nu_\mathcal{S},t)$の確率分布を記述することを目的としたランダム行列モデルを提案する。
我々のモデルはブロックが独立なブロック対角行列によって与えられ、ガウスあるいはジニブレのアンサンブルによって与えられ、それらの数、サイズ、型は$t$で決定される。
この行列の作用素ノルムである$\delta({t})$は、$\sqrt{|\mathcal{S}|}\delta(\nu_\mathcal{S},t)$が分布に収束する確率変数である。
さらに、我々のモデルは、任意の$\epsilon>0$に対して、テール確率 $\mathbb{P}(\delta(t)>2+\epsilon)$ に明示的な境界を与える。
我々はまた、我々のモデルがいわゆるスペクトルギャップ予想を満たすこと、すなわち、確率$t\in\mathbb{Z}_+$ が存在して $\sup_{k\in\mathbb{Z}_{+}}\delta(k)=\delta(t)$ であることを示す。
数値シミュレーションは、提案されたモデルが実際に$\mathcal{S}$の任意の濃度に対してほぼ正確であることを示す証拠を与える。
この現象のヒューリスティックな説明は、我々は、テール確率 $\mathbb{P}(\sqrt{\mathcal{S}}\delta(\nu_\mathcal{S},t)>2+\epsilon)$ が、我々のランダム行列モデルのテール確率 $\mathbb{P}(\delta(t)>2+\epsilon)$ によって上から有界であると推測する。
特に我々の予想は、ハール確率集合 $\mathcal{S}\subset U(d)$ がスペクトルギャップ予想を確率 $1$ を満たすことを示唆している。
関連論文リスト
- Relative volume of comparable pairs under semigroup majorization [0.0]
本研究は, 電子化関係における最近の結果と予想について概説する。
我々は、emphUT-majorization関係の場合、新しい正確な有限-n$の結果を証明した。
論文 参考訳（メタデータ） (2024-10-30T16:48:59Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture
Models [12.746888269949407]
2進隠れマルコフモデルに対する高次元平均推定問題を考える。
ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
論文 参考訳（メタデータ） (2022-06-06T09:34:04Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。
正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文 参考訳（メタデータ） (2022-02-10T23:44:09Z) - 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) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Near-Optimal Model Discrimination with Non-Disclosure [19.88145627448243]
まず、二乗損失を持つよく特定された線形モデルについて考察する。
類似した形態のサンプルの複雑さは、たとえ不特定であっても引き起こされる。
論文 参考訳（メタデータ） (2020-12-04T23:52:54Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。