The paper deals with estimating the local noise robustness in a compressive sensing framework. We provide two algorithms which estimate, for each vector x that can be recovered by $\ell^1$ minimization, the Lipschitz bounds relating the $\ell^1$-reconstruction error to the measurement error (or noise) for a given sensing matrix. Classical theoretical estimations, such as those based on the restricted isometry property, theoretically give error bounds estimates depending on RIP constants. Unfortunately these RIP assumptions can only be applied for random matrices and are unsuitable for a given deterministic matrix. Other known results applying to deterministic matrices give errors bounds estimates under a small noise assumption, using a semi implicit formula of the solution considering small perturbations of the noiseless $\ell^1$ minimization problem. As an alternative, more recent papers focus on the local behavior of the reconstruction error. One such approach theoretically consists in emphasizing an error bound for each member of a certain family of vectors associated to a local noiseless solution. These vectors are called dual certificates and play a fundamental role in several reconstruction criteria. As such, the theoretical bound estimates based on dual certificates are more versatile, since they are local - hence potentially more accurate - and need no a priori assumptions on the magnitude of the measurement noise. However, as a drawback, finding dual certificates might have a significant computational cost. The paper provides two algorithms for computing dual certificates that minimize their related Lipschitz error bounds, based on two different approaches. The first is a greedy algorithm that provides a fast approximate solution, by minimizing the error bound with respect to a dual certificate. This produces a fast approximation of the optimal bound, since all the numerical computations only rely on scalar products. The second algorithm is based on a theoretical geometric result that describes the exact optimal solution. More precisely we showed that the problem of finding the dual certificate minimizing the error bound can be reduced to computing the convex projection of a suitable vector over a certain convex set. As such, it gives the best error bound but has a higher complexitational cost than the greedy approximation. The two algorithms are illustrated and numerically compared for compressive sensing matrices issued from a tomography application framework. The relationship between theoretical bounds and numerical observed bounds is also discussed.< Réduire