Sparse recovery and Fourier sampling
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/85458 |
| _version_ | 1811082660800364544 |
|---|---|
| author | Price, Eric C |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Price, Eric C |
| author_sort | Price, Eric C |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T12:06:38Z |
| format | Thesis |
| id | mit-1721.1/85458 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:06:38Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/854582019-04-11T11:35:05Z Sparse recovery and Fourier sampling Price, Eric C Piotr Indyk. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. 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). 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. by Eric Price. Ph. D. 2014-03-06T15:43:25Z 2014-03-06T15:43:25Z 2013 2013 Thesis http://hdl.handle.net/1721.1/85458 870968793 eng 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. http://dspace.mit.edu/handle/1721.1/7582 160 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Price, Eric C Sparse recovery and Fourier sampling |
| title | Sparse recovery and Fourier sampling |
| title_full | Sparse recovery and Fourier sampling |
| title_fullStr | Sparse recovery and Fourier sampling |
| title_full_unstemmed | Sparse recovery and Fourier sampling |
| title_short | Sparse recovery and Fourier sampling |
| title_sort | sparse recovery and fourier sampling |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/85458 |
| work_keys_str_mv | AT priceericc sparserecoveryandfouriersampling |