Rate-Distortion Function Upper Bounds for Gaussian Vectors and Their Applications in Coding AR Sources

Abstract

In this paper, we give upper bounds for the rate-distortion function (RDF) of any Gaussian vector, and we propose coding strategies to achieve such bounds. We use these strategies to reduce the computational complexity of coding Gaussian asymptotically wide sense stationary (AWSS) autoregressive (AR) sources. Furthermore, we also give sufficient conditions for AR processes to be AWSS.

1. Introduction

In 1956, Kolmogorov [1] gave a formula for the rate-distortion function (RDF) of Gaussian vectors and the RDF of Gaussian wide sense stationary (WSS) sources. Later, in 1970 Gray [2] obtained a formula for the RDF of Gaussian autoregressive (AR) sources.

In 1973, Pearl [3] gave an upper bound for the RDF of finite-length data blocks of Gaussian WSS sources, but he did not propose a coding strategy to achieve his bound for a given block length. In [4], we presented two tighter upper bounds for the RDF of finite-length data blocks of Gaussian WSS sources, and we proposed low-complexity coding strategies, based on the discrete Fourier transform (DFT), to achieve such bounds. Moreover, we proved that those two upper bounds tend to the RDF of the WSS source (computed by Kolmogorov in [1]) when the size of the data block grows.

In the present paper, we generalize the upper bounds and the two low-complexity coding strategies presented in [4] to any Gaussian vector. Therefore, in contrast to [4], here no assumption about the structure of the correlation matrix of the Gaussian vector has been made (observe that since the sources in [4] were WSS the correlation matrix of the Gaussian vectors there considered was Toeplitz). To obtain such generalization we start our analysis by first proving several new results on the DFT of random vectors. Although in [4] (Theorem 1) another new result on the DFT was presented, it cannot be used here, because such result and its proof rely on the power spectral density (PSD) of a WSS process and its properties.

The two low-complexity strategies here presented are applied in coding finite-length data blocks of Gaussian AR sources. Specifically, we prove that the rates (upper bounds) corresponding to these two strategies tend to the RDF of the AR source (computed by Gray in [2]) when the size of the data block grows and the AR source is asymptotically WSS (AWSS).

The definition of AWSS process was introduced by Gray in [5] (Chapter 6) and it is based on his concept of asymptotically equivalent sequences of matrices [6]. Sufficient conditions for AR processes to be AWSS can be found in [5] (Theorem 6.2) and [7] (Theorem 7). In this paper we present other sufficient conditions which make easier to check in practice whether an AR process is AWSS.

The paper is organized as follows. In Section 2 we obtain several new results on the DFT of random vectors which are used in Section 3. In Section 3 we give upper bounds for the RDF of Gaussian vectors, and we propose coding strategies to achieve such bounds. In Section 4 we apply the strategies proposed in Section 3 to reduce the computational complexity of coding Gaussian AWSS AR sources. In Section 5 we give sufficient conditions for AR processes to be AWSS. We finish the paper with a numerical example and conclusions.

2. Several New Results on the DFT of Random Vectors

We begin by introducing some notation. $\mathbb{C}$ denotes the set of (finite) complex numbers, $\mathrm{i}$ is the imaginary unit, $\mathrm{Re}$ and $\mathrm{Im}$ denote real and imaginary parts, respectively. * stands for conjugate transpose, ⊤ denotes transpose, and ${\lambda }_k\left(A\right)$, $k\in \{1,\dots ,n\}$, are the eigenvalues of an $n\times n$ Hermitian matrix A arranged in decreasing order. E stands for expectation, and $V_n$ is the $n\times n$ Fourier unitary matrix, i.e.,

$${\left[V_n\right]}_{j,k}=\frac{1}{\sqrt{n}}{\mathrm{e}}^{-\frac{2\pi (j-1)(k-1)}{n}\mathrm{i}},j,k\in \{1,\dots ,n\}.$$

If $z\in \mathbb{C}$ then $\widehat{z}$ denotes the real (column) vector

$$\widehat{z}=\left(\begin{array}{c}\mathrm{Re}\left(z\right)\\ \mathrm{Im}\left(z\right)\end{array}\right).$$

If $z_k\in \mathbb{C}$ for all $k\in \{1,\dots ,n\}$ then $z_{n:1}$ is the n-dimensional vector given by

$$z_{n:1}=\left(\begin{array}{c}{z}_n\\ z_{n-1}\\ z_{n-2}\\ ⋮\\ z_1\end{array}\right).$$

In this section, we give several new results on the DFT of random vectors in two theorems and one lemma.

Theorem 1.

Let $y_{n:1}$ be the DFT of an n-dimensional random vector $x_{n:1}$, that is, $y_{n:1}=V_n^{*}{x}_{n:1}$.

• If $k\in \{1,\dots ,n\}$ then

  $${\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\le E\left({\left|x_k\right|}^2\right)\le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)$$

  (1)

  and

  $${\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\le E\left({\left|y_k\right|}^2\right)\le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right).$$

  (2)
• If the random vector $x_{n:1}$ is real and $k\in \{1,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$ then

  $$\frac{{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}\le E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)\le \frac{{\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2},$$

  (3)

  and

  $$\frac{{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}\le E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)\le \frac{{\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}.$$

  (4)

Proof. 

(1) We first prove that if $W_n$ is an $n\times n$ unitary matrix then

$${\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\le {\left[W_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)W_n^{*}\right]}_{n-k+1,n-k+1}\le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right).$$

(5)

We have

$$\begin{array}{cc}\hfill {\left[W_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)W_n^{*}\right]}_{k_1,k_2}& =\sum _{h=1}^n{\left[W_n\right]}_{k_1,h}{\left[{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)W_n^{*}\right]}_{h,k_2}\hfill \\ & =\sum _{h=1}^n{\left[W_n\right]}_{k_1,h}\sum _{l=1}^n{\left[{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)\right]}_{h,l}{\left[W_n^{*}\right]}_{l,k_2}\hfill \\ & =\sum _{h=1}^n{\left[W_n\right]}_{k_1,h}{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\overline{{\left[W_n\right]}_{k_2,h}}\hfill \end{array}$$

(6)

for all $k_1,k_2\in \{1,\dots ,n\}$, and hence,

$${\left[W_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)W_n^{*}\right]}_{n-k+1,n-k+1}=\sum _{h=1}^n{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right){\left|{\left[W_n\right]}_{n-k+1,h}\right|}^2.$$

Consequently,

$$\begin{array}{cc}\hfill {\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\sum _{h=1}^n{\left|{\left[W_n\right]}_{n-k+1,h}\right|}^2& \le {\left[W_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)W_n^{*}\right]}_{n-k+1,n-k+1}\hfill \\ & \le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\sum _{h=1}^n{\left|{\left[W_n\right]}_{n-k+1,h}\right|}^2,\hfill \end{array}$$

and applying

$$\sum _{h=1}^n{\left|{\left[W_n\right]}_{n-k+1,h}\right|}^2=\sum _{h=1}^n{\left[W_n\right]}_{n-k+1,h}{\left[W_n^{*}\right]}_{h,n-k+1}={\left[W_n{W}_n^{*}\right]}_{n-k+1,n-k+1}={\left[I_n\right]}_{n-k+1,n-k+1}=1,$$

where $I_n$ denotes the $n\times n$ identity matrix, we obtain Equation (5).

Let $E\left(x_{n:1}{x}_{n:1}^{*}\right)=U_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)U_n^{-1}$ be a diagonalization of $E\left(x_{n:1}{x}_{n:1}^{*}\right)$ where the eigenvector matrix $U_n$ is unitary. As

