Universal compression of piecewise i.i.d. sources

Badri Vellambi; Owen Cameron; Marcus Hutter

doi:10.1109/DCC.2018.00035

Universal compression of piecewise i.i.d. sources

Badri Vellambi, Owen Cameron, Marcus Hutter

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

We study the problem of compressing piecewise i.i.d. sources, which models the practical application of jointly compressing multiple disparate data files. We establish that universal compression of piecewise i.i.d data is possible by modeling the data as a Markov process whose memory grows suitably with the size of the data using the Krichevsky-Trofimov (KT) estimator. The memory order is chosen large enough so that successful learning of the distribution of the each piece of the data from the corresponding contexts is possible for almost any realization of any piecewise i.i.d. data process. This is, a priori, a surprising result given that we are employing a stationary model to asymptotically optimally (model and) compress non-stationary data.

Original language	English
Title of host publication	Proceedings - DCC 2018
Subtitle of host publication	2018 Data Compression Conference
Editors	Ali Bilgin, James A. Storer, Joan Serra-Sagrista, Michael W. Marcellin
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	267-276
Number of pages	10
ISBN (Electronic)	9781538648834
DOIs	https://doi.org/10.1109/DCC.2018.00035
Publication status	Published - 19 Jul 2018
Event	2018 Data Compression Conference, DCC 2018 - Snowbird, United States Duration: 27 Mar 2018 → 30 Mar 2018

Publication series

Name	Data Compression Conference Proceedings
Volume	2018-March
ISSN (Print)	1068-0314

Conference

Conference	2018 Data Compression Conference, DCC 2018
Country/Territory	United States
City	Snowbird
Period	27/03/18 → 30/03/18

Access to Document

10.1109/DCC.2018.00035

Cite this

Vellambi, B., Cameron, O., & Hutter, M. (2018). Universal compression of piecewise i.i.d. sources. In A. Bilgin, J. A. Storer, J. Serra-Sagrista, & M. W. Marcellin (Eds.), Proceedings - DCC 2018: 2018 Data Compression Conference (pp. 267-276). (Data Compression Conference Proceedings; Vol. 2018-March). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DCC.2018.00035

@inproceedings{28ba285d6a13481ea2e7c7aa8d0977e2,

title = "Universal compression of piecewise i.i.d. sources",

abstract = "We study the problem of compressing piecewise i.i.d. sources, which models the practical application of jointly compressing multiple disparate data files. We establish that universal compression of piecewise i.i.d data is possible by modeling the data as a Markov process whose memory grows suitably with the size of the data using the Krichevsky-Trofimov (KT) estimator. The memory order is chosen large enough so that successful learning of the distribution of the each piece of the data from the corresponding contexts is possible for almost any realization of any piecewise i.i.d. data process. This is, a priori, a surprising result given that we are employing a stationary model to asymptotically optimally (model and) compress non-stationary data.",

keywords = "KT estimator, Markov sources, Non stationary source, Piecewise iid sources, Universal compression",

author = "Badri Vellambi and Owen Cameron and Marcus Hutter",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 Data Compression Conference, DCC 2018 ; Conference date: 27-03-2018 Through 30-03-2018",

year = "2018",

month = jul,

day = "19",

doi = "10.1109/DCC.2018.00035",

language = "English",

series = "Data Compression Conference Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "267--276",

editor = "Ali Bilgin and Storer, {James A.} and Joan Serra-Sagrista and Marcellin, {Michael W.}",

booktitle = "Proceedings - DCC 2018",

address = "United States",

}

Vellambi, B, Cameron, O & Hutter, M 2018, Universal compression of piecewise i.i.d. sources. in A Bilgin, JA Storer, J Serra-Sagrista & MW Marcellin (eds), Proceedings - DCC 2018: 2018 Data Compression Conference. Data Compression Conference Proceedings, vol. 2018-March, Institute of Electrical and Electronics Engineers Inc., pp. 267-276, 2018 Data Compression Conference, DCC 2018, Snowbird, United States, 27/03/18. https://doi.org/10.1109/DCC.2018.00035

Universal compression of piecewise i.i.d. sources. / Vellambi, Badri; Cameron, Owen; Hutter, Marcus.
Proceedings - DCC 2018: 2018 Data Compression Conference. ed. / Ali Bilgin; James A. Storer; Joan Serra-Sagrista; Michael W. Marcellin. Institute of Electrical and Electronics Engineers Inc., 2018. p. 267-276 (Data Compression Conference Proceedings; Vol. 2018-March).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Universal compression of piecewise i.i.d. sources

AU - Vellambi, Badri

AU - Cameron, Owen

AU - Hutter, Marcus

PY - 2018/7/19

Y1 - 2018/7/19

N2 - We study the problem of compressing piecewise i.i.d. sources, which models the practical application of jointly compressing multiple disparate data files. We establish that universal compression of piecewise i.i.d data is possible by modeling the data as a Markov process whose memory grows suitably with the size of the data using the Krichevsky-Trofimov (KT) estimator. The memory order is chosen large enough so that successful learning of the distribution of the each piece of the data from the corresponding contexts is possible for almost any realization of any piecewise i.i.d. data process. This is, a priori, a surprising result given that we are employing a stationary model to asymptotically optimally (model and) compress non-stationary data.

AB - We study the problem of compressing piecewise i.i.d. sources, which models the practical application of jointly compressing multiple disparate data files. We establish that universal compression of piecewise i.i.d data is possible by modeling the data as a Markov process whose memory grows suitably with the size of the data using the Krichevsky-Trofimov (KT) estimator. The memory order is chosen large enough so that successful learning of the distribution of the each piece of the data from the corresponding contexts is possible for almost any realization of any piecewise i.i.d. data process. This is, a priori, a surprising result given that we are employing a stationary model to asymptotically optimally (model and) compress non-stationary data.

KW - KT estimator

KW - Markov sources

KW - Non stationary source

KW - Piecewise iid sources

KW - Universal compression

UR - http://www.scopus.com/inward/record.url?scp=85050994191&partnerID=8YFLogxK

U2 - 10.1109/DCC.2018.00035

DO - 10.1109/DCC.2018.00035

M3 - Conference contribution

T3 - Data Compression Conference Proceedings

SP - 267

EP - 276

BT - Proceedings - DCC 2018

A2 - Bilgin, Ali

A2 - Storer, James A.

A2 - Serra-Sagrista, Joan

A2 - Marcellin, Michael W.

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 Data Compression Conference, DCC 2018

Y2 - 27 March 2018 through 30 March 2018

ER -

Universal compression of piecewise i.i.d. sources

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this