Back to search

Cornell University

Information Theory With Large Alphabets And Source Coding Error Exponents

Abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Electrical Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Electrical Engineering
Grantor
Cornell University
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kelly, Benjamin
Chair dc:contributor.chair
  • Wagner, Aaron B.
Committee members dc:contributor.committeemember
  • Tong, Lang
  • Nussbaum, Michael

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7955411

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kelly, Benjamin. Information Theory With Large Alphabets And Source Coding Error Exponents. Doctor of Philosophy thesis, Cornell University, 2011. https://hdl.handle.net/1813/30614