Model-based compressive sensing with Earth Mover's Distance constraints
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
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/82391 |
| _version_ | 1826188199381172224 |
|---|---|
| author | Schmidt. Ludwig, Ph. D. Massachusetts Institute of Technology |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Schmidt. Ludwig, Ph. D. Massachusetts Institute of Technology |
| author_sort | Schmidt. Ludwig, Ph. D. Massachusetts Institute of Technology |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T07:56:03Z |
| format | Thesis |
| id | mit-1721.1/82391 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T07:56:03Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/823912019-04-09T15:35:12Z Model-based compressive sensing with Earth Mover's Distance constraints Schmidt. Ludwig, Ph. D. Massachusetts Institute of Technology 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 (p. 71-72). In compressive sensing, we want to recover ... from linear measurements of the form ... describes the measurement process. Standard results in compressive sensing show that it is possible to exactly recover the signal x from only m ... measurements for certain types of matrices. Model-based compressive sensing reduces the number of measurements even further by limiting the supports of x to a subset of the ... possible supports. Such a family of supports is called a structured sparsity model. In this thesis, we introduce a structured sparsity model for two-dimensional signals that have similar support in neighboring columns. We quantify the change in support between neighboring columns with the Earth Mover's Distance (EMD), which measures both how many elements of the support change and how far the supported elements move. We prove that for a reasonable limit on the EMD between adjacent columns, we can recover signals in our model from only ... measurements, where w is the width of the signal. This is an asymptotic improvement over the ... bound in standard compressive sensing. While developing the algorithmic tools for our proposed structured sparsity model, we also extend the model-based compressed sensing framework. In order to use a structured sparsity model in compressive sensing, we need a model projection algorithm that, given an arbitrary signal x, returns the best approximation in the model. We relax this constraint and develop a variant of IHT, an existing sparse recovery algorithm, that works with approximate model projection algorithms. by Ludwig Schmidt. S.M. 2013-11-18T19:17:25Z 2013-11-18T19:17:25Z 2013 2013 Thesis http://hdl.handle.net/1721.1/82391 862078733 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 72 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Schmidt. Ludwig, Ph. D. Massachusetts Institute of Technology Model-based compressive sensing with Earth Mover's Distance constraints |
| title | Model-based compressive sensing with Earth Mover's Distance constraints |
| title_full | Model-based compressive sensing with Earth Mover's Distance constraints |
| title_fullStr | Model-based compressive sensing with Earth Mover's Distance constraints |
| title_full_unstemmed | Model-based compressive sensing with Earth Mover's Distance constraints |
| title_short | Model-based compressive sensing with Earth Mover's Distance constraints |
| title_sort | model based compressive sensing with earth mover s distance constraints |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/82391 |
| work_keys_str_mv | AT schmidtludwigphdmassachusettsinstituteoftechnology modelbasedcompressivesensingwithearthmoversdistanceconstraints |