No Arabic abstract
Arrow contraction applied to a tropical diagram of probability spaces is a modification of the diagram, replacing one of the morphisms by an isomorphims, while preserving other parts of the diagram. It is related to the rate regions introduced by Ahlswede and Korner. In a companion article we use arrow contraction to derive information about the shape of the entropic cone. Arrow expansion is the inverse operation to the arrow contraction.
After endowing the space of diagrams of probability spaces with an entropy distance, we study its large-scale geometry by identifying the asymptotic cone as a closed convex cone in a Banach space. We call this cone the tropical cone, and its elements tropical diagrams of probability spaces. Given that the tropical cone has a rich structure, while tropical diagrams are rather flexible objects, we expect the theory of tropical diagrams to be useful for information optimization problems in information theory and artificial intelligence. In a companion article, we give a first application to derive a statement about the entropic cone.
We define a natural operation of conditioning of tropical diagrams of probability spaces and show that it is Lipschitz continuous with respect to the asymptotic entropy distance.
In this paper we initiate the study of tropical Voronoi diagrams. We start out with investigating bisectors of finitely many points with respect to arbitrary polyhedral norms. For this more general scenario we show that bisectors of three points are homeomorphic to a non-empty open subset of Euclidean space, provided that certain degenerate cases are excluded. Specializing our results to tropical bisectors then yields structural results and algorithms for tropical Voronoi diagrams.
We consider a class of nonlinear mappings $mathsf{F}_{A,N}$ in $mathbb{R}^N$ indexed by symmetric random matrices $Ainmathbb{R}^{Ntimes N}$ with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations and were studied by Bolthausen [Comm. Math. Phys. 325 (2014) 333-366]. Within information theory, they are known as approximate message passing algorithms. We study the high-dimensional (large $N$) behavior of the iterates of $mathsf{F}$ for polynomial functions $mathsf{F}$, and prove that it is universal; that is, it depends only on the first two moments of the entries of $A$, under a sub-Gaussian tail condition. As an application, we prove the universality of a certain phase transition arising in polytope geometry and compressed sensing. This solves, for a broad class of random projections, a conjecture by David Donoho and Jared Tanner.
In this paper we revisit the results of Loynes (1962) on stability of queues for ergodic arrivals and services, and show examples when the arrivals are bounded and ergodic, the service rate is constant, and under stability the limit distribution has larger than exponential tail.