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.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-airoldi11a, title = {Polytope samplers for inference in ill-posed inverse problems}, author = {Airoldi, Edoardo and Haas, Bertrand}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {110--118}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/airoldi11a/airoldi11a.pdf}, url = {https://proceedings.mlr.press/v15/airoldi11a.html}, 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.} }
Endnote
%0 Conference Paper %T Polytope samplers for inference in ill-posed inverse problems %A Edoardo Airoldi %A Bertrand Haas %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-airoldi11a %I PMLR %P 110--118 %U https://proceedings.mlr.press/v15/airoldi11a.html %V 15 %X 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.
RIS
TY - CPAPER TI - Polytope samplers for inference in ill-posed inverse problems AU - Edoardo Airoldi AU - Bertrand Haas BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-airoldi11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 110 EP - 118 L1 - http://proceedings.mlr.press/v15/airoldi11a/airoldi11a.pdf UR - https://proceedings.mlr.press/v15/airoldi11a.html AB - 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. ER -
APA
Airoldi, E. & Haas, B.. (2011). Polytope samplers for inference in ill-posed inverse problems. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:110-118 Available from https://proceedings.mlr.press/v15/airoldi11a.html.

Related Material