Data pre-processing for high-resolution adaptive algorithms

DATA PRE-PROCESSING FOR HIGH-RESOLUTION ADAPTIVE ALGORITHPIS Gregori VAZQUEZ, Mateo AMENGUAL, Antoni GASULL Dto. Teoria de la Sefial y C'omunicaciones E. T . S. I. C/ Jordi Girona Salgado, s/n 08034, BARCELOW,, SPAIF TELECOMUNICAC ION his pper deals with the inclusicn of ackqqtive xhaws in high-nsoluticn mtMs. Past wrks refer gradient and mjqaW gra3ient aFproaches of Pimrko's spectral line deccnposition mthd for sirusoidal in white noise mxlellirg. 'he prqpal is mre general in the objective definition. It is wdl knrwn that it is psssible to generate a ccrrplete fanily of spctral estktors fran the tbmlizd WimaTl Likelihd MctM, with a structure of per Rayleigh wien. In the generaticn of adaptive versiolls, the ppr prcpses the substitution of the ccnventimal rrean square filtering error by Wratic objectives hilt as inner prcducts of the mefficient error vector oE the estimtor filter. 1. -lla"xta min goal of this paper is the inclusion of daptive mthds in high-esolution sp~tral estimation alprithms. High-reslution refers to Wtral analysis n-ethods that try to estimate a number of sinusoidal signals or scurces in mise. Very often, e have short data seqents, ad thus, use of conventid rrethcds lead to very lcw resolution estimations. If there is any &itid available infomticn of the press w ar~ analyzirg, it can be imlU3ed in the rnet3-d with the use of certain mdels of the process for improving the estimatim prfomces. Erbst of the part of such kid of akjorittmri are based on the Sirgular Value I>xcnpositim (S.V.D.) of the data aukcorrelation mtrix /3/, and thus with a hard canpltation cost. his effort is r&d in algxiths with a partial decarpa;ition, as for Pisarenko, in which mini" eigenvalue its carbid eigenvector are only necessary. This work was supported by CAICYT unrler grant number 21096/84. As an attraztive altemtive to these mthcds the Generalized PcxrRr Maxh Likeliw Metm /2/ can te used , as a consequence of the previous Normalized MaxM LikeliW Mew (N.M.L.M.) /2/. In such a way Blackmn-Tuckey, Maxi" LikeliW (or Capon), ad the N.M.L. Methcds wre irvsludd in the gereralized estimator as particular cases , and with the possibility for extending it to high-resolution diagrams. The same authrs intrduxd the idea far seeing these mthxk as a bank of filter spectral estimation approach, ard giving a unified pint of view. Unfortunately, this interpretation was not exteriled to the high-resolution alprithms. In the ncxt sections e will see hm it is also possible ta see that the Generalized €her M.L.M. is the "quem of usirg similar consideraticns, but m over pre-transfom-ed data. Tnis pre-prmessiq linear transfomtion will let us to generate adaptive schanes for irrproving resolution. 'ke irvslusion of linear tramsfonnations previcus to *tation de fall in crisis saw of the ideas used in the generation of adaptive gradient-based algorithms. To avoid these diffialties e will introkm a generalized cost function as djective to minimize, substitutirg the ccnventiml wan quare filtering errar fwticn by inner prducts of the coefficient error vector of the estimator filter. 2.-- Given a randan, stationary process x(n), the autcmmlaticn sequexe is defid as the secord order statistics: * r(m) = E(x(n+m) x (n)) (1) where, in general, the emtation is substituted Sy a certain estimaticn over the available data record. 'Re per spectnnn follcws fran the Fcurier Transform of the autcmrrelation function (1) : s(w) = r(m) exp(-jmw) (2) m If the pmss x(n) has been &grad& by additive mise, the vtndn will canp3nents due to signal, bt merlappd the antribtion of noise. under sorne ditions it is psible to -ate bth ampmenb. 763 ISCAS'88 CH2458-8/88/0000-0763$1 .OO 0 1988 IEEE If w definc the data vector X(n) as folla~.: X( n) = (x( n) , x(n-1) , . . ,x(n+l) ) intrdd by: (3) for a matrix order N, the autocorrelation matrix is R = E(X(n) ?(n)) (4) Tnis mtrix is as& to be Tceplitz, psitive definite and hermitian, thus, it is psible to decarpcse it in a dal way: R=QA# (5) where Q is the ort3m-m" eigenvector matrix ard A tine diagonal eigenvalue mtrix: Q= COl, Q2r*-*r Q" (€4 with a convenient order: Mer the= corditions it can be stablished a basic property of mtrix R (5), /l/. If the wtrix order N mreases, the eigenvalues agproazh, in saw SellSer the exact values of the spztnm S(wi) (2) for the frequency values wi = (2x/N)i, that is: lim Xi - S((Zx/N)i) N-CU (7) Fssuning that process x(n) has been gemrated by a carbination of M oolplex sinumirlsl signals of arbitrary slplibrdes and $ases in white mise oE man mr, the autocorre~ation matrix will present &c (N-M) least significant eigenvalws a11 qual to the value Amin: A,, = ... = AN = Amin 'PE study of rank for wtrix (EtAI) stablishes an hprtar-k decaqxxiticn for the space in the signal subspace gemratd ly t! M eigenvecbrs carbimd to the M mxt significant eigenvalues, and the mise Susspace that is gemrated by the The constraint that noise must be white may be relaxed and the results ramin unchangel if the dl dqiticn is mde in the mtric of fne autoaxrelation mtrix for the mise. miniq eigenvectors. 'his mition lets us a better description of the process, and the different s,pctral estimation mthxk differs in tnv the informtion is used to hild it, cbirq the noise or the signal eigenvalues ard eigenvectors. PS it is ell km, if the autammlation sequem is windowed, and the spectrum caput4 over a short Wnt of last expression (2) 14s to Blackmm-Tuckey estimator (ELT.), that exqt an scaling factor kecu~s: (9) II %(a) = s RS where vector S is defined by: S = (1, exp(-jo),.., exp(-j(N-l)o 1) (10) Tne ortkgcmlity of eigenvectors ensures that the f"cy response of the misc eigenvectors will present a rull respcnse to the fqemies of the pre sinusoids. 'his p-rty is specially inprtant in the developrent of high-resolution algorittns. Besides, the ortkgcnality of matrix Q lets us to express any pier of mtrix R in a sinple way: k kH R =QA Q Thus, for high values of k, the set of eigenvectors remains unchange.1 and only the eigenvalue spread is mghsized ,and thraqh an dequatd value of k it is possible to chcrose the signal (bo) or the mise subspa (k<O). Maxi" Likelihood Method is an example of an estimator built with mgative pe~ of the atxonrelation mtrix, ard the resolution is much better than for Blad"-Tbckey. ?he design ecpations are vel1 k". For a F.I.R. filter, ve that the per at the atput of the filter is mink. min P = min d' R w (12a) w Ow 'RI avoid the null solution, m can intrdum the linear ccnstrain that the attenuation of the filter for the rrz"?nt frequency is zero: #s=1 (125) Tne ming of this tim equations is that the filter is designed slch that the interferences due to frequemies different to the mamred one (or 'leakage') are minimized. ?he solution for this variatiml prcblem is given by: ad dtitutirq (13) in (1%) w &bin the pwer at the mwt of the filter: ?he value (14) it is not really a paer density estimator, because it "esgcds to a pr mure, ad it nust be mmlized by the bankidth of the filter. PLis mint sugested the Normalized M.L. Method, with a Rayleigh quotient structure. Fran the expression for the M.L.M. (141, Capon /1/ pm the followirq gewralized fanily estimators, where he intrabd a pmer functicn of the autonrrelatim wtrix: Sqp( a) = (SH Rq S)'lq (15) that leads to B.T.(9) far q=l and to M.L.M. for q-1. For the rest of q values, the relation (15) losscs the "J of spectnun estimator and bec-s a 'fwecy detectx' in the signal subspace €or qX or in the mise one €OL q<o. 764 with an autccorrelatim mtrix givm by: R = Tq E(X(n) g'(n)) T = ?H R T (24) Tne mtpt pwsr for the filter with coefficients (13) and for the transform3 data is expressed by: Po = I? B W (25) Let's suppxe that for a ranjom process and for any frquemy (2 , its per density function is given by s (0 &at frequency rem of the filter ie a& &irg for estimating it is W(OJ 1. % filter cutput power is obtained by the contributions f3r all the frequencies, that is: If the filter characterized by vector W is r" eqh, wi? can =roach (16) by: where B (12b) t%t W(cJo) = 1, thus: is the bardwidth of the filter, an3 w3 hpzssl xo Be Takirg the bardwidth of the ideal filter of equal cpladratic area for B w3 .get: 0 =wbw (19) Substituting (13) in (19), and then (19),(14) in (18) w obtain the N.M.L.M.: SH R-l S SH R-2 S b'WO' = -- (20) This result Suggestd the mr Generalized Maxi" Likelihd Method (Q.M.L.M. ) with the follcwirg family of expressions: SH Rq+' S SH Rq S S9,(Wo) = ~- (21) that supplies E!-T (9) far @, M.L.M. (14) for q=1 and N.M.L.M. (20) for q=2. "ne Rayleigh quotient structure for (21) ensures that for all q: splm(LJ) > sqm(uI) ; -tr q > 0 (22) an3 resolution inproves with value q. It is psible to develq (21) in a similar way than for N.M.L.M. ht with a previcus linear pre-transformtion of the data. For a general treatment, let's consider the transform3 data vector: Filter N.M.L.Y. for the new dab ~CQIES: B-l S SH B-l S W' = (26) and the bandwidth of Lk filter(l9) is given by the norm of (26). ktually, it is rot correct t3 strewthen that the Q.M.L.M.(21) is the ccnsequence of trmsfmnirq the data and then intrducing a certain estimator. It is used over the origiml data. Pen, the aitpt ,mr with crzfficient vector (26) can be expressed as: (27) H P = W' R W' Normlizing per (27) by the bardwidth (19) of the filter (26) we get the fiml estinwtor: It is Wsible to fid an &equate transfomtion T (23) such that: Y (29) R = T' RT = Rd2 Including (29) in (281, we obtain the Q.M.L.M. expression (21) for: T = R(q-')I2 (30) This development suggests the possibility of imludirq that kid of linear transfornations ((23) and (30)) in linear adaptive filterirg and prediction. Tne main consequence will be the generation of 11?w quadratic cbjectives for obtaining the daptive schs. In this section WE?. will study the influence of autccorrelatimimtriw-based linear transforms in Wdratic objectives. For a refereme sqle d(n) we try to estimate itwas a liM anbination of the transforred data samples X(n) (23): & x(n) (32) estimation error is given by: 765 and the man quare error (m.s.e.) for (33): ??E optirral mluticn that minimizes de error (34) tBXm?s: W =R (35) * -(k+l) Including (35) into (341, we get the minim matic man error: (36) that is k value indeprdent, ard thus, solution (35) lays on a constant error plane, and cmn to de Wiener solution. The m.s.e. can be expressed as an inner pdct oE the w.?ight error vecbr: E2k = (W - W*)H R2k+1 (w - $) + t2 min (37) * ere W demtes the optimal solution (35). W generalized this imr-prduct as follows: Tne interest of (38) is that the eigenvalue spread of the wighting mtrix is miifid by the value m, but the solution remains uncharged (35). Tne m.s.e. cbjective (37) is only a partialar casc of (38), that is, for m = 2k + 1. 5.- FILTERING AND W3IGHT-VECIDR EmR GRADIENT lPP" Tne sinplest scappnxhing tile solution is to m an initial guest W(0) for the coefficients in the direction of the gradient for the m.s.e. objective (37): Taking instantaneous expressions in (391, the sinplest filtering gradient estimate is the follcwirq: (40a) with the 'a priori' emr defiru3d by: e(n) = d(n) - #(n) ?(n) (40b) 'Re gradient actualization diagram is given by: w(n + 1) = w(n) + P e+(n) T(n) (41) that correspords to the ell knam L.M.S. algorithn. The mveqewe of the mttd is ensured in man for any 'step-size' such that: 'ke convergence time for the m.s.e.(39) is pmf to be: (43) Tmin = (hnru((2rmin)) 2k+l 'flus, for ill ditiored mtrix or for high values of k, the amvergeme tim cculd be inacceptable. Takiq into acccunt that the generalid cbjective (38) gives the saw optimdl wight vector, w.? can try to develop gradient diagrams from it. The generalized grdient is given by: (44) The rrPst attractiw case 14s for WO. In that cax, t'ae mttd exhibits a data irdeperdent performrxx, that is, withcut sensitivity to the eigenvalue spread as for the rest m values: W(n + 1) = W(n) + tl R -(k+l) e+(n) x(n) (45) 'his actualization alternative oo~espds to the classical R.L.S. mW, ard it is possible to give it an exact recursive-&$fyram. The main handicap is the carpltaticn of R that needs the use of tl-e mtrix inversion lemma for some topics as for instance in arrays, but can be optimized with fast versions for spctral estimation (Fast GJmn, FAEST, FIF) The tradeoff betseen performance and ccnplexity is obtained for a third case in (44). Takiq mk+l, the coefficients are updated by: w(n + 1) = w(n) +pe+(n) X(n) (46) Stability is ensured for: (47) o< P <1/(X, )k+l with a convergence tine much better that for L.M.S. (41)(43) an3 with the sari? cqlexity: %e paraneter mtirq in mive and mrecursive mthds will be analyced in further papers. 6.- /1/ V.F. P1SXENK.l. 'ch the Estimation of Spectra by &ans of N0n-Lir-e~ Functions of the Covariance Matrix'. Gea$ys. J.R. Astr. Soc. , Vol. 28, 1972, wq?.511-531. /2/ M.A. LpI;uNps FJT AL. 'An Inproved Maxi" Likelihoxl &W for Emer Spectral Bffiity Esthticn'. IEEE Trans. PSSP, Vol. ASP-32, No.1, Feb. 1984. /3/ R.O. SCBlItlT. 'mltiple Emitter kcation ad Sip1 Water Estimation'. Trans. ht"S md PTmaqaticns, Vol. AF34, No.3, March 1986. /4/ M.A. LAGUNAS. 'Power Functions in Spectral Estimticn'. To be p5lished in ICFSSP-88. New York, U.S.A. 766