# Basis Pursuit and Matching Pursuit

Suppose we observe a signal $x$. With a dictionary $D$, the signal $x$ is represented by a linear equation as $x = D\alpha$. Given the observed signal, our goal is to find the coefficients $\alpha$.

Assuming $\alpha$ sparse vector is one direction. Thus, the solution is formulated as
$\hat{\alpha} = \textrm{argmin}_{\alpha} ||\alpha||_{0}$
$\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 $||x-D\alpha||$.
Basis pursuit is an L1 minimization that solves
$\hat{\alpha} = \textrm{argmin}_{\alpha} ||\alpha||_{1}$
$\textrm{s.t. }x = D\alpha$.