This is our code for the basis pursuit and orthogonal matching pursuit algorithms for 2 dimensional signals, namely images. All of the code was written from scratch by members of the group, and was based on ideas drawn from our research. The code is shown below.
The two algorithms that we are concerned with are basis pursuit (BP) and orthogonal matching pursuit (OMP). What these two algorithms have in common is a requirement to use waveforms from a dictionary to represent an image. One advantage of these two algorithms is that they are very flexible in terms of the dictionary used, which in turn allows for faster, sparser compression. It has been previously shown that while OMP is a faster algorithm, BP yields a more accurate approximation.
Sparse approximation, defined as the practice of representing a given signal as a summation of elements from a dictionary of elementary signals, has traditionally only involved one basis - the canonical basis in which we perceive the world, the Fourier basis that is the foundation of the frequency domain, or the dct basis that is behind the modern JPEG image format. However, recent thought has suggested that more accurate, faster methods for sparse approximation may instead be derived from a "combinational" basis, ie, a basis that consists of two or more bases concatenated onto each other. This resultant basis is often called an "overcomplete" or "redundant" basis, as there are always more vectors in the basis than the magnitude of the dimension of the space they span. Since they are redundant in this effect, the immediate problem would seem to be that there are then an infinite number of representations for any vector, or signal, in a space. Modern theory suggests that there are ideal algorithms for determining these transformations, in terms of number of computations and sparsity of the resultant representation; the two most prevalent being Basis Pursuit (BP) and Orthogonal Matching Pursuit (OMP).
The sparse approximation problem is trying to find a concise approximation of a signal as a linear combination of a few elementary signals from a rich collection. Because the approximation is not possible unless the algorithm finds some latent structure i
