Wavelet transform in the discrete domain

Question

I quote a part of the 5.9.1 section from "The Elements of Statistical Learning" book as the following:

"Notice that since these spaces are orthogonal, all the basis function are orthonormal. In fact, if the domain is discrete with $ N=2^J$ (time) points, this is as far as we can go. There are $2^j$ basis elements at level $j$, and adding up, we have a total of $2^J - 1$ elements in the $W_j$, and one in $V_0$."

At here, I can write $f(x)$ by the following formula: $$ f(x) = c\phi(x) + \sum_{j=0}^{2^J-1}\sum_{k=0}^{2^j-1}d_{jk}\psi_{jk}(x)$$

But I don't understand why we need to have $2^J$ levels and each level has $2^j$ basis function elements ?

Answer 1

I believe you should be talking about having $J$ levels, not $2^J$. This number is a maximum, given the data is of length $2^J$. The indices can used in tricky ways with wavelets, and vary along publications. One can index with increasing or decreasing $j$, or with $2^j$ (dyadically) instead of $j$ (or $-j$). I will try to follow your conventions.

So you start with $2^J$ samples. Assume the data are in space $V_J$ (scaling functions, of dimension $2^J$), and that the space has an orthogonal basis. The two-scale relationship provides you with an axiomatized series of nested subspaces $V_j$, with $V_j \supset V_{j-1} $, and a handful of properties I keep aside for the moment. Basically, $V_{j-1}$ has two times less degrees of freedom than $V_{j}$, so in the finite case, its dimension is divided by $2$, hence its basis will be half-size. $V_{j-1}$ admits a supplementary space $W_{j-1}$ (for wavelets), of half size too.

if you project data onto both the nested space $V_{J-1} \subset V_J$ and the supplementary $W_{J-1}$, you get a pair of projection coefficients, the approximation ones on $V_{J-1}$, the details ones on $W_{J-1}$. You get $2^{J-1}$ coefficients on both sides. Then you iterate the above procedure on space $V_{J-1}$, which you split onto $V_{J-2} \subset V_{J-1}$ and the supplementary $W_{J-2}$, etc.

You can do this until you spill your budget of coefficients in some $V_j$: by dividing by two, starting from $2^J$, you end up with only one coefficient in $V_0$, no further splitting allowed.