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

DOI10.1088/1742-5468/2012/11/P11003MaRDI QIDQ3301299zbMATH OpenOpenAlexFDO

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

Publication date 11 August 2020

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

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

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

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.

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

Cites work

• Bayesian Compressive Sensing Via Belief Propagation
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• 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)