The coding complexity of Lévy processes (Q1029213): Difference between revisions

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, \textit{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. \textit{J. Creutzig, S. Dereich, T. Müller-Gronbach} and \textit{K. Ritter} [Found. Comput. Math. 9, No. 4, 391--429 (2009; Zbl 1177.65011)], \textit{G. Pagès} and \textit{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)].