論文の概要: Exact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak Anticoncentration
- arxiv url: http://arxiv.org/abs/2608.17065v1
- Date: Mon, 17 Aug 2026 19:12:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-19 21:40:53.11302
- Title: Exact Moments of Gaussian Gram Hafnians Reveal an $n^2/\log n$ Threshold for Weak Anticoncentration
- Title（参考訳）: ガウス・グラハム・ハフニアンの厳密なモーメントは、弱反凝縮に対する$n^2/\log n$Thresholdを明らかにする
- Abstract要約: 反濃縮は、近似サンプリングのための硬度引数の中心である。
有限次元ハールモーメント移動と高確率小球対集中は別問題のままである。
- 参考スコア（独自算出の注目度）: 2.8224889996383395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Anticoncentration is central to hardness arguments for approximate sampling. In the independent Gaussian surrogate for collision free Gaussian boson sampling, the moment ratio studied here also determines the averaged ideal linear cross entropy reference value. Let $H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)$, where $X\in\mathbb{C}^{k\times 2n}$ has independent standard circular complex Gaussian entries. We evaluate $\mathbb{E}|H_{k,n}|^2$ and $\mathbb{E}|H_{k,n}|^4$ exactly by reducing four hafnian copies to a rank two Gaussian integral. For $R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4$, we obtain $R_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}$, where $F_{k,n}={}3F_2(-n,-n,1/2;1,k/2;1)$ is a terminating generalized hypergeometric polynomial. If $k/n^2\to c>0$, then $F{k,n}\to e^{1/c}I_0(1/c)$, where $I_0$ is the modified Bessel function of the first kind of order zero, and consequently $R_{k,n}\sqrt{πn}\to[e^{1/c}I_0(1/c)]^{-1}$. Thus $k\asymp n^2$ is a smooth Bessel crossover, whereas the scaling order boundary for inverse polynomial weak anticoncentration is $k\asymp n^2/\log n$. These conclusions concern the Gaussian surrogate moment criterion; finite dimensional Haar moment transfer and high probability small ball anticoncentration remain separate problems.
- Abstract（参考訳）: 反濃縮は、近似サンプリングのための硬度引数の中心である。
衝突のないガウスボソンサンプリングのための独立なガウスサロゲートにおいて、ここで研究されたモーメント比は、平均された理想的な線形クロスエントロピー基準値も決定する。
H_{k,n}=\mathrm{haf}(X^{\mathsf T}X)$ とすると、$X\in\mathbb{C}^{k\times 2n}$ は独立した標準複素ガウス成分を持つ。
4つのハフニアンコピーをランク2のガウス積分に還元することにより、$\mathbb{E}|H_{k,n}|^2$と$\mathbb{E}|H_{k,n}|^4$を正確に評価する。
R_{k,n}=(\mathbb{E}|H_{k,n}|^2)^2/\mathbb{E}|H_{k,n}|^4$ に対して、$R_{k,n}=4^{-n}\binom{2n}{n}/F_{k,n}$ を得る。
もし$k/n^2\to c>0$ なら、$F{k,n}\to e^{1/c}I_0(1/c)$ であり、$I_0$ は第1次 0 のベッセル函数であり、従って$R_{k,n}\sqrt{πn}\to [e^{1/c}I_0(1/c)]^{-1} である。
したがって、$k\asymp n^2$ は滑らかなベッセルクロスオーバーであり、逆多項式の弱反集中のスケーリング次数境界は $k\asymp n^2/\log n$ である。
これらの結論はガウスの代理モーメント基準に関係しており、有限次元のハールモーメント移動と高い確率の小さな球反集中は別の問題のままである。
関連論文リスト
- Zero-SNR Analyticity of the Scalar MMSE Is Equivalent to Gaussianity [0.7499255435598924]
最小平均二乗誤差 $operatornamemmse_X(s)$ がゼロ信号対雑音比で解析可能であることを証明する。
ゼロの$mgeq 2$は、Hermitemathの根に従って分割され、代わりにプレファクタ$n-m/2er_msqrt2n$に寄与する。
論文 参考訳（メタデータ） (2026-09-14T05:07:20Z) - Permanents of matrix ensembles: computation, distribution, and geometry [0.0]
我々はGPUを使用して、$mathbbC,$mathbbR,$ $mathbbF_p$および$mathbbQ.$以上の永久体の計算を劇的に高速化する。
我々は、一元群における恒久的な測地学について研究する。
恒等式から$n$-サイクル置換行列への測地論について、普遍スケーリング関数 $f(t)=frac1nln|perm((t))|$ は$n$ in とは独立である。
論文 参考訳（メタデータ） (2026-02-08T22:31:42Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - 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) - Classical shadows of fermions with particle number symmetry [0.0]
我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。
ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
論文 参考訳（メタデータ） (2022-08-18T17:11:12Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - 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) - Kernel Thinning [26.25415159542831]
カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。
我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
論文 参考訳（メタデータ） (2021-05-12T17:56:42Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。