NDLI: About Adaptive Coding on Countable Alphabets: Max-Stable Envelope Classes

Content Provider	IEEE Xplore Digital Library
Author	Boucheron, S. Gassiat, E. Ohannessian, M.I.
Copyright Year	1963
Abstract	In this paper, we study the problem of lossless universal source coding for stationary memoryless sources on countably infinite alphabets. This task is generally not achievable without restricting the class of sources over which universality is desired. Building on our prior work, we propose natural families of sources characterized by a common dominating envelope. We particularly emphasize the notion of adaptivity, which is the ability to perform as well as an oracle knowing the envelope, without actually knowing it. This is closely related to the notion of hierarchical universal source coding, but with the important difference that families of envelope classes are not discretely indexed and not necessarily nested. Our contribution is to extend the classes of envelopes over which adaptive universal source coding is possible, namely by including max-stable (heavy-tailed) envelopes which are excellent models in many applications, such as natural language modeling. We derive a minimax lower bound on the redundancy of any code on such envelope classes, including an oracle that knows the envelope. We then propose a constructive code that does not use knowledge of the envelope. The code is computationally efficient and is structured to use an expanding threshold for auto-censoring (ETAC), and we therefore dub it the ETAC-code. We prove that the ETAC-code achieves the lower bound on the minimax redundancy within a factor logarithmic in the sequence length, and can be therefore qualified as a near-adaptive code over families of heavy-tailed envelopes. For finite and light-tailed envelopes, the penalty is even less, and the same code follows closely previous results that explicitly made the light-tailed assumption. Our technical results are founded on methods from regular variation theory and concentration of measure.
Sponsorship	IEEE Information Theory Society
Starting Page	4948
Ending Page	4967
Page Count	20
File Size	390358
File Format	PDF
ISSN	00189448
Volume Number	61
Issue Number	9
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Redundancy Source coding Probability distribution Distribution functions Adaptive coding Adaptation models minimax countable alphabets redundancy adaptive compression Countable alphabets
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

About Adaptive Coding on Countable Alphabets

Coding on Countably Infinite Alphabets

Universal Coding on Infinite Alphabets: Exponentially Decreasing Envelopes

About Adaptive Coding on Countable Alphabets: Max-Stable Envelope Classes

1 about adaptive coding on countable alphabets § (2014).

Minimax Pointwise Redundancy for Memoryless Models Over Large Alphabets

On Universal D-Semifaithful Coding for Memoryless Sources with Infinite Alphabets

Universal coding on infinite alphabets: exponentially decreasing envelopes (2008).

Adaptive Coding and Prediction of Sources With Large and Infinite Alphabets

About Adaptive Coding on Countable Alphabets: Max-Stable Envelope Classes

Similar Documents

About Adaptive Coding on Countable Alphabets

Coding on Countably Infinite Alphabets

Universal Coding on Infinite Alphabets: Exponentially Decreasing Envelopes

About Adaptive Coding on Countable Alphabets: Max-Stable Envelope Classes

1 about adaptive coding on countable alphabets § (2014).

Minimax Pointwise Redundancy for Memoryless Models Over Large Alphabets

On Universal D-Semifaithful Coding for Memoryless Sources with Infinite Alphabets

Universal coding on infinite alphabets: exponentially decreasing envelopes (2008).

Adaptive Coding and Prediction of Sources With Large and Infinite Alphabets

About Adaptive Coding on Countable Alphabets: Max-Stable Envelope Classes