論文の概要: Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality
- arxiv url: http://arxiv.org/abs/2604.01367v1
- Date: Wed, 01 Apr 2026 20:23:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-03 14:21:09.961864
- Title: Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality
- Title（参考訳）: 多項式的最小平均によるランダム行列の永続性近似:零点と普遍性
- Authors: Frederic Koehler, Pui Kuen Leung,
- Abstract要約: 入力が零点からわずかに偏ったときにランダム行列の永久性を近似するアルゴリズムについて検討する。
我々は、$mathrmper(zJ + W)$に対して十分大きなゼロ自由領域を確立し、$J$はオールワン行列、$W$は独立平均ゼロエントリを持つランダム行列である。
W$ の成分が複素であるとき、ランダム $mathrmper(zJ + W)$ のすべての零点が半径 $tildeO(n) の円板内にあることを示す。
- 参考スコア（独自算出の注目度）: 11.09360259927697
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and \emph{boson sampling} (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial $\mathrm{per}(zJ + W)$, where $J$ is the all-ones matrix and $W$ is a random matrix with independent mean-zero entries. We show that when the entries of $W$ are standard complex Gaussians, all zeros of the random polynomial $\mathrm{per}(zJ + W)$ lie within a disk of radius $\tilde{O}(n^{-1/3})$, which yields an approximation algorithm when the bias of the entries is $\tildeΩ(n^{-1/3})$. Previously, there were no efficient algorithms at biases smaller than $1/\mathrm{polylog}(n)$, and it was unknown whether there typically exist zeros $z$ with $|z| \ge 1$. As a complementary result, we show that the bulk of the zeros, namely $(1 - ε)n$ of them, have magnitude $Θ(n^{-1/2})$. This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices $W$ with i.i.d. subexponential entries.
- Abstract（参考訳）: 入力が零点からわずかに偏ったときにランダム行列の永久性を近似するアルゴリズムについて検討する。
この問題は、線形光学の古典的複雑性と 'emph{boson sample} (アーロンソンとアルヒポフ'11;エルダルとメフラバン'17) を理解するという目標によって動機付けられている。
バルビノクの補間法は、多項式 $\mathrm{per}(zJ + W)$ に対して十分大きなゼロ自由領域を確立することができ、$J$ はオールワン行列、$W$ は独立平均ゼロ成分を持つランダム行列である。
W$ の成分が標準複素ガウス群であるとき、ランダム多項式 $\mathrm{per}(zJ + W)$ のすべての零点が半径 $\tilde{O}(n^{-1/3})$ の円板内にあることが示される。
以前は1/\mathrm{polylog}(n)$未満のバイアスで効率的なアルゴリズムは存在せず、通常ゼロが$|z| \ge 1$であるかどうかは不明である。
相補的な結果として、零点の大部分、すなわち 1 - ε)n$ が等級$(n^{-1/2})$であることを示す。
これにより、補間法は、永久体を近似する予想平均ケース硬さと矛盾しない。
また、複素頂点フーガシティを持つ一般グラフ上のハードコアモデルに対して、類似のゼロ自由領域を確立する。
さらに,無作為行列が$W$,すなわち部分指数エントリに対してゼロ自由領域を確立する普遍性の結果が証明される。
関連論文リスト
- 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) - 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) - Universality for the global spectrum of random inner-product kernel
matrices in the polynomial regime [12.221087476416056]
本稿では、この現象が普遍であることを示し、X$がすべての有限モーメントを持つi.d.エントリを持つとすぐに保持する。
非整数$ell$の場合、Marvcenko-Pastur項は消滅する。
論文 参考訳（メタデータ） (2023-10-27T17:15:55Z) - 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) - 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) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。