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

(15.2)¶

\hat{x} = arg min_{x \in C^{N}} ‖ x ‖_{0} subject to y = Φ x .

In the presence of measurement noise (i.e. $y = Φ x + e$ ), the recovery problem takes the form of

(15.3)¶

\hat{x} = arg min_{x \in C^{N}} ‖ y - Φ x ‖_{2} subject to ‖ x ‖_{0} \leq K .

when a bound on sparsity is provided, or alternatively:

(15.4)¶

\hat{x} = arg min_{x \in C^{N}} ‖ x ‖_{0} subject to ‖ y - Φ x ‖_{2} \leq ϵ .

when a bound on the measurement noise is provided.

Topics in Signal Processing

Basis Pursuit

Contents

15.2. Basis Pursuit¶

15.2.1. Introduction¶