Hit and Run Sampling from Tropically Convex Sets

DOI10.48550/ARXIV.2209.15045MaRDI QIDQ5978962zbMATH OpenFDO

Authors Ruriko Yoshida, David Barnhill, Ruriko Yoshida, Keiji Miura, David Barnhill

Publication date 29 September 2022

Published in Algebraic Statistics (Search for Journal in Brave)

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

zbMATH Keywords

hit and run samplingMarkov chain Monte Carlotropical convexitytropical geometry

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Statistical sampling theory and related topics (62D99) Statistics on algebraic and topological structures (62Rxx)

Abstract: In this paper we propose Hit and Run (HAR) sampling from a tropically convex set. The key ingredient of HAR sampling from a tropically convex set is sampling uniformly from a tropical line segment over the tropical projective torus, which runs linearly in its computational time complexity. We show that this HAR sampling method samples uniformly from a tropical polytope which is the smallest tropical convex set of finitely many vertices. Finally, we apply this novel method to any given distribution using Metropolis-Hasting filtering over a tropical polytope.

Cites work

• A note on the metric properties of trees
• A practical volume algorithm
• Analysis of phylogenetics and evolution with R
• Approximating the volume of tropical polytopes is difficult
• Convergence properties of hit–and–run samplers
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Essentials of Tropical Combinatorics
• Fast MCMC sampling algorithms on polytopes
• Hit-and-Run from a Corner
• Hit-and-run mixes fast
• Multivariate volume, Ehrhart, and \(h^\ast \)-polynomials of polytropes
• On the Computation of Multidimensional Integrals by the Monte-Carlo Method
• polymake: a framework for analyzing convex polytopes
• The Bergman complex of a matroid and phylogenetic trees
• Tropical and ordinary convexity combined
• Tropical convexity
• Tropical Ehrhart theory and tropical volume

Cited in

(4)

• TML
• Maximum inscribed and minimum enclosing tropical balls of tropical polytopes and applications to volume estimation and uniform sampling
• Tropical geometric tools for machine learning: the TML package
• Probability metrics for tropical spaces of different dimensions

This page was built for publication: Hit and Run Sampling from Tropically Convex Sets

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