This is my understanding of 'energy compaction' and want to know if it is right. Take a vector. The energy of the vector is the sum of the squares of its elements. If A is the transformation matrix that is unitary, it can be proved that the energy in x and Ax are same. Energy conservation property. Energy compaction means that the energy of Ax=y is more concentrated in some elements compared to the distribution of energy in x. DCT is said to have energy compaction property. Does that mean, for any x, if A is DCT matrix, energy of y will be more concentrated when compared to the x. Does this happen to every x or x has to satisfy some properties to get this energy compaction?
Yes, I believe that your understanding of energy compaction is correct.
Does that mean, for any x, if A is DCT matrix, energy of y will be more concentrated when compared to the x.
No, it does not. All that is needed to prove that such is not the case is to show that there is an $x$ that is not compacted by the DCT. White noise, for example, would not be compacted by the DCT. The DCT is useful because in many real life situations the "signal" (e.g. audio, images, videos, etc.) tend to be "pinkish", i.e. tend to have most of their energy in the lower frequencies and so there is a natural assymetry that can be used to our advantage.
Another way to look at this is from an information theory perspective. If a signal is not "white" (i.e. it doesn't have the same power at all frequencies) that implies that there is some correlation between samples in the time domain, which means that the samples have "information" about the value of other samples. This mutual information implies that there is redundancy, and thus should be able to reduce the amount of data without losing information.
Does this happen to every x or x has to satisfy some properties to get this energy compaction?
For frequency-based transforms like the DCT it is clear from the above that what is needed is for the signal to be non-white. The more non-white it is, the more compaction can be achieved.
There are other kinds of transforms though, which presumably could compact signals based on other features. That is pretty much the whole point of compressed sensing.
$\begingroup$ Great. A very clear answer and thank you. How do you say about the performance of DCT with respect to white or non-white? what is the basis? $\endgroup$ Jul 13, 2014 at 19:12
Energy compaction means that a large proportion of the total signal energy is contained in a handful of coefficients. Several metrics could be defined to assess this:
- The number of coefficients accounting for a given percentage (for example 95%) of the total energy.
- The number of coefficients whose energy falls below a given percentage of the total energy.
- Any statistical measure of distribution peakedness - considering the coefficients as samples from a random distribution.
Does that mean, for any x, if A is DCT matrix, energy of y will be more concentrated when compared to the x. Does this happen to every x or x has to satisfy some properties to get this energy compaction?
This property is clearly not valid for any $x$. Otherwise, the transform could be applied iteratively on its result until data ends up being concentrated in a single coefficient.
While this may sound tautological, one could say that DCT has good energy compaction properties on signals which are made by combining a small number of sinusoidal elements; and more generally on signals in which there is an imbalance in the distribution of energy. This happens to be a good description of speech, music and "natural" images. Speech or music sounds are mostly made of a handful of sinusoidal harmonics, with less energy in the high frequencies. Images contain large uniform regions (Consider that a $N \times N$ pixels square has $N^2$ interior pixels and only $4N$ edge pixels).
But DCT will provide very poor energy compaction on signals with plenty of abrupt transitions, or any noise-like signal. In particular, if a sequence of DCT coefficients has good energy compaction, it will have abrupt transitions (a high coefficient surrounded by small values), and applying the DCT on this sequence itself will produce a sequence with poor energy compaction. There is no free lunch, repeatedly applying the transform on the transform's results will get you nowhere...