Services

6 pages
8 views

A kernel canonical correlation analysis algorithm for blind equalization of oversampled Wiener systems

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
A kernel canonical correlation analysis algorithm for blind equalization of oversampled Wiener systems
Transcript
  A KERNEL CANONICAL CORRELATION ANALYSIS ALGORITHMFOR BLIND EQUALIZATION OF OVERSAMPLED WIENER SYSTEMS Steven Van Vaerenbergh, Javier V ´ ıa and Ignacio Santamar ´ ıa { steven,jvia,nacho } @gtas.dicom.unican.esDepartment of Communications EngineeringUniversity of Cantabria, Spain ABSTRACT In this paper we present an algorithm for blind equalizationof single-input multiple-output (SIMO) nonlinear systems, inwhich each nonlinear channel is a Wiener system. The pro-posed method combines ideas from blind linear SIMO iden-tification with kernel canonical correlation analysis (kernelCCA) to identify the nonlinearities. It is shown in the paperthat the blind equalization problem can be solved in an itera-tive manner, alternating between a CCA problem (to estimatethe linear filters) and a kernel CCA problem (to estimate thememoryless nonlinearities). The resulting algorithm can beapplied to the general case of nonlinear SIMO systems with P  outputs. Simulations are included to demonstrate its effec-tiveness. 1. INTRODUCTION In the last decade there has been a great interest in blind iden-tification and equalization methods. In digital communica-tions, blind methods permit channel identification or equal-ization without the need to send known training signals, thussaving bandwidth. In particular, the problem of blind identifi-cationofsingle-inputmultiple-output(SIMO)linear channelshas received considerable attention [1, 2]. In this case, blindidentification can be accomplished by resorting only to thesecond-order statistics (SOS) of the channel output.While a lot of attention has gone to the analysis of linearSIMOsystems, manyreal-lifesystems exhibitnonlinearchar-acteristics. Recently, a growing amount of research has beenconducted on nonlinear system identification [3]. Nonlineardynamical system models generally have a high number of parameters, although many problems can be sufficiently wellapproximated by simplified block-based models. The modelconsisting of a cascade of a linear dynamic system and amemoryless nonlinearity is known as the Wiener system, asillustrated in Fig. 1. Wiener systems are frequently used in This work was supported by MEC (Ministerio de Educaci´on y Ciencia)under grant TEC2007-68020-C04-02 TCM (MultiMIMO) and FPU grantAP2005-5366. s [ n ] n [ n ] x [ n ] y [ n ] H  ( z ) f  ( · ) Fig. 1 . A Wiener system with additive noise n [ n ] .contexts such as digital satellite communications [4], opticalfibre communications [5] and digital magnetic recording.A number of supervised approaches have been proposedto identify or equalize these systems, ranging from black-boxapproachesusingdifferenttypesofstructuresandtrainingcri-teria [6, 7], to approaches that explicitly exploit the systemstructure [8, 9, 10]. However, very little work has been doneon blind identification methods. Blind methods generally as-sume some knowledgeon the input signal statistics and/or thechannel model. A few blind methods to identify Wiener sys-tems can be found in [11, 12]. Blind identification methodsfor other nonlinearsystems such as Volterra models have alsobeen presented in [13, 14].In this paper we present a blind method to identify andequalize nonlinear SIMO systems that consist of variousWiener systems, as illustrated in Fig. 2. These systems couldrepresent a sensor array in which every sensor exhibits a non-linear behavior, or they could be obtained by oversamplingthe output of a nonlinear communications channel [1]. Thepresentedmethodcombines ideas from the blind linear SIMOidentification method in [1] and from the supervised nonlin-ear equalization technique discussed in [9]. It performs atthe same time a kernel-based regression to learn the nonlin-earities and a least-squares (LS) method to retrieve the linearchannels. The assumptions made by our method are thatevery nonlinearity in the SIMO Wiener system is invertible,that the linear channels share no common zeros and, finally,that the maximum channel order is known.  s [ n ] n 1 [ n ] n 2 [ n ] x 1 [ n ] x 2 [ n ] y 1 [ n ] y 2 [ n ] H  1 ( z ) H  2 ( z ) f  1 ( · ) f  2 ( · ) Fig. 2 . A SIMO system consisting of 2 Wiener systems. 2. PROBLEM SETTING Consider a nonlinear SIMO system, in which each channelis modeled as a Wiener system. An example with only twooutputs is shown in Fig. 2. In a general case with P  outputsthe system can be modeled as y i [ n ] = L − 1  j =0 h i [  j ] s [ n −  j ] (1) x i [ n ] = f  i ( y i [ n ]) + n i [ n ] , (2)where s [ n ] represents the input symbol sent at time instant n , h i [  j ] is the j -th coefficient of the i -th linear FIR channel H  i ( z ) , f  i ( · ) is the nonlinearity of channel i and n i [ n ] rep-resents additive Gaussian noise, for i = 1 ,...,P  and n =0 ,...,N  − 1 . Without loss of generality, L represents themaximum channel order (which we assume to be known).The problem considered in this paper is to recover thetransmitted signal s [ n ] when only the output signals x i [ n ] areobserved. 3. BLIND SIMO WIENER SYSTEM EQUALIZATION The solution we propose to the equalization problem ismainly based on the linear identification method presented in[1]. In the following this linear method is explained brieflyfor a 1 × 2 linear SIMO system, although the generalizationto more output channels is straightforward. 3.1. Blind identification of a linear SIMO system Taking a block of  N  observations, define the matrix X i =  x i [ n + L − 1] ··· x i [ n ] ......... x i [ n + N  − 1] ··· x i [ n + N  − L ]  , (3)for i = 1 , 2 . Denoting the estimate of the channel impulseresponse vectors as ˆ h i =  ˆ h i [0] ,..., ˆ h i [ L − 1]  T  , (4) s [ n ] x 1 [ n ] x 2 [ n ] H  1 ( z ) H  2 ( z )ˆ H  1 ( z )ˆ H  2 ( z ) e [ n ] Fig.3 . A blindidentificationschemefora linearSIMO modelwithout noise.it can be easily verified that in a noiseless case the solutionshould satisfy X 1 ˆ h 2 = X 2 ˆ h 1 , (5)as illustrated in Fig. 3.In order to avoid the trivial solution ˆ h i = 0 , a restrictionmust be applied to the solution. Typical restrictions in com-munications are either to fix the norm of the filters ˆ h i , or tofix the norm of the output signal X i ˆ h j .A restriction on the filter norm was used in [1] to developthe LS method, also referred to as cross-relation. This prob-lem consists of minimizing the cost function J  LS =12  X 1 ˆ h 2 − X 2 ˆ h 1  2 s.t.  ˆ h 1  2 +  ˆ h 2  2 = 1 , (6)which is equivalent to the following eigenvalue problem  X T  1 X 1 − X T  1 X 2 − X T  2 X 1 X T  2 X 2  ˆ h = β  ˆ h . (7)The solution ˆ h = [ˆ h T  2 , ˆ h T  1 ] T  is found as the eigenvector cor-responding to the smallest eigenvalue.If, instead, the constraint is applied to the norm of outputsignals as in [2], the cost function to minimize turns out to be J  CCA =12  X 1 ˆ h 2 − X 2 ˆ h 1  2 s.t.  X 1 ˆ h 2  2 +  X 2 ˆ h 1  2 = 1 . (8)This is a canonical correlation analysis (CCA) problem, andits solutionis givenbythe principaleigenvectorofthe follow-ing generalized eigenvalue problem (GEV)  X T  1 X 1 X T  1 X 2 X T  2 X 1 X T  2 X 2  ˆ h = β   X T  1 X 1 00 X T  2 X 2  ˆ h . (9)Once the channels ˆ h 1 and ˆ h 2 have been estimated, they canbe used to obtain an equalizer by applying the zero-forcing(ZF) or the minimum mean square error (MMSE) approach.NotethatboththeLSalgorithmandtheCCA-basedalgorithmrequireknowledgeof themaximumchannelorder L , andtheyassume the linear channels share no common zeroes.When we consider that each channel of the system is re-placed by a Wiener system, the scheme of Fig. 4 can be usedfor blind identification, where the influence of the nonlinear-ities f  i ( · ) is removed first, by estimating the inverse nonlin-earities g i ( · ) =ˆ f  − 1 i ( · ) .  s [ n ] v 1 [ n ] v 2 [ n ] x 1 [ n ] x 2 [ n ] y 1 [ n ] y 2 [ n ] H  1 ( z ) H  2 ( z ) f  1 ( · ) f  2 ( · ) g 1 ( · ) g 2 ( · ) ˆ y 1 [ n ]ˆ y 2 [ n ]ˆ H  1 ( z )ˆ H  2 ( z ) z 12 [ n ] z 21 [ n ] e 12 [ n ] Fig. 4 . The identification diagram for a SIMO system consisting of 2 Wiener subsystems, in which g i ( · ) =ˆ f  − 1 i ( · ) .To estimate the inverse nonlinearities g i ( · ) , we will ap-ply a nonparametric identification approach based on kernelmethods. Nonparametric approaches do not assume that thenonlinearity corresponds to a given model, but rather let thetraining data decide which characteristic fits them best. 3.2. Nonlinear regression with kernel methods Kernel methods [15] are based on a nonlinear transformation Φ of the data from the input space to a high-dimensional fea-ture space H , where it is more likely that a problem can besolved in a linear manner, Φ : R m → H Φ( x ) =˜ x . Scalar products in feature space can be calculated without theexplicit knowledge of the nonlinear transformation Φ , by ap-plying the corresponding kernel function κ ( · , · ) on pairs of data points in the input space, κ ( x i , x j ) :=  ˜ x i , ˜ x j  =  Φ( x i ) , Φ( x j )  . (10)This property, which is known as the “kernel trick”, allowsto perform any scalar product-based algorithm in the featurespace by solely replacing the scalar products with the kernelfunction in the input space.Most kernel algorithms use a kernel matrix K i , which isconstructedbyapplyingthekernelfunctiononpairsofpoints: k i ( m,n ) = κ ( x i [ m ] ,x i [ n ]) , with m,n = 1 ,...,N  . An oftenused kernel function is the Gaussian kernel with width σκ ( x i , x j ) = exp  − x i − x j  2 2 σ 2  , which implies an infinite dimensional feature space [15].Nonlinear regression with kernels is possible by repre-senting the nonlinearity as a kernel expansion ˆ y i [ n ] = g i ( x i [ n ]) = M   m =1 ˆ α i [ m ] κ ( x i [ n ] ,x si [ m ]) , (11)where x si [ m ] are called the support vectors of the nonlin-ear representation. In the following we will use the variable k si ( n,m ) = κ ( x i [ n ] ,x si [ m ]) to simplify the notation. In afirst approach, all available points x i [ n ] will be used as sup-port vectors, i.e., M  = N  .At this point it should be clear that once the inverse non-linearities g i ( · ) have been estimated, retrieval of the linearFIR channels ˆ h i is straightforward through a linear SIMOidentification technique such as the CCA- or LS-based algo-rithms. Given only the outputs x i [ n ] of the system, directestimation of these nonlinearities is difficult, however, sinceno information on the input signal s [ n ] is available.Therefore,since separateestimation ofthe linearandnon-linear parts of this system is difficult, we will design an algo-rithm that allows us to obtain both the linear filters and thenonlinearities simultaneously, through a single cost function. 3.3. Proposed cost function First, we will treat the case where the observed system hasonly two outputs. Given the representation of the nonlinear-ity g i ( · ) as in (11), the output of the proposed identificationscheme can be written as z 12 [ n ] = L − 1  i =0 M   m =1 ˆ h 2 [ i ] k s 1 ( n − i,m )ˆ α 1 [ m ] . (12)In matrix notation, this becomes z 12 [ n ] =ˆ h T  2 K 1 [ n ] ˆ α 1 , (13)where the l -th row of  K  1 [ n ] contains the elements from k s 1 ( n + l − 1 , 1) till k s 1 ( n + l − 1 ,M  ) . The expression for z 21 [ n ] is found in the same manner. Combining N  outputsamples of each channel into the vectors z 12 and z 21 , weobtain the following cost function to minimize: J  2 =  z 12 − z 21  2 s.t.  z 12  2 +  z 21  2 = 1 . (14) 3.4. Proposed iterative solution The minimization problem (14) has no direct analytical so-lution. However, if  ˆ α 1 and ˆ α 2 were available, it would bepossible to obtain the correspondingoptimal filters ˆ h 2 and ˆ h 1  by applying linear CCA. Moreover, since we are represent-ing the nonlinearities g 1 ( · ) and g 2 ( · ) as linear combinationsof support vectors, a similar operation can be carried out toestimate these: if  ˆ h 2 and ˆ h 1 are given, (14) can be solved tofind the optimal coefficients of the kernel expansions ˆ α 1 and ˆ α 2 . This suggests an iterative scheme that alternates betweenupdating the linear channels ˆ h i and the memoryless nonlin-earities ˆ α i . Convergence is guaranteed because each updatemay either decrease or maintain the cost. 3.4.1. Iteration 1: given ˆ α i  , obtain ˆ h i If estimates of  ˆ α 1 and ˆ α 2 are given, Eq. (12) shows that theoutput z 12 [ n ] of the identification scheme can be obtained as z 12 [ n ] = L − 1  i =0 ˆ h 2 [ i ]ˆ y 1 [ n − i ] , (15)where ˆ y 1 [ n − i ] is calculated with (11). In matrix form thiscan be written as z 12 =ˆ Y 1 ˆ h 2 , where n -th row of the matrix ˆ Y 1 contains the elements from ˆ y 1 [ n ] until ˆ y 1 [ n + L − 1] . Theminimization problem (14) can be rewritten as minimizing J  h =  ˆ Y 1 ˆ h 2 − ˆ Y 2 ˆ h 1  2 s.t.  ˆ Y 1 ˆ h 2  2 +  ˆ Y 2 ˆ h 1  2 = 1 , (16)which can be solved by standard linear CCA. 3.4.2. Iteration 2: given ˆ h i  , obtain ˆ α i If estimates of  ˆ h 1 and ˆ h 2 are given, Eq. (12) shows that theoutput z 12 [ n ] of the identification scheme can be obtained as z 12 [ n ] = M   m =1 w 1 [ n,m ]ˆ α 1 [ m ] , (17)wherethe variable w 1 [ n,m ] =  L − 1 i =0 ˆ h 2 [ i ] k 1 ( n − i,m ) is in-troduced. In matrix form this can be written as z 12 = W 1 ˆ α 1 ,where the n -th row of the matrix W 1 contains the elements w 1 [ n, 1] until w 1 [ n,M  ] . The minimization problem (14) canbe rewritten as minimizing J  ˆ α =  W 1 ˆ α 1 − W 2 ˆ α 2  2 s.t.  W 1 ˆ α 1  2 +  W 2 ˆ α 2  2 = 1 . (18)Ifall datapoints x i [ n ] areusedas supportvectorsinthekernelexpansion(11),i.e., if  M  = N  (which implies ˆ α i ∈ R N  ), thedimensionality of this problem is significantly higher than itslinear counterpart (16). This leads to various difficulties.First of all, problem(18)will suffer fromoverfittingwhensufficiently “rich” kernel functions are used, i.e., kernels thatcorrespond to feature spaces whose dimension m ′ is muchhigher than the number of available data points N  . This oc-curs for instance for the Gaussian kernel, whose feature spaceis infinite dimensional. Second, the GEV corresponding tothisproblemrequirestheretrievalofeigenvectorsof  2 N  × 2 N  Algorithm 1 Equalization algorithm for nonlinear SIMOchannels.Initialization: obtain ˆ h i by solving the LS problem (7).Construct the kernel matrices K i from x i [ n ] .Perform kernel PCA to obtain the reduced matrices W i . repeat CCA1: With given ˆ h i , update ˆ α i by solving (18).CCA2: With given ˆ α i , update ˆ h i by solving (16). until ConvergenceObtain s [ n ] from ˆ y i [ n ] and ˆ h i by applying linear ZF orMMSE equalizers.matrices, which in this case implies a high computationalcost.Overfitting is a common issue in kernel CCA that can besolved in different manners [16]. Common workarounds in-clude adding regularization to the problem or reducing thedimensionality of the problem by applying kernel PCA [17].In this case a dimensionality reduction is desired since at thesame time it will avoid overfitting and reduce the computa-tional load. Specifically, kernel PCA reduces the kernel ma-trix K i ∈ R N  × N  to V i Σ i V T i ≈ K i , (19)where Σ i ∈ R M  × M  is a diagonal matrix containing the M  largest eigenvalues of  K i and V i ∈ R N  × M  contains the M  corresponding eigenvectors. This allows us to redefine thevariable w 1 [ n,m ] as w 1 [ n,m ] =  L − 1 i =0 h 2 [ i ] v 1 ( n − i,m ) ,where v 1 ( n,m ) is the n -th element of the m -th eigenvectorin V 1 . Thanks to this reduction, the dimensions of the matrices W i in (18) are reduced to N  × M  , with M  ≪ N  , and thesolutions ˆ α i can be found by applying CCA. 3.5. Extensions and Further Comments Analogously to many other iterative techniques, the perfor-mance of the proposed approach can depend on the initial-ization of the linear channels and nonlinearities. Here, wepropose to obtain an initial estimate of the linear channels ˆ h i by first applying the LS algorithm from [1] to the outputs x i [ n ] , i.e, in the first iteration, the estimated nonlinearities are g i ( x i [ n ]) = x i [ n ] . Furthermore, we must note that the finaltarget of the proposed algorithm consists in recovering thesource signal s [ n ] . Thus, after obtaining the outputs ˆ y i [ n ] andthe linear channels ˆ h i , the input can be easily recovered bymeans of a linear ZF or MMSE equalizer.In the general case of a system with P  sensors, the costfunction needs to take into account the difference betweeneachpair ofoutputs. Note that theoutputsignal z ij representsthe signal x i after being transformed by g i ( · ) and filtered by  −2 −1 0 1 2−4−2024x      y   output x vs real youtput x vs estimated y (a) Nonlinearity estimate. 1 2 3 4 5 −0.6−0.4−0.200.20.40.6   real channel coefficientsestimated channel coefficients (b) Linear filter coefficients. Fig. 5 . Identification results on the 1 × 3 Wiener SIMO sys-tem. (a) shows the noisy output x 3 [ n ] vs. the real internalsignal y 3 [ n ] , and x 3 [ n ] vs. the estimated ˆ y 3 [ n ] . (b) shows theestimated filter coefficients of  h 3 vs. the real coefficients. h j . The cost function to minimize now becomes J  P  = M   i,j =1 i  = j  z ij − z ji  2 s.t. M   i,j =1 i  = j  z ij  2 = 1 , (20)and the resulting algorithm is analogous to that of the two-channel case. The final iterative technique for P  output chan-nels is summarized in Algorithm 1.Finally, we must note that when the SIMO system is ob-tainedbyoversampling,the P  nonlinearitieswill be the same.Obviously, this can be exploited to obtain a more accurate es-timate. The corresponding GEV can be found easily, but it isomitted here due to space restrictions. 4. EXPERIMENTS We experimentally tested the proposed algorithm with somenumerical examples. All tests were conducted on data sets of  N  = 256 data symbols. The fraction of the signal energy dis-cardedbythe kernelPCA procedureintheinitializationphasewas fixed as 10 − 14 . The resulting number of kept eigenvec-tors was between M  = 11 and M  = 15 . In all experimentsconvergencewas obtained in less than 20 iterations.The first system used is a 1 × 3 Wiener SIMO system withlinearfilters h 1 = [0 . 6172 , 0 . 6247 , 0 . 3373 , − 0 . 0349 , − 3 . 2957] T  , h 2 = [ − 0 . 8601 , 0 . 1532 , − 0 . 1888 , − 0 . 6264 , 0 . 9985] T  and h 3 = [1 . 3271 , − 0 . 1472 , − 0 . 4786 , 0 . 6682 , 0 . 0045] T  , respec-tively. The nonlinearity was the same for all the channels,namely f  i ( x ) = tanh(0 . 8 x ) + 0 . 1 x .A first test was conductedon this system with a zeromeanand unit variance Gaussian source. The power of the whiteGaussian noise after the nonlinearities was fixed to obtain a 20 dB SNR. Fig. 5 shows the true and estimated linear filterand nonlinearity for one of the branches of the Wiener SIMOsystem, after 15 iterations of the algorithm.We then compared the proposed algorithm to the linearCCA-based equalizer from [2]. Averages were taken over 0 10 20 30 40 50 6010 −6 10 −5 10 −4 10 −3 10 −2 10 −1 10 0 SNR (dB)     M    S    E   linear CCA on SIMO linear systemlinear CCA on SIMO Wiener systemblind KCCA on SIMO Wiener systemsupervised KCCA on SIMO Wiener system Fig. 6 . MSE comparison for different algorithms. 50 independent Monte-Carlo simulations, and the MSE wascalculated between the true and the estimated input signal.The results are shown in Fig. 6. The curve with solid black dots was obtained by applying the linear CCA-based equal-izer on the system that only contained the linear channels h 1 , h 2 and h 3 . The same algorithm was tested on the nonlinear 1 × 3 SIMO Wiener system, resulting in the curve with whitesquares. The curve marked with circles was obtained by ap-plying the proposed blind method on the 1 × 3 SIMO Wienersystem, and in the last curve (dashed line) we show the re-sults when the supervised method of [9] was applied to thissystem. The proposed method obtains results that are veryclose to those obtained by the supervised method.For the second test we comparedthree SIMO Wiener sys-tems with different numbers of outputs. System 1 was a 1 × 2 SIMO Wiener system with h 1 and h 2 as defined in the firstexperiment. System 2 was the discussed 1 × 3 system. Sys-tem 3 was a 1 × 4 SIMO Wiener system that included allthreepreviousWiener systems and a new linearchannel h 4 =[ − 0 . 1155 , − 0 . 9170 , 0 . 5605 , 0 . 4862 , − 0 . 8004] T  in its fourthbranch. The nonlinearity was maintained, and we exploitedthe fact that it was the same for each channel. The results areshown in Fig. 7. The same test was repeated for a systemwith a binary input s [ n ] ∈ {− 1 , 1 } , but now we did not ex-ploit the information that the nonlinearity was the same foreach channel. The results are shown in Fig. 8. 5. CONCLUSIONS We proposed a blind equalization algorithm for nonlinearSIMO systems in which every channel is a Wiener system.Basically, the method iterates between a CCA algorithm forestimating the linear channel and a KCCA algorithm for es-timating the memoryless nonlinearities. First results showthat this iterative algorithm converges fast and achieves per-formance that is very close to a related supervised method.Future research lines include a comparison to other blindnonlinear equalization methods such as [13, 14].
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x