$$E\left({\left|x_k\right|}^2\right)={\left[E\left(x_{n:1}{x}_{n:1}^{*}\right)\right]}_{n-k+1,n-k+1}={\left[U_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)U_n^{*}\right]}_{n-k+1,n-k+1},$$

Equation (1) follows directly by taking $W_n=U_n$ in Equation (5).

Since

$$\begin{array}{cc}\hfill E\left({\left|y_k\right|}^2\right)& ={\left[E\left(y_{n:1}{y}_{n:1}^{*}\right)\right]}_{n-k+1,n-k+1}\hfill \\ & ={\left[E\left(V_n^{*}{x}_{n:1}{x}_{n:1}^{*}{\left(V_n^{*}\right)}^{*}\right)\right]}_{n-k+1,n-k+1}\hfill \\ & ={\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{*}\right){\left(V_n^{*}\right)}^{*}\right]}_{n-k+1,n-k+1}\hfill \\ & ={\left[V_n^{*}{U}_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right)U_n^{*}{\left(V_n^{*}\right)}^{*}\right]}_{n-k+1,n-k+1}\hfill \\ & ={\left[V_n^{*}{U}_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{*}\right)\right)\right){\left(V_n^{*}{U}_n\right)}^{*}\right]}_{n-k+1,n-k+1},\hfill \end{array}$$

(7)

taking $W_n=V_n^{*}{U}_n$ in Equation (5) we obtain Equation (2).

(2) Applying [4] (Equation (10)) and taking $W_n=U_n$ in Equation (6) yields

$$\begin{array}{c}E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)\hfill \\ =\frac{1}{n}\sum _{k_1,k_2=1}^{n}cos\frac{2\pi (1-k_1)k}{n}cos\frac{2\pi (1-k_2)k}{n}E\left(x_{n-k_1+1}{x}_{n-k_2+1}\right)\hfill \\ =\frac{1}{n}\sum _{k_1,k_2=1}^{n}cos\frac{2\pi (1-k_1)k}{n}cos\frac{2\pi (1-k_2)k}{n}{\left[E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right]}_{k_1,k_2}\hfill \\ =\frac{1}{n}\sum _{k_1,k_2=1}^{n}cos\frac{2\pi (1-k_1)k}{n}cos\frac{2\pi (1-k_2)k}{n}{\left[U_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right)U_n^{*}\right]}_{k_1,k_2}\hfill \\ =\frac{1}{n}\sum _{k_1,k_2=1}^{n}cos\frac{2\pi (1-k_1)k}{n}cos\frac{2\pi (1-k_2)k}{n}\sum _{h=1}^n{\left[U_n\right]}_{k_1,h}{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\overline{{\left[U_n\right]}_{k_2,h}}\hfill \\ =\frac{1}{n}\sum _{h=1}^n{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\left(\sum _{k_1=1}^{n}cos\frac{2\pi (1-k_1)k}{n}{\left[U_n\right]}_{k_1,h}\right)\left(\sum _{k_2=1}^{n}cos\frac{2\pi (1-k_2)k}{n}\overline{{\left[U_n\right]}_{k_2,h}}\right)\hfill \\ =\frac{1}{n}\sum _{h=1}^n{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right){\left|\sum _{l=1}^{n}cos\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2,\hfill \end{array}$$

and therefore,

$$\begin{array}{c}{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}cos\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\le E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)\le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}cos\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2.\hfill \end{array}$$

Analogously, it can be proved that

$$\begin{array}{c}{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}sin\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\le E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)\le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}sin\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2.\hfill \end{array}$$

To finish the proof we only need to show that

$$\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}cos\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2=\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}sin\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2=\frac{1}{2}.$$

(8)

If $b_1,\dots ,b_n$ are n real numbers then

$$\begin{array}{cc}\hfill \frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^n{b}_l{\left[U_n\right]}_{l,h}\right|}^2& =\frac{1}{n}\sum _{h=1}^n\left(\sum _{k_1=1}^n{b}_{k_1}{\left[U_n\right]}_{k_1,h}\right)\left(\sum _{k_2=1}^n{b}_{k_2}\overline{{\left[U_n\right]}_{k_2,h}}\right)=\frac{1}{n}\sum _{k_1,k_2=1}^n{b}_{k_1}{b}_{k_2}\sum _{h=1}^n{\left[U_n\right]}_{k_1,h}{\left[U_n^{*}\right]}_{h,k_2}\hfill \\ & =\frac{1}{n}\sum _{k_1,k_2=1}^n{b}_{k_1}{b}_{k_2}{\left[U_n{U}_n^{*}\right]}_{k_1,k_2}=\frac{1}{n}\sum _{k_1,k_2=1}^n{b}_{k_1}{b}_{k_2}{\left[I_n\right]}_{k_1,k_2}=\frac{1}{n}\sum _{l=1}^n{b}_l^2,\hfill \end{array}$$

(9)

and thus,

$$\begin{array}{cc}\hfill \frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}sin\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2& =\frac{1}{n}\sum _{l=1}^n{\left(sin\frac{2\pi (1-l)k}{n}\right)}^2=\frac{1}{n}\sum _{l=1}^n\left(1-{\left(cos\frac{2\pi (1-l)k}{n}\right)}^2\right)\hfill \\ & =1-\frac{1}{n}\sum _{l=1}^n{\left(cos\frac{2\pi (1-l)k}{n}\right)}^2=1-\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^{n}cos\frac{2\pi (1-l)k}{n}{\left[U_n\right]}_{l,h}\right|}^2.\hfill \end{array}$$

Equation (8) now follows directly from [4] (Equation (15)). ☐

Lemma 1.

Let $y_{n:1}$ be the DFT of an n-dimensional random vector $x_{n:1}$. If $k\in \{1,\dots ,n\}$ then

• $E\left({\left|y_k\right|}^2\right)={\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{*}\right)V_n\right]}_{n-k+1,n-k+1}$.
• $E\left(y_k^2\right)={\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{\top }\right)\overline{V_n}\right]}_{n-k+1,n-k+1}$.
• $E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right)=\frac{1}{2}\mathrm{Im}\left(E\left(y_k^2\right)\right)$.
• $E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)=\frac{E\left({\left|y_k\right|}^2\right)+\mathrm{Re}\left(E\left(y_k^2\right)\right)}{2}$.
• $E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)=\frac{E\left({\left|y_k\right|}^2\right)-\mathrm{Re}\left(E\left(y_k^2\right)\right)}{2}$.

Proof. 

(1) It is a direct consequence of Equation (7).

(2) We have

$$\begin{array}{cc}\hfill E\left(y_k^2\right)& ={\left[E\left(y_{n:1}{y}_{n:1}^{\top }\right)\right]}_{n-k+1,n-k+1}={\left[E\left(V_n^{*}{x}_{n:1}{x}_{n:1}^{\top }{\left(V_n^{*}\right)}^{\top }\right)\right]}_{n-k+1,n-k+1}\hfill \\ & ={\left[E\left(V_n^{*}{x}_{n:1}{x}_{n:1}^{\top }\overline{V_n}\right)\right]}_{n-k+1,n-k+1}={\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{\top }\right)\overline{V_n}\right]}_{n-k+1,n-k+1}.\hfill \end{array}$$

