The Dispersion of the Gauss-Markov Source

The Gauss-Markov source produces $U_i=a{U}_{i-1}+Z_i$ for $i\ge 1$, where $U_0=0$, $\mathrm{\mid }a\mathrm{\mid }<1$ and $Z_i\sim \mathcal{N}(0,{\sigma }^2)$ are i.i.d. Gaussian random variables. We consider lossy compression of a block of $n$ samples of the Gauss-Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss-Markov source with excess-distortion criterion for any distortion $d>0$, and we show that the dispersion has a reverse waterfilling representation. This is the \emph{first} finite blocklength result for lossy compression of \emph{sources with memory}. We prove that the finite blocklength rate-distortion function $R(n,d,ϵ)$ approaches the rate-distortion function $\mathbb{R}(d)$ as $R(n,d,\epsilon) = $\mathbb{R}$(d) + \sqrt{\frac{V(d)}{n}}Q^{-1}(\epsilon) + o\left(\frac{1}{\sqrt{n}}\right)$, where $V(d)$ is the dispersion, $ϵ\in (0,1)$ is the excess-distortion probability, and $Q^{-1}$ is the inverse of the $Q$-function. We give a reverse waterfilling integral representation for the dispersion $V(d)$, which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all $0<d\le \frac{{\sigma }^2}{(1+\mathrm{\mid }a\mathrm{\mid }{)}^2}$, $R(n,d,ϵ)$ of the Gauss-Markov source coincides with that of $Z_k$, the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of $n$ samples of the Gauss-Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter $a$ based on $n$ observations.