Suppose we observe a signal . With a dictionary , the signal is represented by a linear equation as . Given the observed signal, our goal is to find the coefficients .
Assuming sparse vector is one direction. Thus, the solution is formulated as
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 .
Basis pursuit is an L1 minimization that solves