On the stability of the basis pursuit in the presence of noise

Given a signal S is an element of R-N and a full-rank matrix D is an element of R-NxL with N < L, we define the signal's over-complete representation as alpha is an element of R-L satisfying S = D alpha. 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 parallel to alpha parallel to(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 = D alpha. The BP has been extended to treat this case, leading to a denoizing algorithm. The natural question to pose is how the above-mentioned 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 or 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. (C) 2005 Elsevier B.V. All rights reserved.