Robustness Analysis of a List Decoding Algorithm for Compressed Sensing

We analyze the noise robustness of sparse signal recon-struction based on the compressive sensing equivalent of a list-decoding algorithm for Reed Solomon codes -the Coppersmith-Sudan algorithm. We use results from the per-turbation analysis of singular subspaces of matrices to prove the existence of bounds for the noise levels (in the measure-ments) below which the error in the recovered signal (with respect to the original sparse signal) will be guaranteed to be upper bounded. Numerical simulations have been presented which compare the experimental recovery probability to the theoretical lower bound.