Lipschitz Bounds for Noise Robustness in Compressive Sensing: Two Algorithms

The paper deals with numerical estimations of Lipschitz bounds relating locally the reconstruction error to the measurement error in the compressive sensing framework. Most recent theoretical papers in the field parametrize such bounds relatively to certain families of vectors called dual certificates, which are fundamental to several reconstruction criteria. The paper provides two algorithms for computing dual certificates that optimize their related reconstruction error bounds. We give a greedy algorithm that provides a fast approximate solution, and a convex-projection algorithm that computes the exact optimum.