(3) Observe that

$$\begin{array}{cc}\hfill E\left(y_k^2\right)& =E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2-{\left(\mathrm{Im}\left(y_k\right)\right)}^2+2\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\mathrm{i}\right)\hfill \\ & =E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)-E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)+2E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right)\mathrm{i},\hfill \end{array}$$

(10)

and hence,

$$\mathrm{Im}\left(E\left(y_k^2\right)\right)=2E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right).$$

(4) and (5) From Equation (10) we obtain

$$\mathrm{Re}\left(E\left(y_k^2\right)\right)=E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)-E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right).$$

(11)

Furthermore,

$$E\left({\left|y_k\right|}^2\right)=E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2+{\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)=E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)+E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right).$$

(12)

(4) and (5) follow directly from Equations (11) and (12). ☐

Theorem 2.

Let $y_{n:1}$ be the DFT of a real n-dimensional random vector $x_{n:1}$. If $k\in \{1,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$ then

$$\frac{{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}\le {\lambda }_2\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)\le {\lambda }_1\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)\le \frac{{\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}.$$

Proof. 

Fix $r\in \{1,2\}$ and consider a real unit eigenvector $v={(v_1,v_2)}^{\top }$ corresponding to ${\lambda }_r\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)$. We have

$${\lambda }_r\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)={\lambda }_r\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)v^{\top }v=v^{\top }\left({\lambda }_r\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)v\right)=v^{\top }E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)v.$$

From [4] (Equation (10)) we obtain

$$\begin{array}{c}E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\hfill \\ =\frac{1}{n}\sum _{k_1,k_2=1}^n\left(\begin{array}{cc}cos\frac{2\pi (1-k_1)k}{n}cos\frac{2\pi (1-k_2)k}{n}E\left(x_{n-k_1+1}{x}_{n-k_2+1}\right)& cos\frac{2\pi (1-k_1)k}{n}sin\frac{2\pi (1-k_2)k}{n}E\left(x_{n-k_1+1}{x}_{n-k_2+1}\right)\\ sin\frac{2\pi (1-k_1)k}{n}cos\frac{2\pi (1-k_2)k}{n}E\left(x_{n-k_1+1}{x}_{n-k_2+1}\right)& sin\frac{2\pi (1-k_1)k}{n}sin\frac{2\pi (1-k_2)k}{n}E\left(x_{n-k_1+1}{x}_{n-k_2+1}\right)\end{array}\right)\hfill \\ =\frac{1}{n}\sum _{k_1,k_2=1}^n{\left[E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right]}_{k_1,k_2}{w}_{k_1}{w}_{k_2}^{\top }\hfill \end{array}$$

with

$$\begin{array}{c}\hfill w_l=\left(\begin{array}{c}cos\frac{2\pi (1-l)k}{n}\\ sin\frac{2\pi (1-l)k}{n}\end{array}\right),l\in \{1,\dots ,n\},\end{array}$$

and consequently,

$$\begin{array}{cc}\hfill {\lambda }_r\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)& =\frac{1}{n}\sum _{k_1,k_2=1}^n{\left[E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right]}_{k_1,k_2}{v}^{\top }{w}_{k_1}{w}_{k_2}^{\top }v\hfill \\ & =\frac{1}{n}\sum _{k_1,k_2=1}^n\sum _{h=1}^n{\left[U_n\right]}_{k_1,h}{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\overline{{\left[U_n\right]}_{k_2,h}}{v}^{\top }{w}_{k_1}{w}_{k_2}^{\top }v\hfill \\ & =\frac{1}{n}\sum _{k_1,k_2=1}^n{\left(w_{k_1}^{\top }v\right)}^{\top }\sum _{h=1}^n{\left[U_n\right]}_{k_1,h}{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\overline{{\left[U_n\right]}_{k_2,h}}{w}_{k_2}^{\top }v\hfill \\ & =\frac{1}{n}\sum _{h=1}^n{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\left(\sum _{k_1=1}^n{w}_{k_1}^{\top }v{\left[U_n\right]}_{k_1,h}\right)\left(\sum _{k_2=1}^n{w}_{k_2}^{\top }v\overline{{\left[U_n\right]}_{k_2,h}}\right)\hfill \\ & =\frac{1}{n}\sum _{h=1}^n{\lambda }_h\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right){\left|\sum _{l=1}^n{w}_l^{\top }v{\left[U_n\right]}_{l,h}\right|}^2\hfill \end{array}$$

with $E\left(x_{n:1}{x}_{n:1}^{\top }\right)=U_n{\mathrm{diag}}_{1\le j\le n}\left({\lambda }_j\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right)U_n^{-1}$ being a diagonalization of $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$ where the eigenvector matrix $U_n$ is unitary. Therefore,

$$\begin{array}{c}\hfill {\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^n{w}_l^{\top }v{\left[U_n\right]}_{l,h}\right|}^2\le {\lambda }_r\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)\le {\lambda }_1\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^n{w}_l^{\top }v{\left[U_n\right]}_{l,h}\right|}^2.\end{array}$$

To finish the proof we only need to show that

$$\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^n{w}_l^{\top }v{\left[U_n\right]}_{l,h}\right|}^2=\frac{1}{2}.$$

Applying Equation (9) and [4] (Equations (14) and (15)) yields

$$\begin{array}{c}\frac{1}{n}\sum _{h=1}^n{\left|\sum _{l=1}^n{w}_l^{\top }v{\left[U_n\right]}_{l,h}\right|}^2\hfill \\ =\frac{1}{n}\sum _{l=1}^n{\left(w_l^{\top }v\right)}^2=\frac{1}{n}\sum _{l=1}^n{\left(cos\frac{2\pi (1-l)k}{n}{v}_1+sin\frac{2\pi (1-l)k}{n}{v}_2\right)}^2\hfill \\ =v_1^2\frac{1}{n}\sum _{l=1}^n{\left(cos\frac{2\pi (1-l)k}{n}\right)}^2+v_2^2\frac{1}{n}\sum _{l=1}^n{\left(sin\frac{2\pi (1-l)k}{n}\right)}^2+2v_1{v}_2\frac{1}{n}\sum _{l=1}^{n}cos\frac{2\pi (1-l)k}{n}sin\frac{2\pi (1-l)k}{n}\hfill \\ =v_1^2\frac{1}{n}\sum _{l=1}^n{\left(cos\frac{2\pi (1-l)k}{n}\right)}^2+\frac{v_2^2}{2}+v_1{v}_2\frac{1}{n}\sum _{l=1}^{n}sin\frac{4\pi (1-l)k}{n}\hfill \\ =v_1^2\frac{1}{n}\sum _{l=1}^n\left(1-{\left(sin\frac{2\pi (1-l)k}{n}\right)}^2\right)+\frac{v_2^2}{2}-v_1{v}_2\frac{1}{n}\sum _{l=1}^{n}sin\frac{4\pi (l-1)k}{n}\hfill \\ =v_1^2\left(1-\frac{1}{n}\sum _{l=1}^n{\left(sin\frac{2\pi (1-l)k}{n}\right)}^2\right)+\frac{v_2^2}{2}-v_1{v}_2\frac{1}{n}\sum _{l=1}^n\mathrm{Im}\left({\mathrm{e}}^{\frac{4\pi (l-1)k}{n}\mathrm{i}}\right)\hfill \\ =\frac{v_1^2}{2}+\frac{v_2^2}{2}-v_1{v}_2\frac{1}{n}\mathrm{Im}\left(\sum _{l=1}^n{\mathrm{e}}^{\frac{4\pi (l-1)k}{n}\mathrm{i}}\right)=\frac{1}{2}{v}^{\top }v=\frac{1}{2}.\hfill \end{array}$$

