➠➡
A SPARSENESS - MIXING MATRIX ESTIMATION (SMME)SOLVING THE UNDERDETERMINED BSS FOR CONVOLUTIVEMIXTURES
Audrey Blin†‡

Shoko Araki‡

Shoji Makino‡†

Université du Québec, INRS EMT
800 dela Gauchetière Ouest, Suite 6900, Montréal, Québec, H5A 1K6 Canadae-mail: blin@inrs-emt.uquebec.ca‡
NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237, JAPANABSTRACT
We propose a method for blindly separating realenvironment speech signals with as less distortion as possible
in the special case where speech signals outnumber sensors.
Our idea consists in combining sparseness with the use of an
estimated mixing matrix. First, we use a geometricalapproach to perform a preliminary separation and to detect
when only one source is active. This information is then used
to estimate the mixing matrix. Then we remove one sourcefrom the observations and separate the residual signals with
the inverse of the estimated mixing matrix. Experimental
results in a real environment (TR=130ms and 200ms) showthat our proposed method, which we call Sparseness –Mixing Matrix Estimation (SMME), provides separated
signals of better quality than those extracted by only using
the sparseness property of the speech signal.

However we remember that in the determined problem oneof the common ways of solving the BSS issue was toestimate and then invert the mixing matrix modeling thesystem [2,5]. But, here, where sources outnumber sensors,
the mixing matrix is no longer square and we cannot use thissolution.
Nevertheless this gives us the idea to combine thesparseness properties of speech signals with an estimation of
the mixing matrix. First, we use a geometrical approach toperform a preliminary separation and to detect when only one
source is active. This information is then used to estimate themixing matrix. Then we remove one source from theobservations and separate the residual signals with theinverse of the estimated mixing matrix. Indeed we can obtain
more information about the signals to be separated and hence
reduce the zero-padding effect, from which the musical noise
originates.

1. INTRODUCTION
BSS is a method for recovering a set of source signals fromthe observations of their mixtures without any knowledge
about the sources themselves nor the mixing process [1].
While dealing with the BSS issue, we can consider different
levels of complexity whether the mixing process is seen as an
instantaneous mixture or as a convolutive one but also
whether the number of sources outnumbers or not the numberof sensors.
To get closer to the reality, in the speech signal area, themixing process should be considered as convolutive because
speech signals are recorded with their reverberation.
Moreover, to be more realistic with the today’s life, we
decide to work with more sources than sensors. Here are thereasons why this paper focuses on underdetermined blindsource separation (BSS) of three speech signals mixed in areal environment from measurements provided by two
sensors.
This is a tough problem and no satisfying solution has
been proposed yet. Most of the solutions proposed so far [26] are using the assumption of sparseness of speech signals.
That is to say, they assume that most of the samples of thesignals are zero, and therefore, they can assume that signals
do not overlap very often. Finally they utilized binary masks
to extract each source. Such a rough approach leads toconsiderable distortion i.e., loud musical noise, which is due
to discontinuous zero-padding, is heard.

0-7803-8484-9/04/$20.00 ©2004 IEEE

2. PROBLEM STATEMENTS ANDNOTATIONSIn this paper, we consider speech mixtures observed in areal room. In this case, as speeches are mixed with theirreverberation, the observed vectors xj (j=1..M) can bemodeled as convolutive mixtures of the source signals si(i=1..N) as follows:N

xj t¦ h * s (t )
i 1

ji

(1)

i

where hji is the impulse response from a source i to a sensor j.
In this paper, we deal with a case where N=3 sources and
M=2 sensors. Moreover, we assume that the source signals
are mutually independent and sparse: namely signals havelarge values at rare sampling points. We are using the Short
Time Fourier Transform (STFT) to convert our problem intoa linear instantaneous mixtures’ problem as well as toimprove the sparseness of the speech signals [4]. In the timefrequency
domain,oursystembecomes:X ( f , m) H ( f ) S ( f , m) where f is the frequency, m theframe index, H(f) the 2 u 3 mixing matrix whose i-jcomponent is a transfer function from a source i to a sensor j,
X(f,m)=[X1(f,m), X2(f,m)]T and S(f,m)=[S1(f,m), S2(f,m),S3(f,m)]T, namely the Fourier transformed observed signals
and source signals, respectively.

IV - 85ICASSP 2004➡

➡
Our aim is to estimate three speech signals frommeasurements provided by two sensors.

Moreover shows that reverberant data have a lower
Approximate WDO than no-reverberant data. Henceseparating reverberant data becomes more difficult.

