6
$\begingroup$

I've read in multiple places that DCT decorrelates Toeplitz matrices and images usually have Toeplitz structure. Can you explain with an example how DCT decorrelates a Toeplitz matrix?

Example for DFT:

DFT decorrelates circular matrices. This is how I was able to understand that.
Suppose $X$ is a matrix whose correlation matrix is not diagonal. We want to find a transformation $Y=AX$ such that correlation matrix of $Y$ is diagonal.
$$\mathbb{E}[YY^T] = \mathbb{E}[AXX^TA^T] = A\mathbb{E}[XX^T]A^T$$ Let the Eigen Value Decomposition be $$\mathbb{E}[XX^T]=U\Lambda U^T$$
Then $$A=U^T \qquad\text{gives}\qquad\mathbb{E}[YY^T]=U^TU\Lambda U^TU = \Lambda$$ which is diagonal.
So given a matrix, its eigenvector matrix decorrelates it.

Consider a circular matrix $$A = \begin{bmatrix} a & b & c \\ c & a & b \\ b & c & a \\ \end{bmatrix}$$ A $3 \times 3$ DFT matrix is given by $$\begin{bmatrix} 1 & 1 & 1 \\ 1 & w & w^2 \\ 1 & w^2 & w \\ \end{bmatrix}\qquad\text{and}\qquad w^3 = 1 $$

We can easily see that all the columns (or rows since it is symmetric) of the above matrix are eigenvectors of the considered circular matrix $A$. Thus DFT decorrelates circular matrices.

Is it possible to show in a similar way that DCT decorrelates a Toeplitz matrix?

PS: The answers here, here and here didn't solve my doubt.

$\endgroup$
  • $\begingroup$ Doubts take time to be overcome. Do you have suggestions for more details? $\endgroup$ – Laurent Duval Jul 17 at 23:10
  • 1
    $\begingroup$ Yeah, you're right. I'm pretty much satisfied with the current answer. It cites the paper that talks about getting DCT basis vectors as approximate eigenvectors of toeplitz matrix. I think it would be good to add that derivation. $\endgroup$ – Nagabhushan S N Jul 18 at 3:41
  • $\begingroup$ Derivation of what, precisely? $\endgroup$ – Laurent Duval Jul 18 at 13:56
  • 1
    $\begingroup$ How DCT (matrix) comes out as an approximation of eigenvectors of toeplitz matrix. $\endgroup$ – Nagabhushan S N Jul 18 at 18:05
  • 1
    $\begingroup$ I have added a reference to te 1991 paper, mentioned the intuition from Chebyshev polynomials $\endgroup$ – Laurent Duval Jul 19 at 17:06
6
+50
$\begingroup$

[EDIT] In 1991, Nasir Ahmed wrote: "How I Came Up with the Discrete Cosine Transform". Interesting to read, on how he was inspired by Chebyshev polynomials, and on how he didn't get funding, for a tool at the heart of JPEG and MP3.

Natural images are not very stationary, but locally, their covariance is often modeled by a first- or second-order process. Being able to "concentrate" those matrices is one key to efficient compression (not the only one, however).

In different words: one aims at projecting, or representing, the pixels in another system of vectors (a basis, a frame), such that the information content of the picture is better represented, or sparser. Classically, one preserves energy (hence orthogonal or close to orthogonal transformations. Two main options:

  1. compute or learn the best adaptive representation from each image. PRO: more efficient in compaction; CON: computationally expensive and storage lost because should be sent for decoding
  2. use a known and fixed transform (or a set of known transforms). PRO: fast; CON: less optimal.

The DCT is option 2, with the performance of option 1: a fixed transform with close to adaptive performance, for most standard images. It worked, people still use JPEG and MP3, at the heart of which one finds the DCT.

The goal is thus to find the eigenvectors of such (covariance matrices, with less computational cost than matrix diagonalisation. The original DCT (DCT-II) from Discrete Cosine Transform (1974) aimed at finding basis vectors that could approximately diagonalize the first-order Markov Toeplitz matrix:

$$ \left[\begin{array}{c} 1&\rho& \cdots &\rho^{N-1}\\ \rho& 1&\cdots &\rho^{N-2}\\ \vdots& \vdots&\ddots &\vdots\\ \rho^{N-1}& \rho^{N-2}&\ddots &1\end{array}\right] $$

The original motivation for defining the DCT was that its basis set provided a good approximation to the eigenvectors of the class of Toeplitz matrices that constitutes the autocovariance matrix of a first-order stationary Markov process, with the result that it had a better performance than the discrete Fourier transform (DFT) and some other transforms [l], 3, 4 with respect to such kinds of processes. In fact, as shown in 4, the DCT is asymptotically equivalent to the Karhunen-Loeve transform (KLT) of a first-order stationary Markov process as $\rho$ tends to 1, where $\rho$ is the correlation coefficient.

Looking at the basis functions for $\rho=0.9$ eigenvectors and DCT

the match is pretty good, and it turns out that the processing performance is close as well to that of the Karhunen-Loève transform.

In their 1995 paper Diagonalizing Properties of the Discrete Cosine Transforms, the authors provide an extension of the above property.

In this paper, we obtain the eight types of DCT’s as the complete orthonormal set of eigenvectors generated by a general form of matrices in the same way as the discrete Fourier transform (DFT) can be obtained as the eigenvectors of an arbitrary circulant matrix. These matrices can be decomposed as the sum of a symmetric Toeplitz matrix plus a Hankel or close to Hankel matrix scaled by some constant factors.

In 1991, Nasir Ahmed wrote: "How I Came Up with the Discrete Cosine Transform". Interesting to read, some excerpts:

What intrigued me was that the KLT was indeed the optimal transform on the basis of the meansquare- error criterion and the first-order Markov process model, and yet there was no efficient algorithm available to compute it. As such, the focus of my research was to determine whether it would be possible to come up with a good approximation to the KLT that could be computed efficiently.

to study a “cosine transform” using Chebyshev polynomials

The motivation for looking into such “cosine functions” was that they closely resembled KLT basis functions for a range of values of the correlation coefficient $\rho$ (in the covariance matrix).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Very intetresting! $\endgroup$ – Black Yasmin Jul 16 at 15:37
  • 2
    $\begingroup$ I very much like answer with old paper. Its like history lesson :) $\endgroup$ – Black Yasmin Jul 16 at 15:41
  • 2
    $\begingroup$ Our past casts long shadows. I really like digging into old papers, sometimes they are even not available in digital form, or not "researchable' (no OCR), so I still have xerox copies of xerox copies, in piles and boxes, that I browse, from time to time. Most often, a good idea is unnoticed, overlooked, not in a "common enough" language, rediscovered, etc. $\endgroup$ – Laurent Duval Jul 16 at 15:48
  • 1
    $\begingroup$ Nice answer! And, agreed, reading old papers can be enlightening. The motivations are different and explanations are often better than many of today's papers. $\endgroup$ – Peter K. Jul 18 at 18:48
  • 1
    $\begingroup$ the decomposition also lends itself to better use of quantization than the original. If you de/recompose an image and quantize the diagonal it is surprising how coarse you can get before it becomes visually unrecognizable, compared to quantizing individual pixels, keeping the total number of bits equal $\endgroup$ – P2000 Jul 19 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.