Comparison with Other Orthogonal Transforms

To illustrate signal decorrelation and energy compaction, the two desirable properties of the KLT discussed above, we compare the KLT with other orthogonal transforms such as identity transform I (no transform), Walsh-Hadamard transform (WHT) , discrete cosine transform DCT and discrete Fourier transform DFT in the following two examples.

Example 1

Each row of a 256 by 256 image of the clouds (left panel in the figure below) can be treated as an observation (instantiation) of a 1D random vector ${\bf x}$ (with 256 components). Different orthogonal transforms ${\bf y}={\bf A}^T{\bf x}$ are applied to ${\bf x}$, and the corresponding covariance matrices ${\bf\Sigma}_y$ are obtained and compared to see how well they decorrelate the signal and compact its energy. The figure below shows the original image on the left and three covariance matrices corresponding to no transform (identify transform matrix), DCT, and KLT. As the behaviors of DFT and WHT are very similar to that of DCT, they are not discussed here. A conversion $y=x^{0.3}$ has applied to the intensity of the images for covariance matrices for the low values to be still visible.

In the second panel from left representing the covariance matrix of the original signal without any transform, there exist some bright areas off the main diagonal, indicating that many signal components are highly correlated. In the third panel showing the covariance matrix after a DCT, the values of the off diagonal elements are much lower, indicating that the signal components are much decorrelated. Finally, in the right-most panel showing the covariance matrix after a KLT, the off diagonal elements are all zero, indicating that the components are completely decorrelated.

The effect of energy compaction can also be seen in the figure above, as the brightness of the diagonal is gradually reduced from top-left to bottom right. This effect is more clearly shown in the figure below, where the energy distribution among all elements is plotted. The flat curve is the original energy distribution (no transform), the most compact (high on the left and low on the right) is the distribution after PCT. The intermediate ones are by DCT and WHT with similar effects.

The effect of energy compaction can also be illustrated by the table below showing the number of components needed in order to keep certain percentage of the total dynamic energy (information). For example, if one wants to keep 99% of the total energy contained in the original signal, 250 out of 256 components are needed if no transform is carried out, 97 out of 256 are needed after DCT, and only 55 are needed after KLT. Note that DCT's performance is reasonably close to that of the optimal PCT in this case.

Percentage:	90%	95%	99%	100%
I:	209	230	250	256 (all)
DCT:	10	22	97	256 (all)
PCT:	7	13	55	256 (all)

Based on the example above, some observations could be made.

• First, it seems all orthogonal transforms have the tendency of decorrelating the given signals, and KLT does it optimally as the signal is completely decorrelated after the transform. Specifically, given the value of the current sample of a signal as a function of time (e.g., the temperature as a function of time), the value of its next sample can be predicted with reasonable confidence to be close to the current one, i.e., two consecutive time samples are highly correlated. On the other hand, after an orthogonal transform, such as Fourier transform, knowing the magnitude (or the energy proportional to the magnitude squared) of a certain frequency component, one has little idea in terms of the magnitude (or the energy) of the next frequency component, i.e., the two components are much less correlated than the time samples before the transform. The same is true for other transforms such as DCT and WHT.

• Second, at the same time, it also seems to be the case that an orthogonal transform tends to compact the energy contained in the signal into a small number of signal components. For example, after Fourier transform, most of the energy will be concentrated in the DC component and a relatively small number of low frequency components. Most of the high frequency components carry little energy. The same is also true for DCT and WHT.

Based on these observations, can we conclude that the signal correlation can always be reduced by an orthogonal transform, and the energy is always more compacted after a transform? The answer is, it depends on the specific signal being processed. The claim that orthogonal transform always tends to reduce the signal correlation is based on the underlying assumption that signals in general are continuous and smooth due to the nature of most physical processes. However, in some cases in which the assumption is not necessarily valid, orthogonal transforms such as DCT may not perform well, sometimes the signal correlation may even increase after the transform. Also the energy is not necessarily compacted by the transform. This is illustrated in the following example.

Example 2

The left panel of the figure below is an image showing the texture of sand, where the pixels are not correlated as in the previous example, since the color of a grain of sand is not related to those of the neighboring grains. The second panel shows the covariance matrix of the row vectors of the image, where all off-diagonal elements have very low values, indicating the pixels are hardly correlated. In comparison, the third panel shows the covariance matrix after DCT, with most of the off-diagonal elements having higher values than before the transform, indicating the increased correlation among the signal components. Finally, the covariance matrix after KLT shown in the last panel is diagonalized, indicating the complete decorrelation of the signal.

Again, in term of energy compaction, the energy distribution plots shown below indicate that DCT does not make any improvement compared to the original signal (the two very similar flat plots), but KLT can still compact the energy (the other plot high on the left low on the right), although this compaction by KLT is much less effective than in the previous example.

From the two examples above, one can see that whether an orthogonal transform can decorrelate the signal or not depends on the nature of the signal. If it is initially highly correlated, as is true for most of the physical signals, orthogonal transform may indeed significantly decorrelate the signal, as well as compact its energy. This is essentially way orthogonal transforms are widely used in data processing. However, in the not too likely case where the signal is not highly correlated to start with, an orthogonal transform may not reduce the signal correlation, sometimes it may even increase it, as shown in the second example above. Only the KLT will always guarantee that the signal will be complete decorrelated, and its energy optimally compacted.

Although KLT is indeed optimal, other transforms are still widely used for two reasons. First, KLT transform matrix is composed of the eigenvectors of the covariance matrix ${\bf\Sigma}_x$ of the signal ${\bf x}$, which can be estimated only if sufficient amount of data is available. Second, the computational cost for KLT is much higher than other transforms, as not only do we need to estimate the covariance matrix ${\bf\Sigma}_x$ and solve its eigenvalue problem to obtain the transform matrix ${\bf\Phi}$, but also, as there does not exist any fast algorithm for the actual KLT transform ${\bf y}={\bf\Phi}^T {\bf x}$, the complexity of the transform is $O(N^2)$, instead of $N log_2 N$ for most of other transforms.