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

Abstract

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.

17 pages, 6 figures

References in corpus (2)

• Identifying essential genes in E. coli from a metabolic optimization principle
• A scalable algorithm to explore the Gibbs energy landscape of genome-scale metabolic networks

Cited by in corpus (8)

• Statistical mechanics for metabolic networks during steady-state growth
• An analytic approximation of the feasible space of metabolic networks
• A Novel Methodology to Estimate Metabolic Flux Distributions in Constraint-Based Models
• Fast inference of ill-posed problems within a convex space
• Spin Glass Theory of Interacting Metabolic Networks
• Inferring propagation paths for sparsely observed perturbations on complex networks
• Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model
• The dual of the space of interactions in neural network models