➠➡

A ROBUST APPROACH TO THE PERMUTATION PROBLEM
OF FREQUENCY-DOMAIN BLIND SOURCE SEPARATION
Hiroshi Sawada

Ryo Mukai

Shoko Araki

Shoji Makino

NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, Japan{sawada,ryo,shoko,maki}@cslab.kecl.ntt.co.jp
ABSTRACTThis paper presents a robust and precise method for solving
the permutation problem of frequency-domain blind source
separation. It is based on two previous approaches: the direction of arrival estimation approach and the inter-frequency
correlation approach. We discuss the advantages and disadvantages of the two approaches, and integrate them to exploit the both advantages. We also present a closed form
formula to calculate a null direction, which is used in estimating the directions of source signals. Experimental results show that our method solved permutation problems almost perfectly for a situation that two sources were mixed
in a room whose reverberation time was 300 ms.
1. INTRODUCTION
Blind source separation (BSS) is a technique for estimating original source signals using only sensor observations,which consist of mixtures of the original signals. If the
mixture is instantaneous, we can directly apply independent
component analysis (ICA) [1, 2] to separate mixed signals.
In a real room environment, however, signals are mixed ina convolutive manner with reverberations. This makes the
BSS problem difficult since we need a set of filters, not justscalars, to separate signals. One of the major methods toobtain such separating filters is frequency-domain BSS [3–10], where a convolutive mixture in the time domain is converted into multiple instantaneous mixtures. Thus, we canapply ICA to instantaneous mixtures in every frequency bin.
The problem with frequency-domain BSS is the indeterminacy of permutation that is inherent to ICA. We need tomap a separated signal at each frequency to a target source
signal so that we properly reconstruct a separated signal in
the time domain. Various approaches have been proposedto the permutation problem. Making separating matrices
smooth in the frequency domain is one solution. This has
been realized by averaging separating matrices with adjacent frequencies [3], limiting the filter length in the time
domain [4], or considering the coherency of separating matrices at adjacent frequencies [5]. Another approach is basedon direction of arrival (DOA) estimation in the beamforming theory [6, 7]. If source signals are speech, we can employ the inter-frequency correlations of signal envelopes to0-7803-7663-3/03/$17.00 ©2003 IEEEalign permutations [8, 9]. Each of these approaches has different characteristics. They may perform well under certain
specific conditions but not others. Therefore, we believethat integrating some of these approaches is one way of obtaining better performance.
In this paper, we propose a new method for solving the
permutation problem, which incorporates two of the previous approaches. The first is the DOA approach, which is
described in Sec. 3. The second is based on inter-frequency
correlations, which is discussed in Sec. 4. Our new method
is proposed in Sec. 5. The experimental results reported inSec. 6 are promising.
The second contribution of this paper is a closed form
formula for calculating a null direction, which is used in estimating the directions of source signals (Sec. 3). It dramatically reduces the calculation cost of null directions compared with the conventional method by searching for theminimum of a directivity pattern.
2. FREQUENCY-DOMAIN BSS
Suppose that P source signals s p (t) are mixed and observedP 
at Q sensors xq (t) =k hqp (k)sp (t − k), wherep=1
hqp (k) represents the impulse response from source p tosensor q. The goal of BSS is to obtain separated signals
y1 (t), . . . , y P (t) that are estimates of the source signals s1 (t),. . . , s P (t). The separating system typically consists of aset of FIR filters w rq (k) that produces separated signals
Q 
yr (t) = q=1 k wrq (k)xq (t − k).
This paper employs a frequency-domain approach where
frequency responses Wrq (f) of the separating filter w rq (k)are first calculated. By L-point short time DFT, time-domain
signals xq (t) are converted into frequency-domain time-series
signals Xq (f, m), where f = 0, fs /L, . . . , f s (L − 1)/L
(fs : sampling frequency), and m is the frame index. Assume that X(f, m) is a Q-dimensional vector X(f, m) =[X1 (f, m), . . . , X Q (f, m)]T. To obtain frequency responses
Wrq (f), we solve ICA problem Y(f, m) = W(f)X(f, m),where Y(f, m) = [Y1 (f, m), . . . , Y P (f, m)]T and W(f) isa P × Q matrix whose elements are Wrq (f). Yr (f, m) is afrequency-domain representation of y r (t).
The ICA algorithm we use is the information maximization approach [1] combined with the natural gradient [2]. A

V - 381ICASSP 2003

➡

➡

Gain

LPDJLQDU\Y 3156 Hz
1
Y 3156 Hz

1

θ °

2

θ °

0.5

:U

:U
θ °

0045

90
Direction (deg)135
Y 176 Hz1
Y 176 Hz

1
Gain

θQXOO

180

