BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Ivan Stanojević appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
This paper deals with transportation polytopes in the probability simplex (that is, sets of categorical bivariate probability distributions with prescribed marginals). Information projections between such polytopes are studied, and a sufficient condition is described under which these mappings are homeomorphisms.
In this paper, some general properties of Shannon information measures are investigated over sets of probability distributions with restricted marginals. Certain optimization problems associated with these functionals are shown to be NP-hard, and their special cases are found to be essentially information-theoretic restatements of well-known computational problems, such as the SUBSET SUM and the 3-PARTITION. The notion of minimum entropy coupling is introduced and its relevance is demonstrated in information-theoretic, computational, and statistical contexts. Finally, a family of pseudometrics (on the space of discrete probability distributions) defined by these couplings is studied, in particular their relation to the total variation distance, and a new characterization of the conditional entropy is given.
In this paper we study certain properties of Rényi entropy functionals $H_α(\mathcal{P})$ on the space of probability distributions over $\mathbb{Z}_+$. Primarily, continuity and convergence issues are addressed. Some properties shown parallel those known in the finite alphabet case, while others illustrate a quite different behaviour of Rényi entropy in the infinite case. In particular, it is shown that, for any distribution $\mathcal P$ and any $r\in[0,\infty]$, there exists a sequence of distributions $\mathcal{P}_n$ converging to $\mathcal{P}$ with respect to the total variation distance, such that $\lim_{n\to\infty}\lim_{α\to{1+}} H_α(\mathcal{P}_n) = \lim_{α\to{1+}}\lim_{n\to\infty} H_α(\mathcal{P}_n) + r$.
We investigate certain optimization problems for Shannon information measures, namely, minimization of joint and conditional entropies $H(X,Y)$, $H(X|Y)$, $H(Y|X)$, and maximization of mutual information $I(X;Y)$, over convex regions. When restricted to the so-called transportation polytopes (sets of distributions with fixed marginals), very simple proofs of NP-hardness are obtained for these problems because in that case they are all equivalent, and their connection to the well-known \textsc{Subset sum} and \textsc{Partition} problems is revealed. The computational intractability of the more general problems over arbitrary polytopes is then a simple consequence. Further, a simple class of polytopes is shown over which the above problems are not equivalent and their complexity differs sharply, namely, minimization of $H(X,Y)$ and $H(Y|X)$ is trivial, while minimization of $H(X|Y)$ and maximization of $I(X;Y)$ are strongly NP-hard problems. Finally, two new (pseudo)metrics on the space of discrete probability distributions are introduced, based on the so-called variation of information quantity, and NP-hardness of their computation is shown.