7.3.1 RFF-KLMS

Assuming a sequentially arriving data set, $\{({\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n),y(n)),n=1,2,\dots \}$, the typical LMS algorithm models the desired output as $f(\mathbf{x})=\hat{y}={\mathit{\theta }}^T{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})$ and estimates θ, so that the MSE cost function, $\mathcal{L}({\mathbf{x}}_n,y(n),\mathit{\theta })=E\left[{(y(n)-{\mathit{\theta }}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n))}^2\right]$ is minimized. The minimization is carried out via a gradient descent rationale, where the gradient of the cost, is approximated by the current measurement, i.e.,

$\begin{array}{cc}\hfill {\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}({\mathbf{x}}_n,y(n),\mathit{\theta })& =-2E[y(n)-{\mathit{\theta }}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)]{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)\hfill \\ \hfill & \approx -2(y(n)-{\mathit{\theta }}^T{\mathbf{z}}_{\mathrm{\Omega }}({\mathbf{x}}_n)){\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n).\hfill \end{array}$

This method (RFF-KLMS) has been introduced independently in [9] and [10]. Algorithm 1 presents the steps in details. It is a matter of elementary algebra to see that after $n-1$ steps, the estimation of the solution will be ${\mathit{\theta }}_n=\mu {\sum }_{i=1}^{n-1}e(i){\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_i)$, which leads us to conclude that the RFF-KLMS scheme will produce, approximately, the same output as that of the standard KLMS (provided that D is sufficiently large):

$\hat{y}(n)=\mu \sum _{i=1}^{n-1}e(i){\mathbf{z}}_{\mathbf{\Omega }}{({\mathbf{x}}_i)}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)\approx \mu \sum _{i=1}^{n-1}e(i)\kappa ({\mathbf{x}}_i,{\mathbf{x}}_n),$

where for the last relation (which gives the output of the standard KLMS [7,4]) we used Theorem 1. The major difference is that the RFF-KLMS provides a single vector θ of fixed dimensions, instead of a growing expansion of kernel functions, hence no pruning mechanisms are required.

Working similar to the case of the standard LMS, we can study convergence properties of RFFKLMS. Henceforth, we will assume that the data pairs are generated by

$y(n)=\sum _{m=1}^M{\alpha }_m\kappa ({\mathbf{c}}_m,{\mathbf{x}}_n)+\eta (n),$

where ${\mathbf{c}}_1,\dots ,{\mathbf{c}}_M$ are fixed centers, ${\mathbf{x}}_n$ are zero-mean independent and identically distributed samples drawn from the Gaussian distribution with covariance matrix ${\sigma }_X^2{\mathbf{I}}_d$ and $\eta (n)$ are independent and identically distributed noise samples drawn from $\mathcal{N}(0,{\sigma }_{\eta }^2)$. We note that the parameters ${\sigma }_X$ and ${\sigma }_{\eta }$ are the variances of the input and the noise, respectively, and they are not in any way related to the kernel parameter σ. Applying the approximation rationale of Theorem 1, we obtain

$\kappa ({\mathbf{c}}_m,{\mathbf{x}}_n)=E_{\mathit{\omega },\mathit{b}}[z_{\mathit{\omega },\mathit{b}}({\mathbf{c}}_m)z_{\mathit{\omega },\mathit{b}}({\mathbf{x}}_n)]={\mathbf{z}}_{\mathbf{\Omega }}{({\mathbf{c}}_m)}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)+{ϵ}_m(n),$

where ${ϵ}_m(n)$ is the error between the actual value of the kernel function and the approximated one. Thus, if we define

${\mathbf{Z}}_{\mathbf{C}}=({\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{c}}_1),\dots ,{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{c}}_M)),\mathit{\alpha }={({\alpha }_1,\dots ,{\alpha }_M)}^T,{\mathit{\theta }}_o={\mathbf{Z}}_{\mathbf{\Omega }}\mathit{\alpha },$

we get

