MARKOV CHAIN MONTE CARLO SAMPLING OF TROPICALLY CONVEX SETS
Loading...
Authors
Barnhill, David
Subjects
Markov chain Monte Carlo
MCMC
tropical geometry
non-convex sets
MCMC
tropical geometry
non-convex sets
Advisors
Koyak, Robert A.
Carlyle, W. Matthew
Lin, Kyle Y.
Gera, Ralucca
Yoshida, Ruriko
Date of Issue
2024-03
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
Abstract
This dissertation examines the application of Markov chain Monte Carlo (MCMC) Hit-and-Run (HAR) samplers over tropically convex sets. In many scientific fields, we observe data over a projective space characterized in terms of tropical geometry, which is a piecewise-linear analogue of Euclidean geometry. In such a space, tropical convexity, an analogue of classical convexity in Euclidean spaces, plays an important role in analyzing data. Since tropical geometry is a relatively new field, few computational tools exist to analyze data represented in this projective space. In Euclidean space, MCMC HAR samplers are essential tools used for solving complex problems when analytical solutions are unattainable. In this research, we introduce a novel MCMC HAR sampler for use over tropically convex sets, defined as classically convex tropical polytopes, that samples points according to symmetric target distributions in terms of the tropical metric. We illustrate how, using this tropical MCMC HAR sampler, we can approach the NP-hard problem of estimating the volume of tropical polytopes by constructing and then sampling from a minimum enclosing tropical ball. We then apply tropical MCMC HAR methods to kernel density estimation over the tropically convex space of equidistant phylogenetic trees defined as ultrametrics. Experiments show that this tropical kernel density estimation method outperforms existing density estimation methods in terms of accuracy and computational time.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Distribution Statement A. Approved for public release: Distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.