Let Φ denote the dictionary of atoms as a N-by-M matrix with M>N. If the complete, redundant dictionary forms a frame for the signal space, you can obtain the minimum L2 norm expansion coefficient vector by using the frame operator.

$${\Phi}^{\u2020}={\Phi}^{*}{(\Phi \text{\hspace{0.05em}}\text{\hspace{0.05em}}{\Phi}^{*})}^{-1}$$

However, the coefficient vector returned by the frame operator does not preserve sparsity. If the signal is sparse in the dictionary, the expansion coefficients obtained with the canonical frame operator generally do not reflect that sparsity. Sparsity of your signal in the dictionary is a trait that you typically want to preserve. Matching pursuit addresses sparsity preservation directly.

Matching pursuit is a greedy algorithm that computes the best
nonlinear approximation to a signal in a complete, redundant dictionary.
Matching pursuit builds a sequence of sparse approximations to the
signal stepwise. Let Φ= {φ_{k}} denote
a dictionary of unit-norm atoms. Let *f* be your
signal.

Start by defining

*R*=^{0}f*f*Begin the matching pursuit by selecting the atom from the dictionary that maximizes the absolute value of the inner product with

*R*=^{0}f*f*. Denote that atom by φ_{p}.Form the residual

*R*by subtracting the orthogonal projection of^{1}f*R*onto the space spanned by φ^{0}f_{p}.$${R}^{1}f={R}^{0}f-\langle {R}^{0}f,{\varphi}_{p}\rangle {\varphi}_{p}$$

Iterate by repeating steps 2 and 3 on the residual.

$${R}^{m+1}f={R}^{m}f-\langle {R}^{m}f,{\varphi}_{k}\rangle {\varphi}_{k}$$

Stop the algorithm when you reach some specified stopping criterion.

In *nonorthogonal* (or basic) matching pursuit,
the dictionary atoms are not mutually orthogonal vectors. Therefore,
subtracting subsequent residuals from the previous one can introduce
components that are not orthogonal to the span of previously included
atoms.

To illustrate this, consider the following example. The example is not intended to present a working matching pursuit algorithm.

Consider the following dictionary for Euclidean 2-space. This dictionary is an equal-norm frame.

$$\{\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}1/2\\ \sqrt{3}/2\end{array}\right),\left(\begin{array}{c}-1/\sqrt{2}\\ -1/\sqrt{2}\end{array}\right)\}$$

Assume you have the following signal.

$$\left(\begin{array}{c}1\\ 1/2\end{array}\right)$$

The following figure illustrates this example. The dictionary atoms are in red. The signal vector is in blue.

Construct this dictionary and signal in MATLAB^{®}.

dictionary = [1 0; 1/2 sqrt(3)/2; -1/sqrt(2) -1/sqrt(2)]'; x = [1 1/2]';

Compute the inner (scalar) products between the signal and the dictionary atoms.

scalarproducts = dictionary'*x;

The largest scalar product in absolute value occurs between
the signal and `[-1/sqrt(2); -1/sqrt(2)]`

. This is
clear because the angle between the two vectors is almost π
radians.

Form the residual by subtracting the orthogonal projection of
the signal onto `[-1/sqrt(2); -1/sqrt(2)]`

from the
signal. Next, compute the inner products of the residual (new signal)
with the remaining dictionary atoms. It is not necessary to include ```
[-1/sqrt(2);
-1/sqrt(2)]
```

because the residual is orthogonal to that vector
by construction.

residual = x-scalarproducts(3)*dictionary(:,3); scalarproducts = dictionary(:,1:2)'*residual;

The largest scalar product in absolute value is obtained with `[1;0]`

.
The best two atoms in the dictionary from two iterations are ```
[-1/sqrt(2);
-1/sqrt(2)]
```

and `[1;0]`

. If you iterate
on the residual, you see that the output is no longer orthogonal to
the first atom chosen. In other words, the algorithm has introduced
a component that is not orthogonal to the span of the first atom selected.
This fact and the associated complications with convergence argues
in favor of Orthogonal Matching Pursuit (OMP).

In orthogonal matching pursuit (OMP), the residual is always
orthogonal to the span of the atoms already selected. This results
in convergence for a *d*-dimensional vector after
at most *d* steps.

Conceptually, you can do this by using Gram-Schmidt to create
an orthonormal set of atoms. With an orthonormal set of atoms, you
see that for a *d*-dimensional vector, you can find
at most *d* orthogonal directions.

The OMP algorithm is:

Denote your signal by

*f*. Initialize the residual*R*=^{0}f*f*.Select the atom that maximizes the absolute value of the inner product with

*R*=^{0}f*f*. Denote that atom by φ_{p}.Form a matrix,

*Φ*, with previously selected atoms as the columns. Define the orthogonal projection operator onto the span of the columns of*Φ*.$$P=\Phi \text{\hspace{0.05em}}\text{\hspace{0.05em}}{({\Phi}^{*}\Phi )}^{-1}{\Phi}^{*}$$

Apply the orthogonal projection operator to the residual.

Update the residual.

$${R}^{m+1}f=(I-P){R}^{m}f$$

*I*is the identity matrix.

Orthogonal matching pursuit ensures that components in the span of previously selected atoms are not introduced in subsequent steps.

It can be computationally efficient to relax the criterion that the selected atom maximizes the absolute value of the inner product to a less strict one.

$$\left|\langle x,{\varphi}_{p}\rangle \right|\ge \alpha \underset{k}{\mathrm{max}}\left|\langle x,{\varphi}_{k}\rangle \right|\text{\hspace{0.05em}},\text{\hspace{1em}}\alpha \in \left(0,1\right]$$

This is known as *weak* matching pursuit.

Was this topic helpful?