$y(n)={\mathit{\alpha }}^T{\mathbf{Z}}_{\mathbf{\Omega }}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)+ϵ(n)+\eta (n)={\mathit{\theta }}_o^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)+ϵ(n)+\eta (n),$

where $ϵ(n)$ stands for the approximation error between the noise-free component of $y(n)$ (evaluated only by the linear kernel expansion of Eq. (7.8)) and the approximation of this component using random Fourier features, i.e.,

$ϵ(n)=\sum _{m=1}^M{\alpha }_m\kappa ({\mathbf{c}}_m,{\mathbf{x}}_n)-{\mathit{\theta }}_o^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)=\sum _{m=1}^M{a}_m{ϵ}_m(n).$

Let $\mathbf{x}\in {\mathbb{R}}^d$, $y\in \mathbb{R}$, be the random variables that generate the measurements and ${\mathbf{R}}_{zz}=E[{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x}){\mathbf{z}}_{\mathbf{\Omega }}^T(\mathbf{x})]$ the corresponding autocorrelation matrix. We can prove that ${\mathbf{R}}_{zz}$ is positive definite, provided that all the random features are different from each other, i.e., ${\mathit{\omega }}_i\ne {\mathit{\omega }}_j$, for all $i\ne j$ [16]. Thus, the cross-correlation vector takes the form

$E[{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})y]=E[{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})({\mathbf{z}}_{\mathbf{\Omega }}{(\mathbf{x})}^T{\mathit{\theta }}_o+ϵ+\eta )]={\mathbf{R}}_{zz}{\mathit{\theta }}_o+E[{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})ϵ],$

where for the last relation we have used the fact that η is a zero-mean variable representing noise and that ${\mathbf{z}}_{\mathrm{\Omega }}(\mathbf{x})$ and η are independent. For large enough D, we can assume that the approximation error, ϵ, approaches 0 [14], hence the optimal solution becomes

${\mathit{\theta }}_{⁎}=E\left[{(y-{\mathbf{z}}_{\mathbf{\Omega }}{(\mathbf{x})}^T{\mathit{\theta }}_o)}^2\right]={\mathbf{R}}_{zz}^{-1}({\mathbf{R}}_{zz}{\mathit{\theta }}_o+E[{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})ϵ])={\mathit{\theta }}_o+{\mathbf{R}}_{zz}^{-1}E[{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})ϵ]\approx {\mathit{\theta }}_o.$

To summarize, the proposed rationale assumes that, for sufficiently large D, Eq. (7.8) can be closely approximated by $y(n)\approx {\mathit{\alpha }}^T{\mathbf{Z}}_{\mathbf{C}}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)+\eta (n)$. The major difference with the standard LMS case is that the transformed inputs, ${\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)$, can no longer be assumed to be generated by the Gaussian distribution. Applying similar assumptions as in the case of the standard LMS (e.g., independence between ${\mathbf{x}}_n,{\mathbf{x}}_m$, for $n\ne m$ and between ${\mathbf{x}}_n,\eta (n)$), we get several convergence properties, where the eigenvalues of the positive definite matrix ${\mathbf{R}}_{zz}$, i.e., $0<{\lambda }_1⩽{\lambda }_2⩽\cdots ⩽{\lambda }_D$, play a pivotal role:

7.3.2 RFF-KRLS

Contrary to the stochastic approach employed by the LMS, the RLS utilizes information of all past data to estimate θ by minimizing the regularized risk cost function, i.e.,

$\mathcal{L}({\mathbf{x}}_n,y(n),\mathit{\theta })=\sum _{k=1}^n{\beta }^{n-k}{(y(n)-{\mathit{\theta }}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n))}^2+\lambda {\beta }^n{\Vert \mathit{\theta }\Vert }^2,$

