论文标题
关于连续最大熵分布的可计算性
On the computability of continuous maximum entropy distributions with applications
论文作者
论文摘要
我们启动了以下问题的研究：给定连续域$ω$及其凸壳$ \ Mathcal {k} $，一个$ a \ in \ nathcal {k} $和$ω$上的$μ$ in Point $ a \ in Mathcal {k} $，请在$ω$上找到$ a $ $ a $ a $ a $ a kl-ymim y mim y mim y kl-yim y mim y mim y mim，该框架产生了数学，量子力学，统计和理论计算机科学中出现的几种极端分布。我们的技术贡献包括对双重问题优化器的规范的多项式限制，该偶数在非常通用的环境中依赖于$ω$上的度量$ $ $ $ $ $ $的“平衡”属性，以及评估双重算法的精确算法，用于评估$ω$和$ω$和$ $ $的几个有趣的设置。这些结果一起，与椭圆形方法一起，暗示了多项式时间算法来计算这种KL差异最小化分布在几种情况下。我们的结果的应用包括：1）用于将阳性半芬特矩阵圆形的Goemans-Williamson度量的优化表征，2）Bubeck和Eldan研究的多元型熵屏障的可计算性，以及3）多项量的替代量子，以便在多种量化的量化量中，以供应量子量的替代性量子，该量子的含量是替代的，该量子是偶然的。 1970年代的熵：这对应于$ω$是排名一组的矩阵和$μ$的情况，与单位球体上的HAAR度量相对应。我们的技术概括了使用Harish-Chandra-Itzykson-Zuber公式的Hermitian等级$ K $投影的设置，甚至适用于紧凑型Lie Groups的邻居轨道。
We initiate a study of the following problem: Given a continuous domain $Ω$ along with its convex hull $\mathcal{K}$, a point $A \in \mathcal{K}$ and a prior measure $μ$ on $Ω$, find the probability density over $Ω$ whose marginal is $A$ and that minimizes the KL-divergence to $μ$. This framework gives rise to several extremal distributions that arise in mathematics, quantum mechanics, statistics, and theoretical computer science. Our technical contributions include a polynomial bound on the norm of the optimizer of the dual problem that holds in a very general setting and relies on a "balance" property of the measure $μ$ on $Ω$, and exact algorithms for evaluating the dual and its gradient for several interesting settings of $Ω$ and $μ$. Together, along with the ellipsoid method, these results imply polynomial-time algorithms to compute such KL-divergence minimizing distributions in several cases. Applications of our results include: 1) an optimization characterization of the Goemans-Williamson measure that is used to round a positive semidefinite matrix to a vector, 2) the computability of the entropic barrier for polytopes studied by Bubeck and Eldan, and 3) a polynomial-time algorithm to compute the barycentric quantum entropy of a density matrix that was proposed as an alternative to von Neumann entropy in the 1970s: this corresponds to the case when $Ω$ is the set of rank one projections matrices and $μ$ corresponds to the Haar measure on the unit sphere. Our techniques generalize to the setting of Hermitian rank $k$ projections using the Harish-Chandra-Itzykson-Zuber formula, and are applicable even beyond, to adjoint orbits of compact Lie groups.
