Solving the Permutation and Circularity Problemsof 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

Abstract
Blind source separation (BSS) for convolutive mixtures
can be performed efficiently in the frequency domain,
where independent component analysis (ICA) is applied
separately in each frequency bin. However, frequencydomain BSS involves two major problems that must besolved. The first is the permutation problem: the permutation ambiguity of ICA should be aligned so that a separated signal in the time-domain contains the frequency
components of the same source signal. The second problem is the circularity problem: the frequency responses
obtained separately by ICA should be constrained so thatthe corresponding time-domain filter does not rely on thecircularity effect of discrete frequency representation. This
paper discusses these two problems and presents our methods for solving them. The effectiveness of the BSS method
is shown by experimental results for the separation of up
to four sources in a reverberant environment.

1. Introduction
Blind source separation (BSS) [1, 2] is a technique for
estimating original source signals solely from their mixtures at sensors. Its potential audio signal applications
include teleconferences, voice control and hearing aids.
In such applications, signals are mixed in a convolutive
manner with reverberations. This makes the BSS problem much more difficult to solve than the instantaneous
mixture problem. Let us formulate the convolutive BSS
problem. Suppose that N source signals s k (t) are mixed
and observed atM sensors
N xj (t) = k=1 l hjk (l)sk (t − l),where hjk (l) represents the impulse response from source
k to sensor j. The goal is to obtain N output signals y i (t),each of which is a filtered version of a source s k (t). If wehave enough sensors (M ≥ N ), a set of FIR filters w ij (l)of length L is typically used to produce separated signals
M L−1yi (t) = j=1 l=0 wij (l)xj (t − l)at the outputs, and independent component analysis (ICA)[3, 4] is generally used to obtain the FIR filters w ij (l).
We can classify the BSS methods into two types basedon how we apply ICA to convolutive mixtures.
The first is time-domain BSS, where ICA is applied
directly to the convolutive mixture model [5, 6]. It pro-Mo2.D.3

vides good separation once the algorithm converges, andis easy to extend to more than two sources. However, if
the algorithm starts from an initial solution far from thefinal one, it takes many iterations and much time to converge because filter coefficients w ij (l) are interdependent
in the algorithm.
The other approach is frequency-domain BSS, wherecomplex-valued ICA for an instantaneous mixture is applied in each frequency bin [7–11]. The merit of this approach is that the ICA algorithm can be performed separately at each frequency, and the convergence of each
ICA is fast. However, frequency-domain BSS involves
two major problems that must be solved. The first is
the well-known permutation problem. Although various
methods have been proposed for overcoming the permutation problem, most of them are applicable only to twosources or their performance deteriorates as the numberof sources increases. Section 3 of this paper presents amethod for solving the permutation problem robustly andprecisely. It is based on direction of arrival (DOA) estimation and also the inter-frequency correlation of signal
envelopes. The method performs well even when there
are more than two sources.
However, just solving the permutation problem does
not provide good separation performance. We need tosolve the second problem, namely the circularity problem, which originates with the circularity effect of discrete frequency representation. This problem is not aswell known as the permutation problem. We discuss theinfluence and the reason for this problem and present anapproach for its solution in Sec. 4. By solving these twoproblems, the frequency-domain BSS effectively separates many sources in a reverberant environment with low
computational cost. The effectiveness of the presented
methods is shown by experimental results for up to four
sources in Sec. 5.

2. Frequency-domain BSS
This section describes frequency-domain BSS whose flow
is shown in Fig. 1. First, time-domain signals x j (t) at
sensors are converted into frequency-domain time-series
signals Xj (f, t) by short-time Fourier transform (STFT),
where t is now down-sampled with the distance of theI - 89

X( f , t )ICAseparated signals

w (l )x(t )STFTW( f )permutation

180y (t )
IDFT
scaling

160
140

W( f )

Direction (deg)mixed signals

smoothing

Figure 1: Flow of frequency-domain BSS