for some chosen $\lambda >0$, where β is a weighting factor that is usually added as a forgetting mechanism and which makes the algorithm more sensitive to recent data. Solving ${\mathit{\theta }}_{⁎}={\min }_{\mathit{\theta }}\mathcal{L}({\mathbf{x}}_n,y(n),\mathit{\theta })$ requires the inversion of an $n\times n$ matrix at each step. However, employing the matrix inversion lemma, it is possible to compute this solution recursively. Algorithm 2 presents the details. The procedure is identical to that of the standard RLS, except that we replace ${\mathbf{x}}_n$ with the transformed data ${\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n)$. Moreover, we should note that, unlike the LMS case, the proposed scheme provides a solution that is different from other implementations of KRLS (like the ones presented in [6] and [4]). Although all KRLS-like implementations, provided in the respective literature, estimate the system's output as a linear expansion of kernel functions centered at the past data, the estimation of the expansion's coefficients differs in the case presented here.

7.3.3 RFF-PEGASOS

The methods presented in Sections 7.3.1 and 7.3.2 are suitable for online regression problems. In this section, we present an online classification method based on the PEGASOS scheme (see [17]). Consider a training set of the form $\{({\mathbf{x}}_n,y(n)),n=1,2,\dots N\}$, where ${\mathbf{x}}_n\in {\mathbb{R}}^d$ and $y(n)=\pm 1$. PEGASOS is an SVM-like algorithm that processes the data sequentially as follows. On iteration t, the algorithm selects a random training example $({\mathbf{x}}_{n_t},y(n_t))$ by picking an index $n_t$ uniformly at random from $\{1,2,\dots ,N\}$. The scheme follows a stochastic gradient rationale, adopting the regularized hinge loss function, i.e.,

${\mathit{\theta }}_{⁎}=\max \{0,1-y{\langle f,\mathrm{\Phi }(\mathbf{x})\rangle }_{\mathbb{H}}\}+\frac{\lambda }{2}{\Vert f\Vert }_{\mathbb{H}}^2,$

where $\mathbb{H}$ is the RKHS associated with a preselected kernel κ and Φ the respective feature map. Thus, the step update equation becomes:

$f_t=(1-\frac{1}{t})f_{t-1}+{\mathbb{1}}_{+}(1-y(n_t){\langle f_{t-1},\mathrm{\Phi }({\mathbf{x}}_{n_t})\rangle }_{\mathbb{H}})\frac{y_{n_t}}{\lambda t}\mathrm{\Phi }({\mathbf{x}}_{n_t}).$

After a predetermined number of iterations (say T), the algorithm provides the solution, which is given as a sparse linear expansion of kernel functions, similar to Eq. (7.1). The algorithm is implemented by keeping in memory an N-size vector that comprises all the coefficients of the expansion. During each iteration, at most one of these coefficients might change. The performance of the scheme has been shown to improve with data reuse, i.e., when the same data are used again and again for training.

Evidently, since the solution provided by the algorithm depends on the dataset's size, PEGASOS cannot be considered as an online scheme (where the actual size of the dataset is not known beforehand). However, employing the random Fourier features rationale, we can model the output as $f(\mathbf{x})={\mathit{\theta }}^T{\mathbf{z}}_{\mathbf{\Omega }}(\mathbf{x})$, where $\mathit{\theta }\in {\mathbb{R}}^D$, and thus rewrite the step update equation as follows (see Algorithm 3):

${\mathit{\theta }}_n=(1-\frac{1}{n}){\mathit{\theta }}_{n-1}+{\mathbb{1}}_{+}(1-y(n){\mathit{\theta }}_{n-1}^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n))\frac{y(n)}{\lambda n}{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n),$

where we have assumed that the data arrive sequentially. Similar to the LMS case, the proposed algorithm can be seen as a linear PEGASOS on the dataset $\{({\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_n),y(n)),n=1,2,\dots \}$, hence all convergence properties of [17] hold in this case too. We will call this scheme RFF-PEGASOS.

We should note that the proposed algorithm features several significant advantages with respect to the original form of kernel PEGASOS presented in [17]. Firstly, the complexity per iteration is $\mathcal{O}(Dd)$ and does not depend on the training database size, in contrast with the kernel-PEGASOS, which has complexity $\mathcal{O}(Md)$, M being the number of the support vectors. Moreover, RFF-PEGASOS solves the problem of the growing sum and thus it can work in a truly online fashion (where the dataset is not known beforehand), while kernel-PEGASOS was designed for batch processing (i.e., fixed datasets). Finally, it is evident that for datasets with many support vectors (where $M>>D$) RFF-PEGASOS is significantly faster. However, in databases with a low number of support vectors ($M<<D$), it runs slower.

