2.8 The karhuenen-loeve transform

Define the random vector

with mean zero and covariance matrix $R_X=E\left[X{X}^{*}\right]$ ; this matrix is symmetric and positive semidefinite.

Lemma 1 Every eigenvalue of $R_X$ is real and non-negative.

Let e be an eigenvector of $R_X$ with eigenvalue $\lambda$ .

The last statement falls out by the definite of positive semi-definite. We have $\lambda {\parallel e\parallel }^2\ge 0$ . Since ${\parallel e\parallel }^2\ge 0$ , it follows that $\lambda \ge 0$ , i.e. all the eigenvalues are non-negative. The eigenvectors of the matrix $R_X$ provide an orthonormal basis $\{{\phi }_1,{\phi }_2,...{\phi }_N\}$ , which can be collected into an orthonormal basis matrix $\phi =[{\phi }_1{\phi }_2...{\phi }_N]$ . Then let $y={\phi }^{*}x$ . We have:

Let us look at the adjoint of ${\phi }^{*}{R}_X$ :

If we take the adjoint again, we get

Going back to our derivation of $R_Y$ :

The matrix $\phi$ is known as the KLT matrix defined by $R_X$ . The transformation given by the KLT matrix provides a set of random variables $y_i=⟨{\phi }_i,x⟩$ that are uncorrelated.

Example 1 (Whitening Filter) For a random vector $X$ , $R_X$ has positive eigenvalues. Let us write $R_Y^{-1/2}=\mathrm{diag}({\lambda }_1^{-1/2},...{\lambda }_N^{-1/2})$ and $z=R_Y^{-1/2}y$ where $y={\phi }^{*}x$ . We have

The matrix $R_Y^{-1/2}{\phi }^{*}$ is known as a "whitening filter", as it maps an arbitrary random vector $x$ to a “white Gaussian noise” vector $z$ .

Example 2 (Transform Coding) Let $U:{\mathbb{C}}^n\to {\mathbb{C}}^n$ is a unitary operator. Assume we have a signal $x\in {\mathbb{C}}^n$ that we want to send it through a channel by only sending $k$ numbers or "items", where $k<n$ ; in words, we wish to compress the signal $x$ . The block diagram for the compression/transmission system is given in [link] .

We want to minimize $E\left[\parallel x-\widehat{x}\parallel \right]$ given $k$ by choosing the optimal transformation $U$ . We know $y=U^{*}x$ which implies $x=Uy$ since U is unitary. Therefore,

This means that we can minimize $\parallel y-\widehat{y}\parallel$ in place of $\parallel x-\widehat{x}\parallel$ . For simplicity, we choose a basic means of compression that preserves only the first $k$ entries of $y$ :

We then have $E\left[{\parallel x-\widehat{x}\parallel }^2\right]=E\left[{\parallel y-\widehat{y}\parallel }^2\right]=E[{\sum }_{i=k+1}^n|y_i{|}^2]={\sum }_{i=k+1}^{n}E\left[\right|y_i{|}^2]$ . Therefore,

It turns out that the choice of transform basis $U$ that minimizes this amount is provided by the eigendecomposition of $R_X$ , as specified by the following theorem.

Theorem 1 Let X be a length-n random vector with covariance matrix $R_X=E\left[x{x}^{*}\right]$ that has eigenvalues ${\lambda }_1\ge {\lambda }_2\ge {\lambda }_3...\ge {\lambda }_n\ge 0$ and matching eigenvectors ${\phi }_1,{\phi }_2,...{\phi }_N$ . Let $x_M$ be the orthogonal projection of x onto a subspace $M$ of dimension $k$ . Then

with equality if $M=\mathrm{span}\left(\{{\phi }_1,{\phi }_2,...{\phi }_k\}\right)$ .

From equation [link] , we have

where $R_X=\Phi \Lambda {\Phi }^T$ is the eigendecomposition of $R_X$ . Now, since

we have that $u_i^T\Phi \Lambda {\Phi }^T{u}_i={\left({\Phi }^T{u}_i\right)}^T\Lambda {\Phi }^T{u}_i={\sum }_{i=j}^n{\left|⟨u_i,{\phi }_j⟩\right|}^2{\lambda }_j$ . Plugging this into [link] , we have

Now, denote ${\alpha }_j={\sum }_{i=k+1}^n{\left|⟨u_i,{\phi }_j⟩\right|}^2$ , and see that

as all $u_i$ are unit-norm. Now, we have that

Since the ${\lambda }_k$ are monotonically decreasing, we have that

If we set $M=\mathrm{span}\{{\phi }_1,{\phi }_2,...{\phi }_k\})$ , (i.e., $U=\Phi$ ) then it is easy to check that

proving the theorem.

Example 3 (Transform Coding) Transform coding is a common scheme for data compression that leverages the Karhuenen-Loève transform. Examples include JPEG and MP3. In particular, JPEG can be broadly described as follows:

1. Take the image $x$ and create tiles of size $8\times 8$ . We assume that the tiles are draws from a random variable $X$ , i.e., the tiles $x_1,x_2...\in {\mathbb{R}}^{64}$ with $R_X=\frac{1}{n}{\sum }_{i=1}^n{x}_i{x}_i^T$
2. Compute the KLT of the tile random variable $X$ from $R_X$ by obtaining its eigendecomposition $R_X=\Phi \Lambda {\Phi }^T$ .
3. Compute KLT coefficients for each block as $c_i={\Phi }^T{x}_i$ .
4. Pick as many coefficients of $c_i$ as allowed by communications or storage constraints; save them as the compressed image.
5. Load saved coefficients and append zeros to build coefficient vector ${\widehat{c}}_i$ .
6. Run inverse KLT to obtain the decompressed tiles ${\widehat{x}}_i=\Phi {\widehat{c}}_i$ .
7. Reassemble the image from the decompressed tiles.

In practice, it is not desirable to recompute the KLT for each individual image. Thus, the JPEG algorithm employs the discrete cosine transform (DCT). It turns out that the DCT is a good approximation of the KLT for tiles of natural images. Additionally, instead of selecting a subset of the coefficients, they are quantized to varying quality/error according to their index and the total amount of bits available.