WPBEST - Best Tree selection

Usage

c = wpbest(f,w,J,cost);
[c,info] = wpbest(...);

Input parameters

Output parameters

Description

[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:

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:

\begin{equation*} E_{sh}(x) = -\sum_{k:x(k)\neq 0} \left|x(k)\right|^2 \log \left|x(k)\right|^2 \end{equation*}

{'log'}

A logarithm of energy:

\begin{equation*} E_{log}(x) = \sum_{k:x(k)\neq 0} \ln \left|x(k)\right|^2 \end{equation*}

{'lpnorm',p}

Concentration in \(l^p\) norm:

\begin{equation*} E_{lp}(x) = \left( \sum_{k} \left|x(k)\right|^p \right) \end{equation*}

{'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:

\begin{equation*} E_{wlp}(x) = \max k^{1/p}v_k(x), \end{equation*}

where \(0<p\leq 2\) and \(v_k(x)\) denotes the k-th largest absolute value of x.

{'compn',p,f}

Compression number cost:

\begin{equation*} E_{cn}(x) = \arg\min_{k} \left|w_k(x,p) - f\right|, \end{equation*}

where \(0<p\leq 2\), \(0<f<1\) and \(w_k(u,p)\) denotes decreasingly sorted, powered, cumulateively summed and renormalized vector:

\begin{equation*} w_k(x,p) = \frac{\sum_{j=1}^{k} v_j^p(x)}{\sum_{j=1}^{N} v_j^p(x)} \end{equation*}

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:

\begin{equation*} E_{ca}(x) = N - \sum_k w_k(x,p), \end{equation*}

where \(0<p\leq 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');