Show simple item record

dc.contributor.authorCousins, Benjamin
dc.date.accessioned2017-08-17T18:59:31Z
dc.date.available2017-08-17T18:59:31Z
dc.date.created2017-08
dc.date.issued2017-05-31
dc.date.submittedAugust 2017
dc.identifier.urihttp://hdl.handle.net/1853/58671
dc.description.abstractVolume computation is an algorithmic version of the fundamental geometric problem to figure out how much space an object occupies. Related problems of sampling and integration have numerous applications to other fields, thus it is key to develop efficient algorithmic solutions to these problems. This thesis pushes the computational frontier of volume computation, randomized sampling, and integration, both in theory and practice. The search for efficient algorithms for volume computation has been an active area of research over the last few decades. Many geometric problems suffer from computational inefficiency in high-dimensions: the so-called \emph{curse of dimensionality}, where the problem efficiency grows exponentially with the dimension. For volume computation, Dyer, Frieze, and Kannan gave a polynomial time randomized algorithm to approximate the volume of any convex body. While their algorithm complexity was prohibitively high, the fundamental ideas inspired further improvements. Building upon the tools and ideas developed in this line of work, we obtain an $O*(n^3) algorithm to approximate the volume of well-rounded convex bodies. As a crucial tool to our faster volume algorithm, we obtain a faster algorithm for sampling a Gaussian distribution restricted by a convex set. We also generalize the Gaussian sampling restricted by a logconcave function. The Gaussian sampling algorithm additionally yields a faster algorithm for generating a uniform random sample from a convex body. The ideas for the O*(n^3) volume algorithm also lead to an efficient algorithm in practice. While the theoretical developments were inspiring, there was still no satisfying real-world implementation of the algorithm. We implement a variant of our algorithm in MATLAB, which can estimate volume in hundreds of dimensions with relative ease. The implementation allows for volume estimations which were previously far out of the realm of computational feasibility. In collaboration with systems biologists, we additionally explore a direct application of the sampling and volume implementations to the analysis of metabolic networks.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectSampling
dc.subjectVolume computation
dc.subjectRandomized algorithms
dc.subjectMarkov chains
dc.subjectIsoperimetry
dc.titleEfficient high-dimensional sampling and integration
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputer Science
thesis.degree.levelDoctoral
dc.contributor.committeeMemberVempala, Santosh
dc.contributor.committeeMemberDieker, A. B.
dc.contributor.committeeMemberRandall, Dana
dc.contributor.committeeMemberTetali, Prasad
dc.contributor.committeeMemberVigoda, Eric
dc.date.updated2017-08-17T18:59:31Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record