7.3.4 Simulations—Regression

In this section, we provide some simple simulations, which are indicative of the behavior of the proposed algorithms, compared to their typical implementations. For the regression case, we generate 5000 data pairs using the following model: $y(n)={\sum }_{m=1}^M{a}_m\kappa ({\mathbf{c}}_m,{\mathbf{x}}_n)+\eta (n)$, where ${\mathbf{x}}_n\in {\mathbb{R}}^5$ are drawn from $\mathcal{N}(\mathbf{0},{\mathbf{I}}_5)$ and the noise are independent and identically distributed Gaussian samples with ${\sigma }_{\eta }=0.1$. The parameters of the expansion (i.e., $a_1,\dots ,a_M$) are drawn from $\mathcal{N}(0,25)$ and the kernel parameter σ is set to 5. The specific parameters of the algorithms are shown in Table 7.1. We compare RFF-KLMS and RFF-KRLS with a standard implementation of KLMS using the quantization pruning technique and the KRLS version of [6]. Fig. 7.1 shows the evolution of the MSE for 100 realizations of the experiment for several values of D (i.e., the total number of random Fourier features used), where the number of the free parameters of the model is set to $M=100$. As this is a kernel approximation scheme, it is expected that the performance (in terms of MSE) would be somewhat reduced. However, we can see in Fig. 7.1 that the performance of both RFF-KLMS and RFF-KRLS is very close to their typical implementations. In this particular example, both algorithms can achieve similar performance with their standard counterparts earlier in time (see Table 7.2 and Figs. 7.1B, 7.1D for the KLMS and KRLS, respectively). Fig. 7.2 shows the evolution of the MSE for the same experiment using $M=400$ parameters in the design model. In this case, it is evident that a larger number of Fourier features is required to achieve the same approximation quality. For example, the RFF-KRLS requires more than $D=200$ random features and the RFF-KLMS requires $D=2000$ features to achieve approximately the same steady-state MSE as their typical variants. To conclude:

Table 7.2

Mean times needed for the KLMS and KRLS on a typical core i5 machine for M = 100 and M = 400

	$M=100$				$M=400$
	D = 100	D = 200	D = 500	D = 1000	D = 100	D = 200	D = 1000	D = 2000
RFF-KLMS	0.03 s	0.07 s	0.14 s	0.25 s	0.03 s	0.06 s	0.26 s	0.41 s
QKLMS	0.27 s	0.27 s	0.27 s	0.27 s	0.27 s	0.27 s	0.27 s	0.27 s
RFF-KRLS	0.35 s	1.00 s	11.5 s	58.2 s	0.39 s	1.0 s	53.2 s	140.2 s
KRLS	3.03 s	3.2 s	3.2 s	3.2 s	3.2 s	3.2 s	3.2 s	3.2

7.3.5 Simulations—Classification

For the classification case, we have performed two sets of experiments. In the first set, we have compared the performances of the standard kernel-PEGASOS and the RFF-PEGASOS on four datasets downloaded from Leon Bottou's LASVM web page [18]. The chosen datasets are (a) the Adult dataset, (b) the Banana dataset (where we have used the first 4000 points as training data and the remaining 1300 as testing data), (c) the Waveform dataset (where we have used the first 4000 points as training data and the remaining 1000 as testing data) and (d) the MNIST dataset (for the task of classifying the digit 8 versus the rest). The sizes of the datasets are given in Table 7.4. Table 7.5 reports the test errors for each dataset and each method, along with the total number of support vectors after training (only for the kernel-PEGASOS) and the respective time in seconds (in parentheses). The experiments were performed on an i7-3770 machine using a MatLab implementation. The parameters used in each method are reported in Table 7.3. The parameters were selected after extensive trials to give the best possible accuracy. The parentheses (after the title of the method) indicate the number of times the algorithm passed through the entire dataset. As expected from the theoretical analysis of the corresponding complexities, for datasets with a large number of support vectors (such as Adult and Banana), RFF-PEGASOS requires significantly less time than its standard implementation. For datasets with a medium number of SVs (such as Waveform), this difference is diminishing, while for datasets with very few SVs (e.g., MNIST) kernel-PEGASOS can be significantly faster. We note that, for the MNIST database, RFF-PEGASOS attains a 0.47% test error percentage after 20 reruns (19000 s).

