Show simple item record

dc.contributor.advisorWard, Rachel A.
dc.creatorKennedy, Christopher Garrett
dc.date.accessioned2019-02-07T19:10:27Z
dc.date.available2019-02-07T19:10:27Z
dc.date.created2018-12
dc.date.issued2018-12-06
dc.date.submittedDecember 2018
dc.identifierdoi:10.15781/T23F4M83G
dc.identifier.urihttp://hdl.handle.net/2152/72842
dc.description.abstractIn the big data era, dimension reduction techniques have been a key tool in making high dimensional geometric problems tractable. This thesis focuses on two such problems - hashing and parameter estimation. We study locality sensitive hashing(LSH), which is a framework for randomized hashing that efficiently solves an approximate version of nearest neighbor search. We propose an efficient and provably optimal hash function for LSH that builds on a simple existing hash function called cross-polytope LSH. In the context of parameter estimation, we focus on regression, for which the well-known LASSO requires precise knowledge of the unknown noise variance. We provide an estimator for this noise variance when the signal is sparse that is consistent and faster than a single iteration of LASSO. Finally, we discuss notions of distance between probability distributions for the purposes of quantization and propose a distance metric called the Rényi divergence, that achieves both large and small scale bounds.
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.subjectData structures and algorithms
dc.subjectComputational geometry
dc.subjectStatistics theory
dc.subjectInformation theory
dc.titleFast high dimensional approximation via random embeddings
dc.typeThesis
dc.date.updated2019-02-07T19:10:28Z
dc.contributor.committeeMemberBaccelli, Francois
dc.contributor.committeeMemberBlumberg, Andrew
dc.contributor.committeeMemberPrice, Eric
dc.description.departmentMathematics
thesis.degree.departmentMathematics
thesis.degree.disciplineMathematics
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy
dc.type.materialtext


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record