08- Aye - 6375
`ifs IEEE TRANSACTIONS ON
`|51¢
`lest NAL PROCESSING
`
`700|
`{PUBLICATION OF THE IEEE SIGNAL PROCESSING SOCIETY
`
`www.ieee.org/sp/index.html
`
`AUGUST2001
`
`VOLUME 49
`
`NUMBER 8 ITPRED
`
`(ISSN 1053-587X)
`
`vonteatt
`
`9. Thi oles
`
`~—ya
`
`PAPERS
`
`Methods of Sensor Array and Multichannel Processing
`A Subspace-Based Direction Finding Algorithm Using Fractional Lower OrderStatistics .. T.-H. Liu and J, M. Mendel
`Signal Enhancement Using Beamforming and Nonstationarity with Applications to Speech.......---+++-+++s+ssssse00e4
`S. Gannot, D. Burshtein, and E. Weinstein
`
`Signal and System Modeling
`Extensions of the Weighted-Sample Method for Digitizing Continuous-TimeFilters....... C. Wan and A. M. Schneider
`Relations between Fractional Operations and Time-FrequencyDistributions, and Their Applications ..........+sseeeeee
`Peed ence cece cece e cece cece scene ene e ee eee eee eee eee eens seen enen ener e ens seneeees S.-C. Pei and J.-J. Ding
`Multiwindow Time-Varying Spectrum with Instantaneous Bandwidth and Frequency Constraints ............0seeeeeeeee
`F. Cakrak and P. J. Loughlin
`
`1605
`
`1614
`
`1627
`1638
`
`1656
`
`Signal Detection and Estimation
`Adaptive Volterra Filters for Active Control of Nonlinear Noise ProcesseS.........+ss+sseseeerereees L. Tan and J. Jiang 1667
`Frequency Domain Blind MIMOSystem Identification Based on Second- and Higher OrderStatistics .........sseseeees
`B. Chen and A. P. Petropulu.
`nin 6 KWCCANG ) FTF NGNTCIINUEED © ETT REG LATE RMETEZOME ©
`0 oo wo erenexenmsede lode SS EY HME Teee © » wiensenls
`Onthe Behaviorof Information Theoretic Criteria for Model Order Selection.......---- A. P. Liavas and P. A. Regalia
`Filter Design and Theory
`Robust 11,, Filtering for Uncertain Discrete-Time State-Delayed Systems ........seseeerereresserer sees st entrees
`Bey PTRIEES Tatoenesn eogayernra & x Shanasafalaal aed v'a ececnsscelaibiosas 3405 4
`7 ERNLSRNTNNE 3 ¢ R. M. Palhares, C. E. de Souza, and P.L. D. Peres
`M-Band Compactly Supported Orthogonal Symmetric Interpolating Scaling FUNCtionS ......csceeeee scene eneneee ee en ens
`1704
`SPE Siee 180% & Guecesarn on 5 sTAGRISIGG BB UE EARRING 9 4S ao wNTRTO GEG ES «oo oo enue AE HS P.-L. Shui, Z. Bao, and X.-D. Zhang
`1714
`cae Design of Lifting Scheme from General Wavelet ..........+.csssereesrrerrersteess H. Li, Q. Wang, and L. Wu
`1718
`ary Filter Optimization for Segmentation-Based Subband Coding ....+---+-sssrrrrreesererse es A. Mertins
`ee Signal Processing
`é
`1728
`Fre y Domain Computations for Nonlinear Steady-State Solutions ......++++++++-20004+N. P. Telang and L. R. Hunt
`© Convergence of Volterra Filter Equalizers Using a Pth-Order Inverse Approach ....seseereereeteetee eer eeesnes
`Y. Fang, L.-C. Jiao, X.-D. Zhang, and J. Pan 1734
`Rack oo 88S deeguae a eae Hee TINIE SS BAF a CRT RTT EG 4a 8 ow Ronen
`L. Dtaz-Barrero and J. J. Egozcue
`1745
`ction Coefficients Counterpart of Cardan—Viéte Formulas........-" Deasncmay ae J.
`Eave d
`toe
`Y. Yao and H. V. Poor
`1748
`“Cropping in the Synchronous CDMA Channel: An EM-Based Approach .....++++++++++0+*
`
`1677
`1689
`
`1696
`
`les)
`
`ny——=SSee
`
`Les
`
`(Contents Continued on Back Cover)
`
`-i-
`
`MetaPlatforms, Inc. Exhibit 1004
`Page i of 1626
`
`- i -
`
`Meta Platforms, Inc. Exhibit 1004
`Page i of 1626
`
`

