# wmpdictionary

Dictionary for matching pursuit

## Syntax

MPDICT = wmpdictionary(N)
[MPDICT,NBVECT] = wmpdictionary(N)
[MPDICT,NBVECT]= wmpdictionary(N,Name,Value)
[MPDICT,NBVECT,LST] = wmpdictionary(N,Name,Value)
[MPDICT,NBVECT,LST,LONGS] = wmpdictionary(N,Name,Value)

## Description

MPDICT = wmpdictionary(N) returns the N-by-P dictionary, MPDICT, for the default subdictionaries {{'sym4',5},{'wpsym4',5},'dct','sin'}. The column dimension of MPDICT depends on N.

[MPDICT,NBVECT] = wmpdictionary(N) returns the row vector, NBVECT, which contains the number of vectors in each subdictionary. The order of the elements in NBVECT corresponds to the order of the subdictionaries and any prepended or appended subdictionaries. The sum of the elements in NBVECT is the column dimension of MPDICT.

[MPDICT,NBVECT]= wmpdictionary(N,Name,Value) returns the dictionary, MPDICT, using additional options specified by one or more Name,Value pair arguments.

[MPDICT,NBVECT,LST] = wmpdictionary(N,Name,Value) returns the cell array, LST, with descriptions of the subdictionaries.

[MPDICT,NBVECT,LST,LONGS] = wmpdictionary(N,Name,Value) returns the cell array, LONGS, containing the number of vectors in each subdictionary. LONGS is only useful for wavelet subdictionaries. In wavelet subdictionaries, the corresponding element in LONGS gives the number of scaling functions at the coarsest level and wavelet functions by level. See Visualize Haar Wavelet Dictionary for an example using LONGS.

## Input Arguments

 N A positive integer equal to the length of your input signal. The dictionary atoms are constructed to have N elements. N equals the row dimension of the dictionary, MPDICT.

### Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside quotes. You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

 'addbeg' Prepended subdictionary. The prepended subdictionary is an N-by-M matrix where N is the length of the input signal. wmpdictionary does not check that the M column vectors of the prepended dictionary form a basis. If you do not specify a value for lstcpt, the subdictionary is prepended to the default dictionary. The column vectors in the prepended subdictionary do not have to be unit-norm. 'addend' Appended subdictionary. The appended subdictionary is a N-by-M matrix where N is the length of the input signal. wmpdictionary does not check that the M column vectors of the prepended dictionary form a basis. If you do not specify a value for lstcpt, the subdictionary is appended to the default dictionary. The column vectors in the appended subdictionary do not have to be unit-norm. 'lstcpt' A cell array of cell arrays with valid subdictionaries. Each cell array describes one subdictionary. Valid subdictionaries are: A valid Wavelet Toolbox™ orthogonal or biorthogonal wavelet family short name with the number of vanishing moments and an optional decomposition level and extension mode. For example, {'sym4',5} denotes the Daubechies least-asymmetric wavelet with 4 vanishing moments at level 5 and the default extension mode 'per'. If you do not specify the optional level and extension mode, the decomposition level defaults to 5 and the extension mode to 'per'.A valid Wavelet Toolbox orthogonal or biorthogonal wavelet family short name preceded by wp with the number of vanishing moments and an optional decomposition level and extension mode. For example, {'wpsym4',5} denotes the Daubechies least-asymmetric wavelet packet with 4 vanishing moments at level 5. If you do not specify the optional level and extension mode, the decomposition level defaults to 5 and the extension mode to 'per'.'dct' Discrete cosine transform-II basis. The DCT-II orthonormal basis is: ${\varphi }_{k}\left(n\right)=\left\{\begin{array}{ll}\frac{1}{\sqrt{N}}\hfill & k=0\hfill \\ \sqrt{\frac{2}{N}}\mathrm{cos}\left(\frac{\pi }{N}\left(n+\frac{1}{2}\right)k\right)\hfill & k=1,2,\dots ,N-1\hfill \end{array}$'sin' Sine subdictionary. The sine subdictionary is ${\varphi }_{k}\left(t\right)=\mathrm{sin}\left(2\pi kt\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }k=1,2,\dots ⌈\frac{N}{2}⌉\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }0\le t\le 1$where t is a linearly-spaced N-point vector.'cos' Cosine subdictionary. The cosine subdictionary is ${\varphi }_{k}\left(t\right)=\mathrm{cos}\left(2\pi kt\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }k=1,2,\dots ⌈\frac{N}{2}⌉\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }0\le t\le 1$where t is a linearly-spaced N-point vector.'poly' Polynomial subdictionary. The polynomial subdictionary is: ${p}_{n}\left(t\right)={t}^{n-1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }n=1,2,\dots 20\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }0\le t\le 1$where t is a linearly-spaced N-point vector.'RnIdent' The shifted Kronecker delta subdictionary. The shifted Kronecker delta subdictionary is: ${\varphi }_{k}\left(n\right)=\delta \left(n-k\right)\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }k=0,1,\dots N$ Default: {{'sym4',5},{'wpsym4',5},'dct','sin'}

