Polytope samplers for inference in ill-posed inverse problems


Edoardo Airoldi, Bertrand Haas ;
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:110-118, 2011.


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. [pdf][supplementary]

Related Material