`

`VUE VstIVUG.VI YW sPV/Inidgdex, himl
`
`JMBER 8.
`
`ITPRED
`
`(ISSN 1053-5
`
`sing
`, Fractional Lower OrderStatistics .. 7-H. Liy and J. M. Me.
`lonarity with Applications to Speech..................ce
`UT ttt sssseess ess... Gannot, D. Burshtein, and E. Weins;
`
`i Continuous-Time Filters...:... C. Wan andA. M. Schneic
`quency Distributions, and Their Applications). 50 s.2.. 6.5 ys:
`ee PSG Re Wrage Gus wee wal pp D GG «we S.-C. Pei and J.-J. Di
`ous Bandwidth and FrequencyConstraints .....Stee alate Aa ;
`ieee Bak Sy, Tt ttt tte e sees cess... F Cakrak and P. J. Loughli
`
`- ii -
`
`MetaPlatforms, Inc. Exhibit 1004
`Pageii of 1626
`
`- ii -
`
`Meta Platforms, Inc. Exhibit 1004
`Page ii of 1626
`
`

`

`- iii -
`
`Meta Platforms, Inc. Exhibit 1004
`Page iii of 1626
`
`

`

`1614
`
`IEEE TRANSACTIONSON SIGNAL PROCESSING, VOL. 49, NO. 8, AUGUST200;
`
`Signal Enhancement Using Beamforming and
`Nonstationarity with Applications to Speech
`
`Sharon Gannot, Student Member, IEEE, David Burshtein, Senior Member, IEEE, and Ehud Weinstein, Fellow, IEEE
`
`Abstract—We consider a sensor array located in an enclo-
`sure, where arbitrary transfer functions (TFs) relate the source
`signal and the sensors. The array is used for enhancing a signal
`contaminated by interference. Constrained minimum power
`adaptive beamforming, which has been suggested by Frost and,
`in particular, the generalized sidelobe canceler (GSC) version,
`which has been developed by Griffiths and Jim, are the most
`widely used beamforming techniques. These methods rely on the
`assumption that the received signals are simple delayed versions
`of the source signal. The good interference suppression attained
`underthis assumptionis severely impaired in complicated acoustic
`environments, where arbitrary TFs may be encountered. In this
`paper, we consider the arbitrary TF case. We propose a GSC
`solution, which is adapted to the general TF case. We derive a
`suboptimal algorithm that can be implemented by estimating
`the TFs ratios, instead of estimating the TFs. The TF ratios are
`estimated by exploiting the nonstationarity characteristics of the
`desired signal. The algorithm is applied to the problem of speech
`enhancementin a reverberating room. The discussion is supported
`by an experimental study using speech and noise signals recorded
`in an actual room acoustics environment.
`
`Index Terms—Beamforming, nonstationarity, speech enhance-
`ment.
`
`I.
`
`INTRODUCTION
`
`IGNAL quality might significantly deteriorate in the
`
`G rrescnce of interference, especially when the signal
`
`is
`
`also subject to reverberation. Multisensor-based enhancement
`algorithms typically incorporate both spatial and spectral
`information. Hence,
`they have the potential to improve on
`single sensor solutions that utilize only spectral information.
`In particular, when the desired signal is speech, single micro-
`phonesolutions are knownto be limited in their performance.
`Beamforming methods have therefore attracted a great deal of
`interest in the past three decades. Applications of beamforming
`to the speech enhancementproblem have also emergedrecently.
`Constrained minimum power adaptive beamforming, which
`has been suggested by Frost [1], deals with the problem of a
`broadband signal received by an array, where pure delay re-
`lates each pair of source and sensor. Each sensorsignal is pro-
`_cessed by a tap delay line after applying a proper time delay
`
`Manuscript received March 28, 2000; revised April 30, 2001. The associate
`editor coordinating the review ofthis paper and approvingit for publication was
`Dr. Alex C. Kot.
`the Department
`is with
`S. Gannot
`(SISTA), Katholieke Universiteit Leuven,
`Sharon.Gannot @esat.kuleuven.ac.be).
`D. Burshtein and E. Weinstein are with the Department of. Electrical
`Engineering—Systems, Tel-Aviv University, Tel-Aviv,
`Israel
`(e-mail:
`burstyn @eng.tau.ac.il, udi@eng.tau.ac.il),
`Publisher Item Identifier S 1053-587X(01)05874-3.
`
`of Electrical Engineering
`Leuven, Belgium (e-mail:
`
`compensation. The algorithm is capable ofsatisfying some de-
`sired frequency responsein the look direction while minimizing
`the output noise power by using constrained minimization of
`the total output power. This minimization is realized by ad-
`justing the taps ofthe filters under the desired constraint. Frost
`suggested a constrained LMS-type algorithm. Griffiths and Jim
`[2] reconsidered Frost’s algorithm and introduced the general-
`ized sidelobe canceler (GSC) solution. The GSC algorithm is
`comprisedof three building blocks. Thefirst is a fixed beam-
`former, whichsatisfies the desired constraint. The secondis
`a blocking matrix, which produces noise-only reference sig-
`nals by blocking the desired signal (e.g., by subtracting pairs of
`time-aligned signals). The third is an unconstrained LMS-type
`algorithm that attempts to cancel the noise in the fixed beam-
`formeroutput. In [2], it is shown that Frost algorithm can be
`viewed as a special case of the GSC. The main drawback ofthe
`GSCalgorithm isits delay-only propagation assumption.
`Van Veen and Buckley [3] summarized various methods for
`spatial filtering, including the GSC, and introduced a wider
`range of possible constraints on the beam pattern. Cox efal.
`[4] suggested constraint of the norm of the adaptive canceler
`coefficients in order to solve the superdirectivity problem,
`i.e.,
`its sensitivity to steering errors. In particular, they have
`suggested to update Frost’s (or the Griffiths and Jim) algorithm
`by applying a quadratic constraint on the norm of the noise
`canceler coefficients. This constraint, which can limit
`the
`superdirectivity, is added to the usual linear constraints.
`Someauthorshaverecently suggestedusing the GSC forspeech
`enhancementin a reverberating environment. Hoshuyamaetal.
`[5]-[7] used a three-block structuresimilar to the GSC. However,
`the blocking matrix has been modified to operate adaptively. In
`orderto limitthe leakageofthedesired signal, whichisresponsible
`fordistortioninthe outputsignal, aquadraticconstraintisimposed
`onthe normofthe noisecancelercoefficients. Alternatively, useof
`the leaky LMSalgorithm has been suggested.
`Nordholm et al.
`[8] used a GSC solution in which the
`blocking matrix is realized by spatial highpass filtering, thus
`yielding improved noise-only reference signals. Meyer: and
`Sydow [9] have suggested to construct
`the noise reference
`signals by steering the lobes of a multibeam beamformer
`toward the noise and desired signal directions separately.
`Widrow and Stearns [10] have proposed a dual structure
`beamformer. The master beamformeradaptsits coefficients to
`minimize the output power while maintaining the beam-pattern
`toward a predetermined pilot signal from the desired direc-
`tion. Those coefficients are continuously copied to a slave
`beamformer that.is used to enhance the speech signal. Dahl
`et al.
`[11] have extended this solution by proposing a dual
`
`1053-587X/01$10.00 © 2001 IEEE
`
`
`
`- 1614 -
`
`MetaPlatforms, Inc. Exhibit 1004
`Page 1614 of 1626
`
`- 1614 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1614 of 1626
`
`

`

