Deconvolution refers to the problem of estimating the unknown input to an LTI system when the output signal and system response is known. In practice, the available output signal is also noisy. For some systems, the deconvolution problem is quite straight forward; however, for systems that are noninvertible or nearly noninvertible (e.g. narrowband or with frequency response nulls), the problem is more difficult. The use of an exact inverse system can greatly amplify the noise rendering the result useless. In such cases, it is important to utilize prior knowledge regarding the input signal so as to obtain a more accurate estimate of the input signal, even when the system is nearly noninvertible and the observed output signal is noisy.
In some applications of deconvolution, it is known that the input signal is sparse (i.e. a spike train, etc.)
or approximately sparse.
Applications of `sparse deconvolution' include geophysics, ultrasonic nondestructive evaluation, speech processing, and astronomy [11].
One approach to sparse deconvolution involves the minimization of a cost function defined
in terms of the
This tutorial aims to illustrate some of the principles and algorithms of sparse signal processing,
by way of considering the sparse deconvolution problem.
A computationally efficient iterative algorithm for sparse deconvolution is derived using
the majorizationminimization (MM) optimization method.
The MM method is a simple, yet effective and widely applicable, method that replaces a difficult minimization
problem with a sequence of simpler ones [8].
Other algorithms, developed for general
The conditions that characterize the optimal solution are described and illustrated in "Optimality conditions".
With these simple conditions, the optimality of the result computed by
a numerical algorithm can be readily verified.
Moreover, as described in "Setting the regularization parameter, λ",
the optimality conditions provide a straight forward way to set the
regularization parameter
Problem
We assume the noisy data
where
where
Note that the difference equation in Equation 2 can be written in matrix form as
where
then
From Equation 4,
the output
where the system matrix
Note that, even though
Example.
An example is illustrated in Figure 1.
The sparse signal
is the input to a convolution system. The system is second order, defined by the difference equation coefficients:
The system has complex poles at

Optimization formulation
In order to estimate
The use of the
The problem in Equation 12 is useful for many sparse signal processing problems, not just deconvolution.
In the general case, Equation 12 is called `basis pursuit denoising' (BPD) [5]
or the `lasso' [17].
References [5], [17] give examples (other than deconvolution) of problems posed in this form,
and motivations for using the
Notation
The
The
The