Method and system for blind separation of independent source signals

[0002] The present invention relates generally to the recovery of independent user signals simultaneously transmitted through a linear mixing channel, and more particularly, to a method and system for blind recovery of a number of independent user signals.

[0003] In many signal processing applications, the sample signals provided by the sensors are mixtures of many unknown sources. The “separation of sources” problem is to extract the original unknown signals from these known mixtures. Generally, the signal sources as well as their mixture characteristics are unknown. Without knowledge of the signal sources other than the general statistical assumption of source independence, this signal processing problem is known in the art as the “blind source separation problem”. The separation is “blind” because nothing is known about the values of the independent source signals and nothing is known about the mixing process (which is assumed to be linear).

[0004] The blind separation problem is encountered in many familiar forms. For instance, the well-known “cocktail party” problem refers to a situation where the unknown (source) signals are sounds generated in a room and the known (sensor) signals are the outputs of several microphones. Each of the source signals is delayed and attenuated in some (time varying) manner during transmission from source to microphone, where it is then mixed with other independently delayed and attenuated source signals, including multipath versions of itself (reverberation), which are delayed versions arriving from different directions. A person, however, generally wishes to listen to a particular set of sound source while filtering out other interfering sources, including multi-path signals.

[0005] This signal processing problem arises in many contexts other than the simple situation where each of two mixtures of two speaking voices reaches one of two microphones. Other examples involving many sources and many receivers include the separation of radio or radar signals sensed by an array of antennas, sonar array signal processing, image deconvolution, radio astronomy, and signal decoding in cellular telecommunication systems. Those skilled in the signal processing arts have been eager to solve blind source separation problems because of their broad application to many communication fields. Solutions to date, however, are time intensive, require extensive computing power, and the source signal separation is not ideal.

[0006] The present invention broadly contemplates systems and methods for blind source separation based on the identification of a set of conditions which are necessary and sufficient for the separation of the source signals and which any method used for blind source separation must satisfy. Preferably, an optimization technique is used to enforce these conditions to separate and recover the source signals. This approach achieves better signal separation than known processes, and the optimization reduces the time and computing needed to separate the source signals.

[0007] In accordance with the present invention, a simple constrained criterion which stems directly from derived conditions for source separation is identified. Using this criterion, observed, i.e., first signals, and output signals are used to control a filtering matrix. After being initialized, the filtering matrix is updated and projected to the closest unitary matrix. Until the filtering matrix has converged, it continues to be updated and projected to the closest unitary matrix. Once convergence has occurred, the source signals have been recovered.

[0008] FIG. 1 shows a block diagram of the elements in a system utilized for blind separation of independent source signals in accordance with the present invention.

[0009] FIG. 2 shows a flow chart describing a method for blind separation of independent source signals in accordance with an illustrative embodiment of the present invention.

[0010] FIG. 3 shows a flow chart describing the preferred manner in which the projection to the closest unitary matrix is accomplished in accordance with an illustrative embodiment of the present invention.

[0011] Referring to the block diagram of the elements in a system utilized for blind separation of independent source signals in accordance with the present invention shown in FIG. 1, source or transmitted signals 10 are preferably p i.i.d. and mutually independent zero-mean discrete-time sequences a_i(k) i=1, . . . ,p that share the same statistical properties. The source signals pass through transmission channel 20, typically a p×q multiple-input-multiple-output (MIMO) linear memoryless channel which introduces interuser interference (IUI). Received signals 30 are inputted into pre-whitener 40, resulting in observed or sensed signals 50. Received signals 30 and sensed signals 50 may be written as Y(k) and Y′(k), respectively. Sensed signals 50 are then subsequently filtered by a q×p filtering matrix 60 whose outputs, output signals 70, z_j(k), j=1, . . . ,p should ideally match the source signals a_i(k) when the proper filtering matrix 60 is used. To determine the proper filtering matrix 60, output signals 70 are inputted, together with sensed signals 50, into signal processor 80, which controls filtering matrix 60.

[0012] Source signal separation is achieved for both multiple user equalization and single user equalization when the filtering matrix 60 is selected such that it satisfies certain, in each case, conditions. Determining the proper equalizer setting in the case of single user equalization is a special case of multiple user equalization. The conditions to be satisfied in accordance with the present invention are as follows:

[0013] |K(z_j(k))|=|K_a|, j=1, . . . , p  (C1)

[0014] E|z_j(k)|²=σ_a², j=1, . . . , p  (C2)

[0015] E(z_i(k)z_j*(k))=0, i≠j  (C3)

[0016] E denotes the statistical expectation. For a detailed discussion of the derivation of these conditions, the reader is referred to the details which follow.