☐

3. RDF Upper Bounds for Real Gaussian Vectors

We first review the formula for the RDF of a real Gaussian vector given by Kolmogorov in [1].

Theorem 3.

If $x_{n:1}$ is a real zero-mean Gaussian n-dimensional vector with positive definite correlation matrix, its RDF is given by

$$R_{x_{n:1}}\left(D\right)=\frac{1}{n}\sum _{k=1}^{n}max\left\{0,\frac{1}{2}ln\frac{{\lambda }_k\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{\theta }\right\}\forall D\in \left(0,\frac{\mathrm{tr}\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{n}\right],$$

where $\mathrm{tr}$ denotes trace and θ is a real number satisfying

$$D=\frac{1}{n}\sum _{k=1}^{n}min\left\{\theta ,{\lambda }_k\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right\}.$$

We recall that $R_{x_{n:1}}\left(D\right)$ can be thought of as the minimum rate (measured in nats) at which one must encode (compress) $x_{n:1}$ in order to be able to recover it with a mean square error (MSE) per dimension not larger than D, that is:

$$\frac{E\left({∥x_{n:1}-\widetilde{x_{n:1}}∥}_2^2\right)}{n}\le D,$$

where $\widetilde{x_{n:1}}$ denotes the estimation of $x_{n:1}$ and ${\parallel ·\parallel }_2$ is the spectral norm.

The following result provides an optimal coding strategy for $x_{n:1}$ in order to achieve $R_{x_{n:1}}\left(D\right)$ whenever $D\le {\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)$. Observe that if $D\le {\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)$ then

$$R_{x_{n:1}}\left(D\right)=\frac{1}{2n}\sum _{k=1}^{n}ln\frac{{\lambda }_k\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{D}=\frac{1}{2n}ln\frac{det\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{D^n}.$$

(13)

Corollary 1.

Suppose that $x_{n:1}$ is as in Theorem 3. Let $E\left(x_{n:1}{x}_{n:1}^{\top }\right)=U_n{\mathrm{diag}}_{1\le k\le n}\left({\lambda }_k\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right)U_n^{-1}$ be a diagonalization of $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$ where the eigenvector matrix $U_n$ is real and orthogonal. If $D\in \left(0,{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right]$ then

$$R_{x_{n:1}}\left(D\right)=\frac{1}{n}\sum _{k=1}^n{R}_{z_k}\left(D\right)=\frac{1}{2n}\sum _{k=1}^{n}ln\frac{E\left(z_k^2\right)}{D}$$

(14)

with $z_{n:1}=U_n^{\top }{x}_{n:1}$.

Proof. 

We encode $z_1,\dots ,z_n$ separately with $E\left({∥z_k-\widetilde{z_k}∥}_2^2\right)\le D$ for all $k\in \{1,\dots ,n\}$. Let $\widetilde{x_{n:1}}:=U_n\widetilde{z_{n:1}}$, where

$$\widetilde{z_{n:1}}:=\left(\begin{array}{c}\widetilde{z_n}\\ ⋮\\ \widetilde{z_1}\end{array}\right).$$

As $U_n^{\top }$ is unitary (in fact, it is a real orthogonal matrix) and the spectral norm is unitarily invariant, we have

$$\begin{array}{cc}\hfill \frac{E\left({∥x_{n:1}-\widetilde{x_{n:1}}∥}_2^2\right)}{n}& =\frac{E\left({∥U_n^{\top }{x}_{n:1}-U_n^{\top }\widetilde{x_{n:1}}∥}_2^2\right)}{n}=\frac{E\left({∥z_{n:1}-\widetilde{z_{n:1}}∥}_2^2\right)}{n}\hfill \\ & =\frac{E\left({\sum }_{k=1}^n{\left(z_k-\widetilde{z_k}\right)}^2\right)}{n}=\frac{{\sum }_{k=1}^{n}E\left({\left(z_k-\widetilde{z_k}\right)}^2\right)}{n}=\frac{{\sum }_{k=1}^{n}E\left({∥z_k-\widetilde{z_k}∥}_2^2\right)}{n}\le D,\hfill \end{array}$$

and thus,

$$R_{x_{n:1}}\left(D\right)\le \frac{1}{n}\sum _{k=1}^n{R}_{z_k}\left(D\right).$$

To finish the proof we show Equation (14). Since

$$E\left(z_{n:1}{z}_{n:1}^{\top }\right)=E\left(U_n^{\top }{x}_{n:1}{x}_{n:1}^{\top }{U}_n\right)=U_n^{\top }E\left(x_{n:1}{x}_{n:1}^{\top }\right)U_n={\mathrm{diag}}_{1\le k\le n}\left({\lambda }_k\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right),$$

we obtain

$$E\left(z_k^2\right)={\left[E\left(z_{n:1}{z}_{n:1}^{\top }\right)\right]}_{n-k+1,n-k+1}={\lambda }_{n-k+1}\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\ge {\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\ge D>0.$$

Hence, applying Equation (13) yields

$$\begin{array}{cc}\hfill \frac{1}{n}\sum _{k=1}^n{R}_{z_k}\left(D\right)& =\frac{1}{n}\sum _{k=1}^n\frac{1}{2}ln\frac{E\left(z_k^2\right)}{D}=\frac{1}{2n}\sum _{k=1}^{n}ln\frac{{\lambda }_{n-k+1}\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{D}\hfill \\ & =\frac{1}{2n}\sum _{k=1}^{n}ln\frac{{\lambda }_k\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{D}=R_{x_{n:1}}\left(D\right).\hfill \end{array}$$

☐

Corollary 1 shows that an optimal coding strategy for $x_{n:1}$ is to encode $z_1,\dots ,z_n$ separately.

We now give two coding strategies for $x_{n:1}$ based on the DFT whose computational complexity is lower than the computational complexity of the optimal coding strategy provided in Corollary 1.

Theorem 4.

Let $x_{n:1}$ be as in Theorem 3. Suppose that $y_{n:1}$ is the DFT of $x_{n:1}$ and $D\in \left(0,{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right]$. Then

$$\begin{array}{cc}\hfill R_{x_{n:1}}\left(D\right)& \le {\tilde{R}}_{x_{n:1}}\left(D\right)\le {\breve{R}}_{x_{n:1}}\left(D\right)\le \frac{1}{2n}\sum _{k=1}^{n}ln\frac{E\left(\right|y_k{|}^2)}{D}\hfill \end{array}$$

(15)

$$\begin{array}{c}\le R_{x_{n:1}}\left(D\right)+\frac{1}{2}ln\left(1+\frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-V_n{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{\top }\right)V_n\right]}_{k,k}\right)V_n^{*}∥}_F}{\sqrt{n}{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}\right),\hfill \end{array}$$

(16)

where ${\parallel ·\parallel }_F$ is the Frobenius norm,

$${\tilde{R}}_{x_{n:1}}\left(D\right):=\left\{\begin{array}{cc}\frac{R_{y_{\frac{n}{2}}}\left(D\right)+2{\sum }_{k=\frac{n}{2}+1}^{n-1}{R}_{\widehat{y_k}}\left(\frac{D}{2}\right)+R_{y_n}\left(D\right)}{n}\hfill & ifniseven,\hfill \\ \frac{2{\sum }_{k=\frac{n+1}{2}}^{n-1}{R}_{\widehat{y_k}}\left(\frac{D}{2}\right)+R_{y_n}\left(D\right)}{n}\hfill & ifnisodd,\hfill \end{array}\right.$$

and

$${\breve{R}}_{x_{n:1}}\left(D\right):=\left\{\begin{array}{cc}\frac{R_{y_{\frac{n}{2}}}\left(D\right)+{\sum }_{k=\frac{n}{2}+1}^{n-1}\left(R_{\mathrm{Re}\left(y_k\right)}\left(\frac{D}{2}\right)+R_{\mathrm{Im}\left(y_k\right)}\left(\frac{D}{2}\right)\right)+R_{y_n}\left(D\right)}{n}\hfill & ifniseven,\hfill \\ \frac{{\sum }_{k=\frac{n+1}{2}}^{n-1}\left(R_{\mathrm{Re}\left(y_k\right)}\left(\frac{D}{2}\right)+R_{\mathrm{Im}\left(y_k\right)}\left(\frac{D}{2}\right)\right)+R_{y_n}\left(D\right)}{n}\hfill & ifnisodd.\hfill \end{array}\right.$$

Proof. 

Equations (15) and (16) were presented in [4] (Equations (16) and (20)) for the case where the correlation matrix $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$ is Toeplitz. They were proved by using a result on the DFT of random vectors with Toeplitz correlation matrix, namely, ref. [4] (Theorem 1). The proof of Theorem 4 is similar to the proof of [4] (Equations (16) and (20)) but using Theorem 1 instead of [4] (Theorem 1). Observe that in Theorems 1 and 4 no assumption about the structure of $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$ has been made. ☐

Theorem 4 shows that a coding strategy for $x_{n:1}$ is to encode $y_{\lceil \frac{n}{2}\rceil },\dots ,y_n$ separately, where $\lceil \frac{n}{2}\rceil$ denotes the smallest integer higher than or equal to $\frac{n}{2}$. Theorem 4 also shows that another coding strategy for $x_{n:1}$ is to encode separately the real part and the imaginary part of $y_k$ instead of encoding $y_k$ when $k\in \{\lceil \frac{n}{2}\rceil ,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$. The computational complexity of these two coding strategies based on the DFT is lower than the computational complexity of the optimal coding strategy provided in Corollary 1. Specifically, the complexity of computing the DFT ($y_{n:1}=V_n^{*}{x}_{n:1}$) is $O(nlogn)$ whenever the fast Fourier transform (FFT) algorithm is used, while the complexity of computing $z_{n:1}=U_n^{\top }{x}_{n:1}$ is $O\left(n^2\right)$. Moreover, when the coding strategies based on the DFT are used, we do not need to compute a real orthogonal eigenvector matrix $U_n$ of $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$. It should also be mentioned that for these coding strategies based on the DFT the knowledge of $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$ is not even required, in fact, for them we only need to know $E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)$ with $k\in \{\lceil \frac{n}{2}\rceil ,\dots ,n\}$.

The rates corresponding to the two coding strategies given in Theorem 4, ${\tilde{R}}_{x_{n:1}}\left(D\right)$ and ${\breve{R}}_{x_{n:1}}\left(D\right)$, can be written in terms of $E\left(x_{n:1}{x}_{n:1}^{\top }\right)$ and $V_n$ by using Lemma 1 and the following lemma.

Lemma 2.

Let $y_{n:1}$ and D be as in Theorem 4. Then

• $R_{y_k}\left(D\right)=\frac{1}{2}ln\frac{E\left(y_k^2\right)}{D}$ for all $k\in \{1,\dots ,n\}\cap \{\frac{n}{2},n\}$.
• $R_{\widehat{y_k}}\left(\frac{D}{2}\right)=\frac{1}{4}ln\frac{E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)-{\left(E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right)\right)}^2}{{\left(\frac{D}{2}\right)}^2}$ for all $k\in \{1,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$.
• $R_{\mathrm{Re}\left(y_k\right)}\left(\frac{D}{2}\right)=\frac{1}{2}ln\frac{E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)}{\frac{D}{2}}$ for all $k\in \{1,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$.
• $R_{\mathrm{Im}\left(y_k\right)}\left(\frac{D}{2}\right)=\frac{1}{2}ln\frac{E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)}{\frac{D}{2}}$ for all $k\in \{1,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$.

Proof. 

(1) Applying Equation (2) and [4] (Lemma 1) yields

$$0<D\le {\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\le E\left({\left|y_k\right|}^2\right)=E\left(y_k^2\right).$$

Assertion (1) now follows directly from Equation (13).

(2) Applying Theorem 2 we have

$$0<\frac{D}{2}\le \frac{{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}\le {\lambda }_2\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right).$$

Consequently, from Equation (13) we obtain

$$\begin{array}{c}\hfill R_{\widehat{y_k}}\left(\frac{D}{2}\right)=\frac{1}{4}ln\frac{det\left(E\left(\widehat{y_k}{\left(\widehat{y_k}\right)}^{\top }\right)\right)}{{\left(\frac{D}{2}\right)}^2}=\frac{1}{4}ln\frac{det\left(\begin{array}{cc}E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)& E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right)\\ E\left(\mathrm{Im}\left(y_k\right)\mathrm{Re}\left(y_k\right)\right)& E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)\end{array}\right)}{{\left(\frac{D}{2}\right)}^2}.\end{array}$$

Assertions (3) and (4) Applying Equations (3) and (4) yields

$$0<\frac{D}{2}\le \frac{{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}\le E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right).$$

and

$$0<\frac{D}{2}\le \frac{{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{2}\le E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right).$$

Assertions (3) and (4) now follow directly from Equation (13). ☐

We end this section with a result that is a direct consequence of Lemma 2. This result shows when the rates corresponding to the two coding strategies given in Theorem 4, ${\tilde{R}}_{x_{n:1}}\left(D\right)$ and ${\breve{R}}_{x_{n:1}}\left(D\right)$, are equal.

Lemma 3.

Let $x_{n:1}$, $y_{n:1}$, and D be as in Theorem 4. Then the two following assertions are equivalent:

• ${\tilde{R}}_{x_{n:1}}\left(D\right)={\breve{R}}_{x_{n:1}}\left(D\right)$.
• $E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right)=0$ for all $k\in \{\lceil \frac{n}{2}\rceil ,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$.

Proof. 

Fix $k\in \{\lceil \frac{n}{2}\rceil ,\dots ,n-1\}\setminus \left\{\frac{n}{2}\right\}$. From Lemma 2 we have

$$\begin{array}{cc}\hfill 2R_{\widehat{y_k}}\left(\frac{D}{2}\right)& =\frac{1}{2}ln\frac{E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)-{\left(E\left(\mathrm{Re}\left(y_k\right)\mathrm{Im}\left(y_k\right)\right)\right)}^2}{{\left(\frac{D}{2}\right)}^2}\hfill \\ & \le \frac{1}{2}ln\frac{E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)}{{\left(\frac{D}{2}\right)}^2}\hfill \\ & =\frac{1}{2}ln\frac{E\left({\left(\mathrm{Re}\left(y_k\right)\right)}^2\right)}{\frac{D}{2}}+\frac{1}{2}ln\frac{E\left({\left(\mathrm{Im}\left(y_k\right)\right)}^2\right)}{\frac{D}{2}}\hfill \\ & =R_{\mathrm{Re}\left(y_k\right)}\left(\frac{D}{2}\right)+R_{\mathrm{Im}\left(y_k\right)}\left(\frac{D}{2}\right).\hfill \end{array}$$

☐

4. Low-Complexity Coding Strategies for Gaussian AWSS AR Sources

We begin by introducing some notation. The symbols $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{R}$ denote the set of positive integers, integers, and (finite) real numbers, respectively. If $f:\mathbb{R}\to \mathbb{C}$ is continuous and $2\pi$-periodic, we denote by $T_n\left(f\right)$ the $n\times n$ Toeplitz matrix given by

$${\left[T_n\left(f\right)\right]}_{j,k}=t_{j-k},$$

where ${\left\{t_k\right\}}_{k\in \mathbb{Z}}$ is the sequence of Fourier coefficients of f, i.e.,

$$t_k=\frac{1}{2\pi }{\int }_0^{2\pi }f\left(\omega \right){\mathrm{e}}^{-k\omega \mathrm{i}}d\omega \forall k\in \mathbb{Z}.$$

If $A_n$ and $B_n$ are $n\times n$ matrices for all $n\in \mathbb{N}$, we write $\left\{A_n\right\}\sim \left\{B_n\right\}$ if the sequences $\left\{A_n\right\}$ and $\left\{B_n\right\}$ are asymptotically equivalent, that is, $\{\parallel A_n{\parallel }_2\}$ and $\{\parallel B_n{\parallel }_2\}$ are bounded and ${lim}_{n\to \infty }\frac{\parallel A_n-B_n{\parallel }_F}{\sqrt{n}}=0$ (see [5] (Section 2.3) and [6]).

We now review the definitions of AWSS processes and AR processes.

Definition 1.

A random process $\left\{x_n\right\}$ is said to be AWSS if it has constant mean (i.e., $E\left(x_j\right)=E\left(x_k\right)$ for all $j,k\in \mathbb{N})$ and there exists a continuous $2\pi$-periodic function $f:\mathbb{R}\to \mathbb{C}$ such that $\left\{E\left(x_{n:1}{x}_{n:1}^{*}\right)\right\}\sim \left\{T_n\left(f\right)\right\}$. The function f is called (asymptotic) PSD of $\left\{x_n\right\}$.

Definition 2.

A real zero-mean random process $\left\{x_n\right\}$ is said to be AR if

$$x_n=w_n-\sum _{k=1}^{n-1}{a}_{-k}{x}_{n-k}\forall n\in \mathbb{N},$$

or equivalently,

$$\sum _{k=0}^{n-1}{a}_{-k}{x}_{n-k}=w_n\forall n\in \mathbb{N},$$

(17)

where $a_0=1$, $a_{-k}\in \mathbb{R}$ for all $k\in \mathbb{N}$, and $\left\{w_n\right\}$ is a real zero-mean random process satisfying that $E\left(w_j{w}_k\right)={\delta }_{j,k}{\sigma }^2$ for all $j,k\in \mathbb{N}$ with ${\sigma }^2>0$ and ${\delta }_{j,k}$ being the Kronecker delta (i.e., ${\delta }_{j,k}=1$ if $j=k$, and it is zero otherwise).

The AR process $\left\{x_n\right\}$ in Equation (17) is of finite order if there exists $p\in \mathbb{N}$ such that $a_{-k}=0$ for all $k>p$. In this case, $\left\{x_n\right\}$ is called an AR $\left(p\right)$ process.

The following theorem shows that if $x_{n:1}$ is a large enough data block of a Gaussian AWSS AR source, the rate does not increase whenever we encode it using the two coding strategies based on the DFT presented in Section 3, instead of encoding $x_{n:1}$ using an eigenvector matrix of its correlation matrix.

Theorem 5.

Let $\left\{x_n\right\}$ be as in Definition 2. Suppose that ${\left\{a_k\right\}}_{k\in \mathbb{Z}}$, with $a_k=0$ for all $k\in \mathbb{N}$, is the sequence of Fourier coefficients of a function $a:\mathbb{R}\to \mathbb{C}$ which is continuous and $2\pi$-periodic. Then

• ${inf}_{n\in \mathbb{N}}{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\ge \frac{{\sigma }^2}{{max}_{\omega \in [0,2\pi ]}{\left|a\left(\omega \right)\right|}^2}>0$.
• Consider $D\in \left(0,{inf}_{n\in \mathbb{N}}{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)\right]$.

  (a)

  If $\left\{x_n\right\}$ is Gaussian,

  $$\frac{1}{2}ln\frac{{\sigma }^2}{D}=R_{x_{n:1}}\left(D\right)\le {\tilde{R}}_{x_{n:1}}\left(D\right)\le {\breve{R}}_{x_{n:1}}\left(D\right)\le K_1(n,D)\le K_2(n,D)\le K_3(n,D)\forall n\in \mathbb{N},$$

  (18)

  where $K_1(n,D)$ is given by Equation (16), and $K_2(n,D)$ and $K_3(n,D)$ are obtained by replacing ${\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)$ in Equation (16) by ${inf}_{n\in \mathbb{N}}{\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)$ and $\frac{{\sigma }^2}{{max}_{\omega \in [0,2\pi ]}{\left|a\left(\omega \right)\right|}^2}$, respectively.

  (b)

  If $\left\{x_n\right\}$ is Gaussian and AWSS,

  $$\underset{n\to \infty }{lim}{R}_{x_{n:1}}\left(D\right)=\underset{n\to \infty }{lim}{\tilde{R}}_{x_{n:1}}\left(D\right)=\underset{n\to \infty }{lim}{\breve{R}}_{x_{n:1}}\left(D\right)=\underset{n\to \infty }{lim}{K}_3(n,D).$$

  (19)

Proof. (1) Equation (17) can be rewritten as

$$T_n\left(a\right)x_{n:1}=w_{n:1}\forall n\in \mathbb{N}.$$

Consequently,

$$T_n\left(a\right)E\left(x_{n:1}{x}_{n:1}^{\top }\right){\left(T_n\left(a\right)\right)}^{\top }=E\left(T_n\left(a\right)x_{n:1}{\left(T_n\left(a\right)x_{n:1}\right)}^{\top }\right)=E\left(w_{n:1}{w}_{n:1}^{\top }\right)={\sigma }^2{I}_n\forall n\in \mathbb{N}.$$

As $det\left(T_n\left(a\right)\right)=1$, $T_n\left(a\right)$ is invertible, and therefore,

$$\begin{array}{cc}\hfill E\left(x_{n:1}{x}_{n:1}^{\top }\right)& ={\sigma }^2{\left(T_n\left(a\right)\right)}^{-1}{\left({\left(T_n\left(a\right)\right)}^{\top }\right)}^{-1}={\sigma }^2{\left({\left(T_n\left(a\right)\right)}^{\top }{T}_n\left(a\right)\right)}^{-1}={\sigma }^2{\left({\left(T_n\left(a\right)\right)}^{*}{T}_n\left(a\right)\right)}^{-1}\hfill \\ & ={\sigma }^2{\left(N_n{\mathrm{diag}}_{1\le k\le n}\left({\left({\sigma }_k\left(T_n\left(a\right)\right)\right)}^2\right)N_n^{*}\right)}^{-1}=N_n{\mathrm{diag}}_{1\le k\le n}\left(\frac{{\sigma }^2}{{\left({\sigma }_k\left(T_n\left(a\right)\right)\right)}^2}\right)N_n^{*}\hfill \end{array}$$

(20)

for all $n\in \mathbb{N}$, where $T_n\left(a\right)=M_n{\mathrm{diag}}_{1\le k\le n}\left({\sigma }_k\left(T_n\left(a\right)\right)\right)N_n^{*}$ is a singular value decomposition of $T_n\left(a\right)$. Thus, applying [8] (Theorem 4.3) yields

$${\lambda }_n\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)=\frac{{\sigma }^2}{{\left({\sigma }_1\left(T_n\left(a\right)\right)\right)}^2}\ge \frac{{\sigma }^2}{{max}_{\omega \in [0,2\pi ]}{\left|a\left(\omega \right)\right|}^2}>0\forall n\in \mathbb{N}.$$

(2a) From Equation (13) we have

$$\begin{array}{cc}\hfill R_{x_{n:1}}\left(D\right)& =\frac{1}{2n}ln\frac{det\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right)}{D^n}=\frac{1}{2n}ln\frac{det\left({\sigma }^2{\left(T_n\left(a\right)\right)}^{-1}{\left({\left(T_n\left(a\right)\right)}^{\top }\right)}^{-1}\right)}{D^n}\hfill \\ & =\frac{1}{2n}ln\frac{{\left({\sigma }^2\right)}^n}{D^{n}det\left(T_n\left(a\right)\right)det\left({\left(T_n\left(a\right)\right)}^{\top }\right)}=\frac{1}{2n}ln\frac{{\left({\sigma }^2\right)}^n}{D^n}=\frac{1}{2}ln\frac{{\sigma }^2}{D}\forall n\in \mathbb{N}.\hfill \end{array}$$

Assertion (2a) now follows from Theorem 4 and Assertion (1).

(2b) From Assertion (2a) we only need to show that

$$\underset{n\to \infty }{lim}\frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-V_n{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{\top }\right)V_n\right]}_{k,k}\right)V_n^{*}∥}_F}{\sqrt{n}}=0.$$

