Greedy Basis Pursuit (GBP) is a new algorithm for computing sparse signal representations using an overcomplete dictionary. Like Basis Pursuit, GBP computes signal representations with minimum L1-norm; like Matching Pursuit, GBP proceeds by greedily selecting atoms to build-up representations (but also occasionally discarding atoms). In experiments, GBP outperforms standard linear programming methods on dense, high-dimensional problems.
GBP is based on the equivalence between computing the minimum L1-norm signal representation and determining the facet of the convex hull of the dictionary that the signal vector intersects. To find this intersection, GBP proceeds by `gift-wrapping' the convex hull in a particular direction.
The figure below illustrates GBP on a 3-dimensional problem. Given a signal (green vector) and a dictionary of atoms (blue circles), GBP constructs a sequence of hyperplanes (spanned by the dashed lines with normal indicated by the solid line) by iteratively selecting atoms (red circles) to represent the signal. At each iteration, the current approximation to the signal is given by the projection of the signal onto the convex subset (grey region) spanned by the current set of selected atoms. The final hyperplane contains the facet of the convex hull of the dictionary that intersects the signal vector.
|
|
|
|
| Iteration 1 | Iteration 2 | Iteration 3 |
