3.3 The optimal orthogonal transform

An introduction to source-coding Page 1 / 1

In this module, we establish that for transform coding, the optimum orthogonal tranform is the Karhunen-Loeve Transform (KLT). Related properties are also discussed.

Ignoring the effect of transform choice on uniform-quantizer efficiency γ _y , Gain Over PCM suggests that TC reconstruction error can be minimized by choosing the orthogonal transform T that minimizes the product of coefficient variances. (Recall that orthogonal transforms preserve the arithmetic averageof coefficient variances.)
Eigen-analysis of autocorrelation matrices
Say that R is the N × N autocorrelation matrix of a real-valued, wide-sense stationary, discrete time stochastic process.The following properties are often useful:
1. R is symmetric and Toeplitz. (A symmetric matrix obeys $R = R^{t}$ , while a Toeplitz matrix has equal elements on all diagonals.)
2. R is positive semidefinite or PSD. (PSD means that $x^{t} Rx \geq 0$ for any real-valued x .)
3. R has an eigen-decomposition
  $R = V Λ V^{t},$
  where V is an orthogonal matrix ( $V^{t} V = I$ ) whose columns are eigenvectors ${v_{i}}$ of R :
  $V = (v_{0} v_{1} \dots v_{N - 1}),$
  and Λ is a diagonal matrix whose elements are the eigenvalues ${λ_{i}}$ of R :
  $Λ = diag (λ_{0} λ_{1} \dots λ_{N - 1}) .$
4. The eigenvectors ${λ_{i}}$ of R are real-valued and non-negative.
5. The product of the eigenvectors equals the determinant ( $\prod_{k = 0}^{N - 1} λ_{k} = | R |$ ) and the sum of the eigenvalues equals the trace( $\sum_{k = 0}^{N - 1} λ_{k} = \sum_{k} {[R]}_{k, k}$ ).
The KLT: Using the outer product,
$y (m) y^{t} (m) = (\begin{matrix} y_{0}^{2} (m) & y_{0} (m) y_{1} (m) & \dots & y_{0} (m) y_{N - 1} (m) \\ y_{1} (m) y_{0} (m) & y_{1}^{2} (m) & \dots & y_{1} (m) y_{N - 1} (m) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ y_{N - 1} (m) y_{0} (m) & y_{N - 1} (m) y_{1} (m) & \dots & y_{N - 1}^{2} (m) \end{matrix})$
Using A k , k to denote the k t h diagonal element of a matrix A , matrix theory implies
$\begin{matrix} \prod_{k = 0}^{N - 1} σ_{y_{k}}^{2} & = & \prod_{k = 0}^{N - 1} {[E {y (m) y^{t} (m)}]}_{k, k} \\ \geq & |E {y (m) y^{t} (m)}| \\ = & |T E {x (m) x^{t} (m)} T^{t}| \\ = & |\underset{I}{\underset{︸}{T^{t} \cdot T}}, \underset{R_{x}}{\underset{︸}{E {x (m) x^{t} (m)}}}, \underset{I}{\underset{︸}{T^{t} \cdot T}}| since | T^{t} A | = | A | = | AT | for orthogonal T \\ = & \prod_{k = 0}^{N - 1} λ_{k} (R_{x}), \end{matrix}$
thus minimization of ∏ k σ y k 2 would occur if equality could be established above.Say that the eigen-decomposition of the autocorrelation matrix of x ( n ) , which we now denote by R _x , is
$R_{x} = V_{x} Λ_{x} V_{x}^{t}$
for orthogonal eigenvector matrix V _x and diagonal eigenvalue matrix Λ _x . Then choosing T = V x t , otherwise known as the Karhunen-Loeve transform (KLT), results in the desired property:
$E {y (m) y^{t} (m)} = E {V_{x}^{t} x (m) x^{t} (m) V_{x}} = V_{x}^{t} R_{x} V_{x} = V_{x}^{t} V_{x} Λ_{x} V_{x}^{t} V_{x} = Λ_{x} .$
To summarize:
1. the orthogonal transformation matrix T minimizing reconstruction error variance has rows equal to the eigenvectorsof the input's $N \times N$ autocorrelation matrix,
2. the variances of the optimal-transform outputs ${σ_{y_{k}}^{2}}$ are equal to the eigenvalues of the input autocorrelation matrix, and
3. the optimal-transform outputs ${y_{0} (m), \dots, y_{N - 1} (m)}$ are uncorrelated. (Why? Note the zero-valued off-diagonal elements of $R_{y} = E {y (m) y^{t} (m)}$ .)
Note that the presence of mutually uncorrelated transform coefficients supports our approach of quantizing each transform output independentlyof the others.

