English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we consider the problem of computing the likelihood of theprofile of a discrete distribution, i.e., the probability of observing themultiset of element frequencies, and computing a profile maximum likelihood(PML) distribution, i.e., a distribution with the maximum profile likelihood.For each problem we provide polynomial time algorithms that given $n$ i.i.d.\samples from a discrete distribution, achieve an approximation factor of$\exp\left(-O(\sqrt{n} \log n) \right)$, improving upon the previous best-knownbound achievable in polynomial time of $\exp(-O(n^{2/3} \log n))$ (Charikar,Shiragur and Sidford, 2019). Through the work of Acharya, Das, Orlitsky andSuresh (2016), this implies a polynomial time universal estimator for symmetricproperties of discrete distributions in a broader range of error parameter.  We achieve these results by providing new bounds on the quality ofapproximation of the Bethe and Sinkhorn permanents (Vontobel, 2012 and 2014).We show that each of these are $\exp(O(k \log(N/k)))$ approximations to thepermanent of $N \times N$ matrices with non-negative rank at most $k$,improving upon the previous known bounds of $\exp(O(N))$. To obtain our resultson PML, we exploit the fact that the PML objective is proportional to thepermanent of a certain Vandermonde matrix with $\sqrt{n}$ distinct columns,i.e. with non-negative rank at most $\sqrt{n}$. As a by-product of our work weestablish a surprising connection between the convex relaxation in prior work(CSS19) and the well-studied Bethe and Sinkhorn approximations.

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood