Lower bounds for sparse recovery problems

Simple item page
dc.contributor.advisorPrice, Eric, Ph.D.
dc.contributor.committeeMemberGal, Anna
dc.contributor.committeeMemberPlaxton, Greg
dc.contributor.committeeMemberWoodruff, David
dc.creatorKamath, Akshay Devdas
dc.date.accessioned2021-06-10T16:48:33Z
dc.date.available2021-06-10T16:48:33Z
dc.date.created2020-08
dc.date.issued2020-08
dc.date.submittedAugust 2020
dc.date.updated2021-06-10T16:48:34Z
dc.description.abstractSparse recovery or compressed sensing is the problem of estimating a signal from noisy linear measurements of that signal. Sparse recovery has traditionally been used in areas like image acquisition, streaming algorithms, genetic testing, and, more recently, for image recovery tasks. Over the last decade many techniques have been developed for sparse recovery under various guarantees. We develop new lower bound techniques and show the tightness of existing results for the following variants of the sparse recovery problem: (i) adaptive sparse recovery, (ii) sparse recovery under high SNR, (iii) deterministic L2 heavy hitters, and, (iv) compressed sensing with generative models.
dc.description.departmentComputer Science
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2152/86422
dc.identifier.urihttp://dx.doi.org/10.26153/tsw/13373
dc.language.isoen
dc.subjectCompressed sensing
dc.subjectSparse recovery
dc.subjectSublinear algorithms
dc.titleLower bounds for sparse recovery problems
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentComputer Sciences
thesis.degree.disciplineComputer Science
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
KAMATH-DISSERTATION-2020.pdf
Size:
769.89 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UT Electronic Theses and Dissertations