19
Convolutive Mixtures and
Blind Deconvolution
This chapter deals with blind deconvolution and blind separation of convolutive
mixtures.
Blind deconvolution is a signal processing problem that is closely related to basic
independent component analysis (ICA) and blind source separation (BSS). In com-
munications and related areas, blind deconvolution is often called blind equalization.
In blind deconvolution, we have only one observed signal (output) and one source
signal (input). The observed signal consists of an unknown source signal mixed with
itself at different time delays. The task is to estimate the source signal from the
observed signal only, without knowing the convolving system, the time delays, and
mixing coefficients.
Blind separation of convolutive mixtures considers the combined blind deconvolu-
tion and instantaneous blind source separation problem. This estimation task appears
under many different names in the literature: ICA with convolutive mixtures, mul-
tichannel blind deconvolution or identification, convolutive signal separation, and
blind identification of multiple-input-multiple-output (MIMO) systems. In blind
separation of convolutive mixtures, there are several source (input) signals and sev-
eral observed (output) signals just like in the instantaneous ICA problem. However,
the source signals have different time delays in each observed signal due to the finite
propagation speed in the medium. Each observed signal may also contain time-
delayed versions of the same source due to multipath propagation caused typically
by reverberations from some obstacles. Figure 23.3 in Chapter 23 shows an example
of multipath propagation in mobile communications.
In the following, we first consider the simpler blind deconvolution problem, and
after that separation of convolutive mixtures. Many techniques for convolutive mix-
355
Independent Component Analysis. Aapo Hyv
¨
arinen, Juha Karhunen, Erkki Oja

source signal may have an arbitrary scaling (and sign) and time shift compared
with the true one. This situation is similar to the permutation and sign indeterminacy
encountered in ICA; the two models are, in fact, intimately related as will be explained
in Section 19.1.4.
Of course, the preceding ideal model usually does not exactly hold in practice.
There is often additive noise present, though we have omitted noise from the model
(19.1) for simplicity. The source signal sequence may not satisfy the i.i.d condition,
and its distribution is often unknown, or we may only know that the source signal is
subgaussian or supergaussian. Hence blind deconvolution often is a difficult signal
processing task that can be solved only approximately, in practice.
BLIND DECONVOLUTION
357
If the linear time-invariant system (19.1) is minimum phase (see the Appendix),
then the blind deconvolution problem can be solved in a straightforward way. On the
above assumptions, the deconvolving filter is simply a whitening filter that temporally
whitens the observed signal sequence [171, 174]. However, in many appli-
cations, for example, in telecommunications, the system is typically nonminimum
phase [174] and this simple solution cannot be used.
We shall next discuss some popular approaches to blind deconvolution. Blind
deconvolution is frequently needed in communications applications where it is con-
venient to use complex-valued data. Therefore we present most methods for this
general case. The respective algorithms for real data are obtained as special cases.
Methods for estimating the ICA model with complex-valued data are discussed later
in Section 20.3.
19.1.2 Bussgang methods
Bussgang methods [39, 171, 174, 315] include some of the earliest algorithms [152,
392] proposed for blind deconvolution, but they are still widely used. In Bussgang
methods, a noncausal FIR filter structure
(19.3)
of length is used. Here denotes the complex conjugate. The weights of

The constant is chosen in such a way that the gradient of the cost function
is zero when perfect deconvolution is attained, that is, when = . The error
signal (19.5) in the gradient algorithm (19.4) for minimizing the cost function (19.7)
with respect to the weight has the form
(19.9)
In computing , the expectation in (19.7) has been omitted for getting a simpler
stochastic gradient type algorithm. The respective nonlinearity is given by
[171]
(19.10)
Among the family of Godard algorithms, the so-called constant modulus algorithm
(CMA) is widely used. It is obtained by setting in the above formulas. The
cost function (19.7) is then related to the minimization of the kurtosis. The CMA and
more generally Godard algorithms perform appropriately for subgaussian sources
only, but in communications applications the source signals are subgaussian.
1
.The
CMA algorithm is the most successful blind equalization (deconvolution) algorithm
used in communications due to its low complexity, good performance, and robustness
[315].
Properties of the CMA cost function and algorithm have been studied thoroughly
in [224]. The constant modulus property possessed by many types of communications
signals has been exploited also in developing efficient algebraic blind equalization
and source separation algorithms [441]. A good general review of Bussgang type
blind deconvolution methods is [39].
19.1.3 Cumulant-based methods
Another popular group of blind deconvolution methods consists of cumulant-based
approaches [315, 170, 174, 171]. They apply explicitly higher-order statistics of
the observed signal , while in the Bussgang methods higher-order statistics
1
The CMA algorithm can be applied to blind deconvolution of supergaussian sources by using a negative