`GANNOT et al.: SIGNAL ENHANCEMENTUSING BEAMFORMING AND NONSTATIONARITY
`
`1615
`
`beamformer that attempts to cancel both noise and jammer
`signals (e.g., loudspeaker). The pilot signal is constructed by
`offline recordings of the jammer and desired signal
`in the
`actual acoustic environmentduring a calibration phase. Thus,
`both echo cancellation and noise suppression are achieved
`simultaneously.
`Othersolutionsutilize a beamformertype algorithm,followed
`by a postprocessor. Zelinski [12] suggested a Wienerfilter, fol-
`lowed by further noise reduction ina postprocessing configura-
`tion. Meyer and Simmer[13] addressed the problem of high co-
`herence betweenthe microphonesignals at low frequencies,as in-
`dicated by Dal-Degan andPrati 14]. They have suggestedthe use
`ofaspectral subtractionalgorithm in the low-frequency band and
`Wienerfiltering in the high-frequency band. Fischer and Kam-
`meyer[15] suggested to further split the microphone array into
`differentially equispaced subarrays. This structure has been fur-
`ther analyzed by Marro etal. [16]. Bitzer eral. [17] analyzed the
`performance of the GSC solution and showedits dependence on
`the noise field. They showed thatthe noise reduction mightbe in-
`finitely large when the noise source is directional. However, in
`the more practical situation of a reverberant enclosure, when the
`noise field can be regarded as diffused, the performance degrades
`severely. Bitzer ef al. [18] suggested a GSC with fixed Wienerfil-
`ters in the noise canceling blockand furtherpostfilters at the GSC
`output, An improved performancein the lower frequency range
`is achieved. In [19], itis shownthat the Wienerfilters can be com-
`puted in advancebyutilizing prior knowledgeofthenoisefield.
`Jan and Flanagan [20] suggested a matched filter beam-
`forming (MFBF) instead of the conventional delay and sum
`beamformer (DSBF). The MFBFconfiguration realizes signal
`alignment by convolving the microphone signals with the
`(estimated) acoustic transfer function (TF). Rabinkinet al. [21]
`proved that the performance of MFBFis superior to DSBF,
`provided that the room acoustics TF is not too complicated.
`They have also suggested truncation of the estimated acoustic
`TFsto ensure reliable estimates.
`Grenier et al. [22]-[29] have proposed GSC-based enhance-
`mentalgorithms.In [29], the case where general TFs relate the
`source and microphones was considered. A subspace tracking
`solution [30] has been proposed. The resulting TFs are con-
`strained to the array manifold underthe assumption of an FIR
`model and small displacements of the talker. The fixed beam-
`former block of the GSC is realized using MFBF.
`In this paper, we consider a sensor array located in an enclo-
`sure, where general TFsrelate the source signal and the sensors.
`Thearray is used for enhancing a signal contaminated byinter-
`ference. We propose a GSCsolution, which is adapted to the
`general TF case. The TFs are estimated by exploiting the non-
`stationarity characteristics of the desired signal. The algorithm
`is applied to the problem of speech enhancement in a rever-
`berating room. The discussion is supported by an experimental
`study using speech and noise signals recorded in an actual room
`acoustics environment. The outcomeconsists of the assessment
`of sound sonograms, signal-to-noise ratio (SNR) enhancement,
`and informal subjective listening tests. The paper is organized
`as follows. In Section II, we formulate the problem of beam-
`forming in a general TF environmentin the frequency domain.
`The constrained power minimizationis presented in SectionIII,
`
`where both Frost’s algorithm [1] and the Griffiths and Jim [2]
`interpretation are derived in the frequency domain. This deriva-
`tion motivatesthe intuitive structure suggested by other authors
`for the beamformingproblem in reverberant environments. We
`then show that a suboptimal algorithm can be implemented by
`estimating the TF ratios instead of estimating the actual TFs. In
`Section IV, we address the problem ofestimating the TF ratios
`by extendingthe nonstationarity principle, which was suggested
`by Shalvi and Weinstein [31]. An application of the suggested
`algorithm to the speech enhancement problem is presented in
`Section V. Section VI concludes the paper.
`
`II. PROBLEM FORMULATION
`
`Consideran array of sensors in a noisy and reverberantenvi-
`ronment. Thereceived signal is comprised of two components.
`Thefirst is some nonstationary (e.g., speech) signal. The second
`is somestationary interference signal. Our goal is to reconstruct
`the nonstationary signal componentfrom the received signals.
`Weuse the following notation.
`Zm(t)
`mth sensor signal;
`a(t)
`desired signal source;
`Nn (t)
`interference signal of the mth sensor comprised of
`some directional noise component and some am-
`bient noise component;
`time-varying TFs from the desired speech source to
`the mth sensor.
`
`a,,(t)
`
`We have
`
`Zm(t) = am(t) * (t) + M(t); m=1,....M (1)
`
`where * denotes convolution. Suppose that the analysis frame
`duration T’ is chosen such that the signal may be considered
`stationary over the analysis frame. Typically,
`the TFs are
`changing slowly in time so that they may also be considered
`stationary over the analysis frame. Multiplying both sides of
`(1) by a rectangular window function w(t) [w(t) = 1 over the
`analysis frame w(t) = 0 otherwise] and applying the discrete
`time Fourier transform (DTFT)operatoryields
`
`Zm(t, 8”) & Am(e?”)S(t, e2”) + Nin(t, e%”)
`
`m=1,...,M.
`
`(2)
`
`justified for T sufficiently large.
`The approximation is
`Zm(t, e”), S(t, e”) and Nm(t, e%) are the short
`time
`Fourier transforms (STFTs) of the respective signals. Am(e%”)
`is the TF of the mth sensor. Note that we have assumed that
`the TFs are time invariant.
`The vector formulation of the equation set (2) is
`
`Z(t, e”) = A(e™)S(t, e”) + Nit, e)
`
`(3)
`
`where
`
`Z(t, &) = [Zi(t, e*) Zal(t, e) --- Zrr(t, e™)|
`AT (e¥) = [Ar(e™) Ag(e”) +. Anu (e)]
`N7(t, e%”) = [Ni(t, 2%) No(t, ce”)
`--- Nu(t, e)).
`
`- 1615 -
`
`MetaPlatforms, Inc. Exhibit 1004
`Page 1615 of 1626
`
`- 1615 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1615 of 1626
`
`

`