Desired source power
remaining [%]3. SPARSENESS INQUIRIES
3.1. SOURCES’OVERLAPPINGThe first definition of sparseness is that the more zero
samples contained in a source, the more sparse it is, whichmeans that the sources overlap at infrequent intervals.
Figure 1 is a histogram showing the number of sources thatare simultaneously active. It can be seen that the time points
where no sources are active are very numerous whereas thetime points where three sources are active are very
infrequent. We can infer from these observations that thesignals are sparse and that the three signals rarely overlap.

31

Proportion

150

200ms

ȕ

ȑȐ

ȑȕ

ȒȐ

Ȓȕ

ȓȐ

Threshold x [db]Fig. 2: Approximate WDO against the threshold x for a DFT sizeof 512 and a male-male-female combination.

In previously reported methods [2-4], one of the major
drawbacks was the occurrence of distortion, i.e., musicalnoise. To overcome this issue, we propose a three-stepmethod. First, using the sparseness of speech signals, we
adopt a geometrical approach extracting the time points mwhen only one source is active [1st step], then we estimate
the mixing matrix [2nd step] and finally we reconstruct thesignals when two sources are active [3rd step].

1005Frequency (kHz)•4[1st step] Geometrical approacharea 1

Fig. 1: Histogram of the number of active sources: 0, 1, 2 or 3 fora male-male-female combination recorded with a reverberationof 200 ms and for a DFT size of 512.

|X2(f,m)|

We investigated the sparseness more closely andchecked the degree of signal overlap by utilizing a criterion
called Approximate W-Disjoint Orthogonality (WDO)
defined by Rickard and Yilmaz [6]. We use a mask:­1 20 log(| S j ( f , m ) | / | Y j ( f , m ) |) ! x (2)I ( j , x ) ( f , m) ®
otherwise
¯0

S2
S3

area 3area 23|X1(f,m)|Fig. 3: Scatter-plots of the mixtures at a frequency of 312 Hz formale-male-female combination, a reverberation of 130 ms and a
DFT size of 512.

N¦ s (t) i.e. y (t) isiarea 2

S1

3.2. MEASURE OF OVERLAPPING

where Yj(f,m) is the STFT of y j (t)130ms

4. PROPOSED METHOD

00

original

Ȑ

2

1

ȑȐȐ
șȐ
ȘȐ
ȗȐ
ȖȐ
ȕȐ
ȔȐ
ȓȐ
ȒȐ

j

i 1,i z j

the summation of the sources interfering with source j. The
Approximate WDO is defined as:r j ( x) 100 || I ( j , x ) ( f , m) S j ( f , m) || 2 / || S j ( f , m) || 2 . (3)This measures the percentage rj of source j energy fortime-frequency points where it dominates the other signals by
rj % at x dB. From this criterion it emerges that, if we canpredict the time-frequency points at which a source
dominates the others by rj % at x dB, we should be able torecover rj % of the energy of the original sources. If rj issufficiently large, we can separate signals with small
distortion and vice-versa.
For example in Fig.2, if we want a signal-to-interference
ratio of 20 dB, only around 50 % of the original power isrecoverable, which means that almost half the points are
zero-padded by a mask and such distortion cannot be avoided.

This first step consists of detecting the frame indices mwhen only one of the three sources is active for eachfrequency bin f.
Scatter-plots of the measurements, as shown in Fig. 3,
comprise three main lines (if the sources are sparse enough).
According to Vielva et al. [4], these lines symbolize thedirections defined by the column vectors of the mixing
matrix. In other words, they can be seen as a representationof each source existing alone. In between two given
directions, we find the time-frequency points modeling oursystem when two sources (those linked to the above
directions) are active simultaneously.
By setting narrow areas each containing only one line,
such as areas 1, 2 and 3 in Fig. 3, we are able to determine
when only one source is active. At the same time we can also
reconstruct the signals for these time-frequency points. ThisIV - 86➡

➡
Moreover, in this area, if the signals H12(f)S2(f,m) andH13(f)S3(f,m) are not too greatly zero-padded, we expect thatthe distortion of the estimated H12(f)S2(f,m) and H13(f)S3(f,m)
will not be that large. We proceed in the same way whenS3(f,m) is null.
It should be noted that, in Fig.1, we have alreadyconfirmed that we do not often have three sources active
simultaneously.

is the method exploited in previous works [2, 3, 4]. However,as expected by using such a rough approach, the quality ofthe separated signals is not satisfactory. Since the rate ofrecoverable energy is too low (as shown in Fig. 6), wecannot avoid an important zero-padding, which makes thesignals insufficiently continuous. As a result, considerable
distortion i.e., loud musical noise can be heard.
To overcome this lack of quality, we attempt to complete
our separation using a totally different approach, relying on
the knowledge of the mixing matrix.
[2 step] Estimation of mixing matrix
Deville recovers the mixing matrix by estimating a certain
cross-correlation parameter ratio over time-frequency zones
where only one source exists [5]. This ratio was then proved
to be equal to H2i/H1i (i=1, 2, 3).
In contrast to Deville, here we are working with aunderdetermined convolutive case, however his approachgave us the idea to model our system in the time-frequency
domain by:ª X 1 ( f , m) º
« X ( f , m) »
¬ 2
¼