Fig. 2. Directivity pattern on a complex plane

2

0.5
0
0

UHDO

45

90
Direction (deg)

135

180

Fig. 1. Directivity patterns
separating matrix W is gradually improved by the learning
rule ∆W = µ [I − Φ(Y)YH ] W, where µ is a step-size
parameter, · denotes the averaging operator, and Φ(·) is anonlinear function for a complex signal Yr = |Yr | ej·phase(Yr ) .
∂log p(|Yr |) ej·phase(Yr ) assuming
We use Φ(Yr ) = − ∂|Yr|that the density p(Yr ) is independent of the phase [10].
An ICA solution has an ambiguity on permutation: if
we permute the rows of W(f), it is still a solution. Thus,
we have to align the rows of W(f) so that Y r (f, m) at all
frequencies correspond to the same source sp (t). This is
the permutation problem. After solving the problem, we
obtain separating filters w rq (k) by applying inverse DFT to
Wrq (f).
3. THE DIRECTION OF ARRIVAL APPROACH
In this section, we first review the method [6, 7] for solving the permutation problem by estimating the directions ofsource signals. If the sensor spacing is appropriately narrow (e.g., conditions in Table 1), each row of W(f) usuallyforms spatial nulls in the directions of jammer signals andextracts a target signal in another direction [11]. By analyzing the null directions, we can estimate the directions
Θ(f) = [θ1 (f), . . . , θP (f)]T of target signals that every
row of W(f) extracts. Then, we can align permutations
according to Θ(f).
The null directions can be analyzed by plotting the directivity pattern of each output Yr (f, m). Let dq be the position of sensor q (we assume linearly arranged array sensors),and θp be the direction of source sp (the direction orthogonal to the array is 90 ◦ ). In the beamforming theory [12],the frequency response of an impulse response hqp (t) is ap−1
proximated as Hqp(f) = ej2πf c dq cos θp , where c is thevelocity of propagation. In this approximation, we assume
a plane wavefront and no reverberation. The frequency response Brp (f) from a source sp to a separated signal yr can

Q−1
be expressed as Brp (f) = q=1 Wrq (f) · ej2πf c dq cos θp .
If we regard θp as a variable θ, the formula is expressed as
j2πf c−1 dq cos θBr (f, θ) = Q. It changes acq=1 Wrq (f) · e
cording to the direction θ, and thus is called a directivity
pattern.
Figure 1 shows directivity patterns for two sources. The
upper part (3156 Hz) shows that output Y 1 extracts a source
signal originating from around 45 ◦ and suppresses the othersignal coming from around 125 ◦ . With a similar consideration on Y 2 , we estimate the directions Θ(3156) = [45, 125] Tof the target signals. A simple way to solve the permutation
problem is to permute W(f) at each frequency so that Θ(f)are sorted. However, not every frequency bin gives us suchan ideal directivity pattern. The lower part of Fig. 1 is thepattern at a low frequency (176 Hz). We see that a null is
not well formed for Y 1 and the null of Y 2 is in an obscuredirection. In fact, we cannot estimate Θ(176) or decide apermutation for this frequency with confidence.
Now we state two problems with this method: 1) directions of arrival cannot be well estimated at some frequencies, especially at low frequencies where the phase difference caused by a sensor spacing is very small, 2) the calculation of null directions by plotting directivity patterns istime consuming. The first problem will be solved in Sec. 5.
For the second problem, here we provide a closed form
formula for calculating a null direction (only for two sensors). The directivity pattern B r (f, θ) can be simplified as−1
Br (f, θ) = Wr1 (f) + Wr2 (f) · ej2πf c d cos θ if we assume
d1 = 0 and d2 = d. As cos θ changes from 1 to −1 in accordance with the change of direction θ, the frequency response Br (f, θ) rotates around a circle whose center andradius are Wr1 and Wr2 , respectively (Fig. 2). We see thatspatial aliasing does not occur if 2πfc−1 d < π ⇔ f < c/(2d).
When the distance from the origin is minimized, the plotcorresponds to the null direction θ null . The situation is one−1
where Wr2 rotated by ej2πf c d cos θnull points to the opposite direction of W r1 : angle(Wr2 ) + 2πfc−1 d cos θnull =angle(Wr1 ) ± π. Therefore,
angle(Wr1 ) − angle(Wr2 ) ± π
θnull = cos−1
2πfc−1 d
The sign of ±π is selected so that the numerator is in the −π
to π range. There are some cases where the absolute valueof the argument of cos −1 is larger than 1. This corresponds
to a situation where there is no null in 0 ◦ ≤ θ ≤ 180◦ .

V - 382

➡

➡

1
0

50

100

150

200

250

|Y1| 1566 Hz|Y2| 1566 Hz