$2 \times 2$ Klt coder

Recall Example 1 from "Background and Motivation" with Gaussian input having $R_{x} = (\begin{matrix} 1 & ρ \\ ρ & 1 \end{matrix}) .$ The eigenvalues of R _x can be determined from the characteristic equation $|R_{x} - λ I| = 0$ :

|\begin{matrix} 1 - λ & ρ \\ ρ & 1 - λ \end{matrix}| = {(1 - λ)}^{2} - ρ^{2} = 0 \Leftrightarrow 1 - λ = \pm ρ \Leftrightarrow λ = 1 \pm ρ .

The eigenvector v ₀ corresponding to eigenvalue $λ_{0} = 1 + ρ$ solves $R_{x} v_{0} = λ_{0} v_{0}$ . Using the notation $v_{0} = (\begin{matrix} v_{00} \\ v_{01} \end{matrix})$ and $v_{1} = (\begin{matrix} v_{10} \\ v_{11} \end{matrix})$ ,

\begin{matrix} v_{00} + ρ v_{01} & = & (1 + ρ) v_{00} \\ ρ v_{00} + v_{01} & = & (1 + ρ) v_{01} \end{matrix} \Leftrightarrow v_{01} = v_{00} .

Similarly, $R_{x} v_{1} = λ_{1} v_{1}$ yields

\begin{matrix} v_{10} + ρ v_{11} & = & (1 - ρ) v_{10} \\ ρ v_{10} + v_{11} & = & (1 - ρ) v_{11} \end{matrix} \Leftrightarrow v_{11} = - v_{10} .

For orthonormality,

v_{00}^{2} + v_{01}^{2} = 1 \Rightarrow v_{0} = \frac{1}{\sqrt{2}} (\begin{matrix} 1 \\ 1 \end{matrix})

v_{10}^{2} + v_{11}^{2} = 1 \Rightarrow v_{1} = \frac{1}{\sqrt{2}} (\begin{matrix} 1 \\ - 1 \end{matrix}) .

Thus the KLT is given by $T = V_{x}^{t} = {(v_{0} v_{1})}^{t} = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ .
Using the KLT and optimal bit allocation, the error reduction relative to PCM is

\frac{σ_{r}^{2} |_{TC}}{σ_{r}^{2} |_{P C M}} = \frac{γ_{y}}{γ_{x}} \cdot \frac{\sqrt{(1 + ρ) (1 - ρ)}}{\frac{1}{2} ((1 + ρ) + (1 - ρ))} = \sqrt{1 - ρ^{2}}

since $γ_{y} = γ_{x}$ for Gaussian $x (n)$ . This value equals 0.6 when $ρ = 0.8$ , and 0.98 when $ρ = 0.2$ (compare to Figure 2 from "Background and Motivation" ).

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding. OpenStax CNX. Sep 25, 2009 Download for free at http://cnx.org/content/col11121/1.2

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding' conversation and receive update notifications?

Ask

©flickr: U.S.	Molecular Cellular Biology By Ann Schlosser Start Quiz
	8 AP 08 Appendicular Skeleton MCQ By OpenStax Start Quiz
©flickr: Abraham	1 Biology 1 By Sarah Warren Start Test
	Worldport Outside By Rachel Carlisle Start Quiz
	Fluid Mechanics MCQ By Stephanie Redfern Start Quiz
	2 Timeshare 2 By Jams Kalo Start Quiz
©flickr: Hey	Anatomy Physiology Final By Joli Julianna Start Test
	23 AP 23 Digestive System MCQ By OpenStax Start Quiz
	4 Neuroanatomy 04 Spinal Cord Brain Stem By Stephen Voron Start Quiz
	12 AP 12 Nervous System Essay By OpenStax Start Flashcards

3.3 The optimal orthogonal transform

Eigen-analysis of autocorrelation matrices

2 × 2 Klt coder

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

$2 \times 2$ Klt coder