A weighted belief-propagation algorithm for estimating volume-related properties of random polytopes

DOI10.1088/1742-5468/2012/11/P11003zbMATH Open1459.60021arXiv1208.1295OpenAlexW3123040513MaRDI QIDQ3301299FDOQ3301299

Isaac Pérez Castillo, Francesco Alessandro Massucci, Francesc Font-Clos

Publication date: 11 August 2020

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1208.1295

Recommendations

• Efficient random-walk methods for approximating polytope volume
• Expectation of intrinsic volumes of random polytopes
• Random volumes in \(d\)-dimensional polytopes
• A note on volume thresholds for random polytopes
• scientific article; zbMATH DE number 17638
• A random polynomial-time algorithm for approximating the volume of convex bodies
• scientific article; zbMATH DE number 3917135
• Volumes of symmetric random polytopes
• Volume thresholds for Gaussian and spherical random polytopes and their duals
• Intrinsic volumes and f-vectors of random polytopes

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

Cites Work

• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Bayesian Compressive Sensing Via Belief Propagation
• Hit-and-run algorithms for the identification of nonredundant linear inequalities
• Typical properties of optimal growth in the Von Neumann expanding model for large random economies
• Von Neumann’s expanding model on random graphs

Cited In (1)

• Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model

This page was built for publication: A weighted belief-propagation algorithm for estimating volume-related properties of random polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301299)