論文の概要: A polynomial time additive estimate of the permanent using Gaussian
fields
- arxiv url: http://arxiv.org/abs/2212.10672v1
- Date: Tue, 20 Dec 2022 22:13:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 13:39:10.213982
- Title: A polynomial time additive estimate of the permanent using Gaussian
fields
- Title（参考訳）: ガウス場を用いた永久数の多項式時間加法推定
- Authors: Tantrik Mukerji and Wei-Shih Yang
- Abstract要約: 任意の$M×M$実行列$A$から加法誤差までの永久性を推定するためのa-timeランダム化アルゴリズムを提案する。
我々はこのことを、中心となる合同ガウス確率変数の積の期待値として$A$の恒久的な値を見ることによって行う。
- 参考スコア（独自算出の注目度）: 0.2538209532048866
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a polynomial-time randomized algorithm for estimating the
permanent of an arbitrary $M \times M$ real matrix $A$ up to an additive error.
We do this by viewing the permanent of $A$ as the expectation of a product of a
centered joint Gaussian random variables whose covariance matrix we call the
Gaussian embedding of $A$. The algorithm outputs the empirical mean $S_{N}$ of
this product after sampling from this multivariate distribution $N$ times. In
particular, after sampling $N$ samples, our algorithm runs in time $O(MN)$ with
failure probability \begin{equation*}
P(|S_{N}-\text{perm}(A)| > t) \leq \frac{3^{M}}{t^{2}N}\alpha^{2M}
\end{equation*} for $\alpha \geq \|A \|$.
- Abstract（参考訳）: 任意の$M \times M$ real matrix $A$ の永久性を加算誤差まで推定する多項式時間ランダム化アルゴリズムを提案する。
a$ の永続性は、中心となるジョイント・ガウス確率変数の積の期待値と見なすことにより、我々はこれを実現し、その共分散行列を「a$ のガウス埋め込み」と呼ぶ。
このアルゴリズムは、この多変量分布からサンプリングした後、この製品の経験的な平均$s_{n}$を出力する。
特に、$N$サンプルをサンプリングした後、我々のアルゴリズムは失敗確率 \begin{equation*} P(|S_{N}-\text{perm}(A)| > t) \leq \frac{3^{M}}{t^{2}N}\alpha^{2M} \end{equation*} for $\alpha \geq \|A \|$ で実行されます。
関連論文リスト
- Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time [2.311583680973075]
我々はフロベニウスノルムで次元非依存誤差を実現する時間アルゴリズムを設計する。
散乱行列 $Sigma$, for every $t in mathbbN$, we design an estimator that, given $n = dO(t)$ sample, in time $nO(t)$ finds $hatSigma。
論文 参考訳（メタデータ） (2025-02-10T15:31:57Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。