Sparse recovery and Fourier sampling
Name
870968793-MIT.pdf
Description
Full printable version
Size
13.14 MB
Format
Adobe PDF
Checksum (MD5)
3b9191743605ecef49f2e9612c910f32
Author(s)
Price, Eric C
Advisor(s)
Piotr Indyk.
Date Issued
2013
Publisher
Massachusetts Institute of Technology
Abstract
In the last decade a broad literature has arisen studying sparse recovery, the estimation of sparse vectors from low dimensional linear projections. Sparse recovery has a wide variety of applications such as streaming algorithms, image acquisition, and disease testing. A particularly important subclass of sparse recovery is the sparse Fourier transform, which considers the computation of a discrete Fourier transform when the output is sparse. Applications of the sparse Fourier transform include medical imaging, spectrum sensing, and purely computation tasks involving convolution. This thesis describes a coherent set of techniques that achieve optimal or near-optimal upper and lower bounds for a variety of sparse recovery problems. We give the following state-of-the-art algorithms for recovery of an approximately k-sparse vector in n dimensions: -- Two sparse Fourier transform algorithms, respectively taking ... time and ... samples. The latter is within log e log n of the optimal sample complexity when ... -- An algorithm for adaptive sparse recovery using ... measurements, showing that adaptivity can give substantial improvements when k is small. -- An algorithm for C-approximate sparse recovery with ... measurements, which matches our lower bound up to the log* k factor and gives the first improvement for ... In the second part of this thesis, we give lower bounds for the above problems and more.
Description
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 155-160).
Subjects
Electrical Engineering and Computer Science.
MIT Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Terms of Use
M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.
Persistent DSpace Link