## Output Arguments

 MPDICT Matching pursuit dictionary. MPDICT is an N-by-P matrix with the row dimension, N, equal to the length of the input signal. The column dimension of the matrix depends on the size of the concatenated subdictionaries. NBVECT Number of vectors in subdictionaries. NBVECT is a row vector containing the number of elements in each subdictionary. The order of the elements in NBVECT corresponds to the order of the subdictionaries and any prepended or appended subdictionaries. LST Cell array describing the dictionary. LST is a 1-by-N cell array where N is the number of subdictionaries. Each element of the cell array contains a description of a subdictionary. If you specify a prepended or appended subdictionary, the first element of LST is 'AddBeg' or 'AddEnd'. If you specify a level for the wavelet or wavelet packet, the corresponding element of LST is a 1-by-2 cell array containing the wavelet or wavelet packet name in the first element and the level in the second element. LONGS Cell array containing the number of elements for each subdictionary. LONGS is useful only for wavelet subdictionaries. If you specify a wavelet subdictionary, the corresponding element of LONGS provides the number of scaling functions at the coarsest level and the number of wavelets at each level. See Visualize Haar Wavelet Dictionary for an example using LONGS.

## Examples

collapse all

Create the default dictionary to represent a signal of length 100.

mpdict = wmpdictionary(100);

Create a DCT and shifted Kronecker delta dictionary to represent a signal of length 100.

mpdict = wmpdictionary(100,'lstcpt',{'dct','RnIdent'});

Create a Haar wavelet packet (level 2) and DCT dictionary. Return the number of atoms in each subdictionary.

[mpdict,nbvect] = wmpdictionary(100,'lstcpt',{{'wphaar',2},'dct'});

Use the longs output argument to visualize a dictionary. Create a Haar wavelet dictionary consisting of level-2 scaling functions, and level-1 and level-2 wavelet functions. Step through a plot of the translated scaling functions and wavelets by level.

[mpdict,~,~,longs] = wmpdictionary(100,'lstcpt',{{'haar',2}});

for nn = 1:size(mpdict,2)
if (nn<=longs{1}(1))
plot(mpdict(:,nn),'k','linewidth',2)
grid on
xlabel('Translation')
title('Haar Scaling Function - Level 2')
elseif (nn>longs{1}(1) && nn<=longs{1}(1)+longs{1}(2))
plot(mpdict(:,nn),'r','linewidth',2)
grid on
xlabel('Translation')
title('Haar Wavelet - Level 2')
else
plot(mpdict(:,nn),'b','linewidth',2)
grid on
xlabel('Translation')
title('Haar Wavelet - Level 1')
end
pause(0.2)
end

This animation infinitely loops through all the plots generated.

collapse all

### Matching Pursuit

Matching pursuit refers to a number of greedy or weak-greedy algorithms for computing an adaptive nonlinear expansion of a signal in a dictionary. In the majority of matching pursuit applications, a dictionary is an overcomplete set of vectors. The elements of the dictionary are referred to as atoms and are typically constructed to have certain time/frequency or time/scale properties. Matching pursuit takes the NP-hard problem of finding the best nonlinear expansion in a dictionary and implements it in an energy-preserving formulation that guarantees convergence. See Matching Pursuit Algorithms for more details.

## References

[1] Cai, T.T. and L. Wang “Orthogonal Matching Pursuit for Sparse Signal Recovery with Noise”. IEEE® Transactions on Information Theory, vol. 57, 7, 4680–4688, 2011.

[2] Donoho, D., M. Elad, and V. Temlyakov “Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise”. IEEE Transactions on Information Theory, 52,1, 6–18, 2004.

[3] Mallat, S. and Z. Zhang  “Matching Pursuits with Time-Frequency Dictionaries”. IEEE Transactions on Signal Processing, vol. 41, 12, 3397–3415, 1993

[4] Tropp, J.A. “Greed is good: Algorithmic results for sparse approximation”. IEEE Transactions on Information Theory, 50, pp. 2231–2242, 2004.