E (19.15)
where the variance of is often normalized to unity: . Temporal whitening
can be achieved by spectral prewhitening in the Fourier domain, or by using time-
domain techniques such as linear prediction [351]. Linear prediction techniques have
been discussed for example in the books [169, 171, 419].
Shalvi and Weinstein have presented a somewhat more complicated algorithm
for the case E in [398]. Furthermore, they showed that there exists a
close relationship between their algorithm and the CMA algorithm discussed in the
previous subsection; see also [351]. Later, they derived fast converging but more
involved super-exponential algorithms for blind deconvolution in [399]. Shalvi and
360
CONVOLUTIVE MI XTURES AND BLIND DECONVOLUTION
Weinstein have reviewed their blind deconvolution methods in [170]. Closely related
algorithms were proposed earlier in [114, 457].
It is interesting to note that Shalvi and Weinstein’s algorithm (19.14) can be
derived by maximizing the absolute value of the kurtosis of the filtered (deconvolved)
signal under the constraint that the output signal is temporally white [398,
351]. The temporal whiteness condition leads to the normalization constraint of
the weight vector in (19.14). The corresponding criterion for standard ICA is
familiar already from Chapter 8, where gradient algorithms similar to (19.14) have
been discussed. Also Shalvi and Weinstein’s super-exponential algorithm [399] is
very similar to the cumulant-based FastICA as introduced in Section 8.2.3. The
connection between blind deconvolution and ICA is discussed in more detail in the
next subsection.
Instead of cumulants, one can resort to higher-order spectra or polyspectra [319,
318]. They are defined as Fourier transforms of the cumulants quite similarly as
the power spectrum is defined as a Fourier transform of the autocorrelation function
(see Section 2.8.5). Polyspectra provide a basis for blind deconvolution and more
generally identification of nonminimum-phase systems, because they preserve phase
information of the observed signal. However, blind deconvolution methods based

19.2 BLIND SEPARATION OF CONVOLUTIVE MIXTURES
19.2.1 The convolutive BSS problem
In several practical applications of ICA, some kind of convolution takes place simul-
taneously with the linear mixing. For example, in the classic cocktail-party problem,
or separation of speech signals recorded by a set of microphones, the speech signals
do not arrive in the microphones at the same time. This is because the sound travels in
the atmosphere with a very limited speed. Moreover, the microphones usually record
echos of the speakers’ voices caused by reverberations from the walls of the room
or other obstacles. These two phenomena can be modeled in terms of convolutive
mixtures. Here we have not considered noise and other complications that often
appear in practice; see Section 24.2 and [429, 430].
Blind source separation of convolutive mixtures is basically a combination of
standard instantaneous linear blind source separation and blind deconvolution. In the
convolutive mixture model, each element of the mixing matrix in the model
= is a filter instead of a scalar. Written out for each mixture, the data model
for convolutive mixtures is given by
for (19.19)
This is a FIR filter model, where each FIR filter (for fixed indices and ) is defined by
the coefficients . Usually these coefficients are assumed to be time-independent
constants, and the number of terms over which the convolution index runs is finite.
Again, we observe only the mixtures , and both the independent source signals
and all the coefficients must be estimated.
To invert the convolutive mixtures (19.19), a set of similar FIR filters is typically
used:
for (19.20)
The output signals of the separating system are estimates of the
source signals at discrete time .The give the coefficients of
the FIR filters of the separating system. The FIR filters used in separation can be
362
CONVOLUTIVE MI XTURES AND BLIND DECONVOLUTION

