On the modified Basis Pursuit reconstruction for Compressed Sensing with partially known support

Original · EN

The goal of this short note is to present a refined analysis of the modified Basis Pursuit (ℓ₁-minimization) approach to signal recovery in Compressed Sensing with partially known support, as introduced by Vaswani and Lu. The problem is to recover a signal x ∈ Rᵖ using an observation vector y=Ax, where A ∈ Rⁿ× ᵖ and in the highly underdetermined setting n≪ p. Based on an initial and possibly erroneous guess T of the signal's support supp(x), the Modified Basis Pursuit method of Vaswani and Lu consists of minimizing the ℓ₁ norm of the estimate over the indices indexed by Tᶜ only. We prove exact recovery essentially under a Restricted Isometry Property assumption of order 2 times the cardinal of Tᶜ ∩ supp(x), i.e. the number of missed components.