120100806040frame shift. Then, the frequency responses W ij (f ) of filters wij (l) are obtained by complex-valued ICA
Y(f, t) = W(f )X(f, t),where W(f ) is a separation matrix whose elements areWij (f ), X(f, t) = [X1 (f, t), . . . , XM (f, t)]T and Y(f, t)= [Y1 (f, t), . . . , YN (f, t)]T. Any complex-valued ICA
algorithm can be used in this scheme.
The ICA solution in each frequency bin has permutation and scaling ambiguity: even if we permute the rowsof W(f ) or multiply a row by a constant, it is still an ICA
solution. The permutation ambiguity should be fixed
so that Yi (f, t) at all frequencies correspond to the same
source si (t). Thus, the rows of W(f ) are permuted by apermutation Π f : {1, . . . , N } → {1, . . . , N } obtained bya method, such as those discussed in Sec. 3. The scaling
ambiguity is solved by the frequency-domain version of
the minimal distortion principle, W(f ) ← diag[W(f ) −1 ]W(f ), to make Yi (f, t) as close to Xi (f, t) as possible[5, 9]. Then, we solve the circularity problem by the spectral smoothing described in Sec. 4. Finally, time-domain
separation filters wij (l) are obtained by applying inverse
DFT to Wij (f ).

3. The permutation problem
Various methods have been proposed for solving the permutation problem. Let us begin with the direction of arrival (DOA) approach, where the DOAs of source signals are estimated to align permutations. The methods
described in [10, 11] plot the directivity patterns formed
by a separation matrix, and estimate the direction of asource as the minimum of a directivity pattern. In practice, the methods only work for two sources since the directivity patterns become too complicated to analyze formore than two sources.
We have proposed another way of estimating directions that works for any number of sources [12]. It first
calculates the inverse H(f ) = W(f )−1 of the separation matrix W(f ) obtained by ICA. Then, the direction
θi of a source corresponding to the i-th row of W(f ) is
calculated byarg(Hji /Hj  i ),(1)θi = arccos
2πf c−1 (dj − dj  )where Hji is the element of the j-th row and i-th columnof H(f ), c is the propagation velocity, and d j is the position of sensor j. The scaling ambiguity of the ICA solution is eliminated by taking the ratio H ji /Hj  i of two

2001000

2000
Frequency (Hz)

3000

4000

Figure 2: DOA estimations for four sources using ICA

elements from the same column. Figure 2 shows DOA estimations for mixtures of four sources obtained with (1).
We see that directions are well estimated and permutation can be aligned by sorting the estimated directions
at each frequency. However, at some frequencies (especially low frequencies), estimations are not obtained or
are inaccurate. Therefore, the DOA approach alone does
not provide a highly precise solution as shown at “D” inFig. 6.
We also employ the correlation approach [8, 9] to alignpermutations more precisely. We use the envelope v if (t) =|Yi (f, t)| of a separated signal Y i (f, t) to measure correlation. The correlation between two signals x(t) and y(t)is defined as cor(x, y) = (µx·y − µx · µy )/(σx · σy ),where µx is the mean and σx is the standard deviationof x. Envelopes have high correlation at neighboring frequencies if separated signals correspond to the same signal. A simple criterion for deciding the permutation Π fof frequency f is to maximize the sum of the correlations
between neighboring frequencies within distance δ:Nfg
Πf = argmaxΠ |g−f |≤δ i=1 cor(vΠ(i), vΠ),(2)g (i)where Πg is the permutation at frequency g. This criterion is based on local information and has a drawback inthat mistakes in a narrow range of frequencies may leadto the complete misalignment of the frequencies beyond
the range. As shown at “C” in Fig. 6, the correlation approach alone does not provide a robust solution.
Our method effectively integrates these two approaches
to solve the permutation problem robustly and precisely[12]. First, we decide permutations for frequency bins
where the confidence of the DOA estimation is sufficiently
high. Let F be the set of frequency bins where the permutation is already decided. Then, we apply (2) to frequency
bins that are close neighbors with f ∈ F. This procedure
can avoid a consecutive misalignment. However, the permutations at low frequencies are not usually decided at
this stage because the DOA estimations are unreliable asshown in Fig. 2. To decide permutations for these frequencies, we utilize the harmonic structure of a signal.
If the signals are speech, there is a strong correlation be-I - 90

Target: u11(l)0Amplitude

Amplitude

1−11000

2000

3000

4000

5000

6000

Amplitude

Amplitude

