Sequential universal compression for binary sequences with constrained distributions

Gil I. Shamir, Tjalling J. Tjalkens, Frans M.J. Willems

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Two low-complexity methods are proposed for sequential probability assignment for binary i.i.d. individual sequences with empirical distributions whose governing parameters are known to be bounded within a limited interval. The methods can be applied to different problems where fast accurate estimation of the maximizing sequence probability is very essential to minimizing some loss. Such applications include applications in finance, learning, channel estimation and decoding, prediction, and universal compression. The application of the new methods to universal compression is studied, and their universal coding redundancies are analyzed. One of the methods is shown to achieve the minimax redundancy within the inner region of the limited parameter interval. The other method achieves better performance on the region boundaries and is more robust numerically to outliers. Simulations support the analysis.

Original languageEnglish
Title of host publication2008 IEEE 25th Convention of Electrical and Electronics Engineers in Israel, IEEEI 2008
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages674-678
Number of pages5
ISBN (Print)978-1-4244-2481-8
DOIs
Publication statusPublished - 1 Dec 2008
Event2008 IEEE 25th Convention of Electrical and Electronics Engineers in Israel, IEEEI 2008 - Eilat, Israel
Duration: 3 Dec 20085 Dec 2008

Conference

Conference2008 IEEE 25th Convention of Electrical and Electronics Engineers in Israel, IEEEI 2008
Country/TerritoryIsrael
CityEilat
Period3/12/085/12/08

Fingerprint

Dive into the research topics of 'Sequential universal compression for binary sequences with constrained distributions'. Together they form a unique fingerprint.

Cite this