Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. 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/84869 |
| _version_ | 1826205794098479104 |
|---|---|
| author | Grant, Elyot |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Grant, Elyot |
| author_sort | Grant, Elyot |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T13:19:13Z |
| format | Thesis |
| id | mit-1721.1/84869 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:19:13Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/848692019-04-11T10:06:27Z Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing Grant, Elyot 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 (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. Cataloged from PDF version of thesis. Includes bibliographical references (pages 41-42). In this thesis, we establish theoretical guarantees for several dimension reduction algorithms developed for applications in compressive sensing and signal processing. In each instance, the input is a point or set of points in d-dimensional Euclidean space, and the goal is to find a linear function from Rd into Rk , where k << d, such that the resulting embedding of the input pointset into k-dimensional Euclidean space has various desirable properties. We focus on two classes of theoretical results: -- First, we examine linear embeddings of arbitrary pointsets with the aim of minimizing distortion. We present an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most ... is the smallest possible distortion over all orthonormal embeddings into k dimensions. This PTAS-like result transcends lower bounds for well-known embedding teclhniques such as the Johnson-Lindenstrauss transform. -- Next, motivated by compressive sensing of images, we examine linear embeddings of datasets containing points that are sparse in the pixel basis, with the goal of recoving a nearly-optimal sparse approximation to the original data. We present several algorithms that achieve strong recovery guarantees using the near-optimal bound of measurements, while also being highly "local" so that they can be implemented more easily in physical devices. We also present some impossibility results concerning the existence of such embeddings with stronger locality properties. by Elyot Grant. S.M. 2014-02-10T16:56:35Z 2014-02-10T16:56:35Z 2013 Thesis http://hdl.handle.net/1721.1/84869 868329734 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 42 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Grant, Elyot Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing |
| title | Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing |
| title_full | Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing |
| title_fullStr | Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing |
| title_full_unstemmed | Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing |
| title_short | Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing |
| title_sort | dimension reduction algorithms for near optimal low dimensional embeddings and compressive sensing |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/84869 |
| work_keys_str_mv | AT grantelyot dimensionreductionalgorithmsfornearoptimallowdimensionalembeddingsandcompressivesensing |