have given an efficient temporal whitening method based on FIR matrix algebra and
Fourier transforms in [257].
Standard ICA makes use of spatial statistics of the mixtures to learn a spatial blind
separation system. In general, higher-order spatial statistics are needed for achieving
this goal. However, if the source signals are temporally correlated, second-order
spatiotemporal statistics are sufficient for blind separation under some conditions,
as shown in [424] and discussed in Chapter 18. In contrast, blind separation of
convolutive mixtures must utilize spatiotemporal statistics of the mixtures to learn a
spatiotemporal separation system.
Stationarity of the sources has a decisive role in separating convolutive mixtures,
too. If the sources have nonstationary variances, second-order spatiotemporal statis-
tics are enough as briefly discussed in [359, 456].
BLIND SEPARATION OF CONVOLUTIVE MIXTURES
363
For convolutive mixtures, stationary sources require higher than second-order
statistics, just as basic ICA, but the following simplification is possible [430]. Spa-
tiotemporal second-order statistics can be used to decorrelate the mixtures. This step
returns the problem to that of conventional ICA, which again requires higher-order
spatial statistics. Examples of such approaches are can be found in [78, 108, 156].
This simplification is not very widely used, however.
Alternatively, one can resort to higher-order spatiotemporal statistics from the
beginning for sources that cannot be assumed nonstationary. This approach has been
adopted in many papers, and it will be discussed briefly later in this chapter.
19.2.2 Reformulation as ordinary ICA
The simplest approach to blind separation of convolutive mixtures is to reformulate
the problem using the standard linear ICA model. This is possible because blind
deconvolution can be formulated as a special case of ICA, as we saw in (19.18).
Define now a vector by concatenating time-delayed versions of every source
signal:
(19.23)

separation of convolutive mixtures, too. A fundamental reason of the computational
difficulties encountered with convolutive mixtures is the fact that the number of the
unknown parameters in the model (19.19) is so large. If the filters have length ,itis
-fold compared with the respective instantaneous ICA model. This basic problem
cannot be avoided in any way.
19.2.3 Natural gradient methods
In Chapter 9, the well-known Bell-Sejnowski and natural gradient algorithms were
derived from the maximum likelihood principle. This principle was shown to be quite
closely related to the maximization of the output entropy, which is often called the
information maximization (infomax) principle; see Chapter 9. These ICA estimation
criteria and algorithms can be extended to convolutive mixtures in a straightforward
way. Early results and derivations of algorithms can be found in [13, 79, 121, 268,
363, 426, 427]. An application to CDMA communication signals will be described
later in Chapter 23.
Amari, Cichocki, and Douglas presented an elegant and systematic approach for
deriving natural gradient type algorithms for blind separation of convolutive mixtures
and related tasks. It is based on algebraic equivalences and their nice properties. Their
work has been summarized in [11], where rather general natural gradient learning
rules have been given for complex-valued data both in the time domain and -
transform domain. The derived natural gradient rules can be implemented in either
batch, on-line, or block on-line forms [11]. In the batch form, one can use a noncausal
FIR filter structure, while the on-line algorithms require the filters to be causal.
In the following, we represent an efficient natural gradient type algorithm [10, 13]
described also in [430] for blind separation of convolutive mixtures. It can be
implemented on-line using a feedforward (FIR) filter structure in the time domain.
The algorithm is given for complex-valued data.
The separating filters are represented as a sequence of coefficient matrices
at discrete time and lag (delay) . The separated output with this notation and
causal FIR filters is
(19.26)

either. Thus we can apply Fourier transform to both sides of Eq. (19.19). Denoting
by , ,and the Fourier transforms of , ,and ,
respectively, we obtain
for (19.29)
This shows that the convolutive mixturemodel (
19.19) is transformed
into an instan-
taneous linear ICA model in the frequency domain. The price that we have to pay
for this is that the mixing matrix is now a function of the angular frequency while
in the standard ICA/BSS problem it is constant.
366
CONVOLUTIVE MI XTURES AND BLIND DECONVOLUTION
To utilize standard ICA in practice in the Fourier domain, one can take short-time
Fourier transforms of the data, instead of the global transform. This means that
the data is windowed, usually by a smooth windowing function such as a gaussian
envelope, and the Fourier transform is applied separately to each data window. The
dependency of on can be simplified by dividing the values of into a
certain number of frequency bins (intervals). For every frequency bin, we have then a
number of observations of , and we can estimate the ICA model separately for
each frequency bin. Note that the ICs and the mixing matrix are now complex-valued.
See Section 20.3 on how to estimate the ICA model with complex-valued data.
The problem with this Fourier approach is the indeterminacy of permutation and
sign that is ubiquitous in ICA. The permutation and signs of the sources are usually
different in each frequency interval. For reconstructing a source signal in the
time domain, we need all its frequency components. Hence we a need some method
for choosing which source signals in different frequency intervals belong together.
To this end, various continuity criteria have been introduced by many authors; see
[15, 59, 216, 356, 397, 405, 406, 430].
Another major group of Fourier methods developed for convolutive mixtures
avoids the preceding problem by performing the actual separation in the time domain.

