Basis Pursuit
Contents
15.2. Basis Pursuit¶
15.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:
(15.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
(15.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:
(15.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.