×

The coding complexity of Lévy processes. (English) Zbl 1175.60046

The authors deal with the coding problem for \(\mathbb D[0,\infty)\)-valued processes \(X\), where \(\mathbb D[0,\infty)\) denotes the space of càdlág functions endowed with the Skorokhod topology, with the \(L_p[0,l]\)-norm distortion under a given complexity constraint on the approximating random variable \(\hat{X}\). The following three classical complexity constraints are considered [see, for instance, A. N. Kolmogorov, Int. J. Comput. Math. 2, 157–168 (1968; Zbl 0172.42701)]: 1. \(\log|\text{range}(\hat{X})|\leq r\) (quantization constraint). 2. \( H(\hat{X})\leq r\), where \(H\) denotes the entropy of \(X\) (entropy constraint). 3. \(I(X;\hat{X})\leq r\), where \(I\) denotes the Shannon mutual information of \(X\) and \(\hat{X}\) (mutual information constraint).
The quantization constraint naturally appears when coding the signal \(X\) under a strict bit-length constraint for its binary representation. The entropy constraint corresponds to an average bit-length constraint and optimal codes are obtained via Huffman coding. Allowing simultaneous coding of several independent copies of the source signal and measuring the error by the sum of the individual errors results in further increase in the efficiency. Due to Shannon’s source coding theorem, the distortion-rate function \(D\) measures the corresponding best-achievable error. The authors established lower bounds that prove the optimality of the proposed coding scheme in many cases.
For more results see, e.g. J. Creutzig, S. Dereich, T. Müller-Gronbach and K. Ritter [Found. Comput. Math. 9, No. 4, 391–429 (2009; Zbl 1177.65011)], G. Pagès and J. Printems [Monte Carlo Methods Appl. 11, No. 4, 407–446 (2005; Zbl 1161.91402), Handbook of Numerical Analysis 15, 595–648 (2009; Zbl 1180.91309)].

MSC:

60G51 Processes with independent increments; Lévy processes
60G35 Signal detection and filtering (aspects of stochastic processes)
94A15 Information theory (general)
41A25 Rate of convergence, degree of approximation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. Aurzada, S. Dereich, M. Scheutzow, C. Vormoor, High resolution quantization and entropy coding of jump processes. Preprint, URL: http://arxiv.org/abs/0712.0964 (2007). · Zbl 1177.94120
[2] J. Bertoin, Lévy Processes. Cambridge Tracts in Mathematics, vol. 121 (Cambridge University Press, Cambridge, 1996).
[3] L. Breiman, Probability. Classics in Applied Mathematics, vol. 7 (Philadelphia, SIAM, 1993).
[4] T.M. Cover, J.A. Thomas, Elements of Information Theory, 2nd edn. (Wiley, New York, 2006). · Zbl 1140.94001
[5] J. Creutzig, Approximation of S{\(\alpha\)} S Lévy processes in L p norm, J. Approx. Theory 140(1), 71–85 (2006). · Zbl 1092.41017 · doi:10.1016/j.jat.2005.11.015
[6] S. Dereich, High resolution coding of stochastic processes and small ball probabilities. Ph.D. Dissertation, TU Berlin, URL: http://edocs.tu-berlin.de/diss/2003/dereich_steffen.htm (2003).
[7] S. Dereich, The coding complexity of diffusion processes under supremum norm distortion, Stoch. Process. Their Appl. 118(6), 917–937 (2008). · Zbl 1157.60036 · doi:10.1016/j.spa.2007.07.003
[8] S. Dereich, The coding complexity of diffusion processes under L p [0,1]-norm distortion, Stoch. Process. Their Appl. 118(6), 938–951 (2008). · Zbl 1151.60018 · doi:10.1016/j.spa.2007.07.002
[9] S. Dereich, M. Scheutzow, High resolution quantization and entropy coding for fractional Brownian motion, Electron. J. Probab. 11, 700–722 (2006). · Zbl 1110.60030
[10] S. Dereich, F. Fehringer, A. Matoussi, M. Scheutzow, On the link between small ball probabilities and the quantization problem for Gaussian measures on Banach spaces, J. Theor. Probab. 16(1), 249–265 (2003). · Zbl 1017.60012 · doi:10.1023/A:1022242924198
[11] S. Dereich, J. Creutzig, T. Müller-Gronbach, K. Ritter, Infinite-dimensional quadrature and approximation of distributions, Found. Comput. Math. (2008, to appear). · Zbl 1177.65011
[12] P. Elias, Universal codeword sets and representations of the integers, IEEE Trans. Inf. Theory 21, 194–203 (1975). · Zbl 0298.94011 · doi:10.1109/TIT.1975.1055349
[13] S. Ihara, Information Theory for Continuous Systems (World Scientific, Singapore, 1993). · Zbl 0798.94001
[14] A.N. Kolmogorov, Three approaches to the quantitative definition of information, Int. J. Comput. Math. 2, 157–168 (1968). · Zbl 0172.42701 · doi:10.1080/00207166808803030
[15] H. Luschgy, G. Pagès, Sharp asymptotics of the functional quantization problem for Gaussian processes, Ann. Probab. 32(2), 1574–1599 (2004). · Zbl 1049.60029 · doi:10.1214/009117904000000324
[16] H. Luschgy, G. Pagès, Functional quantization of a class of Brownian diffusions: a constructive approach, Stoch. Process. Their Appl. 116(2), 310–336 (2006). · Zbl 1091.60007 · doi:10.1016/j.spa.2005.09.003
[17] H. Luschgy, G. Pagès, Functional quantization rate and mean pathwise regularity of processes with an application to Lévy processes, Ann. Appl. Probab. 18(2), 427–469 (2008). · Zbl 1158.60005 · doi:10.1214/07-AAP459
[18] G. Pagès, J. Printems, Functional quantization for numerics with an application to option pricing, Monte Carlo Methods Appl. 11(4), 407–446 (2005). · Zbl 1161.91402 · doi:10.1515/156939605777438578
[19] P.E. Protter, Stochastic Integration and Differential Equations, 2nd edn. Applications of Mathematics (New York), vol. 21 (Springer, Berlin, 2004). · Zbl 1041.60005
[20] K. Sato, Lévy Processes and Infinitely Divisible Distributions. Cambridge Studies in Advanced Mathematics, vol. 68 (Cambridge University Press, Cambridge, 1999). · Zbl 0973.60001
[21] C. Vormoor, High resolution coding of point processes and the Boolean model. Ph.D. Thesis, Technische Universität Berlin, URL: http://opus.kobv.de/tuberlin/volltexte/2007/1502/ (2007). · Zbl 1211.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.