Fugu-MT 論文翻訳(概要): Additive estimates of the permanent using Gaussian fields

論文の概要: Additive estimates of the permanent using Gaussian fields

arxiv url: http://arxiv.org/abs/2212.10672v2
Date: Tue, 13 Feb 2024 19:28:13 GMT
ステータス: 処理完了
システム内更新日: 2024-02-15 20:24:03.939192
Title: Additive estimates of the permanent using Gaussian fields
Title（参考訳）: ガウス場を用いた永久数の加法的推定
Authors: Tantrik Mukerji and Wei-Shih Yang
Abstract要約: 本稿では,M$M$実行列$A$から加法誤差までの永久性を推定するランダム化アルゴリズムを提案する。我々は$mathrmperm(A)$を$epsilonbigg(sqrt32Mprod2M_i=1 C_iibigg)$の加算誤差に時間内に見積もることができる。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present a randomized algorithm for estimating the permanent of an $M \times M$ real matrix $A$ up to an additive error. We do this by viewing the permanent $\mathrm{perm}(A)$ of $A$ as the expectation of a product of centered joint Gaussian random variables with a particular covariance matrix $C$. The algorithm outputs the empirical mean $S_{N}$ of this product after sampling $N$ times. Our algorithm runs in total time $O(M^{3} + M^{2}N + MN)$ with failure probability \begin{equation*} P(|S_{N}-\text{perm}(A)| > t) \leq \frac{3^{M}}{t^{2}N} \prod^{2M}_{i=1} C_{ii}. \end{equation*} In particular, we can estimate $\mathrm{perm}(A)$ to an additive error of $\epsilon\bigg(\sqrt{3^{2M}\prod^{2M}_{i=1} C_{ii}}\bigg)$ in polynomial time. We compare to a previous procedure due to Gurvits. We discuss how to find a particular $C$ using a semidefinite program and a relation to the Max-Cut problem and cut-norms.
Abstract（参考訳）: 我々は,$m \times m$ real matrix $a$ の永続性を加算誤差まで推定するランダム化アルゴリズムを提案する。これを、特定の共分散行列 $c$ を持つ中央結合ガウス確率変数の積の期待として、永続的な $\mathrm{perm}(a)$ of $a$ を見て行う。このアルゴリズムは、この製品の経験的な平均$s_{n}$を、n$をサンプリングした後出力する。我々のアルゴリズムは総時間$O(M^{3} + M^{2}N + MN)$で、失敗確率 \begin{equation*} P(|S_{N}-\text{perm}(A)| > t) \leq \frac{3^{M}}{t^{2}N} \prod^{2M}_{i=1} C_{ii} で実行される。特に、$\mathrm{perm}(A)$を$\epsilon\bigg(\sqrt{3^{2M}\prod^{2M}_{i=1} C_{ii}}\bigg)$の加法誤差に多項式時間で推定することができる。我々は、Gurvitsによる以前の手順と比較する。半定値プログラムを用いて特定の$C$を見つける方法と、Max-Cut問題とカットノルムとの関係について論じる。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文参考訳（メタデータ） (2024-08-16T02:33:07Z)
Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文参考訳（メタデータ） (2024-02-22T02:20:24Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
Matrix Completion in Almost-Verification Time [37.61139884826181]
99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
論文参考訳（メタデータ） (2023-08-07T15:24:49Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Classical shadows of fermions with particle number symmetry [0.0]
我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
論文参考訳（メタデータ） (2022-08-18T17:11:12Z)
Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文参考訳（メタデータ） (2021-11-28T14:08:25Z)
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)
Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文参考訳（メタデータ） (2021-05-31T14:41:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。