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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s