Suppose we observe a signal $latex x$. With a dictionary $latex D$, the signal $latex x$ is represented by a linear equation as $latex x = D\alpha$. Given the observed signal, our goal is to find the coefficients $latex \alpha$.
Assuming $latex \alpha$ sparse vector is one direction. Thus, the solution is formulated as $latex \hat{\alpha} = \textrm{argmin}{\alpha} ||\alpha||{0}$ $latex \textrm{s.t. }x = D\alpha$. However, this L0 norm minimization is known as NP-hard. Instead of L1 minimization, both Basis Pursuit (BP) and Matching Pursuit (MP) are applicable for this problem.
MP is categorized as a greedy algorithm that greedy minimizes $latex ||x-D\alpha||$. Basis pursuit is an L1 minimization that solves $latex \hat{\alpha} = \textrm{argmin}{\alpha} ||\alpha||{1}$ $latex \textrm{s.t. }x = D\alpha$.
