A weighted belief-propagation algorithm to estimate volume-related properties of random polytopes
arXiv:1208.1295 · doi:10.1088/1742-5468/2012/11/P11003
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.
arXiv comment17 pages, 6 figures
References in corpus (5)
- Global organization of metabolic fluxes in the bacterium, Escherichia coli
- Statistical physics-based reconstruction in compressed sensing
- 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
- The solution space of metabolic networks: producibility, robustness and fluctuations
Cited by in corpus (9)
- 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
- Spin Glass Theory of Interacting Metabolic Networks
- Fast inference of ill-posed problems within a convex space
- Inferring propagation paths for sparsely observed perturbations on complex networks
- Replica theory for learning curves for Gaussian processes on random graphs
- 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