Greedy basis pursuit

We introduce greedy basis pursuit (GBP), a new algorithm for computing sparse signal representations using over-complete dictionaries. GBP is rooted in computational geometry and exploits an equivalence between minimizing the l(1)-norm of the representation coefficients and determining the intersection of the signal with the convex hull of the dictionary. GBP unifies the different advantages of previous algorithms: like standard approaches to basis pursuit, GBP computes representations that have minimum l(1)-norm; like greedy algorithms such as matching pursuit, GBP builds up representations, sequentially selecting atoms. We describe the algorithm, demonstrate its performance, and provide code. Experiments show that GBP can provide a fast alternative to standard linear programming approaches to basis pursuit.