Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2212.10672 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929242539819008 |
|---|---|
| author | Mukerji, Tantrik Yang, Wei-Shih |
| author_facet | Mukerji, Tantrik Yang, Wei-Shih |
| contents | 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 $ε\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_10672 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Additive estimates of the permanent using Gaussian fields Mukerji, Tantrik Yang, Wei-Shih Probability Data Structures and Algorithms Combinatorics Quantum Physics 15A15, 60G15, 68W20 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 $ε\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. |
| title | Additive estimates of the permanent using Gaussian fields |
| topic | Probability Data Structures and Algorithms Combinatorics Quantum Physics 15A15, 60G15, 68W20 |
| url | https://arxiv.org/abs/2212.10672 |