論文の概要: Permanent of random matrices from representation theory: moments,
numerics, concentration, and comments on hardness of boson-sampling
- arxiv url: http://arxiv.org/abs/2104.06423v1
- Date: Tue, 13 Apr 2021 18:00:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-03 23:22:35.846673
- Title: Permanent of random matrices from representation theory: moments,
numerics, concentration, and comments on hardness of boson-sampling
- Title（参考訳）: 表現論からのランダム行列の永続性:ボソンサンプリングの硬さに関するモーメント、数値、濃度およびコメント
- Authors: Sepehr Nezami
- Abstract要約: ランダムな複素ガウス行列とランダムなユニタリ行列のサブ行列の永続性について検討する。
ハイブリッド理論とアプローチを用いて、永久分布のすべての瞬間に対して強い下界を証明した。
我々は、我々の限界が近いことを示し、その瞬間の正確な見積もりを構成する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computing the distribution of permanents of random matrices has been an
outstanding open problem for several decades. In quantum computing,
"anti-concentration" of this distribution is an unproven input for the proof of
hardness of the task of boson-sampling. We study permanents of random i.i.d.
complex Gaussian matrices, and more broadly, submatrices of random unitary
matrices. Using a hybrid representation-theoretic and combinatorial approach,
we prove strong lower bounds for all moments of the permanent distribution. We
provide substantial evidence that our bounds are close to being tight and
constitute accurate estimates for the moments. Let $U(d)^{k\times k}$ be the
distribution of $k\times k$ submatrices of $d\times d$ random unitary matrices,
and $G^{k\times k}$ be the distribution of $k\times k$ complex Gaussian
matrices. (1) Using the Schur-Weyl duality (or the Howe duality), we prove an
expansion formula for the $2t$-th moment of $|Perm(M)|$ when $M$ is drawn from
$U(d)^{k\times k}$ or $G^{k\times k}$. (2) We prove a surprising size-moment
duality: the $2t$-th moment of the permanent of random $k\times k$ matrices is
equal to the $2k$-th moment of the permanent of $t\times t$ matrices. (3) We
design an algorithm to exactly compute high moments of the permanent of small
matrices. (4) We prove lower bounds for arbitrary moments of permanents of
matrices drawn from $G^{ k\times k}$ or $U(k)$, and conjecture that our lower
bounds are close to saturation up to a small multiplicative error. (5) Assuming
our conjectures, we use the large deviation theory to compute the tail of the
distribution of log-permanent of Gaussian matrices for the first time. (6) We
argue that it is unlikely that the permanent distribution can be uniquely
determined from the integer moments and one may need to supplement the moment
calculations with extra assumptions to prove the anti-concentration conjecture.
- Abstract（参考訳）: ランダム行列の永久分布の計算は、数十年間、際立ったオープンな問題であった。
量子コンピューティングにおいて、この分布の「反集中」はボソンサンプリングのタスクの硬さを証明する未証明の入力である。
ランダムな複素ガウス行列およびより広義に、ランダムなユニタリ行列の部分行列の永続性について研究する。
ハイブリッド表現論的および組合せ的アプローチを用いて、永久分布のすべてのモーメントに対して強い下界を証明できる。
我々は、我々の境界が厳密に近く、その瞬間の正確な見積もりを構成するというかなりの証拠を提供する。
U(d)^{k\times k}$を$k\times k$submatrices of $d\times d$ random unitary matrices, and $G^{k\times k}$を$k\times k$ complex Gaussian matricesの分布とする。
1) シュル=ワイル双対性(あるいはハウ双対性)を用いて、$M$が$U(d)^{k\times k}$または$G^{k\times k}$から引かれるとき、$|Perm(M)|$の2t$-番目のモーメントの拡張公式を証明する。
ランダムな$k\times k$行列の永続の$t$-thモーメントは、$t\times t$行列の永続の$k$-thモーメントに等しい。
(3) 連続行列の高次モーメントを正確に計算するアルゴリズムを設計する。
(4) 行列の任意のモーメントに対する下限は、$g^{k\times k}$ または $u(k)$ から導かれることを証明し、我々の下限は小さな乗算誤差まで飽和に近いと推測する。
(5) 予想を仮定し, ガウス行列の対数永久分布のテールを初めて計算するために, 大偏差理論を用いる。
(6) 恒常分布が整数のモーメントから一意に決定できる可能性は低いし、反集中予想を証明するために余分な仮定でモーメント計算を補う必要があるかもしれない。
関連論文リスト
- Efficient Unitary T-designs from Random Sums [0.6640968473398456]
Unitary $T$-Designsは、量子アルゴリズム、ベンチマーク、トモグラフィ、通信における様々な応用において、量子情報において重要な役割を果たす。
我々は、$tildeO(T2 n2)$量子ゲートを用いたランダム行列理論による$T$-designsの新たな構成を提供する。
論文 参考訳（メタデータ） (2024-02-14T17:32:30Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex
Gaussian Perturbations [28.431572772564518]
この機構によって出力される行列と最高ランクの$k$の近似との差のフロベニウスノルムが、およそ$tildeO(sqrtkd)$で有界であることを示す。
これは、$M$のすべてのトップ-$k$固有値間のギャップが、同じ境界に対して少なくとも$sqrtd$であることを要求する以前の作業を改善する。
論文 参考訳（メタデータ） (2023-06-29T03:18:53Z) - A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。
後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
論文 参考訳（メタデータ） (2022-12-21T17:48:01Z) - Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson
Brownian Motion [28.431572772564518]
対称行列 $M$ とベクトル $lambda$ が与えられたとき、行列によって$M$ を近似するガウス機構のフロベニウス距離ユーティリティ上の新しい境界を示す。
私たちのバウンダリは、$lambda$と$M$の固有値のギャップの両方に依存します。
論文 参考訳（メタデータ） (2022-11-11T18:54:01Z) - An Equivalence Principle for the Spectrum of Random Inner-Product Kernel
Matrices with Polynomial Scalings [21.727073594338297]
この研究は、機械学習と統計学の応用によって動機付けられている。
スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。
我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
論文 参考訳（メタデータ） (2022-05-12T18:50:21Z) - 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) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Uniform Probability Distribution Over All Density Matrices [0.0]
確率測度 $u$ on $mathscrD$ を $mathscrD$ 上の一様分布と見なすことができる。
この測定値に従って分布するランダム密度行列の固有値の合同分布を計算する。
論文 参考訳（メタデータ） (2020-03-29T17:45:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。