[0017] The only provision for an appendix is under rule 37 CFR 1.96 for reference to computer program listings which must be provided on CD. The reference to an Appendix was removed to avoid confusion and to avoid mis-treatment of pages 12-16 to ensure that they are properly printed as part of the specification. $\begin{array}{cc}\{\begin{array}{cc}\underset{G}{\max }& F\left(G\right)=\sum _{j=1}^p\left|K\left(z_j\right)\right|\\ \mathrm{subject}\mathrm{to}\text{:}& G^{H}G=I\end{array}& \left(1\right)\end{array}$

[0018] where I is the p×p identity matrix and H denotes the Hermitian (or else complex conjugate) transpose. The constraint in (1) comes from the fact that, according to (C2) and (C3),

[0019] E(zz^H)=σ_a²I  (2)

[0020] (It is assumed for simplicity that σ_a²=1) In accordance with the present invention, (1) is the preferred maximization criterion. The global optima of this preferred criterion achieve blind recovery.

[0021] The p×q channel matrix is denoted by C and the q×1 channel output vector by Y(k). Although denoted Y(k), it is preferred this channel output be “pre-whitened” in both “space” and time by pre-whitener 40. Thus, channel output Y(k) corresponds to sensed signal 50. The sensed signal model is then:

[0022] Y(k)=C^TA(k)+n(k)  (3)

[0023] where Y(k)=[y₁(k) . . . y_q(k)]^Tand n(k) is the q×1 vector of additive noise samples. The receiver output, sensed signal 50, can then be written as

[0024] z(k)=W^T(k)Y(k)=W^T(k)C^TA(k)+n′(k)=G^T(k)A(k)+n′(k)  (4)

[0025] where W(k) and G(k)=CW(k) are the q×p receiver matrix and p×p global response matrix, respectively, and n′(k)=W^T(k)n(k) is the colored noise at the receiver output, all at time instant k.

[0026] FIG. 2 illustrates a flow chart of the steps executed by the signal processor 80 in determining the proper filtering matrix 60, in accordance with the technique of the present invention, which may be referred to as a multi-user kurtosis (MUK) algorithm for blind source separation. Step S20 involves initializing filtering matrix 60, that is for k=0, setting W(0)=W₀. This is accomplished by first computing the gradient of F(G) with respect to W. By writing F(G) as $\begin{array}{c}F\left(G\right)=\sum _{j=1}^p\mathrm{sign}\left(K\left(z_j\right)\right)K\left(z_j\right)\\ =\mathrm{sign}\left(K_a\right)\sum _{j=1}^p\left(E{\left|z_j\right|}^4-2E^2{\left|z_j\right|}^2-{\left|E\left(z_j^2\right)\right|}^2\right)\end{array}$

[0027] and assuming symmetrical inputs (E(a_i²(k)=0)), the gradient of F(G) with respect to W equals $\begin{array}{cc}\nabla \left(F\left(G\right)\right)=4\sum _{j=1}^{p}E\left({\left|z_j\left(k\right)\right|}^2{z}_j\left(k\right)Y^{*}\left(k\right)\right)& \left(5\right)\end{array}$

[0028] At Step S21, for k>0, it is determined if the matrix has converged. If the matrix has converged, the recovered signals outputted in Step S22 are very close to the input signals. If convergence has not occurred, the filtering matrix is updated in Step S23. In accordance with the present invention, W(k) is updated in the direction of the in stantaneous gradient (dropping the expectation operator in (5)) as follows:

[0029] W′(k+1)=W(k)+μ sign(K_a)Y*(k)Z(k)  (1)

[0030] where

[0031] Z(k)=[|z₁(k)|²z₁(k) . . . |z_p(k)|²z_p(k)]  (2)

[0032] and μ is the algorithm's step size. The orthogonality constraint needs to be satisfied at the next iteration of the algorithm:

[0033] G^H(k+1)G(k+1)=I  (3)

[0034] For this to be feasible, it is necessary for the channel output to be “pre-whitened” in both “space” and time. This corresponds to assuming the channel matrix C to be unitary, which is achieved by the pre-whitener 40 in FIG. 1. Assuming that C is unitary, to satisfy the constraint (8) it suffices to satisfy

[0035] W^H(k+1)W(k+1)=I  (4)

[0036] Because there is no guarantee that W′(k+1) will satisfy the constraint (9), it must be hence transformed to a unitary W(k+1)=f(W′(k+1)).

[0037] Preferably, W(k+1) is chosen to be a q×p matrix which is as close as possible to W′(k+1) in the Euclidean sense. Dropping the time index for convenience, this can be achieved with an iterative procedure which satisfies the following criterion successively for j=1, . . . , p: $\begin{array}{cc}\{\begin{array}{cc}\underset{w_j}{\min }& \Delta \left(W_j\right)=\left|\right|W_j-W_j^{\prime }{\left|\right|}^2\\ \mathrm{subject}\mathrm{to}\text{:}& W_l^H{W}_j={\delta }_{\mathrm{ij}},l=1,\dots ,j\end{array}& \left(10\right)\end{array}$

[0038] where ∥X∥²=X^HX is the squared Euclidean norm of vector X and where W′ is defined from

[0039] W′=[W′₁. . . W′_p]  (11)

[0040] The problem (10) can also be written as $\begin{array}{cc}\{\begin{array}{cc}\underset{w_j}{\min }& \Delta \left(W_j\right)={\left(W_j-W_j^{\prime }\right)}^H\left(W_j-W_j^{\prime }\right)\\ \mathrm{subject}\mathrm{to}\text{:}& W_l^H{W}_j={\delta }_{\mathrm{ij}},l=1,\dots ,j\end{array}& \left(12\right)\end{array}$

[0041] To solve the problem (12) the Lagrangian of Δ(W_j) is constructed, which equals $\begin{array}{cc}\begin{array}{c}{𝔷}_{\Delta }\left(W_j,{\lambda }_j,\mu ,v\right)=\Delta \left(W_j\right)-{\lambda }_j\left(W_j^H{W}_j-1\right)-\\ \sum _{l=1}^{j-1}{\mu }_{\mathrm{lj}}\mathrm{Re}\left(W_l^H{W}_j\right)-\sum _{l=1}^{j-1}{v}_{\mathrm{lj}}\mathrm{Im}\left(W_l^H{W}_j\right)\end{array}& \left(13\right)\end{array}$

[0042] where λ_j, μ_lj, v_ljare real scalar parameters. Setting the gradient of £_Δ(W_j, λ_j, μ, v) with respect to W_jto zero $\left(\frac{\partial {𝔷}_{\Delta }}{\partial W_j^{*}}=0\right),$

[0043] the following are obtained for each j: $\begin{array}{cc}{W}_j-W_j^{\prime }-{\lambda }_j{W}_j-\sum _{l=1}^{j-1}{\beta }_{\mathrm{lj}}{W}_l=0& \left(14\right)\end{array}$

[0044] where β_lj=½(μ_lj+{square root over (−1)}v_lj). From (14)

[0045] $\begin{array}{cc}\{\begin{array}{c}{\lambda }_j=1-W_j^H{W}_j^{\prime }\\ {\beta }_{\mathrm{ij}}=-W_l^H{W}_j^{\prime }\end{array}& \left(15\right)\end{array}$

[0046] is obtained, which gives $\begin{array}{cc}\left(1-{\lambda }_j\right)W_j=W_j^{\prime }-\sum _{l=1}^{j-1}\left(W_l^H{W}_j^{\prime }\right)W_l& \left(16\right)\end{array}$

[0047] According to (16), $\begin{array}{cc}{W}_j\propto \left(W_j^{\prime }-\sum _{l=1}^{j-1}\left(W_l^H{W}_j^{\prime }\right)W_l\right)& \left(17\right)\end{array}$

[0048] where ∝ denotes “proportional”. In light of (17), and keeping in mind that W_j^HW_j=1, W_j(bringing back the time index) must be chosen as: $\begin{array}{cc}{W}_j\left(k+1\right)=\frac{W_j^{\prime }\left(k+1\right)-\sum _{l=1}^{j-1}\left(W_l^H\left(k+1\right)W_j^{\prime }\left(k+1\right)\right)W_l\left(k+1\right)}{\Vert W_j^{\prime }\left(k+1\right)-\sum _{l=1}^{j-1}\left(W_l^H\left(k+1\right)W_j^{\prime }\left(k+1\right)\right)W_l\left(k+1\right)\Vert }& \left(18\right)\end{array}$

[0049] The updated filtering matrix is then projected to the closest unitary matrix in Step S24. FIG. 3 illustrates a flow chart of the steps taken in projecting the filtering matrix to the closet unitary matrix in Step S24. In Step S30, the norm of the first column of the updated filtering matrix 60 is corrected, that is $W_1\left(k+1\right)=\frac{W_1^{\prime }\left(k+1\right)}{\left|\left|W_1^{\prime }\left(k+1\right)\right|\right|}$

[0050] In Step S31 it is determined if there are more columns in the filtering matrix whose norm needs to be corrected. If not, a unitary filtering matrix is generated from the corrected columns in Step S32, according to equation (12). If so, the norm for the next column is corrected, that is: W_j(k+1) is computed in accordance with Equation (18).

[0051] Steps S30-33 correspond to a Gram-Schmidt orthogonalization of W′(k+1). The projection described by steps S30-33 would reduce to the mere normalization of Step 530 in the case of a single user. Also, if the transmitted input is non-symmetrical, equation (6) should use instead of Z(k) in (7) the following vector:

[0052] Z′(k)=[|z₁(k)|²z₁(k)−<z₁²(k)>z₁*(k) . . . |z_p(k)|²z_p(k)−<z_p²(k)>z_p*(k)]  (19)

[0053] where < > denotes empirical averaging.

[0054] The system of the present invention includes an input signal receiver, a filtering matrix, a signal processor, and a convergence detector, which may be implemented on a suitably programmed general purpose computer. These may also be implemented on an Integrated Circuit, part of an Integrated Circuit, or parts of different Integrated Circuits. Thus, it is to be understood that the invention may be implemented in hardware, software, or a combination of both. Accordingly, the present invention includes a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform any of the method steps herein described for performing blind source separation of independent source signals. Such method steps could include, for example, receiving an input signal which is the result of an independent source signal having passed through a transmission channel; pre-whitening said input signal to obtain an observed signal; inputting said input signal into a filtering matrix to obtain a recovered signal; utilizing said observed signal and said recovered signal to update said filtering matrix; projecting said updated filtering matrix to the closest unitary matrix, outputting a signal representing said independent source signal when said recovered signal has converged, when said recovered signal has not converged, employing said closest unitary matrix as a new filtering matrix and continuing to input said input signal into a filtering matrix to obtain a recovered signal, utilizing said observed signal and said recovered signal to update said filtering matrix, projecting said updated filtering matrix to the closest unitary matrix, and outputting a signal representing said independent source signal when said recovered signal has converged.

[0055] Again, it is to be emphasized that any of the method steps, in any combination, can be encoded and tangibly embodied on a program storage device according to the present invention.

[0056] While only certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes or equivalents will now occur to those skilled in the art. It is therefore intended to be understood that the appended claims are intended to cover all such modifications and changes that fall within the true spirit of the invention.

[0057] The equalizer output signals, z_j(k), j=1, . . . , p can be written as a function of the source signals a_i(k), i=1, . . . , p as follows: $\begin{array}{cc}{z}_j\left(k\right)=\sum _{l=1}^p{g}_{\mathrm{jl}}{a}_l\left(k\right)=G_j^{T}A\left(k\right),j=1,\dots ,p& \left(20\right)\end{array}$

[0058] where A(k)=[a₁(k) . . . a_p(k)]^T. G_jis the channel/equalizer cascade that contains the contribution of all the p channel inputs to the j-th equalizer output, and T denotes matrix transpose. Equation (20) can be also written in the familiar form

[0059] z(k)=[z₁(k) . . . z_p(k)]^T=G^TA(k)  (21)

[0060] where $\begin{array}{cc}G=\left[G_1\dots G_p\right]=\left[\begin{array}{ccc}{g}_{11}& \cdots & g_{\mathrm{p1}}\\ ⋮& ⋮& ⋮\\ g_{1p}& \cdots & g_{\mathrm{pp}}\end{array}\right]& \left(22\right)\end{array}$

[0061] The above-described linear mixture setup can be used to model narrowband antenna-array systems, code division multiple access (CDMA) systems, or oversampled systems.

[0062] Each output's power and kurtosis may be expressed as: $\begin{array}{cc}E\left({\left|z\left(k\right)\right|}^2\right)={\sigma }_a^2\sum _{l=1}^p{\left|g_{\mathrm{jl}}\right|}^2,j=1,\dots ,p& \left(23\right)\\ K\left(z_j\right)=K_a\sum _{l=1}^p{\left|g_{\mathrm{jl}}\right|}^4,j=1,\dots ,p& \left(24\right)\end{array}$

[0063] respectively K_ais the (unnormalized) kurtosis and σ_a²the variance of each a_j(k) (since they are all assumed to share the same distribution), defined as

[0064] K_a=K(a_j(k))

[0065] σ_a²=E(|a_j(k)|²)  (25)

[0066] where K(x)=E(|x|⁴)−2E²(|x|²)−|E(x²)|².

[0067] Determining the proper equalizer setting in the case of single user equalization of intersymbol interference channels (ISI) channels is a special case of multiple user equalization. The single equalizer output may be written as z(k)=G^TA(k), where G is a (possibly infinite-length) column vector containing the coefficients of the channel impulse response. Similar to equations (23) and (24), the output power and kurtosis for a single equalizer output are $\begin{array}{cc}E\left({\left|z_j\left(k\right)\right|}^2\right)={\sigma }_a^2\sum _{l\in P}{\left|g_l\right|}^2& \left(26\right)\\ K\left(z\left(k\right)\right)=K_a\sum _{l\in P}{\left|g_l\right|}^4& \left(27\right)\end{array}$

[0068] where P is a subset of the set of integers. Based on these expressions, the following set of conditions are necessary and sufficient for BE: $\begin{array}{cc}\{\begin{array}{c}\left|K\left(z\left(k\right)\right)\right|=K_a\\ E{\left|z\left(k\right)\right|}^2={\sigma }_a^2\end{array}& \left(28\right)\end{array}$

[0069] which stems from the fact that $\begin{array}{cc}\sum _{l\in P}{\left|g_l\right|}^4\le {\left(\sum _{l\in P}{\left|g_l\right|}^2\right)}^2& \left(29\right)\end{array}$

[0070] Equality in (29) holds only in the case that there exists a unique nonzero element g_lof unit magnitude for some lεP. Based on the condition (28), the following constrained optimization problem has been suggested for BE $\begin{array}{cc}\{\begin{array}{cc}\underset{G}{\max }& F_{\mathrm{SW}}\left(G\right)=\left|K\left(z_j\right)\right|\\ \mathrm{subject}\mathrm{to}\text{:}& G^{H}G=1\end{array}& \left(30\right)\end{array}$

[0071] An important result about the behavior of criterion (11) is that the cost function F_SW(G) is free of undesired local maxima on G^HG=1 if G is infinite-length. This makes the corresponding algorithm for BE globally convergent to a “Dirac” solution, that is a solution with a single non-zero element (up to a scalar phase shift). Moreover, the popular Constant Modulus Algorithm (CMA) 2—2 can be seen as a special case of constrained optimization criteria when the input is sub-Gaussian, thus it reflects the global convergence property as well.

[0072] As is typical in blind equalization, the method of the present invention permits each transmitted signal to be recovered up to a unitary scalar rotation. This is due to the inherent inability of statistical blind techniques to distinguish between different rotated versions of the input signals. Therefore, blind recovery will be achieved if (after suitable reordering of the equalizer outputs) the following holds:

[0073] z_j(k)=e^{{square root over (−1)}φ}a_j(k)  (31)  (31)

[0074] for some φ_jε[0,2π) and all jε{1, . . . , p}.

[0075] Based on (23) and (24), if each a_i(k), i=1, . . . , p is an i.i.d. zero-mean sequence, {a_i(k)}, {a_j(k)} are statistically independent for i≠j and share the same statistical properties, then the following set of conditions are necessary and sufficient for the recovery of all the transmitted signals at the equalizer outputs:

[0076] |K(z_j(k))|=|K_a|, j=1, . . . , p  (C1)

[0077] E|z_j(k)|²=σ_a², j=1, . . . , p  (C2)

[0078] E(z_i(k)z_j*(k))=0, i≠j  (C3)

[0079] To achieve perfect recovery (31) must hold, from which (C1) and (C2) follow immediately and (C3) follows since E(a_i(k)a_j*(k))=0 for i≠j (* denotes complex conjugate).

[0080] From (24) and (C1), the following is obtained: $\begin{array}{cc}\sum _{l=1}^p{\left|g_{\mathrm{jl}}\right|}^4=1& \left(32\right)\end{array}$

[0081] From (23) and (C2), the following is obtained: $\begin{array}{cc}\sum _{l=1}^p{\left|g_{\mathrm{jl}}\right|}^2=1& \left(33\right)\end{array}$

[0082] Therefore, equations (32) and (33) dictate, in the light of (29), that G_jmust be of the form

[0083] G_j=[. . . e^{{square root over (−1)}φ}. . . ]^T  (34)

[0084] where the single non-zero element can be at any position. Combining (C3) with (21) gives:

[0085] G_i^HG_j=0, i≠j  (35)

[0086] where H denotes the Hermitian (or else complex conjugate) transpose. According to (34) and (35), if G_j's non-zero element is at position n, then G_icannot have its non-zero element at position n. Hence, the p different “Dirac”-type vectors G_jof the form (34) will all contain their unique nonzero elements at different positions. This corresponds to the recovery of all the p different inputs a_j(k). Therefore, after re-ordering, (31) is obtained and perfect signal separation (in the above sense) has been achieved.