ª 1
« H 21 ( f )«H ( f )¬ 11

1
H 22 ( f )H12 ( f )1 º ª H11 ( f ) S1 ( f , m) º
H 23 ( f ) »  « H ( f ) S ( f , m)».
2
« 12»
H13 ( f ) »¼ « H ( f ) S ( f , m) »
3
¬ 13
¼

5.1. EXPERIMENTAL CONDITIONS

S3 (male)
S2 (male)(4)
S1 (female)

Therefore, using time points estimated in the first stepwhen only Si (i=1, 2, 3) is active, we have:­ ȋ 1 (f,m) H 1i (f)Si (f,m)®
¯ ȋ 2 (f,m) H 2i (f)Si (f,m)

Fig. 4: Experimental conditions(5)

The recordings were done in a room whose reverberant
times were TR=130 and 200 ms using a two-element array of
directional microphones 4 cm apart. The speech signals,
sampled at 8 kHz, came from three directions: 120° (male),90° (male) and 50° (female) and the distance between thesources and the sensors was L = 55 cm. The DFT frame size
was 512 where we can get the sparsest representation [7].

whose ratio X2(f,m)/X1(f,m) provides one of the componentsof the mixing matrix H2i(f)/H1i(f).
•5.2. STABILITY OF THE ESTIMATED
MIXING MATRIX COEFFICIENTS
2

3

1.8

2

1.6

H23(f)/H13(f)H23(f)/H13(f)1.4

amplitude[3rd step] Reconstruction of time-frequency points
when two sources are active
At this stage, it should be noted that knowing the mixing
matrix does not enable us to separate the signals when threesources are active. This is because the mixing matrix is not
square and does not have any inverse. Deville has only
applied his method to a squared mixing matrix.
Nevertheless, it is still possible to rebuild the time-frequency
points when two sources are active, providing that for eachfrequency bin, we know the frame indices for which this caseoccurs. Once more this information is provided by thegeometrical approach employed in the first step. But thistime, instead of setting the limits very close to the observed
directions, we are considering much wider areas so as toenclose the points located between two given directions.
Indeed let us suppose that, for an estimated (f, m) detectedduring the first step, S1(f, m) is null (area 23 in Fig. 3), in thisarea, our system becomes:
11ª X1 f , m º ª H ( f ) H ( f ) º ª H12 ( f )S2 f , m º
(6)
«
»«
22
23
».
«X f ,m »¬ 2¼ «¬ H12 ( f ) H13 ( f ) »¼ ¬ H13 ( f )S3 f , m ¼
Now the mixing matrix is square and can thus be
inverted, leading to H12(f)S2(f,m) and H13(f)S3(f,m):
1ª H12 ( f ) S 2 f , m º ª H 1( f ) H 1( f ) º ª X 1 f , m º (7)» «23« H ( f ) S f , m » « 22
».
3
¬ 13
¼ «¬ H12 ( f ) H13 ( f ) »¼ ¬ X 2 f , m ¼

Phase (rad.)•5. EXPERIMENTS

nd

1.2
1

H22(f)/H12(f)

0.8
0.6

1

0

−1

H21(f)/H11(f)

0.4

−2

H21(f)/H11(f)

0.2
0

0

50

100

150

200

250

Frequency bins

300

−3

H22(f)/H12(f)
0

50

100

150

200

250

Frequency bins

Fig. 5: Representation of the matrix coefficients, male(H23(f)/H13(f)) - male(H22(f)/H12(f)) -female (H21(f)/H11(f)) combination,
DFT size=512, TR=130 ms.

To evaluate the efficiency of our method, we need to know
about the stability of the mixing matrix we estimated in the
2nd. In Fig. 5, we plotted the amplitude and phase of the threecoefficients H2i(f)/H1i(f) (i=1,2,3) in (4). As we can see, ourestimation offers a great stability in the whole, except for the
low frequencies, where the time delay between the two
microphones, which stand very close to each other, is harder

IV - 87300

➡

➠
to calculate with accuracy. However we can observe theconstant amplitude and the linear phase of the coefficients.

5.3. MASK JUSTIFICATION
Figure 6 justifies our decision to use wide masks. Indeed if
we use narrow masks (e.g., area 3 in Fig. 3) as in the previous
method, the recoverable power is only around 45 % with athreshold of 10 dB whereas if we utilize wider masks (e.g.,area 23 in Fig. 3), we can recover over 60 % of this power.
Desired source power
remaining [%]ȑȐȐTable 1: SIR and SDR calculated in dB for different approaches,
DFT size=512, TR=130 ms
SIR1

