Efficient Markov bases for Z-polytope sampling : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics at Massey University, Manawatū, New Zealand
Loading...
Date
2021
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
Abstract
In this thesis we study the use of lattice bases for fibre sampling, with particular attention paid to applications in volume network tomography. We use a geometric interpretation of the fibre as a Z-polytope to provide insight into the connectivity properties
of lattice bases.
Fibre sampling is used when we are interested in fitting a statistical model to a random process that may only be observed indirectly via the underdetermined linear system y = Ax. We consider the observed data y and random variable of interest x to contain count data. The likelihood function for such models requires a summation over the fibre Fy, the set of all non-negative integer vectors x satisfying this equation for some particular y. This can be computationally infeasible when Fy is large.
One approach to addressing this problem involves sampling from Fy using a Markov Chain Monte Carlo algorithm, which amounts to taking a random walk through Fy . This is facilitated by a Markov basis: a set of moves that can be used construct such a walk,
which is therefore a subset of the kernel of the configuration matrix A.
Algebraic algorithms for finding Markov bases based on the theory of Gröbner bases are available, but these can fail when the configuration matrix is large and the calculations become computationally infeasible. Instead, we propose constructing a sampler based on a type of lattice basis we call a column partition lattice basis, defined by a matrix U. Constructing such a basis is computationally much cheaper than constructing a Gröbner basis.
It is known that lattice bases are not necessarily Markov bases. We give a condition on the matrix U that guarantees that it is a Markov basis, and show for a certain class of configuration matrices how a U matrix that is a Markov basis can be constructed.
Construction of lattice bases that are Markov bases is facilitated when the configuration matrix is unimodular, or has unimodular partitions. We consider configuration matrices from volume network tomography, and give classes of traffic network that have
configuration matrices with these desirable properties.
If a Markov basis cannot be found, one alternative is to sample from some larger set that includes Fy . We give some larger sets that can be used, subject to certain conditions.
Description
Listed in 2022 Dean's List of Exceptional Theses
Keywords
Dean's List of Exceptional Theses, Markov processes, Lattice theory, Matrices