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.
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 .