# On the computability of continuous maximum entropy distributions with applications

arXiv: https://arxiv.org/abs/2004.07403 · HTML: https://mlsanity.com/paper/2004.07403/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

## Built on by (most cited first, 2 of 2)

- [Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion](https://mlsanity.com/paper/2211.06418/) (2022)
- [Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory](https://mlsanity.com/paper/2109.01080/) (2021)

## Abstract (arXiv)

We initiate a study of the following problem: Given a continuous domain Omega along with its convex hull K, a point A ∈ K and a prior measure μ on Omega, find the probability density over Omega 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 Omega, and exact algorithms for evaluating the dual and its gradient for several interesting settings of Omega 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 Omega 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.