2020/04/15 by Jonathan R. Leake, Leake, Jonathan, Nisheeth K. Vishnoi +1
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Mechanics and Entropy #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2004.07403
openalex publication_date 2020/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate a study of the following problem: Given a continuous domain\n\Ω along with its convex hull \K, a point A \∈ \K\nand a prior measure \μ on \Ω, find the probability density over\n\Ω whose marginal is A and that minimizes the KL-divergence to \μ.\nThis framework gives rise to several extremal distributions that arise in\nmathematics, quantum mechanics, statistics, and theoretical computer science.\nOur technical contributions include a polynomial bound on the norm of the\noptimizer of the dual problem that holds in a very general setting and relies\non a "balance" property of the measure \μ on \Ω, and exact algorithms\nfor evaluating the dual and its gradient for several interesting settings of\n\Ω and \μ. Together, along with the ellipsoid method, these results\nimply polynomial-time algorithms to compute such KL-divergence minimizing\ndistributions in several cases. Applications of our results include: 1) an\noptimization characterization of the Goemans-Williamson measure that is used to\nround a positive semidefinite matrix to a vector, 2) the computability of the\nentropic barrier for polytopes studied by Bubeck and Eldan, and 3) a\npolynomial-time algorithm to compute the barycentric quantum entropy of a\ndensity matrix that was proposed as an alternative to von Neumann entropy in\nthe 1970s: this corresponds to the case when \Ω is the set of rank one\nprojections matrices and \μ corresponds to the Haar measure on the unit\nsphere. Our techniques generalize to the setting of Hermitian rank k\nprojections using the Harish-Chandra-Itzykson-Zuber formula, and are applicable\neven beyond, to adjoint orbits of compact Lie groups.\n