(21)

As the Frobenius norm is unitarily invariant we obtain

$$\begin{array}{cc}0\hfill & \le \frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-V_n{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{\top }\right)V_n\right]}_{k,k}\right)V_n^{*}∥}_F}{\sqrt{n}}\hfill \\ & \le \frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥T_n\left(f\right)-{\widehat{C}}_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥V_n{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}E\left(x_{n:1}{x}_{n:1}^{\top }\right)V_n\right]}_{k,k}\right)V_n^{*}-{\widehat{C}}_n\left(f\right)∥}_F}{\sqrt{n}}\hfill \\ & =\frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥T_n\left(f\right)-{\widehat{C}}_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥V_n{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)\right)V_n\right]}_{k,k}\right)V_n^{*}∥}_F}{\sqrt{n}}\hfill \\ & =\frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥T_n\left(f\right)-{\widehat{C}}_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)\right)V_n\right]}_{k,k}\right)∥}_F}{\sqrt{n}}\hfill \\ & \le \frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥T_n\left(f\right)-{\widehat{C}}_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥V_n^{*}\left(E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)\right)V_n∥}_F}{\sqrt{n}}\hfill \\ & =2\frac{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)-T_n\left(f\right)∥}_F}{\sqrt{n}}+\frac{{∥T_n\left(f\right)-{\widehat{C}}_n\left(f\right)∥}_F}{\sqrt{n}},\hfill \end{array}$$