Table 7.3

Parameters for each classification method

Method	Adult	Banana	Waveform	MNIST
Kernel-PEGASOS	$\begin{array}{c}\hfill \sigma =\sqrt{10}\hfill \\ \hfill \lambda =0.0000307\hfill \end{array}$	$\begin{array}{c}\hfill \sigma =0.7\hfill \\ \hfill \lambda =\frac{1}{316}\hfill \end{array}$	$\begin{array}{c}\hfill \sigma =\sqrt{10}\hfill \\ \hfill \lambda =0.001\hfill \end{array}$	$\begin{array}{c}\hfill \sigma =4\hfill \\ \hfill \lambda ={10}^{-7}\hfill \end{array}$
RFF-PEGASOS	$\begin{array}{c}\hfill \sigma =\sqrt{10}\hfill \\ \hfill \lambda =0.0000307\hfill \\ \hfill D=2000\hfill \end{array}$	$\begin{array}{c}\hfill \sigma =0.7\hfill \\ \hfill \lambda =\frac{1}{316}\hfill \\ \hfill D=200\hfill \end{array}$	$\begin{array}{c}\hfill \sigma =\sqrt{10}\hfill \\ \hfill \lambda =0.001\hfill \\ \hfill D=2000\hfill \end{array}$	$\begin{array}{c}\hfill \sigma =4\hfill \\ \hfill \lambda ={10}^{-7}\hfill \\ \hfill D=100000\hfill \end{array}$

In the second set of experiments we tested the performance of RFF-PEGASOS and compared it with that of the LA-SVM [19]. LA-SVM is one of the most elegant and fast SVM training implementations. In order to compare running times we used a C implementation of the respective algorithms (as the C implementation of LA-SVM is publicly available on the web). The experiments were performed on an i5 650 machine running at 3.20 GHz with 6 Gb of RAM. The parameters for LA-SVM (shown in Table 7.3) have been taken from [19]. The results are shown in Table 7.6. Once more, we observe that for datasets with a large number of support vectors RFF-PEGASOS is faster. This is not the case however for datasets with a lower number of support vectors, where RFF-PEGASOS can be significantly slower.

7.4.1 Diffusion KLMS

Adopting the mean square error in place of $\mathcal{L}$ and estimating the gradient by its current measurement, the Random Fourier Features Diffusion KLMS (RFF-DKLMS) results, where Eq. (7.12) can be recast as

${\mathit{\theta }}_{k,n}={\mathit{\psi }}_{k,n-1}+\mu {\epsilon }_k(n){\mathbf{z}}_{\mathrm{\Omega }}({\mathbf{x}}_{k,n}),$

where ${\epsilon }_k(n)=y_n-{\mathit{\psi }}_{k,n-1}^T{\mathbf{z}}_{\mathrm{\Omega }}({\mathbf{x}}_{k,n})$. Algorithm 4 describes the proposed method in detail.

Under certain general conditions, we can establish consensus (i.e., that all nodes converge to the same solution), [16], following the results of the standard Diffusion LMS (e.g., [24,25]). To this end, we will assume that the data pairs are generated by

$y_k(n)=\sum _{m=1}^M{\alpha }_m\kappa ({\mathbf{c}}_m,{\mathbf{x}}_{k,n})+{\eta }_k(n),$

