deposit_your_work

Bounds for optimal compressed sensing matrices and practical reconstruction schemes

Files in this item

Files Size Format View
3309955.PDF 6.134Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: Bounds for optimal compressed sensing matrices and practical reconstruction schemes
Author: Sarvotham, Shriram
Advisor: Baraniuk, Richard G.
Degree: Doctor of Philosophy thesis
Abstract: Compressed Sensing (CS) is an emerging field that enables reconstruction of a sparse signal x ∈ Rn that has only k << n non-zero coefficients from a small number m << n of linear projections. The projections can be thought of as a vector that is obtained by multiplying a k-sparse signal in Rn by a matrix (called CS matrix) of size m x n where k < m << n. The central theme of this thesis is to study the role of the CS matrix on robustness in reconstruction as well as the complexity involved in reconstruction schemes. In the first part of the thesis, we explore the impact of the CS matrix on robustness, as measured by the Restricted Isometry Property (RIP). We derive two converse bounds for RIP of the CS matrix in terms of n, m and k. For the first bound (structural bound), ee employ results from algebra of Singular Value Decomposition (SVD) of sub-matrices. The second bound (packing bound) is based on sphere packing arguments which we motivate by showing the equivalence of the RIP measure and codes on grassmannian spaces. The derivation of the two bounds offer rich geometric interpretation and illuminate the relationship between CS matrices and many diverse concepts such as equi-angular tight frames, codes on Euclidean spheres, and the generalized Pythagorean Theorem. In the second part of the thesis, we propose strategies to design the CS matrix so that it lends itself to low-complexity reconstruction schemes. We argue that sparse matrices are a good choice in CS and present two strategies for reconstruction involving group testing and belief propagation respectively.
Citation: Sarvotham, Shriram. (2008) "Bounds for optimal compressed sensing matrices and practical reconstruction schemes." Doctoral Thesis, Rice University. http://hdl.handle.net/1911/22221.
URI: http://hdl.handle.net/1911/22221
Date: 2008

This item appears in the following Collection(s)