0−1
1000

2000 3000 4000
Time (sample)

5000

0.5

0.500−0.5

1Interference: u14(l)

3000

4000

5000

−0.5

0.50.500

3000

4000

5000

6000

Figure 3: Periodical time-domain filter represented byfrequency responses sampled at L = 2048 points (above)and its one-period realization (below).

tween the envelopes of a frequency f and its harmonics
2f, 3f and so forth. Thus, we decide the permutation at
frequency f with high confidence, if the sum shown below can be clearly maximized:
Nfg, vΠ).
Πf = argmaxΠ g=2f,3f,... i=1 cor(vΠ(i)g (i)Finally, we apply (2) again for frequencies where the permutation is not yet decided.

4. The circularity problem
The frequency-domain BSS described in Sec. 2 is influenced by the circularity of discrete frequency representation. The circularity refers to the fact that frequency
responses sampled at L points with an interval f s /L (fs :sampling frequency) represent a periodical time-domain
signal whose period is L/f s . Figure 3 shows two timedomain filters. The upper one is a periodical infinitelength filter represented by frequency responses W ij (f )calculated by ICA at L points. Since this filter is unrealistic, we usually use its one-period realization shown in
the lower part.
However, such one-period filters may cause a problem. Figure 4 shows impulse responses from a sourcesk (t) to an output y i (t):M L−1uik (l) = j=1 τ =0 wij (τ )hjk (l − τ ).
Those on the left u 11 (l) correspond to the extraction ofa target signal, and those on the right u 14 (l) correspondto the suppression of an interference signal. The upper
responses are obtained with the infinite-length filters, andthe lower ones with the one-period filters. We see that theone-period filters create spikes, which distort the target
signal and degrade the separation performance.
Here, we consider two reasons for these spikes. One
is that the frequency responses are under-sampled and thecorresponding time-domain filter has an overlap with another period. ICA solutions separately obtained in frequency bins generally require the time-domain filters tobe longer than L. The other reason is that adjacent periods work together to perform some filtering even if the−0.5

3000
4000
5000
Time (sample)

−0.5

3000
4000
5000
Time (sample)

Figure 4: Impulse responses u ik (l) obtained with the periodical filter (above) and with its one-period realization(below).
first problem is solved. The effect of the second problem
can be mitigated if the amplitude of the filter coefficientsaround both ends is small. It might be thought that a sufficiently large L would solve these problems. However,an excessively long STFT frame results in fewer samples
at each frequency and worse ICA solutions [13].
Our approach to this problem involves controlling thefrequency responses W ij (f ) so that the correspondingtime-domain filter wij (l) fits length L and has small amplitude around the ends. This is carried out by windowing wij (l)·g(l) with a window g(l) that tapers smoothly
to zero at each end, such as a Hanning window. With
this operation, frequency responses W(f ) obtained by s −∆fG(φ)W(f−φ),
ICA are smoothed as W(f ) ← fφ=0
where G(f ) is the frequency response of g(l) and ∆f =fs /L. If a Hanning window is used, the frequency responses are smoothed as W(f ) ← [W(f −∆f )+2W(f )+W(f +∆f)]/4. The windowing successfully eliminates
the spikes. However, it changes the frequency response
obtained by ICA and causes an error. Thus, we minimize
the error by adjusting the scaling of the ICA solution before windowing. See [14] for the details of the error andhow to minimize it.

5. Experimental results
We performed experiments to separate speech signals inan environment whose conditions are summarized in Fig. 5.
We tested cases of two, three and four sources whosepositions are indicated in Table 1. The sensors were arranged linearly, and the number of sensors used was thesame as the number of sources. We used filters of length
L = 2048 because this length performed the best under the conditions. The ICA algorithm we used was thecomplex-valued version of FastICA [4].
The results shown in Table 1 are the average of eightcombinations of 7-second speeches. The signal to interference ratio (SIR) at output i is 
calculated as the ratio of
the power of a target component l uii (l)si (t−l) and in-I - 91

Reverberation time:
130 msFor three sources

Sampling rate:
8000 Hzb 110°4cm
4cm

SIR (dB)

a 150°

1.2m

15
10
Average of 8 cases
Each of 8 cases

5c 70°4cm

D

SIR (dB)

Figure 5: Experimental conditions
Table 1: Overall results
3/abd
no yesD+C+HaOptimalFor four sources

d 30°

Room size:
4.45 m × 3.55 m × 2.50 mC#sources / position
Spectral smoothing

2/ac
no yesSIR (dB)
Execution time (s)18.4 21.2 13.3 16.5 9.4 11.6
4.1 4.1 7.5 7.6 12.3 12.5

6. Conclusion
This paper presented effective methods for overcoming
the two major problems of frequency domain BSS. We
succeeded in separating many sources mixed in a real environment with a short execution time. The results shown
here were for up to four sources with linearly arranged
sensors. We have also separated six sources with a planar
array of eight sensors based on similar techniques [15].

7. References[1] S. Haykin, Ed., Unsupervised Adaptive Filtering (Volume
I: Blind Source Separation), John Wiley & Sons, 2000.
[2] A. Cichocki and S. Amari, Adaptive Blind Signal andImage Processing, John Wiley & Sons, 2002.
[3] T. W. Lee, Independent Component Analysis - Theory andApplications, Kluwer Academic Publishers, 1998.
[4] A. Hyvärinen, J. Karhunen, and E. Oja, Independent Component Analysis, John Wiley & Sons, 2001.

5
Average of 8 cases
Each of 8 cases

04/abcdno yes
terference components k=i l uik (l)sk (t − l). We seethat the spectral smoothing discussed in Sec. 4 improves
the average SIR with every setup. The short execution
time, as shown in Table 1, enables the BSS system to perform in real-time if the number of source signals is notvery large.
Figure 6 shows SIRs for three and four sources withthe different methods for solving the permutation problem discussed in Sec. 3: “D” is the DOA approach alone,“C” is the correlation approach alone, “D+C+Ha” is theproposed method, and “Optimal” is the optimal solutionobtained by utilizing the information of s k (t) and hjk (l).
The performance of “D” was stable but insufficient. The
performance of “C” was unstable and very poor for foursources. The proposed method “D+C+Ha” performed
very well and was close to “Optimal” even when the number of sources was more than two.

10D

C

D+C+HaOptimalFigure 6: Separation performance with different methods
for solving the permutation problem[5] K. Matsuoka and S. Nakashima, “Minimal distortion principle for blind source separation,” in Proc. ICA 2001, Dec.
2001, pp. 722–727.
[6] S. C. Douglas and X. Sun, “Convolutive blind separationof speech mixtures using the natural gradient,” SpeechCommunication, vol. 39, pp. 65–78, 2003.
[7] P. Smaragdis, “Blind separation of convolved mixturesin the frequency domain,” Neurocomputing, vol. 22, pp.
21–34, 1998.
[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] S. Kurita, H. Saruwatari, S. Kajita, K. Takeda, andF. Itakura, “Evaluation of blind signal separation method
using directivity pattern under reverberant conditions,” inProc. ICASSP 2000, June 2000, pp. 3140–3143.
[11] M. Z. Ikram and D. R. Morgan, “A beamforming approachto permutation alignment for multichannel frequencydomain blind speech separation,” in Proc. ICASSP 2002,May 2002, pp. 881–884.
[12] H. Sawada, R. Mukai, S. Araki, and S. Makino, “A robust
and precise method for solving the permutation problemof frequency-domain blind source separation,” in Proc.
ICA2003, Apr. 2003, pp. 505–510.
[13] S. Araki, R. Mukai, S. Makino, T. Nishikawa, andH. Saruwatari, “The fundamental limitation of frequency
domain blind source separation for convolutive mixturesof speech,” IEEE Trans. Speech Audio Processing, vol.
11, no. 2, pp. 109–116, 2003.
[14] H. Sawada, R. Mukai, S. de la Kethulle, S. Araki, andS. Makino, “Spectral smoothing for frequency-domain
blind source separation,” in Proc. IWAENC2003, Sept.
2003.
[15] R. Mukai, H. Sawada, S. de la Kethulle, S. Araki, andS. Makino, “Array geometry arrangement for frequency
domain blind source separation,” in Proc. IWAENC2003,
Sept. 2003.

I - 92