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. $\mathcal{D}=\mathbf{I}$ and $N=D$). Further, we assume signal $\mathbf{x}$ to be $K$-sparse in ${\mathbb{C}}^N$. With the sensing matrix $\mathrm{\Phi }$ and the measurement vector $\mathbf{y}$, the CS sparse recovery problem in the absence of measurement noise (i.e. $\mathbf{y}=\mathrm{\Phi }\mathbf{x}$) is stated as:

(21.2)$$\hat{\mathbf{x}}=\text{arg }\underset{\mathbf{x}\in {\mathbb{C}}^N}{min}\Vert \mathbf{x}{\Vert }_0\text{ subject to }\mathbf{y}=\mathrm{\Phi }\mathbf{x}.$$

In the presence of measurement noise (i.e. $\mathbf{y}=\mathrm{\Phi }\mathbf{x}+\mathbf{e}$), the recovery problem takes the form of

(21.3)$$\hat{\mathbf{x}}=\text{arg }\underset{\mathbf{x}\in {\mathbb{C}}^N}{min}\Vert \mathbf{y}-\mathrm{\Phi }\mathbf{x}{\Vert }_2\text{ subject to }\Vert \mathbf{x}{\Vert }_0\le K.$$

when a bound on sparsity is provided, or alternatively:

(21.4)$$\hat{\mathbf{x}}=\text{arg }\underset{\mathbf{x}\in {\mathbb{C}}^N}{min}\Vert \mathbf{x}{\Vert }_0\text{ subject to }\Vert \mathbf{y}-\mathrm{\Phi }\mathbf{x}{\Vert }_2\le ϵ.$$

when a bound on the measurement noise is provided.