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

Simple item page
dc.confidentialEmbargo : Noen_US
dc.contributor.advisorvan Brunt, Bruce
dc.contributor.authorMcVeagh, Michael
dc.date.accessioned2022-01-09T19:31:39Z
dc.date.accessioned2022-05-10T23:55:00Z
dc.date.available2022-01-09T19:31:39Z
dc.date.available2022-05-10T23:55:00Z
dc.date.issued2021
dc.descriptionListed in 2022 Dean's List of Exceptional Thesesen
dc.description.abstractIn 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.en_US
dc.identifier.urihttp://hdl.handle.net/10179/17095
dc.publisherMassey Universityen_US
dc.rightsThe Authoren_US
dc.subjectDean's List of Exceptional Thesesen
dc.subjectMarkov processesen
dc.subjectLattice theoryen
dc.subjectMatricesen
dc.subject.anzsrc490407 Mathematical logic, set theory, lattices and universal algebraen
dc.titleEfficient 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 Zealanden_US
dc.typeThesisen_US
massey.contributor.authorMcVeagh, Michaelen_US
thesis.degree.disciplineMathematicsen_US
thesis.degree.grantorMassey Universityen_US
thesis.degree.levelDoctoralen_US
thesis.degree.nameDoctor of Philosophy (PhD)en_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
McVeaghPhDThesis.pdf
Size:
1.07 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Theses and Dissertations