10
for ( ∀ f ) Θ(f) = DOA(f, W(f))
mΘ = Θ(f)f /* averaged directions */F = ∅ /* the set of fixed frequencies *//* Fix permutations by the DOA approach */for ( ∀ f ) {if ( confident (Θ(f), mΘ , W(f)) ) {πf = getPermutation(Θ(f))
F = F ∪ {f}}}/* Fix permutations by the correlation approach */while ( ∃ f ∈ F ) {for ( ∀ f ∈ F ) {f, vπkk (p) )cf = maxπ |k−f |≤D,k∈F p cor(vπ(p)f
πf = argmaxπ |k−f |≤D,k∈F p cor(vπ(p) , vπkk (p) )}i = argmaxf cf
F = F ∪ {i}ci = 0}|Y | 1562 Hz
1|Y2| 1562 Hz

50

100

150

200

250

|Y1| 3516 Hz|Y2| 3516 Hz

2
1
0

50

100
150
Frame index

200

250

Fig. 3. Envelopes at different frequencies

4. THE CORRELATION APPROACH
This section discusses an approach to permutation alignment based on inter-frequency correlation [5, 8, 9]. We takethe envelope vrf (m) = |Yr (f, m)| of a separated signal
Yr (f, m) to measure correlations. Let us define the correlation of two signals x(m) and y(m) as cor(x, y) = [x · y−x · y]/(σx · σy ), where · is an averaging operator and σ
is a standard deviation. Based on this definition, cor(x, x) =1, and cor(x, y) = 0 if x and y are uncorrelated. Envelopes
have high correlations at neighboring frequencies if separated signals correspond to the same source signal [8, 9].
Figure 3 shows an example. Two envelopes v11562 and v11566 ,as well as v21562 and v21566 , are highly correlated. Thus, calculating such correlations helps us to align permutations.
Henceforth let π denote a permutation: {1, . . ., P } →{1, . . ., P }. A simple criterion to decide a permutation π f
of frequency f is to maximize the sum of correlations between neighboring frequencies within distance D:f
πf = argmaxπ |k−f |≤D p cor(vπ(p), vπkk(p) ),(1)
where πk is the permutation at frequency k. This criterion isbased on local information and has a drawback that mistakes
in a narrow range of frequencies may lead to the complete
misalignment of the frequencies beyond that point. To avoid
this problem, the method proposed in [9] does not limit thefrequency range in which correlations are calculated. It decides permutations one by one based on the criterion:f
πf = argmaxπ p cor( vπ(p), k∈F vπkk(p) ),(2)
where F is a set of frequencies in which the permutation
is decided. This method assumes high correlations of envelopes even between frequencies that are not close neighbors, although this is not always the case. As shown in Fig.
3, vr1566 and vr3516 do not have a high correlation. Therefore, this method still has a drawback in that permutations
may be misaligned at many frequencies.

Fig. 4. Pseudo-code for the integrated method
5. A ROBUST INTEGRATED APPROACH
In this section, we propose a robust and precise approach
which integrates the two approaches discussed above. We
consider their characteristics below.
robustness The direction of arrival (DOA) approach is robust since a misalignment at a frequency does not affect other frequencies. The correlation approach is
not robust as discussed in Sec. 4.
preciseness The DOA approach is not precise since the evaluation is based on the approximation of a mixing system as explained in Sec. 3. The correlation approachis precise as long as signals are well separated by ICA
since the measurement is based on separated signals.
Our approach benefits from both advantages: the robustness of the DOA approach and the preciseness of the correlation approach. Figure 4 shows the pseudo-code.
We first fix permutations at some frequencies where theconfidence of the DOA approach is sufficiently high. The
procedure confident decides whether the confidence is highenough. Our criteria for the decision are: 1) the number of
estimated directions is the same as the number of sources,
2) the directions Θ(f) do not largely differ from the averaged directions mΘ , 3) the SNR calculated by the frequency
responses Br (f, θp ) for each direction is sufficiently large.
Then, we decide the permutations for the remaining frequencies by the correlation method without changing the
permutations fixed by the DOA approach. The permutations are decided in order of the sum of correlations with
fixed frequencies k ∈ F within distance |k − f| ≤ D.

V - 383

➡

➠

Table 1. Experimental conditions
6 sec
50 ◦ and 120◦ (2 sources)d = 4 cm
TR = 300 ms
fs = 8 kHz
L = 2048
Φ(Yr ) = ej·phase(Yr )D = 3 · f s /L

15
SNR (dB)

Length of source signal
Direction of sources
Distance between 2 sensors
Reverberation time
Sampling rate
Frequency resolution
Nonlinear function
Distance to take correlation

