WPBEST Best Tree selection
Usage: c = wpbest(f,w,J,cost);
[c,info] = wpbest(...);
Input parameters:
f : Input data.
w : Wavelet Filterbank.
J : Maximum depth of the tree.
Output parameters:
c : Coefficients stored in a cell-array.
info : Transform parameters struct.
[c,info]=WPBEST(f,w,J,cost) selects the best sub-tree info.wt from
the full tree with max. depth J, which minimizes the cost function.
Only one-dimensional input f is accepted. The supported formats of
the parameter w can be found in help for FWT. The format of the
coefficients c and the info struct is the same as in WFBT.
Please note that w should define orthonormal wavelet filters.
First, the depth J wavelet packet decomposition is performed using WPFBT.
Then the nodes are traversed in the breadth-first and bottom-up order
and the value of the cost function of the node input and cost of the
combined node outputs is compared. If the node input cost function value
is less than the combined output cost, the current node and all
possible descendant nodes are marked to be deleted, if not, the input is
assigned the combined output cost. At the end, the marked nodes are
removed and the resulting tree is considered to be a best basis (or
near-best basis) in the chosen cost function sense.
The cost parameter can be a cell array or an user-defined function handle.
accepting a single column vector. The cell array should consist of a
string, followed by a numerical arguments.
The possible formats are listed in the following text.
Additive costs:
---------------
The additive cost E of a vector x is a real valued cost function
such that:
..
E(x) = sum E(x(k)),
k
and E(0)=0. Given a collection of vectors x_i being coefficients in
orthonormal bases B_i, the best basis relative to E is the one for
which the E(x_i) is minimal.
Additive cost functions allows using the fast best-basis search algorithm
since the costs can be precomputed and combined cost of two vectors is
just a sum of their costs.
{'shannon'}
A cost function derived from the Shannon entropy:
..
E_sh(x) = -sum |x(k)|^2 log(|x(k)|^2),
k:x(k)~=0
{'log'}
A logarithm of energy:
..
E_log(x) = sum log(|x(k)|^2),
k:x(k)~=0
{'lpnorm',p}
Concentration in l^p norm:
..
E_lp(x) = ( sum (|x(k)|^p) ),
k
{'thre',th}
Number of coefficients above a threshold th.
Non-additive costs:
-------------------
Cost function, which is not additive cost but which is used for the
basis selection is called a non-additive cost. The resulting basis for
which the cost is minimal is called near-best, because the non-additive
cost cannot guarantee the selection of a best basis relative to the
cost function.
{'wlpnorm',p}
The weak-l^p norm cost function:
..
E_wlp(x) = max k^{\frac{1}{p}}v_k(x),
where 0<p<= 2 and v_k(x) denotes the k*-th largest absolute value
of x.
{'compn',p,f}
Compression number cost:
..
E_cn(x) = arg min |w_k(x,p) - f|,
k
where 0<p<= 2, 0<f<1 and w_k(u,p) denotes decreasingly sorted,
powered, cumulateively summed and renormalized vector:
k N
w_k(x,p) = sum v_j^p(x) / sum v_j^p(x)
j=1 j=1
where v_k(x) denotes the k*-th largest absolute value of x and
N is the number of elements of x.
{'compa',p}
Compression area cost:
..
E_ca(x) = N - sum w_k(x,p),
k
where 0<p<= 2 and w_k(u,p) and N as in the previous case.
Examples:
---------
A simple example of calling WPBEST :
f = gspi;
J = 8;
[c,info] = wpbest(f,'sym10',J,'cost','shannon');
% Use 2/3 of the space for the first plot, 1/3 for the second.
subplot(3,3,[1 2 4 5 7 8]);
plotwavelets(c,info,44100,90);
subplot(3,3,[3 6 9]);
N=cellfun(@numel,c); L=sum(N); a=L./N;
plot(a,'o');
xlim([1,numel(N)]);
view(90,-90);
xlabel('Channel no.');
ylabel('Subsampling rate / samples');
References:
M. V. Wickerhauser. Lectures on wavelet packet algorithms. In INRIA
Lecture notes. Citeseer, 1991.
C. Taswell. Near-best basis selection algorithms with non-additive
information cost functions. In Proceedings of the IEEE International
Symposium on Time-Frequency and Time-Scale Analysis, pages 13--16. IEEE
Press, 1994.
Package: ltfat