Matching Pursuit Algorithms

Basic Matching Pursuit

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.

Φ=Φ*(ΦΦ*)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.

  1. Start by defining R0f = f

  2. Begin the matching pursuit by selecting the atom from the dictionary that maximizes the absolute value of the inner product with R0f = f. Denote that atom by φp.

  3. Form the residual R1f by subtracting the orthogonal projection of R0f onto the space spanned by φp.

    R1f=R0f<R0f,ϕp>ϕp

  4. Iterate by repeating steps 2 and 3 on the residual.

    Rm+1f=Rmf<Rmf,ϕk>ϕk

  5. 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 reintroduce components that are not orthogonal to the span of the 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.

{(10),(1/23/2),(1/21/2)}

Assume you have the following signal.

(11/2)

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. This means that a previously selected atom may be selected again. This fact and the associated complications with convergence argues in favor of Orthogonal Matching Pursuit (OMP).

Orthogonal Matching Pursuit

In orthogonal matching pursuit (OMP), the residual is always orthogonal to the atoms already selected. This means that the same atom can never be selected twice and 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:

  1. Denote your signal by f. Initialize the residual R0f = f.

  2. Select the atom that maximizes the absolute value of the inner product with R0f = f. Denote that atom by φp.

  3. Form a matrix, Φ, with previously selected atoms as the columns. Define the orthogonal projection operator onto the span of the columns of Φ.

    P=Φ(Φ*Φ)1Φ*

  4. Apply the orthogonal projection operator to the residual.

  5. Update the residual.

    Rm+1f=(IP)Rmf

    I is the identity matrix.

Orthogonal matching pursuit ensures that the previously selected atoms are not chosen again in subsequent steps.

Weak Orthogonal Matching Pursuit

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.

|<x,ϕp>|αmaxk|<x,ϕk>|α(0,1]

This is known as weak matching pursuit.

Was this topic helpful?