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.