where ${\mathbf{c}}_1,\dots ,{\mathbf{c}}_M$ are fixed centers, ${\mathbf{x}}_{k,n}$ are zero-mean i.i.d, samples drawn from the Gaussian distribution with covariance matrix ${\sigma }_X^2{\mathbf{I}}_d$ and ${\eta }_k(n)$ are independent and identically distributed noise samples drawn from $\mathcal{N}(0,{\sigma }_{\eta }^2)$. Hence, we have

$\begin{array}{cc}\hfill y_k(n)& =\sum _{m=1}^M{\alpha }_m{E}_{\mathit{\omega },\mathit{b}}[z_{\mathit{\omega },\mathit{b}}({\mathbf{c}}_m)z_{\mathit{\omega },\mathit{b}}({\mathbf{x}}_{k,n})]+{\eta }_k(n)\hfill \\ \hfill & \approx {\mathit{\alpha }}^T{\mathbf{Z}}_{\mathbf{\Omega }}^T{\mathbf{z}}_{\mathrm{\Omega }}({\mathbf{x}}_{k,n})+{ϵ}_k(n)+{\eta }_k(n)\hfill \\ \hfill & ={\mathit{\theta }}_o^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_{k,n})+{ϵ}_k(n)+{\eta }_k(n),\hfill \end{array}$

where ${\mathbf{Z}}_{\mathbf{\Omega }}=({\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{c}}_1),\dots ,{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{c}}_M))$, $\mathit{\alpha }={({\alpha }_1,\dots ,{\alpha }_M)}^T$, ${\mathit{\theta }}_o={\mathbf{Z}}_{\mathbf{\Omega }}\mathit{\alpha }$ and ${ϵ}_k(n)$ is the approximation error between the noise-free component of $y_k(n)$ (evaluated only by the linear kernel expansion of Eq. (7.16)) and the approximation of this component using random Fourier features, i.e., ${ϵ}_k(n)={\sum }_{m=1}^M{\alpha }_m\kappa ({\mathbf{c}}_m,{\mathbf{x}}_{k,n})-{\mathit{\theta }}_o^T{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_{k,n})$. Using block-matrices we can derive the following, more compact, formulation for the entire network:

${\underset{\_}{\mathbf{y}}}_n={\underset{\_}{\mathit{V}}}_n^T{\underset{\_}{\mathit{\theta }}}_o+{\underset{\_}{\mathit{ϵ}}}_n+{\underset{\_}{\mathit{\eta }}}_n,$

where

Let ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_K\in {\mathbb{R}}^d$, $\underset{\_}{\mathbf{y}}\in {\mathbb{R}}^K$, be the random variables that generate the measurements of the nodes and

$\underset{\_}{\mathit{V}}=\mathrm{diag}({\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_1),{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_2),\dots ,{\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_K))$

be the $DK\times K$ matrix that collects the transformed random variables for the whole network. Moreover, let $\underset{\_}{\mathbf{R}}=E[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]$ be the $DK\times DK$ respective autocorrelation matrix. It is not difficult to see that $\underset{\_}{\mathbf{R}}$ can be given in a block form as $\underset{\_}{\mathbf{R}}=E[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]=\mathrm{diag}({\mathbf{R}}_{zz},{\mathbf{R}}_{zz}\dots ,{\mathbf{R}}_{zz})$, where ${\mathbf{R}}_{zz}=E[{\mathbf{z}}_{\mathrm{\Omega }}({\mathbf{x}}_k){\mathbf{z}}_{\mathrm{\Omega }}{({\mathbf{x}}_k)}^T]$, for all $k=1,2,\dots ,K$. We can prove that, under certain general conditions, the autocorrelation matrix R is invertible (see [16] for the proof).

Moreover, as ${\mathbf{R}}_{zz}$ is positive definite (this has been also discussed in Section 7.4.1), the respective eigenvalues satisfy $0<{\lambda }_1⩽{\lambda }_2⩽\cdots ⩽{\lambda }_D$. In this case, the optimal solution is given by

