Advances in sparse signal recovery methods

The general problem of obtaining a useful succinct representation (sketch) of some piece of data is ubiquitous; it has applications in signal acquisition, data compression, sub-linear space algorithms, etc. In this thesis we focus on sparse recovery, where the goal is to recover sparse vectors exactly, and to approximately recover nearly-sparse vectors. More precisely, from the short representation of a vector x, we want to recover a vector x* such that the approximation error ... is comparable to the "tail" min[subscript x'] ... where x' ranges over all vectors with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years, notably in areas such as data stream computing and compressed sensing. We consider two types of sketches: linear and non-linear. For the linear sketching case, where the compressed representation of x is Ax for a measurement matrix A, we introduce a class of binary sparse matrices as valid measurement matrices. We show that they can be used with the popular geometric " 1 minimization" recovery procedure. We also present two iterative recovery algorithms, Sparse Matching Pursuit and Sequential Sparse Matching Pursuit, that can be used with the same matrices. Thanks to the sparsity of the matrices, the resulting algorithms are much more efficient than the ones previously known, while maintaining high quality of recovery. We also show experiments which establish the practicality of these algorithms. For the non-linear case, we present a better analysis of a class of counter algorithms which process large streams of items and maintain enough data to approximately recover the item frequencies. The class includes the popular FREQUENT and SPACESAVING algorithms. We show that the errors in the approximations generated by these algorithms do not grow with the frequencies of the most frequent elements, but only depend on the remaining "tail" of the frequency vector. Therefore, they provide a non-linear sparse recovery scheme, achieving compression rates that are an order of magnitude better than their linear counterparts.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Berinde, Radu

Advisor dc:contributor.advisor

• Piotr Indyk.

• Electrical Engineering and Computer Science.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/61274

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/61274