`1616
`
`IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL.49, NO. 8, AUGUST 2091
`
`wt (t, e”)bz2(t, ee“)Wit, ev)
`
`Wopt (t, ee )
`F(e*) = ots Fle’)
`
`
`
`
`
`
`
`Constraint plane: At(e*”)W(t,e”) = Fle”)
`
`Fig.1.
`
`Constrained minimization.
`
`III. CONSTRAINED OUTPUT POWER MINIMIZATION
`
`In [1], a beamforming algorithm was proposed under the
`assumption that the TF from the desired signal source to each
`sensor includes only gain and delay values, In this section,
`we consider the general case of arbitrary TFs. By following
`the derivation of [1] in the frequency domain, we derive a
`beamforming algorithm for the general TF case. First, we
`obtain a closed-form, linearly constrained, minimum variance
`beamformer. Then, we derive an adaptive solution. The out-
`come will be a constrained LMS-type algorithm. We proceed,
`following the footsteps of Griffiths and Jim [2], and formulate
`an unconstrained adaptive solution. We will initially assume
`that the TFs are known.Later, in Section IV, we deal with the
`problem of estimating the TFs.
`
`A. Frequency Domain Frost Algorithm
`1) Optimal Solution: Let W*(t, e”);m=1,..., Mbea
`set of M filters
`
`Writ, ei”) = (Wit, ee”) Wi(t, e”) --- Waylt, e*)]
`
`where * denotes conjugation, and t denotes conjugation trans-
`pose. A beamformeris realized by filtering each sensor output
`by W*(t, ce”) m=1,..., M and summing the outputs
`
`Y(t, ei”) = W(t, e”)Z(t, e”)
`= Writ, e”)A(e%”)S(t, el)
`+ W(t, e%”)N(t, e”)
`Sy,(t, &”) + Y,(t,)
`
`(4)
`
`where Y,(t, e?”) is the desired signal part, and Y,,(t, e”) is the
`noise part. The output power of the beamformeris
`
`E{Y(t, &)¥*(t, e)}
`= E{Wit, e”)Z(t, e)Zt(t, e”)W(t, e””)}
`= Wi(t, e™”)Sz2(t, e7”)Wt, e”)
`
`where Szz(t, 4”) 2 E{Z(t, e%)Zt(t, e”)}. We want to
`minimize the output powersubject to the following constraint
`on Y,(t, e?”)
`Y,(t, e#”) = Wit, e@”)A(e%”)S(t, e?”)
`= F*(t, e™”)S(t, e”)
`
`where F*(t, e?”) is some prespecified filter (usually a simple
`delay). We thus have the following minimization problem:
`min {Wi(t, 8”)bzz(t, e”)W(t, e”)}
`subject to W(t, 7”)A(e™) = F*(t, e!”).
`
`(5)
`
`Theminimization (5) is demonstrated in Fig. 1. The point where
`the equipower contours are tangent to the constraint plane is
`the optimum vector of beamformingfilters. The perpendicular
`F(e?“) from theorigin to the constraint plane will be calculated
`in Section III-A2.
`To solve (5), we first define the following complex Lagrange
`functional:
`
`L(W) = Wit, e)dz2(t, ce”)W(t, e”)
`+A [wiie, e™”)A(el”) — F*(t, e”)|
`+A* [AT(t, e”)W(e) — F(t, e*)]
`
`where A is a Lagrange multiplier. Setting the derivative with
`respect to W*to 0 (e.g., [32]) yields
`
`Vw-L(W) = z2z(t, &”)W(t, e”) + AA(e™) =0.
`
`Now,recalling the constraintin (5), we obtain the following set
`of optimal filters:
`W(t, el) = [At(e)O52(t, &)A(e)]
`- BZ2(t, ef”)A(e)Fle).
`
`This closed-form solutionis difficult to implementand does not
`havethe ability to track changes in the environment. Therefore,
`an adaptive solution should be more useful.
`
`- 1616 -
`
`MetaPlatforms, Inc. Exhibit 1004
`Page 1616 of 1626
`
`- 1616 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1616 of 1626
`
`

`

`GANNOT et al.: SIGNAL ENHANCEMENT USING BEAMFORMING AND NONSTATIONARITY
`
`1617
`
`Wit = 0,e) = F(ei)
`W(t +1,e%) =
`
`P(e”) (we,efv) —=wale,e)¥*(t,eJ”)] +Fle)
`(P(e) and F(e)are defined by (6) and (7)).
`
`Fig. 2. Frequency domain frost algorithm.
`
`2) Adaptive Solution: Consider the following steepest de-
`scent, adaptive algorithm:
`
`W(t +1, e”)
`= Wit, e”) — nVw- Le)
`= Wit, e™) — w [Szz(t, &)W(t, e*) + AA(e™)].
`Imposing our constraint on W(t + 1, e”) yields
`
`F(e™) = At(e*)W(t + 1, e)
`= At(e*)Wit, e/”)
`— pAl(e)”)Sz7(t, ei”)W(t, ei)
`— pAt(e”)A(e3”).
`
`Solving for the Lagrange multiplier and applying furtherre-
`arrangement of terms yields
`
`W(t+1, ec”) = P(e”)Wit, &”)
`— pP(*)baz(t, &)W(t, &) +F(e™)
`
`where
`
`and
`
`soy 7. Ale)ANCS)
`Pe) = 1 Te)
`;
`Jat
`ju) A(e/”)
`7
`Me) = Taye
`replacing
`by
`simplification can be
`achieved
`Further
`$zz(t, e%”) byits instantaneousestimator Z(t, e%”)Z'(t, e#”)
`and recalling (4). We thus obtain
`
`©
`
`W(t +1, e”)
`= P(e) [W(t, e%”)—uZ(t, e*)Y*(t, e%*)] + Fle).
`
`The algorithm is summarized in Fig.2.
`
`B. Generalized Sidelobe Canceler (GSC) Interpretation
`
`In [2], Griffiths and Jim considered the case where each TF
`is a delay element (with some gain). Griffiths and Jim obtained
`an unconstrained adaptive enhancement algorithm, using the
`same constrained, minimum output powercriterion used by
`Frost
`[1]. The unconstrained algorithm is computationally
`more efficient than the constrained algorithm. Furthermore, the
`unconstrained algorithm is based on the well behaved NLMS
`scheme.In Section III-A2, we obtained an adaptive algorithm
`for the case where each TF is represented by an arbitrary linear
`time-invariant system by tracing the derivation of Frost in the
`frequency domain. We now repeat the arguments of Griffiths
`
`and Jim for our case (arbitrary TFs) and derive an unconstrained
`adaptive enhancement algorithm.
`Considerthe null space of A(e!”), which is defined by
`
`N(e*) = {W|At(e?”)W = 0}.
`
`The constraint hyperplane
`
`A(e”)) 2 {W| At(e#)W = F(e*)}
`is parallel to. ’(e”’). In addition to that, let
`
`R(ei#) & {«A(e%™) | for any real «}
`be the column space. By the fundamental theorem of linear al-
`gebra (e.g., (33]) R(ei”) 1 N(e%”). In particular, F(e™) is
`perpendicular to V/(e4”) since
`
`jw
`F(e)
`jw
`ju
`F(e’ j= jaceyqe A ) E Rie? ).
`
`Furthermore
`
`At (ec)F(e)
`= At(ei)A(e%) (At(e)A(e%)) 7 F(e”) =F(e%).
`Thus, F(e%”) € A(e”) and F(e”) 1 A(e”). Hence, F(e?”)
`is the perpendicular fromtheorigin to the constraint hyperplane
`A(e”). The matrix P(e”), which is defined in (6), is the pro-
`jection matrix to the null space of A(e”’), N(e7”).
`Now,a vector in linear space can be uniquely split into a sum
`of two vectors in mutually orthogonal subspaces (e.g., [33]).
`Hence
`
`Wit, e”) = Wo (t, e”) — V(t, e)
`
`(8)
`
`where Wo(t, e””) € R(e!), and —V(t, e%”) € N(e”). By
`the definition of M/(e7”)
`
`Vit, &”) = Hei”)Git, ei”)
`
`(9)
`
`where H(e%”) is some M x (M — 1) matrix, such that the
`columns of #{(e7”) span the null space of A(e?“), i.e.,
`
`At(e!”)H(el”) =0
`
`rank {H(e)} = M-—1.
`
`(10)
`
`The vector G(t, e%”) is an (M — 1) x 1 vector of adjustable
`filters. By the geometrical interpretation of Frost’s algorithm
`
`Wo(t, e”) = F(e”) =
`
`A(ei”)
`\|A(e™) |?
`
`Fle”).
`
`1)
`
`[Recall that F(e%”) is the perpendicular from theorigin to the
`constraint hyperplane A(e?“).] Now, using (4), (8), and (9) we
`get
`
`Y(t, e&) = Yrnr(t, e”) — Yno(t, e”)
`
`(12)
`
`where
`
`Yepr(t, e”) = Walt, e*)Z(t, e)
`Ync(t, %) = Gt(t, e)H"(e™)Z(é, e).
`
`(13)
`
`- 1617 -
`
`MetaPlatforms, Inc. Exhibit 1004
`Page 1617 of 1626
`
`- 1617 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1617 of 1626
`
`