spatial covariance matrix of at time is
(19.31)
where and are respectively the covariance matrices of the sources
and the noise at time . If the sources are nonstationary with respect to their
covariances, then in general for . This allows to write
multiple conditions for different choices of to solve for , ,and .
Note that the covariances matrices and are diagonal. The diagonality of
follows from the independence of the sources, and can be taken diagonal
because the components of the noise vector are assumed to be uncorrelated.
We can also look at cross-covariance matrices =E
over time. This approach has been mentioned in the context of convolutive mixtures
in [456], and it can be used with instantaneous mixtures as described in Chapter 18.
For convolutive mixtures, we can write in frequency domain for sample averages
[359, 356]
(19.32)
where is the averaged spatial covariance matrix. If is nonstationary, one can
again write multiple linearly independent equations for different time lags and solve
for unknowns or find LMS estimates of them by diagonalizing a number of matrices
in the frequency domain [123, 359, 356].
If the mixing system is minimum phase, decorrelation alone can provide a unique
solution, and the nonstationarity of the signals is not needed [55, 280, 402]. Many
methods have been proposed for this case, for example, in [113, 120, 149, 281,
280, 296, 389, 390, 456]. More references are given in [430]. However, such
decorrelating methods cannot necessarily be applied to practical communications
and audio separation problems, because the mixtures encountered there are often not
minimum-phase. For example in the cocktail-party problem the system is minimum
phase if each speaker is closest to his or her “own” microphone, otherwise not [430].
19.2.6 Other methods for convolutive mixtures
Many methods proposed for blind separation of convolutive mixtures are extensions
of earlier methods originally designed for either the standard linear instantaneous BSS

to nonlinear PCA criteria [236] and several other ICA methods [11].
In this chapter, we have briefly discussed Bussgang, cumulant, and ICA based
methods for blind deconvolution. Still one prominent class of blind deconvolution
and separation methods for convolutive mixtures consists of subspace approaches
[143, 171, 311, 315, 425]. They can be used only if the number of output signals
(observed mixtures) strictly exceeds the number of sources. Subspace methods
resort to second-order statistics and fractional sampling, and they are applicable to
cyclostationary source signals which are commonplace in communications [91].
General references on blind deconvolution are [170, 171, 174, 315]. Blind decon-
volution and separation methods for convolutive mixtures have often been developed
in context with blind channel estimation and identification problems in communica-
tions. These topics are beyond the scope of our book, but the interested reader can
find useful review chapters on blind methods in communications in [143, 144].
In the second half of this chapter, we have considered separation of convolutive
mixtures. The mixing process then takes place both temporally and spatially, which
complicates the blind separation problem considerably. Numerous methods for
handling this problem have been proposed, but it is somewhat difficult to assess
their usefulness, because comparison studies are still lacking. The large number of
parameters is a problem, making it difficult to apply convolutive BSS methods to large
APPENDIX
369
scale problems. Other practical problems in audio and communications applications
have been discussed in Torkkola’s tutorial review [430]. More information can be
found in the given references and recent reviews [257, 425, 429, 430] on convolutive
BSS.
Appendix Discrete-time filters and the -transform
In this appendix, we briefly discuss certain basic concepts and results of discrete-time signal
processing which are needed in this chapter.
Linear causal discrete-time filters [169, 339] can generally be described by the difference
equation

convolution sum
(A.3)
is the product of the z-transforms of the sequences and :
(A.4)
370
CONVOLUTIVE MI XTURES AND BLIND DECONVOLUTION
The weights in (A.3) are called impulse response values, and the quantity =
is called transfer function. The transfer function of the convolution sum (A.3) is
the
-transform of its impulse response sequence.
The Fourier transform of a sequence is obtained from its
-transform as a special case by
constraining the variable
to lie on the unit circle in the complex plane. This can be done by
setting
(A.5)
where
is the imaginary unit and the angular frequency. The Fourier transform has similar
convolution and other properties as the
-transform [339].
Applying the
-transform to both sides of Eq. (A.1) yields
(A.6)
where
(A.7)
is the -transform of the coefficients where the coefficient
corresponds to ,and is the -transform of the output sequence .
and are defined quite similarly as -transform of the coefficients ,
and the respective input signal sequence
.