# A Kernel Least Mean Square Algorithm Based on Randomized Feature Networks
## 2 The KLMS Algorithm Based on Random Fourier Features
### The Random Fourier Feature Mapping  
The randomized feature mapping method was proposed by [PERSON] and [PERSON] [18; 19] and has been widely used in classification applications [21; 23]. The input samples can be mapped into a randomized Fourier feature space, in which the inner product of any two transformed vectors is equivalent to a shift-invariant kernel (such as Gaussian kernel) operation. Assume that there exists a feature map \(\varphi(\mathbf{x}):R^{m}\to R^{M}\) such that the inner product between a pair of transformed points approximates their kernel evaluation:  
\[K(\mathbf{x},\mathbf{x}^{\prime})=<\Phi(\mathbf{x}),\Phi(\mathbf{x}^{\prime})>\approx\varphi( \mathbf{x})^{T}\varphi(\mathbf{x}^{\prime}) \tag{7}\]  
To construct the feature space, where the inner product of the randomized features can uniformly approximate the shift-invariant kernel \(K(\mathbf{x}-\mathbf{x}^{\prime})\), the inverse Fourier transform \(p(\mathbf{w})\) of the well-scaled shift-invariant kernel is assumed to be a proper probability distribution, which can be ensured by [PERSON]'s theorem [24]. In addition, defining \(\xi_{w}(\mathbf{x})=e^{i\mathbf{w}^{T}\mathbf{x}}\), the following formula can be obtained:  
\[K(\mathbf{x}-\mathbf{x}^{\prime})=\int_{\mathbb{R}_{d}}p(\mathbf{w})e^{i\mathbf{w}^{T}(\mathbf{x} -\mathbf{x}^{\prime})}dw=E_{w}[\xi_{w}(\mathbf{x})^{T}\xi_{w}(\mathbf{x}^{\prime})] \tag{8}\]  
such that \(\xi_{w}(\mathbf{x})^{T}\xi_{w}(\mathbf{x}^{\prime})\) is an unbiased estimate of \(K(\mathbf{x},\mathbf{x}^{\prime})\) when \(\mathbf{w}\) is randomly sampled from the possibility distribution \(p(\mathbf{w})\)[18]. To obtain the real-valued random feature that meets the condition \(E[\varphi_{w}(\mathbf{x})^{T}\varphi_{w}(\mathbf{x}^{\prime})]=K(\mathbf{x},\mathbf{x}^{\prime})\), the probability distribution \(p(\mathbf{w})\) and kernel \(K(\mathbf{x}-\mathbf{x}^{\prime})\) should be real. Therefore, the \(e^{i\mathbf{w}^{T}(\mathbf{x}-\mathbf{x}^{\prime})}\) is substituted by \(cos(\mathbf{w}^{T}(\mathbf{x}-\mathbf{x}^{\prime}))\). Furthermore, according to the conclusion of the authors of [25], the mapping relation can be expressed as \(\varphi_{w}(\mathbf{x})=[cos(\mathbf{w}^{T}\mathbf{x})~{}~{}sin(\mathbf{w}^{T}\mathbf{x})]^{T}\). To lower the variance of \(\varphi_{w}(\mathbf{x})^{T}\varphi_{w}(\mathbf{x}^{\prime})\), the map \(\varphi_{w}(\mathbf{x})\) is normalized. Therefore, the real-valued and normalized approximation can be expressed as  
\[K(\mathbf{x},\mathbf{x}^{\prime})=\frac{1}{M}\sum_{i=1}^{M}cos(\mathbf{w}_{i}^{T}(\mathbf{x}- \mathbf{x}^{\prime}))=~{}<\varphi(\mathbf{x}),\varphi(\mathbf{x}^{\prime})> \tag{9}\]  
where the real-valued random Fourier feature vector \(\varphi(\mathbf{x})=\sqrt{\frac{1}{M}}[cos(\mathbf{w}_{1}^{T}\mathbf{x}),\_\infty(\mathbf{w}_ {M}^{T}\mathbf{x}),sin(\mathbf{w}_{1}^{T}\mathbf{x}),\_\infty(\mathbf{w}_{M}^{T}\mathbf{x})]\). \(\mathbf{w}_{1},...,\mathbf{w}_{M}\in R^{M}\) is independent and identically distributed samples drawn from \(p(\mathbf{w})\). The parameter M of random Fourier features represents the dimension of an Euclidean inner product space. In addition to the mapping function \(\varphi(\cdot)\), the feature mapping function \(\psi_{w}(\mathbf{x})=\sqrt{2}cos(\mathbf{w}^{T}\mathbf{x}+b)\) where \(\mathbf{w}\) is also drawn from \(p(\mathbf{w})\) and b is drawn uniformly from \([0,2\pi]\) also satisfies the the condition shown by Equation (9).