On the Stability of the Basis Pursuit in the Presence of Noise

Michael Elad, David Donoho Coders: Michael Elad, David Donoho

Code and Data Abstract

This code analyses graphically the behavior of the basis pursuit (BP) algorithm in presence of noise. The stability conditions are given for a general dictionary as well as for a union of orthonormal matrices. For this, the user must specify the mutual incoherence (M), the signal length (N), the noise-to-signal-ratio (NSR), the maximal number of orthonormal matrices (J) and the normalized NSR, (R). Set M to 1/100 to get the same second set of plots as in the paper. For more information, please visit the SparseLab (Seeking Sparse Solutions to Linear Systems of Equations) website (http://sparselab.stanford.edu/).

Paper Abstract

Given a signal S ( R^N and a full-rank matrix D ( R^NL with N<L, we define the signal’s over-complete representation as a ( R^L satisfying S=Da. Among the infinitely many solutions of this under-determined linear system of equations, we have special interest in the sparsest representation, i.e., the one minimizing ||a||0. This problem has a combinatorial flavor to it, and its direct solution is impossible even for moderate L. Approximation algorithms are thus required, and one such appealing technique is the basis pursuit (BP) algorithm. This algorithm has been the focus of recent theoretical research effort. It was found that if indeed the representation is sparse enough, BP finds it accurately. When an error is permitted in the composition of the signal, we no longer require exact equality S=Da. The BP has been extended to treat this case, leading to a denoizing algorithm. The natural question to pose is how the abovementioned theoretical results generalize to this more practical mode of operation. In this paper we propose such a generalization. The behavior of the basis pursuit in the presence of noise has been the subject of two independent very wide contributions released for publication very recently. This paper is another contribution in this direction, but as opposed to the others mentioned, this paper aims to present a somewhat simplified picture of the topic, and thus could be referred to as a primer to this field. Specifically, we establish here the stability of the BP in the presence of noise for sparse enough representations. We study both the case of a general dictionary D, and a special case where D is built as a union of orthonormal bases. This work is a direct generalization of noiseless BP study, and indeed, when the noise power is reduced to zero, we obtain the known results of the noiseless BP.

Michael Elad, David Donoho Coders: Michael Elad, David Donoho, et al. "On the Stability of the Basis Pursuit in the Presence of Noise ." Signal Processing (2006).     Retrieved 06/24/2019 from researchcompendia.org/compendia/2013.127/

Page Owner


created 11/12/2013

modified 01/16/2014

blog comments powered by Disqus

rmc id