Information Theory With Large Alphabets And Source Coding Error Exponents
| dc.contributor.author | Kelly, Benjamin | en_US |
| dc.contributor.chair | Wagner, Aaron B. | en_US |
| dc.contributor.committeeMember | Tong, Lang | en_US |
| dc.contributor.committeeMember | Nussbaum, Michael | en_US |
| dc.date.accessioned | 2012-12-17T13:50:37Z | |
| dc.date.available | 2016-12-30T06:47:02Z | |
| dc.date.issued | 2011-08-31 | en_US |
| dc.description.abstract | The early twenty-first century has been referred to as the 'information age'; this appears to be an apt name given the massive amounts of data that are created daily. However, the utility of the data is limited by the tools we possess to extract and manipulate the information contained within. Towards this end, in this thesis we examine some problems concerning classification and communication. The first problem examined is that of classification in a 'large-alphabet' regime. In this large-alphabet regime, which is motivated by natural language, standard statistical approaches to classification based on chi-squared tests or maximum likelihood are inconsistent. We derive the limit (in terms of alphabet growth rate) beyond which consistent classification is impossible and propose a new consistent test that achieves this limit. We also propose a new classifier which has good empirical performance. The second problem addressed concerns compression of sources with large alphabets. We first characterize for which alphabet growth rates is universal compression possible. We then study the permitted alphabet growth-rate in the non-universal case in which the goal is to compress a source generated by a known sequence of distributions. We finally examine error exponents for source coding/compression problems. The error exponent characterizes the optimal exponential decay of the error probability. For the cases of the Wyner-Ziv and source coding with side information problems we provide new upper and lower bounds on the error exponent. These bounds match for some special cases. We also make connections between source coding error exponents and graph theory and provide new upper bounds on Witsenhausen's rate and complementary graph entropy, two useful quantities from graph theory. | en_US |
| dc.identifier.other | bibid: 7955411 | |
| dc.identifier.uri | https://hdl.handle.net/1813/30614 | |
| dc.language.iso | en_US | en_US |
| dc.subject | Information Theory | en_US |
| dc.subject | Hypothesis Testing | en_US |
| dc.subject | Classification | en_US |
| dc.subject | Error Exponents | en_US |
| dc.title | Information Theory With Large Alphabets And Source Coding Error Exponents | en_US |
| dc.type | dissertation or thesis | en_US |
| thesis.degree.discipline | Electrical Engineering | |
| thesis.degree.grantor | Cornell University | en_US |
| thesis.degree.level | Doctor of Philosophy | |
| thesis.degree.name | Ph. D., Electrical Engineering |
Files
Original bundle
1 - 1 of 1