Pursuit Algorithm
Table of Contents
Pursuit algorithms find the sparse representation \(x \in \mathbb{R}^k\) of a signal \(y \in \mathbb{R}^n\) when provided with a dictionary \(D \in \mathbb{R}^{n \times k}\). Here, \(k > n\) so the problem is overcomplete.
So, the problem is to find \(x\) such that number of nonzeros in \(x\) is minimized and \(y = Dx\).
\(\arg \min_x ||x||_0\) subject to \(||y - Dx||_2^2 \leq \epsilon\)
This sparse-coding problem is NP-hard so these algorithms provide approximate solutions.
1. Basis Pursuit
Convert the \(l_0\) norm to \(l_1\) norm and solve the optimization problem using linear programming.
\begin{align*} \min_x ||x||_1 \textrm{ such that } y = Dx \end{align*}This can be formulated as a linear programming problem with the objective:
\begin{align*} \min \sum u_i \\ \textrm{such that,} \\ & u_i \geq x_i \\ & u_i \geq -x_i \\ & u_i \geq 0 \\ & Dx = x \\ \end{align*}This gives good solutions but can be computationally expensive.
2. Matching Pursuit
We can use a greedy alogrithm, where we select a \(d_i\) that has highest correlation with signal \(y\) then subtract that component of \(y\), and iteratively continue with the residual selecting another \(d_i\) and so on.
This gives good solutions in practice and is fast. But can be susceptible to outliers.