$\begin{array}{cc}\hfill {\underset{\_}{\mathit{\theta }}}_{⁎}& ={\mathrm{argmin}}_{\underset{\_}{\mathit{\theta }}}E[{\Vert \underset{\_}{\mathbf{y}}-{\underset{\_}{\mathit{V}}}^T\underset{\_}{\mathit{\theta }}\Vert }^2]\hfill \\ \hfill & =E{[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]}^{-1}E[\underset{\_}{\mathit{V}}\underset{\_}{\mathbf{y}}]\hfill \\ \hfill & =E{[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]}^{-1}(E[\underset{\_}{\mathit{V}}({\underset{\_}{\mathit{V}}}^T{\underset{\_}{\mathit{\theta }}}_o+\underset{\_}{\mathit{ϵ}}+\underset{\_}{\mathit{\eta }})])\hfill \\ \hfill & =E{[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]}^{-1}(E[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]{\underset{\_}{\mathit{\theta }}}_o+E[\underset{\_}{\mathit{V}}\underset{\_}{\mathit{ϵ}}]+E[\underset{\_}{\mathit{V}}\underset{\_}{\mathit{\eta }}])\hfill \\ \hfill & =E{[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]}^{-1}(E[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]{\underset{\_}{\mathit{\theta }}}_o+E[\underset{\_}{\mathit{V}}\underset{\_}{\mathit{ϵ}}]),\hfill \end{array}$

where for the last relation we have used the notion that η is a zero mean vector representing noise and that $\underset{\_}{\mathit{V}}$ and $\underset{\_}{\mathit{\eta }}$ are independent. For large enough D, the approximation error vector $\underset{\_}{\mathit{ϵ}}$ approaches ${\mathbf{0}}_K$, hence the optimal solution becomes

${\underset{\_}{\mathit{\theta }}}_{⁎}={\underset{\_}{\mathit{\theta }}}_o+E{[\underset{\_}{\mathit{V}}{\underset{\_}{\mathit{V}}}^T]}^{-1}E[\underset{\_}{\mathit{V}}\underset{\_}{\mathit{ϵ}}]\approx {\underset{\_}{\mathit{\theta }}}_o.$

Since we work under the assumption that $\underset{\_}{\mathit{ϵ}}$ approaches ${\mathbf{0}}_K$, we can say that Eq. (7.17) can be closely approximated by ${\underset{\_}{\mathbf{y}}}_n\approx {\underset{\_}{\mathit{V}}}_n{\underset{\_}{\mathit{\theta }}}_o+{\underset{\_}{\mathit{\eta }}}_n$. This actually means that the RFF-DKLMS is nothing more than the standard diffusion LMS applied to the data pairs $\{({\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_{k,n}),y_k(n),k=1,\dots ,K,n=1,2\dots \}$. However, the difference is that the input vectors ${\mathbf{z}}_{\mathbf{\Omega }}({\mathbf{x}}_{k,n})$ may have nonzero mean and do not follow, necessarily, the Gaussian distribution. In fact we can prove that, if ${\mathbf{x}}_{k,n}\sim \mathcal{N}(\mathbf{0},{\sigma }_X{\mathbf{I}}_d)$, then the entries of ${\mathbf{R}}_{zz}$ can be evaluated as

$\begin{array}{cc}\hfill r_{i,j}=& \frac{1}{2}\exp \left(\frac{-{\Vert {\mathit{\omega }}_i-{\mathit{\omega }}_j\Vert }^2{\sigma }_X^2}{2}\right)\cos (b_i-b_j)\hfill \\ \hfill & +\frac{1}{2}\exp \left(\frac{-{\Vert {\mathit{\omega }}_i+{\mathit{\omega }}_j\Vert }^2{\sigma }_X^2}{2}\right)\cos (b_i+b_j).\hfill \end{array}$

Consequently, the available results regarding convergence and stability of diffusion LMS (e.g., [24,26]) cannot be applied here directly, as in these works the inputs are assumed to be zero mean Gaussian (to simplify the formulas related to stability). However, it is possible to end up with similar conclusions (the proofs are given in [16]).