Polytope Samplers for Inference in Ill-Posed Inverse Problems

Abstract

We consider linear ill-posed inverse problems $y=Ax$, in which we want to infer many count parameters x from few count observations $y$, where the matrix $A$ is binary and has some unimodularity property. Such problems are typical in applications such as contingency table analysis and network tomography (on which we present testing results). These properties of $A$ have a geometrical implication for the solution space: It is a convex integer polytope. We develop a novel approach to characterize this polytope in terms of its vertices; by taking advantage of the geometrical intuitions behind the Hermite normal form decomposition of the matrix $A$, and of a newly defined pivoting operation to travel across vertices. Next, we use this characterization to develop three (exact) polytope samplers for $x$ with emphasis on uniform distributions. We showcase one of these samplers on simulated and real data.