where f is (asymptotic) PSD of $\left\{x_n\right\}$ and ${\widehat{C}}_n\left(f\right)=V_n{\mathrm{diag}}_{1\le k\le n}\left({\left[V_n^{*}{T}_n\left(f\right)V_n\right]}_{k,k}\right)V_n^{*}$. Assertion (2b) now follows from $\left\{E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right\}\sim \left\{T_n\left(f\right)\right\}$ and [9] (Lemma 4.2). ☐

If ${\sum }_{k=-\infty }^0\left|a_k\right|<\infty$, there always exists such function a and it is given by $a\left(\omega \right)={\sum }_{k=-\infty }^0{a}_k{\mathrm{e}}^{k\omega \mathrm{i}}$ for all $\omega \in \mathbb{R}$ (see, e.g., [8] (Appendix B)). In particular, if $\left\{x_n\right\}$ is an AR $\left(p\right)$ process, $a\left(\omega \right)={\sum }_{k=-p}^0{a}_k{\mathrm{e}}^{k\omega \mathrm{i}}$ for all $\omega \in \mathbb{R}$.

5. Sufficient Conditions for AR Processes to be AWSS

In the following two results we give sufficient conditions for AR processes to be AWSS.

Theorem 6.

Let $\left\{x_n\right\}$ be as in Definition 2. Suppose that ${\left\{a_k\right\}}_{k\in \mathbb{Z}}$, with $a_k=0$ for all $k\in \mathbb{N}$, is the sequence of Fourier coefficients of a function $a:\mathbb{R}\to \mathbb{C}$ which is continuous and $2\pi$-periodic. Then the following assertions are equivalent:

• $\left\{x_n\right\}$ is AWSS.
• $\left\{{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)∥}_2\right\}$ is bounded.
• $\left\{T_n\left(a\right)\right\}$ is stable (that is, $\{\parallel {\left(T_n\left(a\right)\right)}^{-1}{\parallel }_2\}$ is bounded).
• $a\left(\omega \right)\ne 0$ for all $\omega \in \mathbb{R}$ and $\left\{x_n\right\}$ is AWSS with (asymptotic) PSD $\frac{{\sigma }^2}{{\left|a\right|}^2}$.

Proof. 

(1)⇒(2) This is a direct consequence of the definition of AWSS process, i.e., of Definition 1.

(2)⇔(3) From Equation (20) we have

$${∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)∥}_2=\frac{{\sigma }^2}{{\left({\sigma }_n\left(T_n\left(a\right)\right)\right)}^2}={\sigma }^2{∥N_n{\mathrm{diag}}_{1\le k\le n}\left(\frac{1}{{\sigma }_k\left(T_n\left(a\right)\right)}\right)M_n^{*}∥}_2^2={\sigma }^2{∥{\left(T_n\left(a\right)\right)}^{-1}∥}_2^2$$

for all $n\in \mathbb{N}$.

(3)⇒(4) It is well known that if $f:\mathbb{R}\to \mathbb{C}$ is continuous and $2\pi$-periodic, and $\left\{T_n\left(f\right)\right\}$ is stable then $f\left(\omega \right)\ne 0$ for all $\omega \in \mathbb{R}$. Hence, $a\left(\omega \right)\ne 0$ for all $\omega \in \mathbb{R}$.

