Measurement matrix design for compressive sensing with side information at the encoder

We study the problem of measurement matrix design for Compressive Sensing (CS) when the encoder has access to side information, a signal analogous to the signal of interest. In particular, we propose to incorporate this extra information into the signal acquisition stage via a new design for the measurement matrix. The goal is to reduce the number of encoding measurements, while still allowing perfect signal reconstruction at the decoder. Then, the reconstruction performance of the resulting CS system is analysed in detail assuming the decoder reconstructs the original signal via Basis Pursuit. Finally, Gaussian width tools are exploited to establish a tight theoretical bound for the number of required measurements. Extensive numerical experiments not only validate our approach, but also demonstrate that our design requires fewer measurements for successful signal reconstruction compared with alternative designs, such as an i.i.d. Gaussian matrix.