Abstract
Abstract-The design of adaptive nonlinear filters has sparked a great interest in the machine learning community. The present paper aims to present some recent developments in nonlinear adaptive filtering. We present an in-depth analysis of the per formance and complexity of a class of kernel filters based on the recursive least-squares algorithm. A key feature that underlies kernel algorithms is that they map the data in a high dimensional feature space where linear filtering is performed. The arithmetic operations are carried out in the initial space via evaluation of inner products between pairs of input patterns called kernels. We evaluated the SNR improvement and the convergence speed of kernel-based recursive least-squares filters on two types of applications: time series prediction and cardiac artifacts extraction from magnetoencephalographic data.
I. INTRODUCTION
Linear filters have played a crucial role in the development of various signal processing techniques. The obvious advantage of linear filters is their inherent simplicity. Design and analysis of such filters are relatively straightforward tasks in many applications. However, there are many practical situations that require nonlinear processing of the signals involved. A great deal of research effort was expended on the development of nonlinear filters. Unlike linear filters which are characterized by their impulse response, there exists a whole variety of system representations for nonlinear filters. Two models have prevailed in the literature. Polynomial filters [1] and neural networks [2] . Polynomial filters can model a large class of nonlinear systems. They are attractive because their output is expressed as a weighted linear sum of monomial functions of the input patterns which simplifies the filter design. However, their primary disadvantage is their computational complexity that explodes exponentially as their modeling capacity in creases. Neural networks provide powerful tools for solving general nonlinear filtering problems. They are endowed with the universal approximation property [2] in the sense that they can approximate any continuous multivariate function to any degree of accuracy, provided that sufficiently many hidden neurons are available. However, they are hindered by their nonconvex optimization nature and the risk of being stuck in local minima.
I. INTRODUCTION
Kernel algorithms, based on the theory of reproducing ker nel Hilbert spaces (RKHS), represent an emerging technology rooted in many fields such as classification, regression and Adaptive kernel filters, based on the recursive least-squares (RLS) and least-mean-squares (LMS) algorithms have also been designed [4] , [5] . Optimum and adaptive filters have shown outstanding performances in many applications. In essence, kernel algorithms map the data in a high-dimensional feature space where linear algorithms are applied. The arith metic operations are carried out in the initial space via evalu ation of inner products between pairs of input patterns called kernels. The main problem that arises in kernel methods is their linear growing structure with each new sample, which enforces the need for sparsification techniques. Sparsification aims at discarding training samples that do not affect model performance. Several sparsification techniques have been de veloped to curtail the growth of kernel models including the approximate linear dependency [4] , the novelty criterion [5] and the surprise criterion [5] . A kernel adaptive filter embodies a two-step process: a sparsification step that removes undesired training data and a parameter update step.
I. INTRODUCTION
The present paper discusses algorithm design, performance, and complexity issues associated with kernel recursive least squares algorithms. It is organized as follows. In section II, we introduce the theoretical concepts of optimal filtering in RKHS. In section III, we describe the kernel-based RLS algorithms in fair details and analyze their complexity. Finally, experiments involving both synthetic and real data are reported in section IV. Some concluding remarks are given in section V.
II. PRINCIPLES OF KERNEL-BASED OPTIM AL FILTERING IN RKHS
A. Background
II. PRINCIPLES OF KERNEL-BASED OPTIM AL FILTERING IN RKHS
Let 1l be a reproducing kernel Hilbert space of real valued functions 'IjJ ( .) on a compact set X c IR?, and let < . , . >1{ denote the dot product defined on 1l. As the Riesz representation theorem states, there is a unique function ",( . , y) of 1l which verifies the following reproducing property [6] 'IjJ ( y) = <'IjJ,"'(·,Y»1{, \/'IjJ E 1l,
II. PRINCIPLES OF KERNEL-BASED OPTIM AL FILTERING IN RKHS
for every y E X. The function "'(-, y) is referred to as reproducing kernel. Note that 1l can be restricted to the span {",(., y) : y E X} because according to (1) nothing outside this set affects 'IjJ ( .) evaluated at any point of X. Replacing
II. PRINCIPLES OF KERNEL-BASED OPTIM AL FILTERING IN RKHS
Denoting by r.p the map that assigns to each input y the kernel function �(" y), (2) 
II. PRINCIPLES OF KERNEL-BASED OPTIM AL FILTERING IN RKHS
The kernel � then evaluates the dot product of every pair of elements of X mapped into 1i, without any explicit knowledge of either ip or 1i. The basic concept of kernel methods is to nonlinearly map the input data into a feature space and then apply conventional linear techniques. Although the feature space may be of high or even infinite dimension, inner products can be computed by using kernel functions. Thus any linear algorithm that can be expressed only in terms of dot products can be extended to nonlinear processing by replacing each dot product by a kernel. This idea, known as the kernel trick, is the backbone of kernel methods. Classical examples of kernels are the radial Gaussian kernel �(x, y) = exp ( -llx -y I12/ 2 p'2), with p' > 0 and the polynomial kernel �(x, y) = (a+ < X , Y »q with a :;0. 0 and q E IN*. A sufficient condition to ensure that a function is a valid kernel is that it should be positive definite [5] .
B. Optimal filtering in RKHS
Let 1i be a RKHS defined by a kernel � . The regularized least-squares problem in 1i consists in finding a function 1/;(.) minimizing the empirical risk
B. Optimal filtering in RKHS
where {Xi, ddi =1 is a given set of n input samples and their corresponding desired responses. The regularization parameter A has been added in order to prevent data overfitting. By virtue of the representer theorem [7] , the function 'ljJ(.) of 1i minimizing (3) admits a representation of the form n 1/;(.) = L aj �(., Xj). j =1
B. Optimal filtering in RKHS
Combining (3) and (4), the problem can be formulated as
B. Optimal filtering in RKHS
a where K is the Gram matrix whose (i, j)th entry is �(Xi' Xj). The solution vector 0: is determined by 0: = (K + AI) -l d.
III. KERNEL-BASED ADAPTIVE RLS FILTERING
The main concern that arises in kernel adaptive filtering is how to restrain the growth of the model (4) as new data is collected. An adaptive kernel algorithm involves two procedures: sparsification and filter parameters update.
A. Sparsification
The aim of sparsification is to produce a reduced order model of the form I jJ n(.) = L an,j �(.,Cj), j =1 (6) at any time step n, where the centers Cj are picked from the input samples. The set Cn = {Cj} j;\ is referred to as dictionary and mn is the cardinality. An efficient method to construct a sparse dictionary is to test the approximate linear dependency (ALD) condition [4] :
A. Sparsification
a CjEC'/I.-l where l/ is a preset threshold that determines the level of sparsity of the model. If the ALD condition is satisfied then Xn is not inserted in the dictionary and Cn = Cn-1. Otherwise, the dictionary is expanded with Xn, i.e. Cn = Cn-1 U {xn} and mn = mn-l + 1. By straightforward calculus, the solution of problem (7) is given by an = G;;� 1 hn, 5n = �(xn, xn) -h�an,
A. Sparsification
where Gn-1 is the Gram matrix defined on Cn-1 as [ Gn-1]i,j = �(Ci,Cj), i,j = 1 , ... ,mn-l and hn [ �(xn' Cl)"' " �(xn' cmn_1W. We mainly identify two types of kernel-based RLS algorithm: the regularized kernel re cursive least-squares (RKRLS) proposed by Liu et al. [5] totally discards the training data that were not admitted in the dictionary, whereas the original KRLS [4] uses the redundant samples in the adaptation of the parameters.
B. RKRLS
Consider the regularized least-squares problem (5). In RKRLS, the solution is determined using only the data selected as centers. It is expressed as a kernel expansion in terms of the centers Cj (6) , where the parameters an,j are determined by solving min a II dn -Gno: 11 2 +Ao:tGno:. This system is similar to (5), wherein the matrix K is replaced by Gn. The solution is given by (9) A recursive formulation for O:n appropriate for adap tive filtering can be derived. We notice that Gn
xn)
. ts mverse can e compute recursIvely using the block matrix inversion lemma [5] 
xn)
The quantities an and 5n are computed in the ALD test. Substituting (10) into (9) where e n = dn -h� O:n-l is the prediction error. In terms of computational complexity, the matrix inversion (10) is performed with O(m2) and the parameter update equation (11) with O(m) operations. The overall computational complexity of the RKRLS algorithm is O(m2).
C. KRLS
KRLS solves the least-squares problem min II dn -Kno: 11 2, a
C. KRLS
where K n is defined by [ K n]i,j = �(Xi' Xj), i, j = 1 , ... , n.
C. KRLS
The regularization parameter A is set to O. An approximation for K n can be derived, based on the ALD test. For every element Xi, we have 
IS Imp les
. (18) Substituting (10) and (18) which is identical to (11).
IS Imp les
[n the first case, the computation of Pn (16) and (3n (17) is achieved with O(m2) operations. In the second case, Pn requires O(m2) and (3n O(m) operations. The computational complexity in both cases is O(m2).
D. Comparison between RKRLS and KRLS
The main difference between RKRLS and KRLS resides in their processing of redundant data. In RKRLS, only the centers are involved in the determination of the filter parameters. The other samples are excluded. This enables any sparsification procedure to be applied with RKRLS. However redundant samples, even they induce additional computational cost, may bear useful information in the parameter update process. We shall see in the experimental section that the size of the kernel expansion in KRLS is significantly lower than RKRLS. It never exeeds a few tens, thereby rendering the use of the regularization parameter unnecessary. This result may be attributed to the use of all the training data in the derivation of the KRLS solution.
IV. EXPERIMENTS
Experiments were conducted on simulated and real data to assess the performance of the proposed methods. The Gaussian kernel was considered in all the experiments. For the purpose of comparison with stochastic gradient algorithms, a state-of the-art kernel-based LMS algorithm, the quantized kernel least mean-squares (QKLMS) [8] , was also tested. QKLMS adopts a quantization technique to curb the model growth. It aims to quantize and hence compress the input (or feature space). QKLMS exploits data quantization in order to perform a local update of the coefficients i.e., update only the coefficient of the closest center, using stochastic gradient descent. Its computational complexity is O(m) per iteration.
A. Experiments on simulated data
We consider first the problem of predicting the highly nonlinear time series [9] 
A. Experiments on simulated data
The data were generated by iterating the above equation from the initial conditions (0.1,0.1). Output dn was corrupted by an additive zero-mean white Gaussian noise with variance 172.
A. Experiments on simulated data
We considered different realizations of the noise as depicted in table 1. We chose the time embedding as 2, i.e, Xn = [ Xn-2 Xn-1r was used as the input to predict Xn. A test set of 100 sequences of 1000 samples was constituted and the performance of the algorithms was measured in steady state by evaluating the normalized mean square error (NMSE) over the last 200 samples of each sequence, namely
A. Experiments on simulated data
where 17 d is the variance of the desired output in the selected interval. The optimum parameters setting was determined by performing a fine grid search over a supplied parameter ranges. 25 sequences of 1000 samples were generated and the average NMSE was computed on the last 200 samples. The parameters that entailed the minimum error were selected. Table [ reports the average NMSE and the average dictionary size on the test set for different noise variances 172. We observe that RKRLS and KRLS exhibit comparable performances, with a slight advantage for RKRLS. They outperformed QKLMS. RKRLS requires significantly higher number of centers than KRLS and QKLMS, as might be expected, since RKRLS removes totally the redundant training data. A significant amount of input samples were admitted in the dictionary because they are needed for the adjustment of the filter parameters. The tradeoff between complexity and convergence speed is well known in linear adaptive filtering. It is expected that this tradeoff would persist with their kernel-based counterparts. This is confirmed by Fig. 1 that depicts the learning curves for (}2 = 0.01. RKRLS and KRLS, whose complexity is an order of magnitude higher than QKLMS, converge faster than QKLMS, requiring about 500 iterations to converge.
B. Magnetoencephalographic signal denoising
We applied RKRLS, KRLS and QKLMS on magnetoen caphalographic (MEG) data corrupted by cardiac artifacts. The recorded electocardiographic (ECG) signal was used as the reference signal. The MEG signal was used as the desired output so the residue is the denoised MEG signal. As a measure of performance, we used NMSE. The optimum parameters were selected by cross-validation as previously by conducting a grid search over all admissible values to find the best setting. RKRLS, KRLS and QKLMS were tested on 10 independent sequences of 8000 samples and NMSE was computed on the last 4000 samples of each sequence. Table II summarizes the results, averaged over the 10 independent trials. RKRLS presents a small advantage over KRLS and QKLMS. However, in terms of sparsity, KRLS and QKLMS produced a much sparser model than RKRLS. Fig. 2 presents KRLS results for one trial, where the dimension of the input vector p = 8, the kernel parameter f3 = 0.055 and the threshold v = 0.7. The highest two curves show the contaminated and denoised MEG signals. Curves Cl and C2 show the ECG reference channel and the estimated artifact signal.
V. CONCLUSION
In this paper, we investigated the performance of ker nel RLS methods RKRLS and KRLS. A comparison with 

{'paper_id': '1201328', 'title': 'Performance analysis of kernel adaptive filters based on RLS algorithm', 's2_url': 'https://api.semanticscholar.org/CorpusID:1201328', 'source': 'S2ORC'}