# 21.2. Basis Pursuit#

## 21.2.1. Introduction#

We recall following sparse recovery problems in compressive sensing. For simplicity, we assume the sparsifying dictionary to be the Dirac basis (i.e. $$\bDDD = \bI$$ and $$N = D$$). Further, we assume signal $$\bx$$ to be $$K$$-sparse in $$\CC^N$$. With the sensing matrix $$\Phi$$ and the measurement vector $$\by$$, the CS sparse recovery problem in the absence of measurement noise (i.e. $$\by = \Phi \bx$$) is stated as:

(21.2)#$\widehat{\bx} = \text{arg } \underset{\bx \in \CC^N}{\min} \| \bx \|_0 \text{ subject to } \by = \Phi \bx.$

In the presence of measurement noise (i.e. $$\by = \Phi \bx + \be$$), the recovery problem takes the form of

(21.3)#$\widehat{\bx} = \text{arg } \underset{\bx \in \CC^N}{\min} \| \by - \Phi \bx \|_2\text{ subject to } \| \bx \|_0 \leq K.$

when a bound on sparsity is provided, or alternatively:

(21.4)#$\widehat{\bx} = \text{arg } \underset{\bx \in \CC^N}{\min} \| \bx \|_0 \text{ subject to } \| \by - \Phi \bx \|_2 \leq \epsilon.$

when a bound on the measurement noise is provided.