9.1 Background

Algorithms

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 mroe accurate approximation.

Basis pursuit

Basis pursuit is an effective algorithm which replace the sparse approximation problem by a linear programming problem. It selects the coefficients that will represent the signal to be those with the minimum L1 coefficients. Essentially what it does is the following: Given a signal X, it takes the inner product of X with each element in the dictionary and at the end takes selects the one that yields the larger result (this will be the element the most closely resembles X). This element is added to previously selected elements, and subtracted from the signal X. It does repeat this process on the residual signal until N elements have been chosen, where N is the number of desired coefficients in the approximate representation of X.

Orthogonal matching pursuit

Orthogonal matching pursuit is an iterative greedy algorithm that chooses the dictionary element that best represents the residual part of the signal at each iteration (just like the BP algorithm). It then projects this element onto those elements which have already been selected, which yields a new approximant signal. This differs from the BP algorithm in that redundant information is not repeated.

Continue

• Background Information
• Procedure
• Results
• Conclusion
• Our Code
• Team Members
• References