1
$\begingroup$

I have been trying to find out how can the discrete wavelet transform (DWT) be possible to reduce dimension of data.

Then I saw the question which is seemingly related to my work:

But after seeing the post, I have a question in my mind.

Is it possible to say that setting DWT coefficient values to zero which is lower than threshold is the dimensional reduction?

I mean, suppose we have 5 dimensional vector <1,4,3,5,2> which can be thought as result of DWT.
And after setting some vector's values to zero in case the threshold is 3, we get <0,4,3,5,0>.

I think it seems inappropriate to say that this is the dimensional reduction. Because I understand the dimensional reduction is the actually reduction such <1,4,3,5,2> -> <4,3,5>

So I searched some paper to give some light on my curiousness. Some researches say that they select DWT coefficients for dimensional reduction.

But I wander how it can be possible. Because,,, what if we want to reconstruct original signal or data from DWT coefficients?

I guess ,by selecting some values from DWT coefficients (<1,4,3,5,2> -> <4,3,5>), they already lose the meaning of original data. It should be <0,4,3,5,0> not <4,3,5>. So I think they should post some encoding-decoding technique to replace selected DWT coefficients (<4,3,5> -> <0,4,3,5,0>), but they don't.

Am I misunderstanding?

$\endgroup$
0
$\begingroup$

I totally agree with your interrogations, and I appreciate the reference that was not on my watch.

Basically, dimension reduction supposes that, for sufficiently informative data $d$ in dimension $N$, there exists a close approximation that lives in a very lower dimension $M$, i.e. that can be parametrized in a different $M$ dimensional fashion. For instance, 2D points gathered around a circular shape don't really need 2 coordinates, as they could be approximated by a 1D variable (an angle for instance). As one can see, the reduction doesn't not have to be linear. Basically, if the data in a huge space can be approximated by a regular-enough surface (e.g. a manifold) of small dimension, we have it!

Non-linear can be quite complicated. And at least-locally, people can look at linear combinations of simple shapes $s_k$, of course with little non-zero combinations, compared to a canonical set of vectors $e_n$

$$d = \sum_1^N d_n.e_n \sim \sum_1^M a_m .s_m\,.$$

In practical PCA, one first computes eigenvectors (that depend on data statitics, and heuristically on its covariance matrix). And sometimes performs dimension reduction keeping the $M$ largest eigenvalues, that best explain the energy of the signal. How do we recover the data then? Using the $M$ "largest" vectors, whose knowledge was somewhat based on the whole original data (or at least their second order statistics).

With practical DWT, the paradigm changed a little. You assume that the data is somehow piece-wise regular, and some fixed set of wavelet vectors is used to project the data. It does not depend on the data anymore. Under some conditions, one expect that the coefficients with highest magnitude approximate the data well. What is indeed misleading, as you mentioned, is that one should know to which wavelet vector coordinates they are attached.

The hidden notion of the best $M$-estimation (keep the best $M$ wavelet coefficients for approximation) is a complicated issue, highly non-linear in a second sense of linearity.

But it appear that in practice, keeping the highest coefficients can both serve as compression and denoising, and for a given data, the structure of the highest coefficients can be arranged in trees, that can keep track of coefficient location, without too much cost. Moreover, a second dimension reduction appears: the quantization of the data. By keeping only the most-significant bits of the coefficients, the data keeps being nicely approximated by less coefficients and less bits at the same time. This is about what you refer to as "encoding-decoding technique".

All of the above is subject to more precision: which is your approximation space and distance, but wavelets are good approximants in many theoretical spaces.

So yes, putting coefficients to zero is a little bit of cheating, but this appears to be sound for several classes of piecewise regular data, and works correctly in practice.

$\endgroup$

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.