Functional compression : theory and application
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.M. in Technology and Policy)--Massachusetts Institute of Technology Engineering Systems Division, Technology and Policy Program, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2008
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/43038 |
| _version_ | 1826200758872178688 |
|---|---|
| author | Doshi, Vishal D. (Vishal Devendra) |
| author2 | Devavrat Shah and Muriel Médard. |
| author_facet | Devavrat Shah and Muriel Médard. Doshi, Vishal D. (Vishal Devendra) |
| author_sort | Doshi, Vishal D. (Vishal Devendra) |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.M. in Technology and Policy)--Massachusetts Institute of Technology Engineering Systems Division, Technology and Policy Program, 2008. |
| first_indexed | 2024-09-23T11:41:18Z |
| format | Thesis |
| id | mit-1721.1/43038 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:41:18Z |
| publishDate | 2008 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/430382022-01-31T19:51:44Z Functional compression : theory and application Doshi, Vishal D. (Vishal Devendra) Devavrat Shah and Muriel Médard. Massachusetts Institute of Technology. Technology and Policy Program. Massachusetts Institute of Technology. Engineering Systems Division. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Engineering Systems Division Technology and Policy Program Electrical Engineering and Computer Science. Technology and Policy Program. Engineering Systems Division. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; and, (S.M. in Technology and Policy)--Massachusetts Institute of Technology Engineering Systems Division, Technology and Policy Program, 2008. Includes bibliographical references (p. 75-77). We consider the problem of functional compression. The objective is to separately compress possibly correlated discrete sources such that an arbitrary deterministic function of those sources can be computed given the compressed data from each source. This is motivated by problems in sensor networks and database privacy. Our architecture gives a quantitative definition of privacy for database statistics. Further, we show that it can provide significant coding gains in sensor networks. We consider both the lossless and lossy computation of a function. Specifically, we present results of the rate regions for three instances of the problem where there are two sources: 1) lossless computation where one source is available at the decoder, 2) under a special condition, lossless computation where both sources are separately encoded, and 3) lossy computation where one source is available at the decoder. Wyner and Ziv (1976) considered the third problem for the special case f(X, Y) = X and derived a rate distortion function. Yamamoto (1982) extended this result to a general function. Both of these results are in terms of an auxiliary random variable. Orlitsky and Roche (2001), for the zero distortion case, gave this variable a precise interpretation in terms of the properties of the characteristic graph; this led to a particular coding scheme. We extend that result by providing an achievability scheme that is based on the coloring of the characteristic graph. This suggests a layered architecture where the functional layer controls the coloring scheme, and the data layer uses existing distributed source coding schemes. We extend this graph coloring method to provide algorithms and rates for all three problems. by Vishal D. Doshi. S.M. 2008-11-07T18:54:57Z 2008-11-07T18:54:57Z 2008 2008 Thesis http://hdl.handle.net/1721.1/43038 243609500 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 77 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Technology and Policy Program. Engineering Systems Division. Doshi, Vishal D. (Vishal Devendra) Functional compression : theory and application |
| title | Functional compression : theory and application |
| title_full | Functional compression : theory and application |
| title_fullStr | Functional compression : theory and application |
| title_full_unstemmed | Functional compression : theory and application |
| title_short | Functional compression : theory and application |
| title_sort | functional compression theory and application |
| topic | Electrical Engineering and Computer Science. Technology and Policy Program. Engineering Systems Division. |
| url | http://hdl.handle.net/1721.1/43038 |
| work_keys_str_mv | AT doshivishaldvishaldevendra functionalcompressiontheoryandapplication |