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.