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