Greedy Basis Pursuit

We introduce greedy basis pursuit (GBP), a new algorithm for computing sparse signal representations using overcomplete dictionaries. GBP is rooted in computational geometry and exploits equivalence between minimizing the l¹-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¹-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.