Michael Elad

Technion - Israel Institute of Technology

Israel

Personnal website:
Other affiliations:

Michael Elad created these companion sites

Why Simple Shrinkage is Still Relevant for Redundant Representations?
Abstract
Shrinkage is a well known and appealing denoising technique, introduced originally by Donoho and Johnstone in 1994. The use of shrinkage for denoising is known to be optimal for Gaussian white noise, provided that the sparsity on the signal’s representation is enforced using a unitary transform. Still, shrinkage is also practiced with non-unitary, and even redundant representations, typically leading to very satisfactory results. In this paper we shed some light on this behavior. The main argument in this paper is that such simple shrinkage could be interpreted as the first iteration of an algorithm that solves the basis pursuit denoising (BPDN) problem. While the desired solution of BPDN is hard to obtain in general, we develop in this paper a simple iterative procedure for the BPDN minimization that amounts to step-wise shrinkage. We demonstrate how the simple shrinkage emerges as the first iteration of this novel algorithm. Furthermore, we show how shrinkage can be iterated, turning into an effective algorithm that minimizes the BPDN via simple shrinkage steps, in order to further strengthen the denoising effect.
Elad, M., "Why Simple Shrinkage is Still Relevant for Redundant Representations?", IEEE Transactions on Information Theory , 52, 5559-5569.
Authors: Elad
Coders: Elad
Last update
07/06/2012
Ranking
28
Runs
4
Visits
30
On the Stability of the Basis Pursuit in the Presence of Noise
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.
Donoho, D., and M. Elad, "On the Stability of the Basis Pursuit in the Presence of Noise ", Signal Processing , 86 , 511-532.
Authors: Donoho
Elad
Coders: Donoho
Elad
Last update
10/08/2012
Ranking
29
Runs
N.A.
Visits
63
Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise
Abstract
Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.
Donoho, D., M. Elad, and V. Temlyakov, "Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise", Transactions on Information Theory, 52.
Authors: Donoho
Elad
Temlyakov
Coders: Donoho
Elad
Temlyakov
Last update
10/08/2012
Ranking
14
Runs
10
Visits
89