`

`1618
`
`The outputof the constrained beamformeris a difference of two
`terms, both operating on the input signal Z(t, e7”). The first
`term Yrpr(t, e?”) utilizes only fixed components (which de-
`pend on the TFs); therefore, it can be viewed as a fixed beam-
`former (FBF). We now examinethe secondterm Ync(t, e”).
`Note that
`
`U(t, e%”) =Ht(e”
`)Z(t, e”)
`_=H" (e)
`“) [A(e**)S(t, e#) + N(é, e*)]
`=H(el
`N(t, e”).
`
`(14)
`
`IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 49, NO. 8, AUGUST 200)
`
`Thus, when Wo(t, e%”) is given by (16), the signal term of
`Yrar(t, e’) is the desired signal distorted only bythefirst TF
`A,(e4”). Now, suppose that
`
`Wolt, e”) = Hei)F(e),
`
`(17)
`
`In this case, Wo(t, e?”) is comprisedofthe cascade of H(e%)
`whichis a filter matched to the TFsratio, and ¥(e/”). The new
`Wo(t, e”) can be derived from (16) under the assumption that
`||H(e%”)||? is constant. In fact, Grenier et al. [29] argue that
`this assumption can be verified empirically. The FBF term of
`the output is now given by
`
`Yrar(t, e!”) =
`
`F*(e”)S(t, e!)
`
`AC)?
`Ae)
`+ F*(ei”)H'(e”)N(t, e!”),
`
`(18)
`
`The signal componentof Yrpr(t, e?”) is now distorted. Hence,
`only a suboptimal solution is achieved. Note, however,that all
`the sensor outputs are added together coherently [this can be
`seen from the term || A(e”)||?].
`2) Blocking Matrix
`(BM): Consider
`M x (M — 1) matrix H(e%”):
`
`following
`
`the
`
`The last transition is due to (10). U(t, e) are reference
`noise signals. Hence,
`the signal dependent component of
`Ync(¢, e%”) is completely eliminated (blocked) by Ht(e*”)
`so that Yno(t, e/”) is a pure noise term. The noise term of
`Yrpr(t, e?”) can be reduced by properly adjustingthefilters
`G(t, e7”), using the minimum output powercriterion. This
`adjustment problem is in fact the classical multichannel noise
`cancellation problem. An adaptive LMSsolutionto the problem
`was proposed by Widrow[34].
`The GSCsolution is comprised of three components:
`1) fixed beamformer (FBF);
`2) blocking matrix (BM)that constructs the noise reference
`signals;
`
`i (e?*)
`_ Axle”) A3(e7*)
`3) multichannel noise canceler (NC).
`We nowdiscuss each of these componentsin details.
`
`Aj(e)—Aj (e) ~ Aj(e)
`1) Fixed Beamformer (FBF): By (3), (11), and (13), we
`1
`0
`wee
`0
`have
`0
`1
`-
`0
`
`Yrar(t, e™) = F*(e™)S(t, e)
`F*(ei4)
`| A(e2”) ||?
`
`+
`
`At(e™”)N(t, e”).
`
`0
`
`0
`
`1
`
`(19)
`
`H(e*) =
`
`It can be easily verified that this matrix satisfies (10) and is,
`hence, a proper blocking matrix that may be used for generating
`the reference noise signals U(t, e*”). By (14), we have
`
`Hn(e”) =Ai(ei)' m= 1, wy M, (15)
`
`
`
`Let
`
`Thefirst term on the right-hand side is the signal term. The
`secondis the noise term. Note that by setting F*(e/”) = e~J¥7
`(i.e., adelay), the signal componentof Yrpr(t, e?”) is an undis-
`torted, delayed version of the desired signal.
`Unfortunately, we usually do not have access to the actual
`A,,(e”)
`j
`jw
`‘
`TFs (An(e7”); m = 1, ..., M). Later, we show how we can
`
`Un(e?”)=Zm(t, e?”) (e™) Z(t, e7”)
`J =4m\l, qe) 7.
`™m
`”
`estimate the TFs ratio
`m=2,..., M.
`(20)
`Am(e™)
`
`Thus,
`the knowledge of
`the TFs
`ratios H,,(e”)
`=
`Am(e™)/A1(e/”) is sufficient
`to implement
`the sidelobe
`canceler.
`are) = [1 FE Beh = ar
`
`T/piwy —[,Az(e™) Am(e)] _ AT(e%)
`3) Noise Canceler: By the GSC derivation, we have con-
`structed twosignals. The first is Yrgr(t, e7”), which contains
`both a desired speech term and a residual noise term. The second
`If in (11), the actual TFs are replaced by the TFsratios, then
`signal is Yyo(t, e””). Yno(t, e?”) consists of an adaptive set
`
`: _H(e)|of filters G(t, e7”) that are applied to the noise-only signals
`jw
`’
`Wolt, e”) = eI Fie),
`(16) Ut, ei.
`Recall that our goal is to minimize the output power under
`By (3) and (13), we have
`a constraint on the responseat the desired direction. Bysetting
`J
`jw
`jw) —
`ee
`jw
`;
`;
`Wo(t, e?”) accordingto (11), the constraintis satisfied. Hence,
`\F (e™)S(t, e™)
`Yeor(t, e!") = Arle
`minimization of the output poweris achieved by adjusting the
`1 F*(e™) Ht(e/)N(t, e#).
`filters Git, el). This is an unconstrained minimization, ex-
`||H(e4”)||?
`actly as in Widrow’s classical problem [34]. We can implement
`
`Jus
`fw)
`
`- 1618 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1618 of 1626
`
`- 1618 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1618 of 1626
`
`

`

`GANNOT etal.: SIGNAL ENHANCEMENT USING BEAMFORMING AND NONSTATIONARITY
`
`1619
`
`it by using the multichannel Wienerfilter. Recalling (12), our
`goalis to set G(t, e) to minimize
`E {|lYrer(t, e”) — Gt(t, e)U(t, e)|7}.
`
`Let
`
`buy (t, ) =E {U(t, e)¥sp(t, e”)}
`duult, e) = E {U(t, e*)Ut(t, ei”)}.
`Then,the multichannel Wienerfilter is given by [19], [35]
`G(t, e”) = 5b (t, e”)Our(t, e).
`
`(21)
`
`In orderto be able to track changes, we processthe signals by
`segments. The following frequency domain LMSalgorithm is
`used. Let the residual signal be
`
`Y(t, e!”) = Yppr(t, e™”) — Gtit, e”)U(t, e#).
`
`Note that the residual signal is also the output of the enhance-
`ment algorithm. By the orthogonality principle, the erroris or-
`thogonal to the measurements. Thus
`
`E{U(t, e™*)Y*(t, e*)} =0.
`
`(22)
`
`Following the standard Widrow procedure, the solutionis
`
`G(t+1, e”) = Git, e”) + pUlt, e”)Y*(t, e”).
`
`Usually, a more stable solution is achieved by using the nor-
`malized LMS (NLMS)algorithm, in which each frequency is
`normalized separately, yielding
`
`Gn(t+ 1, e”) =Gnilt, el”) tu
`m=2,...,M
`
`Umn(t, e%)¥*(t, e™)
`P. e(t ej)
`
`where
`Pest(t, e?”) = pPest(t -1, e”) + (1 _ p) > |Zm(t, ei)|?
`(23)
`pis a forgetting factor(typically 0.8 < p < 1). Anotherpossi-
`bility is to calculate P.,_ using the powerofthe noise reference
`signals. However,in that case, an energy detector is required so
`that G(t, e?”) is updated only whenthere is no active signal.
`If on the other hand, wecalculate P.s(t, e7”) using the input
`sensorsignals,as indicated in (23); then, an energy detector may
`be avoided. This is due to the fact that the adaptation term be-
`comesrelatively small during periods ofactive input signal.
`We assume that the noncasual TFs ratios h,, and the noise
`cancelingfilters g,, are both FIRs:
`
`ht =([hm(—az), ---) Mm(¢r)]
`gl, = [9m(—-Kx), seey 9m(Kr)]
`
`(24)
`
`(both h,,, and gm are functionsof time; however, for notational
`simplicity, we omit this dependence). Note that the TFs might
`havezeros outside the unit circle. Thus, to ensure stability of the
`TFs ratios, we do not impose them to be causal. When A; (e)”)
`contains zerosthatare close to the unitcircle,the noise reference
`
`signals U,,(e”) at the corresponding frequencies might assume
`very large values[recall (20)]. This may result in sharp peaks in
`the reconstructed spectrum.This problemis partially overcome
`by constraining the impulse response ofh,,, to an FIR structure.
`It is also possible to constrain the maximal valueof the estimated
`|H,n(e2”)| to be lower than somethreshold.
`In orderto fulfill the FIR structure constraint (24), the filters
`update is now given by
`
`Um(t, e*)¥*(t, e?)
`Gn(t +1, €”) = Gm(t, e*) +p ut, ef”)
`Gin(t +1, &”) = Ga(t +1, e”)
`
`(25)
`
`for m = 2,..., M. The operator <— includes the following
`three stages,First, we transform Gn (t+1, e?”) to the time do-
`main. Second, we truncate the resulting impulse responseto the
`interval [—K,, Kp] (i-e., we impose an FIR constraint). Third,
`wetransform back to the frequency domain.
`Notethat the variousfiltering operations (multiplications in
`the transform domain) are realized using the overlap and save
`method [36].
`The new algorithm can be regarded as an extension of the
`Griffiths and Jim algorithm for the general TF case. Figs. 3 and
`4 summarize our suggested solution. Theratios of the TFs are
`assumedto be known atthis stage.
`
`IV. SYSTEM IDENTIFICATION USING NONSTATIONARITY
`
`Thus far, we assumed that the TFs ratio vector H(e%”) is
`known.In practice, however, H(e?”) are not known and should
`be estimated. Rearranging termsin (20), we have
`
`Zmi(t, &”) = Hm(e?”)Z,(t, 2”) + Um(t, 2”).
`
`(26)
`
`We have assumedthat the TFsratios are slowly changing in
`time compared to the time variations of the desired signal. We
`further assumethat the statistics of the noise signal is slowly
`changing compared with thestatistics of the desired signal. Con-
`sider someanalysis interval during which both the TFs and the
`noise signal are assumedto be stationary. We divide that analysis
`interval into frames such that the desired signal may be consid-
`ered stationary during each frame. Consider the kth frame. By
`(26), we have
`
`OL"),(e) = Hm(e?*)OU), (e™) + by, 2, (7)
`k=1,...,K
`(27)
`where K is the number of frames used. ot) (e!”) is the
`cross-PSD between z; and z; during the kth frame. ©,,_, ., (e7”)
`is the cross-PSD between u,, and z,. Now,(2) and (20) imply
`that
`
`Um(t, e™) = Nm(t, e”) — Hin(e3”)Ni(t. e”)
`(28)
`Zi(t, e%”) = Ar(e¥”)S(t, e#”) + Ni(t, eM).
`(29)
`Since Nm(t, e), m = 1,..., M are assumed stationary
`overthe analysis interval and since S(t, e/”) is independentof
`Nm(t, e?”), it follows that ©,.,(e%”) is independent of the
`frame index k.
`
`- 1619 -
`
`MetaPlatforms, Inc. Exhibit 1004
`Page 1619 of 1626
`
`- 1619 -
`
`Meta Platforms, Inc. Exhibit 1004
`Page 1619 of 1626
`
`

`

`1620
`
`IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.49, NO. 8, AUGUST 2001
`
`Zx(t, 3”) alin
`
`Zi(t,e”) —=|>
`
`Za(t,e”) SHZu(t,ei) ql”
`
`Ypnr(t,¢e’”)
`
`Yno(t, e/)
`
`wee eee ee Hee em em Me Me eK
`
`Ua(t, ei“)
`
`t“outAD
`
`q
`
`HI
`
`Um(t,ee") ,
`
`'
`
`Fig. 3. Linearly constrained adaptive beamformer.
`
`used to obtain an unbiased estimate of H,,(e?”). Unfortunately,
`by (28) and (29), U,,(t, e”) and Z;(t, e7”) are, in general, cor-
`related. Hence,in [31], it is proposed that we obtain an unbiased
`estimate of H,,(e%”) by applying least squaresto the following
`set of overdetermined equations
`
`1) TF-s ratios: H(e/”) = Ae
`2) Fixed beamformer:
`Yrar(t,e) = Wh(e)Z(t,e)
`3) Noise reference si
`U(t, e) = Ht(ei)Z(t, ej”)
`4) Outputsignal:
`Y(t,e%”) = Yppr(t,oe Gt(t,e)U(t,e)
`5) Filters u