Basis Pursuit

Given a set of basis functions , a signal may be approximated by the linear combination . Typically, the larger the basis, the better a signal can be approximated. However, not all signals need all of the basis functions for a reasonable approximation. The idea of basis pursuit is to choose a small subset of a larger set, or dictionary, of basis functions that may be overdetermined.

This example demonstrates how basis pursuit can be done easily and efficiently using Fit with the FitRegularization option.

For signals with discrete time sampling, the reconstruction can simply be given as a matrix equation , where is the matrix with elements . For overdetermined bases, the coefficients α that give the best approximation can simply be found by least squares. If, instead of minimizing , an L1 regularization term is added to give , sufficiently large values of the parameter encourage components of α to be zero. The problem can be efficiently solved using Fit with the new FitRegularization option.

Use a basis of Gabor functions and for an example of a large dictionary of basis functions.

Here is a plot of showing a sample of Gabor functions.

On the interval from 0 to 1 with a time sample interval , a set of basis functions with , and a fixed are sufficient to exactly represent a wide variety of signals.

The basis matrix can be constructed using DesignMatrix.

This matrix is very large, but with a small loss in representation accuracy, it is possible to use the fact the the Gabor functions decay quickly from to make it sparse by using a threshold.

Now consider a signal.

The signal can be discretized by just evaluating at all the time samples.

A least squares fit will indicate how well the function can be represented by the basis functions. This takes a long time because the matrix is so large.

The full representation error is effectively machine-precision roundoff.

Now use L1 regularization to find a sparse fit. This is actually faster to compute than the least squares fit since it uses a sparse algorithm.

The sparse representation uses only 50 out of 30561 basis elements. This is small enough to actually get a functional form.

Show the error.

The fit can be improved slightly by doing a least squares fit with just those basis elements.

The error can be tuned by changing the parameter . Generally, larger will result in fewer basis functions and more error, while smaller will result in more basis functions and smaller error. Here are error plots for other choices of .