21.2. Basis Pursuit#
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:
In the presence of measurement noise (i.e. \(\by = \Phi \bx + \be\)), the recovery problem takes the form of
when a bound on sparsity is provided, or alternatively:
when a bound on the measurement noise is provided.