Applying [8] (Lemma 4.2.1) yields $\left\{{\left(T_n\left(a\right)\right)}^{\top }\right\}=\left\{{\left(T_n\left(a\right)\right)}^{*}\right\}=\left\{T_n\left(\overline{a}\right)\right\}$. Consequently, from [7] (Theorem 3) we obtain

$$\left\{{\left(T_n\left(a\right)\right)}^{\top }{T}_n\left(a\right)\right\}=\left\{T_n\left(\overline{a}\right)T_n\left(a\right)\right\}\sim \left\{T_n\left(\overline{a}a\right)\right\}=\left\{T_n\left({\left|a\right|}^2\right)\right\}.$$

Observe that the sequence

$$\left\{{∥{\left({\left(T_n\left(a\right)\right)}^{\top }{T}_n\left(a\right)\right)}^{-1}∥}_2\right\}=\left\{{∥\frac{1}{{\sigma }^2}E\left(x_{n:1}{x}_{n:1}^{\top }\right)∥}_2\right\}=\left\{\frac{1}{{\sigma }^2}{∥E\left(x_{n:1}{x}_{n:1}^{\top }\right)∥}_2\right\}$$

is bounded. As the function ${\left|a\right|}^2$ is real, applying [8] (Theorem 4.4) we have that $T_n\left({\left|a\right|}^2\right)$ is Hermitian and $0<{min}_{\omega \in [0,2\pi ]}{\left|a\left(\omega \right)\right|}^2\le {\lambda }_n\left(T_n\left({\left|a\right|}^2\right)\right)$ for all $n\in \mathbb{N}$, and therefore,

$${∥{\left(T_n\left({\left|a\right|}^2\right)\right)}^{-1}∥}_2=\frac{1}{{\lambda }_n\left(T_n\left({\left|a\right|}^2\right)\right)}\le \frac{1}{{min}_{\omega \in [0,2\pi ]}{\left|a\left(\omega \right)\right|}^2}\forall n\in \mathbb{N}.$$

Thus, from [5] (Theorem 1.4) we obtain

$$\left\{\frac{1}{{\sigma }^2}E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right\}=\left\{{\left({\left(T_n\left(a\right)\right)}^{\top }{T}_n\left(a\right)\right)}^{-1}\right\}\sim \left\{{\left(T_n\left({\left|a\right|}^2\right)\right)}^{-1}\right\}.$$

Hence, applying [10] (Theorem 4.2) and [5] (Theorem 1.2) yields

$$\left\{\frac{1}{{\sigma }^2}E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right\}\sim \left\{T_n\left(\frac{1}{{\left|a\right|}^2}\right)\right\}.$$

Consequently, from [8] (Lemma 3.1.3) and [8] (Lemma 4.2.3) we have

$$\left\{E\left(x_{n:1}{x}_{n:1}^{\top }\right)\right\}\sim \left\{{\sigma }^2{T}_n\left(\frac{1}{{\left|a\right|}^2}\right)\right\}=\left\{T_n\left(\frac{{\sigma }^2}{{\left|a\right|}^2}\right)\right\}.$$

(4)⇒(1) It is obvious.

Corollary 2.

Let $\left\{x_n\right\}$ be as in Definition 2 with ${\sum }_{k=-\infty }^0\left|a_k\right|<\infty$. If ${\sum }_{k=0}^{\infty }{a}_{-k}{z}^k\ne 0$ for all $\left|z\right|\le 1$ then $\left\{x_n\right\}$ is AWSS.

Proof. 

It is well known that if a sequence of complex numbers ${\left\{t_k\right\}}_{k\in \mathbb{Z}}$ satisfies that ${\sum }_{k=-\infty }^{\infty }\left|t_k\right|<\infty$ and that ${\sum }_{k=-\infty }^{\infty }{t}_k{z}^k\ne 0$ for all $\left|z\right|\le 1$ then $\left\{T_n\left(f\right)\right\}$ is stable with $f\left(\omega \right)={\sum }_{k=-\infty }^{\infty }{t}_k{\mathrm{e}}^{k\omega \mathrm{i}}$ for all $\omega \in \mathbb{R}$. Therefore, $\left\{T_n\left(b\right)\right\}$ is stable with $b\left(\omega \right)={\sum }_{k=0}^{\infty }{a}_{-k}{\mathrm{e}}^{k\omega \mathrm{i}}$ for all $\omega \in \mathbb{R}$. Thus,

$$\left\{{∥{\left(T_n\left(a\right)\right)}^{-1}∥}_2\right\}=\left\{{∥{\left({\left(T_n\left(a\right)\right)}^{-1}\right)}^{\top }∥}_2\right\}=\left\{{∥{\left({\left(T_n\left(a\right)\right)}^{\top }\right)}^{-1}∥}_2\right\}=\left\{{∥{\left(T_n\left(b\right)\right)}^{-1}∥}_2\right\}$$

is bounded with $a\left(\omega \right)={\sum }_{k=-\infty }^0{a}_k{\mathrm{e}}^{k\omega \mathrm{i}}$ for all $\omega \in \mathbb{R}$. As $\left\{T_n\left(a\right)\right\}$ is stable, from Theorem 6 we conclude that $\left\{x_n\right\}$ is AWSS. ☐

6. Numerical Example and Conclusions

6.1. Example

Let $\left\{x_n\right\}$ be as in Definition 2 with $a_{-k}=0$ for all $k>1$. Observe that $\frac{{\sigma }^2}{{max}_{\omega \in [0,2\pi ]}{\left|a\left(\omega \right)\right|}^2}=\frac{{\sigma }^2}{(1+|a_{-1}{\left|\right)}^2}$. If $|a_{-1}|<1$ from Corollary 2 we obtain that the $AR\left(1\right)$ process $\left\{x_n\right\}$ is AWSS. Figure 1 shows $R_{x_{n:1}}\left(D\right)$, ${\tilde{R}}_{x_{n:1}}\left(D\right)$, and ${\breve{R}}_{x_{n:1}}\left(D\right)$ by assuming that $\left\{x_n\right\}$ is Gaussian, $a_{-1}=-\frac{1}{2}$, ${\sigma }^2=1$, $D=\frac{{\sigma }^2}{(1+|a_{-1}{\left|\right)}^2}=\frac{4}{9}$, and $n\le 100$. Figure 1 also shows the highest upper bound of $R_{x_{n:1}}\left(D\right)$ presented in Theorem 5, namely, $K_3(n,D)$. Observe that the figure bears evidence of the equalities and inequalities given in Equations (18) and (19).

6.2. Conclusions

The computational complexity of coding finite-length data blocks of Gaussian sources can be reduced by using any of the two low-complexity coding strategies here presented instead of the optimal coding strategy. Moreover, the rate does not increase if we use those strategies instead of the optimal one whenever the Gaussian source is AWSS and AR, and the considered data block is large enough.