Timeline for Smallest $\mathrm{D}(Q\|P)$ given fixed marginals $\mathrm{D}(Q_X\|P_X)$ and $\mathrm{D}(Q_Y\|P_Y)$
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 10, 2020 at 9:22 | comment | added | Thomas Dybdahl Ahle | At this point I would be excited for just computability. Even an exponential time algorithm for the case where $P$ has finite support. | |
| Dec 10, 2020 at 9:18 | vote | accept | Thomas Dybdahl Ahle | ||
| Dec 9, 2020 at 18:10 | comment | added | Tom | to add to above, this equivalence does not actually make your problem any easier. It just converts from an entropy problem to an equivalent functional one. Except in special cases (e.g., where $P$ is product of rho-correlated Gaussians or Rademachers), a characterization of the extremizers is likely non-explicit. However, if $P$ is a product measure, you can use tensorization of Brascamp--Lieb inequalities (and their entropic equivalents) to conclude that the extremizers will also have product structure. You should also be able to see this directly. | |
| Dec 9, 2020 at 17:46 | comment | added | Tom | Regarding your first comment on hypercontractivity, you are mostly correct. This equivalence holds in a general sense. $P$ being $(1/a,1/b)$-hypercontractive is equivalent to the infimum of $𝐷(𝑄||𝑃)−𝑎𝐷(𝑄1||𝑃1)−𝑏𝐷(𝑄2||𝑃2)$ over all $Q$ being zero. More generally, the infimum of this problem will be nonzero, which by duality then corresponds to something like hypercontractivity, but with a prefactor in the norm inequality. See, e.g., page 22 here: arxiv.org/pdf/1702.06260.pdf, and references therein (in particular, Carlen and Cordero-Erausquin, 2009). | |
| Dec 9, 2020 at 14:48 | comment | added | Thomas Dybdahl Ahle | Or maybe minimizing $\frac{D(Q\|P)}{a D(Q_1\|P_1)+b D(Q_2\|P_2)}$ actually, over all $Q$, so the scaling doesn't matter. | |
| Dec 9, 2020 at 13:36 | comment | added | Thomas Dybdahl Ahle | Even if there is no simple form, at least it's a tractable convex optimization problem. Minimizing $D(Q\|P)-a D(Q_1\|P_1)-b D(Q_2\|P_2)$ I think is equivalent to finding the hypercontractive norm of a positive matrix, by Lemma 1.1 in thomasahle.com/papers/supermajority.pdf . But that problem appears to possibly be NP hard, though there is no proof afaik. | |
| Dec 9, 2020 at 5:45 | history | answered | Tom | CC BY-SA 4.0 |