10
DOA
Cor (1)
Cor (2)Integrated
Optimal5This approach does not result in a large misalignment
as long as the permutations fixed by the DOA approach arecorrect. Moreover, the correlation part compensates for thelack of preciseness of the DOA approach.

0
1

2

3

4

5 6 7 8 9 10 11 12 ave
Combination of speechFig. 5. Experimental results
6. EXPERIMENTAL RESULTS
We performed experiments to separate speech signals in areverberant environment whose conditions are summarizedin Table 1. We generated mixed signals by convolving aspeech signal sp (t) and an impulse response hqp (t) so that
we can calculate
SNRs (signal-to-noiseratios)by
10 log[ r=p t yrp (t)2 ] − 10 log[ r=p t yrp (t)2 ],Q 
where yrp (t) = q=1 k wrp (k)xqp (t − k) and xqp (t) =k hqp (k)sp (t − k). We separated 12 combinations ofspeech signals with 4 different methods for comparison:
the DOA approach, the correlation approach based on (1),the correlation approach based on (2), and our proposed
method. Figure 5 shows the results, where “ave” shows theaverage result of 12 combinations for each method.
The performance with “DOA” is stable, but not sufficient. The results with “Cor (1)” and “Cor (2)” are not stable
and sometimes very poor, although most of the time they arevery good. The “Integrated” method offers stable and very
good results. The percentages of the permutations fixed by
the DOA approach with confidence were around 45%. We
additionally obtained optimal permutations by maximizing
the SNR at each frequency. Although this is not a realistic
solution, we can estimate the upper bounds of performance.
The average of “Optimal” was 16.8 dB. Since the average
performance with “Integrated” was 16.3 dB, we consider
that the integrated method performed very well.
7. CONCLUSIONSWe proposed a robust and precise method for solving permutation problem. It integrates two previous approaches:
the DOA approach and the correlation approach. The criterion of the DOA approach is directions which is absolute.
This makes the approach robust. By contrast, the criterionof the correlation approach is calculated from the separated
signals themselves. This makes the approach precise. Our
proposed method benefits from both advantages. In our experiments, the proposed method solved permutation problems almost perfectly under conditions whereby 2 sourceswere mixed in a room where TR = 300 ms.

8. REFERENCES[1] A. Bell and T. Sejnowski, “An information-maximization approach to blind separation and blind deconvolution,” NeuralComputation, vol. 7, no. 6, pp. 1129–1159, 1995.
[2] S. Amari, “Natural gradient works efficiently in learning,”
Neural Computation, vol. 10, no. 2, pp. 251–276, 1998.
[3] P. Smaragdis, “Blind separation of convolved mixtures in
the frequency domain,” Neurocomputing, vol. 22, pp. 21–34,
1998.
[4] L. Parra and C. Spence, “Convolutive blind separation of
non-stationary sources,” IEEE Trans. Speech Audio Processing, vol. 8, no. 3, pp. 320–327, May 2000.
[5] F. Asano, S. Ikeda, M. Ogawa, H. Asoh, and N. Kitawaki,“A combined approach of array processing and independent
component analysis for blind separation of acoustic signals,”in Proc. ICASSP 2001, May 2001, pp. 2729–2732.
[6] S. Kurita, H. Saruwatari, S. Kajita, K. Takeda, and F. Itakura,“Evaluation of blind signal separation method using directivity pattern under reverberant conditions,” in Proc. ICASSP
2000, June 2000, pp. 3140–3143.
[7] M. Z. Ikram and D. R. Morgan, “A beamforming approach topermutation alignment for multichannel frequency-domain
blind speech separation,” in Proc. ICASSP 2002, May 2002,
pp. 881–884.
[8] J. Anemüller and B. Kollmeier, “Amplitude modulation
decorrelation for convolutive blind source separation,” inProc. ICA 2000, June 2000, pp. 215–220.
[9] N. Murata, S. Ikeda, and A. Ziehe, “An approach to blindsource separation based on temporal structure of speech signals,” Neurocomputing, vol. 41, no. 1-4, pp. 1–24, Oct. 2001.
[10] H. Sawada, R. Mukai, S. Araki, and S. Makino, “Polar coordinate based nonlinear function for frequency-domain blindsource separation,” in Proc. ICASSP 2002, May 2002, pp.
1001–1004.
[11] H. Sawada, S. Araki, R. Mukai, and S. Makino, “Blindsource separation with different sensor spacing and filter
length for each frequency range,” in Proc. Workshop on Neural Networks for Signal Processing, Sept. 2002, pp. 465–474.
[12] B. D. Van Veen and K. M. Buckley, “Beamforming: a versatile approach to spatial filtering,” IEEE ASSP Magazine, pp.
2–24, Apr. 1988.

V - 384