Show simple item record

dc.contributor.advisor Baraniuk, Richard G.
dc.creatorSarvotham, Shriram
dc.date.accessioned 2009-06-03T19:54:21Z
dc.date.available 2009-06-03T19:54:21Z
dc.date.issued 2008
dc.identifier.urihttps://hdl.handle.net/1911/22221
dc.description.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.
dc.format.extent 135 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectElectronics
Electrical engineering
dc.title Bounds for optimal compressed sensing matrices and practical reconstruction schemes
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Electrical and Computer Engineering
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Sarvotham, Shriram. "Bounds for optimal compressed sensing matrices and practical reconstruction schemes." (2008) Diss., Rice University. https://hdl.handle.net/1911/22221.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record