Basis Pursuit
Contents
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.