Wednesday, August 8, 2012

1208.1295 (Francesc Font-Clos et al.)

A weighted belief-propagation algorithm to estimate volume-related
properties of random polytopes
   [PDF]

Francesc Font-Clos, Francesco Alessandro Massucci, Isaac Pérez Castillo
In this work we introduce a novel weighted message-passing algorithm based on the cavity method to estimate volume-related properties of random polytopes, properties which are relevant in various research fields ranging from metabolic networks, to neural networks, to compressed sensing. Unlike the usual approach consisting in approximating the real-valued cavity marginal distributions by a few parameters, we propose an algorithm to faithfully represent the entire marginal distribution. We explain various alternatives to implement the algorithm and benchmark the theoretical findings by showing concrete applications to random polytopes. The results obtained with our approach are found to be in very good agreement with the estimates produced by the Hit-and-Run algorithm, known to produce uniform sampling.
View original: http://arxiv.org/abs/1208.1295

No comments:

Post a Comment