Sparse graph codes for compression, sensing, and secrecy
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/60141 |
| _version_ | 1826216648352202752 |
|---|---|
| author | Chandar, Venkat (Venkat Bala) |
| author2 | Gregory W. Wornell and Devavrat Shah. |
| author_facet | Gregory W. Wornell and Devavrat Shah. Chandar, Venkat (Venkat Bala) |
| author_sort | Chandar, Venkat (Venkat Bala) |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T16:51:10Z |
| format | Thesis |
| id | mit-1721.1/60141 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:51:10Z |
| publishDate | 2010 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/601412019-04-10T23:01:26Z Sparse graph codes for compression, sensing, and secrecy Chandar, Venkat (Venkat Bala) Gregory W. Wornell and Devavrat Shah. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Cataloged from student PDF version of thesis. Includes bibliographical references (p. 201-212). Sparse graph codes were first introduced by Gallager over 40 years ago. Over the last two decades, such codes have been the subject of intense research, and capacity approaching sparse graph codes with low complexity encoding and decoding algorithms have been designed for many channels. Motivated by the success of sparse graph codes for channel coding, we explore the use of sparse graph codes for four other problems related to compression, sensing, and security. First, we construct locally encodable and decodable source codes for a simple class of sources. Local encodability refers to the property that when the original source data changes slightly, the compression produced by the source code can be updated easily. Local decodability refers to the property that a single source symbol can be recovered without having to decode the entire source block. Second, we analyze a simple message-passing algorithm for compressed sensing recovery, and show that our algorithm provides a nontrivial f1/f1 guarantee. We also show that very sparse matrices and matrices whose entries must be either 0 or 1 have poor performance with respect to the restricted isometry property for the f2 norm. Third, we analyze the performance of a special class of sparse graph codes, LDPC codes, for the problem of quantizing a uniformly random bit string under Hamming distortion. We show that LDPC codes can come arbitrarily close to the rate-distortion bound using an optimal quantizer. This is a special case of a general result showing a duality between lossy source coding and channel coding-if we ignore computational complexity, then good channel codes are automatically good lossy source codes. We also prove a lower bound on the average degree of vertices in an LDPC code as a function of the gap to the rate-distortion bound. Finally, we construct efficient, capacity-achieving codes for the wiretap channel, a model of communication that allows one to provide information-theoretic, rather than computational, security guarantees. Our main results include the introduction of a new security critertion which is an information-theoretic analog of semantic security, the construction of capacity-achieving codes possessing strong security with nearly linear time encoding and decoding algorithms for any degraded wiretap channel, and the construction of capacity-achieving codes possessing semantic security with linear time encoding and decoding algorithms for erasure wiretap channels. Our analysis relies on a relatively small set of tools. One tool is density evolution, a powerful method for analyzing the behavior of message-passing algorithms on long, random sparse graph codes. Another concept we use extensively is the notion of an expander graph. Expander graphs have powerful properties that allow us to prove adversarial, rather than probabilistic, guarantees for message-passing algorithms. Expander graphs are also useful in the context of the wiretap channel because they provide a method for constructing randomness extractors. Finally, we use several well-known isoperimetric inequalities (Harper's inequality, Azuma's inequality, and the Gaussian Isoperimetric inequality) in our analysis of the duality between lossy source coding and channel coding. by Venkat Bala Chandar. Ph.D. 2010-12-06T17:28:26Z 2010-12-06T17:28:26Z 2010 2010 Thesis http://hdl.handle.net/1721.1/60141 680653000 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 212 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Chandar, Venkat (Venkat Bala) Sparse graph codes for compression, sensing, and secrecy |
| title | Sparse graph codes for compression, sensing, and secrecy |
| title_full | Sparse graph codes for compression, sensing, and secrecy |
| title_fullStr | Sparse graph codes for compression, sensing, and secrecy |
| title_full_unstemmed | Sparse graph codes for compression, sensing, and secrecy |
| title_short | Sparse graph codes for compression, sensing, and secrecy |
| title_sort | sparse graph codes for compression sensing and secrecy |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/60141 |
| work_keys_str_mv | AT chandarvenkatvenkatbala sparsegraphcodesforcompressionsensingandsecrecy |