SIR2

SIR3

SDR1

SDR2

SDR3

sparseness

15.3

9.9

10.6

8.4

10.3

3.4

invH12

11.6

3.1

8.7

12.2

invH23

3.3

SIR1

no masks

ȔȐwide area

ȒȐ

12.5

7.2

Table 2: SIR and SDR calculated in dB for different approaches,
DFT size=512, TR=200 ms

ȘȐ
ȖȐ

7.6

SIR2

sparseness

8.6

5.6

invH124.0

1.3

invH23

0.4

SIR3
11.6

SDR1

SDR2

SDR3

0.9

3.3

1.4

2.5

4.8

8.9

7.2

4.5

narrow area

Ȑ
Ȑ

ȕ

ȑȐ

ȑȕ

ȒȐ

Ȓȕ

ȓȐ

Threshold x [dB]Fig. 6: Approximate WDO against the threshold, DFT size=512,
TR=130 ms.

Consequently the technique using wide areas makes it
possible to reduce the distortion of the separated signals,
which was our aim.

5.4. EVALUATION MEASURES
To evaluate the separation performance of our method, we
have chosen to calculate the Signal-to-Interference Ratio(SIR) as a measure of separation performance and the Signalto-Distortion Ratio (SDR) as a measure of sound quality:2(8)¦t yis (t)
SIR i

10log

6. CONCLUSION
We proposed a separation method for use when there are
more speech signals than sensors by combining a sparsenessapproach and an estimation of the mixing matrix. The firstexperimental results are very encouraging in terms of quality
and suggest that the SMME is an approach that deserves
serious investigation.

7. REFERENCES

i

10log

¦ ¦y
iz j

SDR i

As we can see, the use of our SMME method allows us
to obtain less distorted signals without suffering from serious
deterioration in the separation performance (SIR). Moreover
we performed informal listening tests and it is important tonote that much less musical noise is heard when separation isundertaken using SMME than when only sparseness is used.

t

2
is j

¦x
t

2
ksi

(t)

(t)

(9)

¦ (xksi (t)  Įyisi (t  M ))2

A. Hyvarinen, J. Karhunen and E. Oja,
Component Analysis, John Wiley & Sons, 2001.

[2]

P. Bofill and M. Zibulevsky, “Blind separation of more
sources than mixtures using sparsity of their short-time Fouriertransform,” Proc. ICA2000, pp. 87-92, 2000.

[3]

M. Zibulesky, B. A. Pearlmutter, P. Bofill and P. Kisilev,“Blind source separation by sparse decomposition in a signal
dictionary,” TR No. CS99-1, University of New Mexico,
Albuquerque, July 1999.

[4]

L. Vielva, D. Erdogmus, C. Pantaleon, I. Santanmaria, J.
Pereda and J. C. Principe, “Underdetermined blind source
separation in a time-varying environment,”
Proc.
ICASSP2002, vol. 3, pp. 3049-3052, 2002.

[5]

Y. Deville, “Temporal and time frequency correlation-based
blind source separation methods,” Proc. ICA2003, pp. 10591064, 2003.

[6]

S. Rickard and O. Yilmaz, “On the approximate w-disjoint
orthogonality of speech,” Proc. ICASSP2002, vol.1, pp. 529532, 2002.

twhere the permutation is solved before calculating SIR and
SDR, i.e. yi(t) is the estimation of si(t), and yiSj is the outputof the whole separating system at yi when only sj is active andsk (k z j) does not exist, and xkSj is the observation obtainedby microphone k when only sj exists. D is a constant thatcompensates for the amplitude difference and M is an angle
that fits the phase difference between input xkSj and output
yiSj. To evaluate of the previous method (sparseness only
method), we calculated SIR and SDR using both
microphones’ measurements, and adopted the better values.

5.5. RESULTS
Tables 1 and 2 show the results we obtained from ourmeasurements. By “sparseness” we imply that we are
evaluating the performance of our speech signals when weare applying the narrow masks. “invH12” means that we areapplying our mixing matrix to area 12 comprising speech
signals 1 and 2. Likewise “invH23” means that we areapplying our mixing matrix to area 23 comprising speech
signals 2 and 3. Actually, we are comparing the conventional
method with our SMME method. The results are shown in
Tables 1 (when TR=130 ms) and 2 (when TR=200 ms).

Independent[1][7] A. Blin, S. Araki and S. Makino, “Blind source separation whenspeech signals outnumber sensors using a sparseness-mixing
matrix combination,” Proc. IWAENC2003, pp. 211-214.

IV - 88