| Title:
|
Universally typical sets for ergodic sources of multidimensional data (English) |
| Author:
|
Krüger, Tyll |
| Author:
|
Montúfar, Guido |
| Author:
|
Seiler, Ruedi |
| Author:
|
Siegmund-Schultze, Rainer |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
49 |
| Issue:
|
6 |
| Year:
|
2013 |
| Pages:
|
868-882 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We lift important results about universally typical sets, typically sampled sets, and empirical entropy estimation in the theory of samplings of discrete ergodic information sources from the usual one-dimensional discrete-time setting to a multidimensional lattice setting. We use techniques of packings and coverings with multidimensional windows to construct sequences of multidimensional array sets which in the limit build the generated samples of any ergodic source of entropy rate below an $h_{0}$ with probability one and whose cardinality grows at most at exponential rate $h_{0}$. (English) |
| Keyword:
|
universal codes |
| Keyword:
|
typical sampling sets |
| Keyword:
|
entropy estimation |
| Keyword:
|
asymptotic equipartition property |
| Keyword:
|
ergodic theory |
| MSC:
|
60F15 |
| MSC:
|
62D05 |
| MSC:
|
94A08 |
| MSC:
|
94A17 |
| MSC:
|
94A24 |
| idZBL:
|
Zbl 1293.94037 |
| idMR:
|
MR3182645 |
| . |
| Date available:
|
2014-01-27T12:26:01Z |
| Last updated:
|
2015-03-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143576 |
| . |
| Reference:
|
[1] Bjelaković, I., Krüger, T., Siegmund-Schultze, R., Szkoła, A.: The Shannon-McMillan theorem for ergodic quantum lattice systems..Invent. Math. 155 (2004) (1), 203-222. Zbl 1092.81043, MR 2025304, 10.1007/s00222-003-0318-3 |
| Reference:
|
[2] Breiman, L.: The individual ergodic theorem of information theory..Ann. Math. Statist. 28 (1957), 809-811. Zbl 0092.34001, MR 0092710, 10.1214/aoms/1177706899 |
| Reference:
|
[3] Kieffer, J. C.: A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space..Ann. Probab. 3 (1975), 6, 1031-1037. MR 0393422, 10.1214/aop/1176996230 |
| Reference:
|
[4] Lempel, A., Ziv, J.: Compression of two-dimensional data..IEEE Trans. Inform. Theory 32 (1986), 1, 2-8. 10.1109/TIT.1986.1057132 |
| Reference:
|
[5] Lindenstrauss, E.: Pointwise theorems for amenable groups..Invent. Math. 146 (2001), 2, 259-295. Zbl 1038.37004, MR 1865397, 10.1007/s002220100162 |
| Reference:
|
[6] McMillan, B.: The basic theorems of information theory..Ann. Math. Statist. 24 (1953), 2, 196-219. Zbl 0050.35501, MR 0055621, 10.1214/aoms/1177729028 |
| Reference:
|
[7] Ornstein, D. S., Weiss, B.: The Shannon-McMillan-Breiman theorem for a class of amenable groups..Israel J. Math. 44 (1983), 1, 53-60. Zbl 0516.28020, MR 0693654, 10.1007/BF02763171 |
| Reference:
|
[8] Ornstein, D. S., Weiss, B.: How sampling reveals a process..Ann. Probab. 18 (1990), 3, 905-930. Zbl 0709.60036, MR 1062052, 10.1214/aop/1176990729 |
| Reference:
|
[9] Shannon, C. E.: A mathematical theory of communication..Bell Syst. Techn. J. 27 (1948), 1, 379-423, 623-656. Zbl 1154.94303, MR 0026286, 10.1002/j.1538-7305.1948.tb01338.x |
| Reference:
|
[10] Schmidt, K.: A probabilistic proof of ergodic decomposition..Sankhya: Indian J. Statist, Ser. A 40 (1978), 1, 10-18. Zbl 0412.60004, MR 0545459 |
| Reference:
|
[11] Shields, P.: The Ergodic Theory of Discrete Sample Paths..Amer. Math. Soc., Graduate Stud. Math. 13 (1996). Zbl 0879.28031, MR 1400225, 10.1090/gsm/013 |
| Reference:
|
[12] Welch, T. A.: A technique for high-performance data compression..Computer 17 (1984), 6, 8-19. 10.1109/MC.1984.1659158 |
| Reference:
|
[13] Ziv, J., Lempel, A.: A universal algorithm for sequential data compression..IEEE Trans. Inform. Theory 23 (1977), 3, 337-343. Zbl 0379.94010, MR 0530215, 10.1109/TIT.1977.1055714 |
| Reference:
|
[14] Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding..IEEE Trans. Inform. Theory 24 (1978), 5, 530-536. Zbl 0392.94004, MR 0507465, 10.1109/TIT.1978.1055934 |
| . |
