Adaptive Learning with Reproducing Kernels (General topics on applications of reproducing kernels)

(1)

Adaptive

Learning with

Reproducing

Kernels

Masahiro Yukawa

DepartInent

of Electronics and Electrical Engineering, Kcio University

1 An

Overview

$R(-11)\iota\cdot$odncing kernels have been proven an attractive tool in the context of online

esti-mation of nonlinear functions

over

the last decades in the signal procesbing and $nla(^{\backslash },hin$

learning communities [1-16]. (See [17-27] for the thcory and applications of reproducing

kernels.) TheclPI)roach of onlinenonlinear estimation with kcrnel has 1ildcomputational

complcxitv compared to the approach based on Volterra $S^{\supset}.ri(s_{ノ}$ expansion (of

which $th_{P}$

second 01 third order approximation is typically used) and has

convex

nature of

stochas-tic optimization unlike the neural network. The challenges of the kernel based $appro_{c})_{\vee}ch$

include

$\dot{r}\mathfrak{j})k_{C^{1}.1Jt)}1$ design (how to design

$lep_{1}\cdot o$ducing kernel that fits the nonlinear function to

be $e_{k}^{1}\searrow(ti_{In_{c\lambda_{\fbox{Error::0x0000}}}}ted)\prime$

:

diction ary construction (how to construct a dictionary, $a|_{-}\backslash ^{t}pt$ ofvectors,

that spans $a\nearrow$

:low-dimensional’ linc.ar subspacecontaining avector close to the nonlinear function);

and

parameter $estinlatiol\downarrow$ $($howto $e_{\backslash }s^{1}tin1i).te$ th coeﬃcients of fhe dictiou,_{$\lambda ryelen1(^{\supset}.nts$} to

$dpp_{1}\cdot$oximate the nonlinear function in online and adaptive fashion).

Here, the low dimensionality is of great importance in practice for eﬃciency both in

computation and

memory

resource. For item c), any algorithmic $solve1b’$ that have been

developed $fo1^{\cdot}$ linear adaptive $fi1t_{1}$erixlg tasks can be directly applied, $su(^{\backslash \}_{1}}$

as the adaptive

projected subgradient method (APShf) [28-43], the adaptive proximal$f_{01}\cdot ward$-backward

splitting (APFBS) method [44-$\cdot$48], etc. APSM is $c\prime m$ adaptive $(_{t}^{\backslash }$xten sion of thc projected

subgradient method studied by Polyak $[49]_{{\}}$ and it includes as its particular case the

classical normalized least $me_{c}^{\tau}\iota n$ square (NLMS) algorithm $[i^{\ulcorner}($,51], the aﬃne projection

$algol\cdot$ithm [$5254]$, the arlaptivc parallel subgradient projection algorithm [5558], and

(2)

asymptotic minimization problem of a sequence of nonnegative convex functions, and a

strong convergence theorem has been established in [28]

un

der certain mild conditions.

As a direct consequence of the convergence theoreln, it extends $tl_{1}e$ convergence theorenl

for the projections onto

convex

sets (POCS), acelebrated alternating projection method

for

convex

feasibilitv problems (cf. [62]), to the $cai\supset^{1}e$ of infinitely many closed

convex

sets.

It should be renlal.ked here that the strong convergence is proved forAPSM, whereas the

$widely-knowI11^{\cdot}e_{\backslash }^{\zeta^{\backslash }},ult$ for POCSis weak convergence (see, e.g., [63]). APFBS isan adaptive

extensionof the proxi nalforward backward splitting method [64,65] for minimizing a sum

of blnooth aIld nonsmooth

convex

functions by using Moreau’s proximity operator [66-68].

Its tvpical $ap\iota$)$lication_{\supset}^{\backslash }$ include adaptive estim mation of sparse impulse responses [14].

$Fo1^{\cdot}$ item a), the author has

$p_{1}\cdot$oposed multikernel adaptive filterinq [6972]:

a

convex-analytic learning paradignl using ‘multiple’ reproducing kernels; the reader may refer to

the tutoridl paper [73]. Multikernel adaptive filtering is particularly eﬀective wh$\backslash .n(i)$

the nonlinear function contains multiple componentswith diﬀerent char teristics $su(:h_{t}=\iota$

linear and nonlinear components and high- and low- frequency $(_{ノ}$onlponents [$74-77]$, and

(ii) an adequate kernel is unavailable because the amount of prior information $al$)$out$ the

unknown function is limited, and/or because the unknown function is time-varying and

so is

an

adequate kernel for the function. Related approaches have been considered by

diﬀerent research groups [78-80].

The (Luthor $h_{d}s$ also proposed $aI1$ eﬃcient $single-k_{G}rIle1aI^{J}$ , filtering algorithm

na1ned hyperplanp $pl\cdot$ojection along aﬃne subspace (HYPASS) [81-83]. The HYPASS

algorithm is a natural extension of the simple stochastic gradient based method called

the naive online $R_{1eg}$ minimization algorithm (NORNIA) proposed by Kivinen et al. [2].

NORMA builds

a

dictionary by using all the observed data, meaning that the dictionary

size grow,$\backslash lineal\cdot ly$ with the number of dataobservpd. As

a

remedy for thisissue,

a

simple

truncation rule has been introduced in [2]. This approach is apparently ineﬃcient

be-cause the dictionary may contain redundant $Vt^{n}$ctors, which cause high dimensionality of

the subspace spanned by the dictionary. HYPASS selectively addb each $0\uparrow$₎served

datum

into the dictionary based on the so-called coherence criterion $[9]_{:}\cdot othe\iota$. criteria have also

been proposed, e.g., in $[3_{:}84]$. If a datum does not enter the dictionarv, the

stochastic-grarlient $di_{1}\cdot$ection does not belong to the dictionary subspace aJld thus the datuin is

$s_{\backslash }i_{1}$nply d$i(,$carded. In othpr words, as long as sticking to the stochastic gradient method,

one has to $di_{SCa1}\cdot d$ such a datum although it may contain information for updating the

coeﬃcients. The HYPASS algorithm systematically eliminate this limitation by

enforc-ing the update direction to lie in the dictionary subspace. HYPASS includes the sparse

sequential method of Dodd $ct$ al. [85] and the quantized kernel LMS (QKLMS) [12] $a_{A}s$

(3)

refinement of the dictionary [71,86,87], borrowing the idea of sparse signal recovery,$suc:h$

as

compressed sensing [8890]. (See [91] for a sparse signal recovery using non quadratic

strictly

convex

objectives.

See

also $[^{(}J2,93$] for studiest of regularization paths with $l_{p}$

quasi-nornls for

$0<p<1.$

) It $h_{c}\Re$ also been extended to online model selection and

learning schene in [94-96], and the scheme has succebsfully been applied to

an

adaptive

online

coverage-map

reconstruction problem in wirelebs communications [97].

The existing $<\iota 1gorith_{I}ns$ of online nonlinear estimation with kernels

caIl be classified

into two categories: the functional approach and the parameter approach. Here, _the

functional approach $fol\cdot\ln$nlates the online nonlinear estimation problem in a

reproducing

kernel Hilbert $sp_{C}\iota ce$ (RKHS), while the parameter $a\iota$)proach formulates the problem in

a parameter (Euclidean) space. Our recent studies have shown significant advanta.ges

of the functional approach

over

the parameter bpace [81-83]. The Cartesian HYPASS

(CHYPASS) algorithm proposed in [72] is

a

multik$(^{3}rne1$ adaptive filtering scheme falling

$i_{I1}to$ the

functionaJ

approach, which unifies $th_{P}$ works in [71] _{$i\iota nd[81-83]$}.

CHYPASS

has

been applied to tinle-series prediction problenswith lasel$\cdot$

signals and C02 emission data,

and $it\sigma$

eﬃcdcy has been de non,strated _in _[72]. _In _{the remainder of this} $\dot{c}l.1\dagger$icle we present

basic materials that support the CHYPASS algorithnl, and then pl.esent its concept in a

simple nlanner.

2 _{Sum Space and Reproducing Kernel}

We denote by $\mathbb{R}$ and $\mathbb{N}$ the sets

of all real numbers and nonnegative integers,

respec-tively. Vectors and lnatrices

are

dexloted bylower

case

dJld u$pper-(^{\backslash }abc^{J}1ettc^{\Delta}rs$ in bold face,

$1’$espectively. The identity matrix is denoted by $I$ and the transpositionofavector/matrix

is denoted by $(\cdot)^{T}$. We denote the rlull (zero)

function by $0.$

Let $\mathcal{U}\subset \mathbb{R}^{L}$

and $\mathbb{R}$

be the input and output spaces, respectively. We consider the

$proble\ln$ _of$estimating/t_{la(^{\urcorner}}$king a nonlinear unknown $functio\iota 1\psi$ : $\mathcal{U}arrow \mathbb{R}$ from

sequen-tially arl.iving input-output measurements $u_{n}\in \mathcal{U}$ and $d_{n}$ $:=\psi(u_{n})+p)_{n}\in \mathbb{R},$ $7l\in \mathbb{N},$

where $\iota)_{r1}\in \mathbb{R}$ is the additive noise. We $focui\supset^{\backslash }$

on the

case

$wherC^{\lrcorner}\psi$ contains beveral

dis-tinctive components; e.g., linear and nonlinear (but smooth) components, high- and

low-frequency components, etc. To generate a minimal model to describe such a

mnlticom-$1)$onent function $\psi$, we _$Ube$ nlultiple RKHSs

$(\mathcal{H}_{1\backslash 9} \rangle_{\mathcal{H}_{1}})$, $(\mathcal{H}_{2}, \rangle_{\mathcal{H}_{2}})$, $\cdots$

: $(\mathcal{H}_{Q}, \rangle_{\mathcal{H}_{Q}})$

over

$\mathcal{U}$,

where each of the $\mathcal{H}_{q}s$ consists of functions from $\mathcal{U}$ to $\mathbb{R}$. Here, _$Q$

is the number

of components of $\psi$, and each

RKHS

is associated with each component.

The positive

definite kernel associated with the qth RKHS $\mathcal{H}_{q},$ $q\in \mathcal{Q}$ $:=\{1, 2. \cdots. Q\}$_, is denoted by

$\wedge^{\wedge}q$ :

$\mathcal{U}\cross \mathcal{U}arrow \mathbb{R}$

, and the norm _{induced by} $\rangle_{\mathcal{H}_{q}}$ is denote by

(4)

modeled as

an

element ofthe

snm

space

$\mathcal{H}^{+}:=\mathcal{H}_{1}+\mathcal{H}_{2}+\cdots+\mathcal{H}_{Q}:=\{\sum_{q\in Q}f_{q}:f_{q}\in \mathcal{H}_{q}\}.$

GiveIl an elenle1lt $f\in \mathcal{H}^{+}$, the decomposition $f= \sum_{q\in \mathcal{Q}}f_{q},$ $f_{q}\in \mathcal{H}_{q}$, is not necessarily

unique in general. If the decomposition is unique for any $f\in \mathcal{H}_{!}^{+}\mathcal{H}^{+}$ is the direct $|su7$’

of$\mathcal{H}_{q}s[98]$, anld it is usually denoted by $\mathcal{H}^{+}=\mathcal{H}_{1}\oplus \mathcal{H}_{2}\oplus\cdots\oplus \mathcal{H}_{Q}.$

Theorem 1 (Reproducing kernel of

sum

space $\mathcal{H}^{+}[17|$) The

sum

space$\mathcal{H}^{+}$ equipped

with the

norvn

$\Vert f\Vert_{\mathcal{H}^{+}}^{2}:=\min\{\sum_{q\in Q}\Vert f_{q}\Vert_{\mathcal{H}_{q}}^{2}|f=\sum_{q\in \mathcal{Q}}f_{q},$ $f_{q}\in \mathcal{H}_{q}\},$ $f\in \mathcal{H}^{+}$, (1)

is a RKHS with the reproducing kernel $\kappa$ $:= \sum_{q\in Q}\kappa_{q}.$

Theorem 2 Let $\kappa$ : $\mathcal{U}\cross \mathcal{U}arrow \mathbb{R}$ be the reproducing kernel

of

a real Hilbert space

$(\mathcal{H}_{:} \rangle_{\mathcal{H}})$. Then, given an arbitrary$w>0,$ $\kappa_{1t)}(u, v)$ $:=w\kappa(u, v)$, $u,$$v\in \mathcal{U}$, is the

repro-ducing kernel

_of

the RKHS $(\mathcal{H}, \rangle_{\mathcal{H},w})$ with the inner product $\langle u,$$v\rangle_{\mathcal{H},w}:=(\mu)^{-1}\langle u,$$v\rangle_{\mathcal{H}}.$

$u,$$v\in \mathcal{U}.$

Theorems 1 and 2 yield the following result.

Corollary 1 (Weighted norm and reproducing kernel) Given any $u_{q}$) $>0,$ $q\in \mathcal{Q}_{:}$

$\prime_{1}w(u, v)$ $:= \sum_{q\in Q^{tl)}q^{f_{1ノ}^{-}}q}(u, v)$, $u,$$v\in \mathcal{U}$

.

is the reproducing kemel

of

the sum space $\mathcal{H}^{+}$

eqni.pped with the weighted $no7m\Vert\cdot\Vert_{\mathcal{H}+.w}$

defined

as $\Vert f\Vert_{\mathcal{H}+,w}^{2}:=\min\{\sum_{q\in Q}w_{q}^{-1}\Vert f_{q}\Vert_{\mathcal{H}_{q}}^{2}|$

$f= \sum_{q\in \mathcal{Q}}f_{q}.$ $f_{q}\in \mathcal{H}_{q}\},$ $f\in \mathcal{H}^{+}.$

3 Examples of Reproducing Kernels and Basic Results

Example 1 (Positive definite kernels)

1. Linear kernel: Given $c\geq 0_{:}$

$ki_{L}(x_{:}y):=x^{T}y+c, x, y\in \mathcal{U}$_. (2)

2. Polynomial kernel: Given $c\geq 0$ and$m\in \mathbb{N}^{*}:=\mathbb{N}\backslash \{0\},$

$\kappa_{P}(x, y):=(x^{T}y+c)^{n\iota}, x, y\in \mathcal{U}$_. (3)

3. Gaussian kernel $(no7$malized) : Given $\sigma>0.$

(5)

The following theorem has been shown by Minh in 2(JIO.

Theorem 3 ([99]) Let$\mathcal{U}\subset \mathbb{R}^{L}$

be any set with nonempty inter\’ior and$\mathcal{H}_{f_{1G.\sigma}}$ the RKHS

associated with a Gaussian $ke7Y\iota el\kappa_{G\sigma}(x_{:}y)$

for

an arbitrary $\sigma>0$ together $\prime u\prime ith$ the

input space $\mathcal{U}$. Then,

$\mathcal{H}_{\kappa_{G.\sigma}}$ does not contain any polynomial on$\mathcal{U}$

.

including the nonzero

constant

_function.

Corollary 2 (Polynomial and Gaussian RKHSs [72]) $A,sume$ _that _{the input space}

$\mathcal{U}\subset \mathbb{R}^{L}$

has nonempty interior. Let $\mathcal{H}_{\kappa_{P\sigma}}$ and $\mathcal{H}_{\kappa_{C_{v},\sigma}}$_, be the RKHSs _$a99$ociated, $r(^{J},S \oint$)$ec-$

tively, uith a $poly_{7}\iota omial$ kernel $\kappa_{P}$ and a Gaussian kernel $\kappa_{G,\sigma}$

for

arbitrary parameters

$c\geq 0.$ $m\in \mathbb{N}^{*}$_, and$\sigma>0$. Then,

$\mathcal{H}_{Ap}\cap \mathcal{H}_{A}\sigma=\{0\}$. (5)

Inparticular, (5)

_for

$m=1$ _{implies that}

$\mathcal{H}_{\kappa}L\cap \mathcal{H}_{\kappa_{G\sigma}}=\{0\}$_. (6)

Theorem 4 ([72]) Let $\mathcal{U}\subset \mathbb{R}^{L}$

be

an

arbitrary subset and $r_{1}$ $:=w_{1}\kappa_{G,\sigma_{1}}$ and $\kappa_{2}$ $:=$

$w_{2^{\prime_{b}’}G,\sigma 2}Gau_{(}6ian$ kernels

for

$\sigma_{1}>\sigma_{2}>$ and $w_{1},$$w_{2}>0$. Then, the $as6$ociated $RKHS_{\langle}s.$ $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ satisfy thefollowing:

1. $\mathcal{H}_{1}\subset \mathcal{H}_{2}$

.

and

2. $\sqrt{n)_{1}}\Vert f\Vert_{\mathcal{H}_{1}}\geq\sqrt{w_{2}}\Vert f\Vert_{\mathcal{H}_{2}}$

for

any $f\in \mathcal{H}_{1}.$

See $[10[\vdash 102]$ for the $1^{\cdot}$elated results to Theorem 4.

4 Adaptive Leaning Algorithm Based

on

Orthogonal Projection

in

Product Space

Suppobe that $\mathcal{H}_{I)}\cap \mathcal{H}_{q}=\{O\}$ for any_{$p\neq q$} (cf. Corollary 2). Then, any $f\in \mathcal{H}^{+}C\dot{c}\lambda$ be

decornposed $u7\iota$iquely into _{$f= \sum_{q\in Q}f_{q\backslash }f_{q}\in \mathcal{H}_{q}$}. It is clear in this

case

that, under the

correspondence between $f$ and the $Q$-tuple $(f_{q})_{q\in Q}$, the sum space $\mathcal{H}^{+}$ is isomorphic to

the $Carte_{i}s^{\fbox{Error::0x0000}}iaJ1$ product

$\mathcal{H}^{\cross}:=\mathcal{H}_{1}\cross \mathcal{H}_{2}\cross\cdots\cross \mathcal{H}_{Q}:=\{(f_{1}, f_{2}, \cdots, f_{Q}):f_{q}\in \mathcal{H}_{q}, q\in \mathcal{Q}\},$

whicli is a real Hilbert space equipped with the inner product defined by

$\langle f,$

$g \rangle_{\mathcal{H}^{\cross}}:=\sum_{q\in Q}\langle f_{(1},$

(6)

We de1lote by $\mathcal{D}_{(1^{7l}},\subset\{\kappa_{q}(\cdot, u)|u\in \mathcal{U}\}$ the $dictionar^{v}y$ constructed for the qth kernel

at time $\iota\in \mathbb{N}$. The $dicti_{ona1}\cdot y$ typically btarts with $\mathcal{D}_{q,-1}:=\emptyset$ and $g1^{\cdot}OWS$ based on some

$no\vee elt$ criterion $S1(^{\backslash .h}$ as the coheren$(^{1}e$ criterion (dictionary constructions for

CHYPASS

depend on kernels $c^{Y}mployed$; see [72] for details). The kernel-by-kernel dictionary

sub-:spaccs are defined as $\mathcal{M}_{q,n}:=\backslash ,p_{c}^{r}m\mathcal{D}_{q.n}\subset \mathcal{H}_{q)}q\in \mathcal{Q},$ $n\in \mathbb{N}$. The multikernel adaptive

filtcr at time $ni_{b}$ given _ab

$\backslash /\wedge:=\sum_{\sim}(_{r^{\cap}q,n}q\in O\in \mathcal{H}^{+} tl\in \mathbb{N},$ (8)

$whel\cdot C\varphi_{q_{\fbox{Error::0x0000}}n}\in \mathcal{M}_{q,n-1}$. Thus, the dictiona1y $\mathcal{D}_{q,n}$ contains thc atoms (vcctors) that form

the next estimate $\vee^{\eta}q,n+1.$

$It_{\backslash }sho\iota\iota 1d$be$eln1)ha_{\iota\backslash }^{\iota’}$ized that the iso norphisl1l mentioned abo$v^{}$ reliesonthe assumption

$\mathcal{H}_{p}\cap \mathcal{H}_{q}=\{0\}_{:}\forall p\neq q$. In general, the norm in the sum space $h_{tL}$ no closed-form,

as

can

be seen $fro\ln$ Corollary 1. This lnakes $th_{P}$ orthogonal projection in the sum space diﬃcult

to compute in practice. The CHYPASS algorithm therefore projects the current estimate

onto a zero $i_{I1}stantanpous$-error _hyperplane in the product space (rather than in the

sunn

space). Aftel$\cdot$

simple $n1_{C}$mipulations, with the initial filter $\varphi_{0}:=0_{1}$ its update equation is

given

as

follows [72]:

$\Psi^{\circ}r\}+1:=\hat{\Psi}n+\lambda_{n}\frac{d_{71}-\varphi_{n}(u_{n})}{\sum_{(q\in 2}\Vert P_{\mathcal{M}_{q_{\backslash }n}}(\kappa_{q}(\cdot,u_{n}))\Vert_{\mathcal{H}_{Q}}^{2}}\sum_{q\in Q}P_{\mathcal{M}_{q.n}}(\wedge\cdot q(\cdot, u_{7} 7l\in \mathbb{N},$

(9)

whel $\lambda,$ $\in(0,2)$ is the step $\backslash _{L^{\backslash }}i_{7_{v}}c$

alld $P_{\mathcal{M}_{q,r1}}(\prime i_{q}(\cdot, u_{n}))$ denotes the orthogonal projection

of $\tau_{q}^{-(\cdot.u_{r/})}\}$ onto the closed linear subspace $\mathcal{M}_{q.n}[98]$. This can be $(^{\rangle}(1$nputed eﬃciently,

When we employ a linear (or polynomial) kernel together with a Gaussian

kernel

the $p_{1}\cdot$oduct space

$\mathcal{H}^{\cross}$ is isomorphic to the sum space $\mathcal{H}^{+}\}_{J}y$ Corollary 2, which

im-plies that CHYPASS can be interpreted as projecting the current estimate into the zero

$in_{\backslash }^{(i_{)}}$

tantaneous error hyperplane in the sum space $\mathcal{H}^{+}$

in this

case.

Referring to Theorenl

4,

on

the $oth(r$ _hand, _the

_same

_{does not apply to the}

case

_where

we

_{employ lnultiple}

Gau sian kernels. CHYPASS works well in both cases, as demon strated by simulations

in [72].

References

[1] L. Cbato and M. Opper, Sparse representation

_for

Gaussian process models, in

Ad-vances inNeural Infornlation Processing Systemb 13. MITPress, 2001, pp. 444-450.

[2] J. Kivinen, A. J. Smola, and R. C. Williamson, “Online leal.ning with kernels,”

(7)

[3] Y. Engel, S. Mannor, and R. Meir, “The kernel recursive least-squares algorithm

IEEb Trans. Signal Process., vol. 52, no. 8, pp.

2275

$2285_{7}$ Aug.

2004.

[4] A. V. $\perp\grave{}$

Ialipatil, Y.-F. $Hu_{\dot{c}})_{\mathfrak{l}}ng$, S. Andra, and K. Bennett, “Kernelized

set-$m(^{\Delta}$mbership

a

$ppro\partial x_{\fbox{Error::0x0000}}h$to nonlinear adaptive filtering in Proc. IEEE ICASSP, 2005,

pp. 149152.

[5] P. Laskov, C.Gehl, S.Kriiger, and K.-R. M\"uller, “Incremental support vector

learn-ing: Analysis, imple nentation and $a1^{J}plication_{\iota}\backslash ^{\backslash },’\backslash /$ J. Mach. Learn. Res., vol. 7, pp.

1909 1936, 2006.

[6] W. Liu and J. Pr\’incipe, Kernel aﬃne projection algorithms EURASIP

I. Adv. Signal Proces.s., vol. 20()8, pp. 1 12, 2008, article ID

784292.

[7] K. Slavakis, S. Theodoridi and I. Yanlada, “Online ke1nel-based classificationusing

adaptive projection $alg_{01}itl_{1}m\xi_{:}^{1}$’ IEEE ’lTans. Signal $Proce\mathcal{S}S.$, vol. 56, no. 7,

$P1^{J}.$

2781 $27^{(}J6$, July 2008.

[8] –, ‘Adaptive constrained learning in repl.oducing kernel Hilbert spaces: the

ro-bubt bea nforming case,“’ IEEE Trans. Signal Process., vol. 57,

no.

12, pp.

4744-4764, Dec.

2009.

[9] C. $Rj(:f_{1’}xrd$_, _J. _Bermudez, _{and P.} _Honeine, _{“Online prediction of time series data}

with kqnels,” IEEE Trans. Siqnal Process., vol. 57, no. 3, pp. 1058-1067, $\perp\backslash I_{\partial}r.$

$200^{(}J.$

[10] W. Liu, J. Pr\’incipe, andS. Haykin, Kernel Adaptive Filtcri7lg. New Jersey: Wilev,

2010.

[11] S. Van Vaerenbcrgh, M. $L\acute{a}7aro$-Gredilla, and I. Santamar\’ia, “Kernel recursive

least-squares trackc for $tim\ovalbox{\tt\small REJECT} val\cdot$ying r

$egr(^{\backslash }$ssion,., IEEE Trans. Neural Networks and

Learning Systemg, vol. 23, no. 8, pp. 1313-1326, Aug. 2012.

[12] B. CheIl, S. Zhao, P. Zhn, and J. C. Pr\’incipe, “Quantized kernel least lnean square

algorithm IEEE Trans. Neural Networks and Lea,rning Systems, vol. 23, no. 1, pp.

22-32, Jan. 2012.

[13] K. Slavakis, P. Bouboulis, nd S. Theodoridis, :(Online _{learning in} _reproducing

kernel Hilbert spaces in Academic Press Library in Signal Processing: 1st Edition,

Signal Proce,ssing Theory and Machine $Learnir/_{ノ}g$. Elsevier, 2014, vol. 1, pp.

883-987.

[14] W. Gao, J. Chexl, C. Ricbard, and J. Huang, “Online dictionary learning for kernel

(8)

[15] H. Fan, Q. Song, and S. B. Shrestha, “Online learning with kernel regularized least

mean

square algorithms,” Knowledge-Based Systems, vol. 59, pp. 21-32, Mar.

2014.

[16] P. Honeine, “Analy ing sparse dictionaries for online leal.ning with kernels,” IEEE

Trans. Siq77al Process., vol. 63, no. 23, pp. 6343-6353, Dec. 201

[17] N. Aronszajn, T eory of reproducing kernels Trans. Amer. Math. Soc., vol. 68,

no. 3, pp. 337-404, May

1950.

[18] S. Saitoh, Integral $Transfo/ms$, Reproducing Kernels and Their Applications,

ser.

Pitnan Research Notesin MMathematics. Addison Wesley Longman, 1997,vol. 369.

[19] V. N. Vapnik, Statistical Learning Theory. New York: Wiley, 1998.

[20] K.-R. Miiller,

S.

Mika,

G.

R\"atsch, K. Tsuda, and B. $S(^{5}h\"{o} 1$kopf, (An introductio1l

to kernel bascd learning algorithm lEEE Trans. Neural Networks, vol. 12, _no. 2,

pp. 181-201, Mar. 2001.

[21] B. Sch\"olkopfand A. J. Smola, $Lea7^{v}ning$ with Kernels. $c_{an1}bri(ge$, MA: $\perp\backslash IIT$ Press,

2001.

[22] A. Bel.linet and C. Thomas-Agnan, Reproducing kernel Hilbert spaces in probability

and statisties. Boston: MA: $Kh\iota wer$ Academic, 2004.

[23] J. Shawe-Taylor and N. $Crilc\grave{},$tianini, Kernel Methods

for

Pattern Analysis.

Cam-bridge University Press, 2004.

[24] S. $Theodo\iota\cdot$idis and K. Koutroumbas, Pattern Recognition: 4th cd. New York:

Academic, 20()8.

[25] $\ovalbox{\tt\small REJECT}_{7}\rfloor\langle|\ovalbox{\tt\small REJECT}^{\backslash \wedge}ノ\backslash$

, カ$-*l\triangleright\yen\lambda F\ddagger.$ $FfJ\ovalbox{\tt\small REJECT} ffl\# R$,

2010.

[26] IEEE Signal Processing Magazine, SpecialSection: Advances inKernel based

Learn-inq

_for

Signal Processing, July 2013.

[27] Y. MMotai, ”Kernel association for classification and prediction: a surve.y,’

IEEE

Trans. Neural Networks and Learning Systems, vol. 26, no. 2, pp. 208-223, Feb.

2015.

[28] I. Yamada and N. Ogura, (Adaptive projected subgradient method for

asvmptotic minimization of sequence of nonnegative

convex

functions

(9)

[29] M. $Yuka\urcorner h^{\tau}a$, R. L. G. _{$Cavalcante_{1}$} andI. $Y_{t}$)mada, ‘Eﬃcient blind$\backslash _{\wedge}$IAI

suppression in

DS/CDMA systemsby embedded constraint parallel projection techniques,“’ IEICE

D.ens. $Fundan\mathfrak{l}$entalS, vol. E88-A,

no.

8, pp. 2062-2071, Aug. 2005.

[30] R.L. G. Cavalcante, M.Yuktwa, andI. Yamada, (Set-theol.etic$DS/CD\perp\backslash IA$receiver

for fading channels })y adaptive projected subgradient method in Proc. IEEE

GLOBECOM, SP06-1,

_2005.

[31] K. Slavakis I. Yamada, tmd N. Ogura, (The _adaptive _projected _subgradient

method

over

the fixed point set of strongly attracting nonexpansive mappings,“’

Numer. Funct. $A\gamma$

’al. Optim., vol. 27, no.

7&8,

pp. 905-930, 2006.

[32] M. Yukawa, K. Slavakis, and I. Yamada, AdaptivP parallel quadratic-lnetric

pro-jection algorithnls $IEF_{J}^{1}E$ Trans. Audio, Spoech and Langua.qe Proccssin vol. 15,

no. 5, pp. $166_{c}^{\ulcorner})$ 1680, July

2007.

[33] R. L. G. Cavalcante and I, _Yamada, _{Multiaccesb interference} $supp^{1(^{\backslash }.ssion}$ in

or-thogonal space-timeblock coded MIMO systems by adaptiv($\lrcorner$ projected subgradient

$1XJc^{Y}$thod,’ IEEE $\ulcorner l^{7}ratl8$. Signal Processing, vol. 56, no. 3, pp. 1028-1042, $\Lambda Iar$. 2008.

[34] –, (Aflexit)le peak to average power ratio $r(^{\lrcorner duction}$ scheme for OFDM systems

by the adaptive projected $\{\supset^{1}$ubgradient method,“ IEEF Trans. Signal $Processing_{1}$

vol. 57, no. 4, pp. 1456-1468, Apr. 2009.

[35] M. Yukawa, (Krylov-proportionate adaptive filtering techniques not limited to

sparse $systeI1_{\iota}b,$” IEEE Trans. Siqnal $Froces_{く}\backslash ing$, vol. 57, no. 3, pp. (J27-943, $\rceil\perp\backslash I_{c}$

}r.

2()09.

[36] M. Yukawa, R. C. de Lamare, and I. Yamada, “Ifobust reduced rank adaptive

algorithm based on parallel subgradient projection $c\gamma 11d$ krylov subspace,’“ IEEE

Tran6. Si.qnal Process., vol. 57, no. 12, pp. 4660-4674, Dec. 2009.

[37] M. Yukawd arld I. Yamada, “A unified view of adaptive variable-metric proje

tion algorithms EURASIP,J. _Advances _in _Signal _{Processiny, vol.} 2009, Article ID

589260, 13 pages, 2009.

[38] M. Yukawa, K. Slavakis, and I. Yamada, $\perp\rceil\backslash Iulti$

-domain adaptive learning $b_{a}*ed$ on

feasibility splitting andadaptiveprojectedsubgradient lnethod IEICE Trans.

Fun-damentals, vol. E93-A,

no.

2, pp. 456-466, Feb.

2010.

[39] M. Yukawa and W. Utschick, ((A _{fast stochastic gradient algorithm: AIaximal}_use _of

sparsification benefits under computational constraints,“‘ IEICE Trans.

(10)

[40] S. $Theod_{01}\cdot$idis, K. Slavakis, and I. Yamada, ((Adaptive learning in

a

world of

pro-jections: a unifying framework for linear and nonlinear classification and regression

tabkb,“ IEEE Signal Process. Mag., vol. 28,

no.

1, pp. 97-123, Jan. 2011.

[41] bI. Yukawa and I. Yamada, (Set-theoretic _adaptive _filtering _based _on _data-driven

$bp_{\dot{C}})$rsification,” International Journal

of

Adaptive Control and Signal Processing,

vol. $25_{\backslash ,\prime}[)p.$ $707-722_{\backslash ,\prime}$Wiley, 2011.

[42] hI. Yukawa,Y. Sung, and

G.

Lee, (_$(Dual$

-dornain adaptive$beamf_{01}\cdot mer$ underlinearly

and quadratically constrained minimum variance IEEE Tran,s. _Signal Process.,

vol.

_61:

no.

_11:

pp. 2874-2S86, Jun. 2013.

[43] O. Toda, M. Yukawa, S. Sasaki. and H. Kikuchi, “A eﬃcient adaptive filtering

scheme based on combining multiple $met_{1}\cdot icb$, IEICE Trans. Fundamentals, vol.

E97-A, no. 3, pp. 800-808, Mar. 2014.

[44] Y. Murakami, $\perp\backslash I$

. Yamagishi, M. Yukawa, $\subset\prime\iota nd$I. Yamada, (A sparse adaptive

filter-ing usfilter-ing time-varyfilter-ing soft-thresholdfilter-ing techniques in Proc. IEEE

_ICASSP:

2010,

pp.

37343737.

[45] M. Yamagishi, M. Yukawa, and I. Yamada, _{“Sparse system identification} by

expo-nentially weighted adaptive parallel projection and generalized soft-thresholding,

in Proc. APSIPA Annual Surnmit and Conference, 2010, pp.

367-370.

[46] M. Yukawa, Y. Tawara, M. Yamagishi, and I. Yamada, “Sparsity-aware adapti$v^{}$

filter,- _based_on$\ell_{p}$-norminspired soft-thresholding technique,“’ in Proc. IEEEISCAS,

2012, pp.

2749-2752.

[47] M. Yukawa, Y. Tawara, S. Sasaki, and I. Yamada, “Asparsity based design of

regu-larization parameter for adaptive proximal forward-backward splitting algorithm,”

in Proc. IEEE ISWCS, 2013, pp. 190 193.

[48] $*\backslash I$. Yamagishi, $\backslash _{\perp}I$

. Yukawa, and I. Yamada, (Shrinkagetuning based

on an

unbiased

MSE estimate for sparsity

aware

adaptive filtering in Proc. IEEE ICASSP, 2014,

pp. 5514-5518.

[49] B. T. Polyak, “Minimization of unsmooth functionals USSR

Com-pnt. Math. Physics 9, pp. 14-29, 1969.

[50] J. Nagumo and J. Noda, “A learning method for system identification IEEE Trans.

(11)

[51] A. E. $All)ert$ _{and L.} _S. _Gardner _Jr., _{Stochastic Approximation} _and

Nonlinear

Re-grebsion. Cambridge MA: MIT Press, 1967.

[52] T. Hinamoto and S. Maekawa, (Extended _theory _of $1earni_{li}g$ identification,“‘

Trans. Inst. Elect. Eng. Jpn., vol. 95, no. 10, pp. 227-234, ₁₉₇₅ (in Japanese).

[53] K. Ozeki and T. Umeda, (An $ada\iota)$tive filtering algorithm using

an

orthogonal

pro-jection to an afline subspace and its properties Electron. Commun. $\mathfrak{b}Japan$, vol.

$67-A_{\tau,\prime}$ no.

5:

pp. 19-27, 1984.

[14] M. Rupp, “A family of adaptive filtel algorithms with decorrelating properties

IEEE Trans. Signal Processing, vol. 46, no. $3_{I}$ pp. 771-775, Mar. 1998.

I. Yamada, K. $S1_{c}\iota v_{c}$)kis, and K. Yamada, (An eﬃcient robust adaptive filtering

algorithm$ba_{k}^{t},ed$

on

parallel $su\dagger$₎gradient projection_$te(,$hniqnes,’ IEEE 7 ans. Signal

$P_{7OCeS\mathcal{S}}ir\iota.(J$, vol. 50, no. 5, pp. 1091-1101, May 2002.

$[\backslash r)()]$ M. $Ynk_{c}\iota w$ and I. YarIlada. Eﬃcient adaptive btereo $e(hoc_{c}\iota$nceling schemes based

onsimultaneous

use

of multiplestate data,” IEICE Trans. Fnndomentals, vol.

E87-$A$_, no. 8, pp. 1049-1957, Aug. 2004.

[57] –, (Pairwiseoptimal weight $reali_{7}$ation–Accelerationtechniquefor set theorctic

adaptiveparallel subgradientprojection algorithm IEEE Trans. Signal Processing,

vol. 54, no. 12, pp. 4557-4571, Dec. 2006.

[58] M. $Yuk_{(}\downarrow wa$, N. Murakoshi, and I. Yamada. .:Eﬃcient fast ster$(^{\lrcorner}0$acoustic echo

cancel-lation based on pairwise optimal weight realization technique,” EURASIP,I. _Appl.

Signal Processing, vol. 2006, Article ID 84797, 15 $pageb_{:}$ 2006.

[59] O. L. Frost, (A _{algorithm for}_linearly _constrained _adaptive _array _{processing,”}

Pro-ceedings

_of

the

_IEEE

vol. 60, pp. 926935, Aug. 1972.

$[6()]$ H. Cox, R. M. Zeskind, aJld M. M. Owen, $:(Robust_{r1}da1)$tive b$e_{c}\gamma$mforming, IEEE

Trans, $Aco\prime nt.$_, Speech, Signal Processing, vol. ASSP-35, no. 10, pp. 1365-1376, Oct.

1987.

[61] M. L. R. de $Campo_{\iota}s_{:}^{t}$ S. Werner, and J. A. Apolin$\acute{a}1^{\cdot}io$ Jr., $(Con_{c}^{\gamma}\backslash trained$ adaptation

algorithms enlploying householder transformation IEEE Trans. Signal Processinq,

vol. 50,

no.

9, pp.

21872195.

Sept.

2002.

[62] P. L. Combettes, “The foundations of set theoretic estimation Proc.

_of

IEEE,

(12)

[63] H. Stark and Y. Yang, Vector Space $Projection_{t}s-A$ Numerical Approach to Signal

and Image Processiny, Neural Nets, and Optics. New $Yo\iota\cdot k$: John Wiley

&

Sons,

1998.

[64] P. L. Lions and B. Mercier, $t$

‘Splitting algorithms for $th_{P}$ sum of two nonlincar

$operato1^{\cdot}b^{\backslash },$

’‘

SIAM J. Numer. Anal., vol. 16, no.

_6:

pp. 964979, 1979.

[65] P. L. Combettes and V. R. lVajs, (

(Signal recovery by proxinlal forward backward

splitting

SIAM

$Jo\tau\iota 7V7al$

on

Multiscale Modeling and Simulation, vol. 4, pp.

1168-$1200_{1}$ 2005.

[66] J. .I. Moreau, (Fonctions

_convexes

_dualc _{et points proximaux dans} _un_espace

hilber-tien C. R. Acad. $S(:i$. Paris S\’er, vol. 255, pp. _{$2897-2899_{:}$}

1962.

[67] H. H. Bauschke and P. L. $c_{on1}$bettes, Convex Analysis and Monotone $07$)erator

$Tl$

,

eory in Hilbert Spaces, 1st ed. New York: $NY$: Springer, 2011.

[68] I. Yamada, M. Yuk.$awa$, and M. Yamagishi,

$t.$

$Minimi/_{\lrcorner}’ing$ the Moreau envelope of

$n($Ilsmooth convcx functions over the fixed point set ofC,Prtain quasi nonexpansive

lnappings,’ in Fixed-Point Algorithms

_for

Inverse Problcms in Science and

Engi-ne$(’ ring_{:}$ ser. optimization and Its Applications, vol. 49. NewYork: Springer,

2011:

$P1^{J}\cdot 345-390.$

[69] $\wedge\backslash I$

. Yukawa, :$[$)$n$ use of multiple kernels in adaptive learning –Extended

reproduc-ing kernel Hilbert space with $C_{c}\gamma_{\fbox{Error::0x0000}}$

rtesian product,” in Proc.

IEICE

Signal Processing

Symposium: Nov. 2010, pp.

59-64.

[70] –, ’‘Nonlinear adaptive filtering techniques with multiple $kerne1_{S_{\backslash }}$

. in European

Signal Processing

_Conference

(EUSIPCO), 2011, pp. 136 140.

[71] -, (Multikelnel adaptive filtering,” IEEE Trans. Signal Processing, vol. 60,

no.

9,

pp. $4672-4682_{:}$ Sept.

2012.

[72] –, $:’$

Adaptive learninginCartesian productof reproducing kernel Hilbert spaces

IEEE Trans. Signal Process., vol. 63, no. 22, pp. 60376048, Nov. 2015.

[73] $\grave{7}\ovalbox{\tt\small REJECT}\int||_{\overline{J}h\hslash\grave{r}},$ $”‘\ni\lceil_{\wedge}^{\wedge}\ovalbox{\tt\small REJECT} i\Psi_{J\grave{},}’H|_{l^{\backslash }}^{L\wedge}\llcorner\backslash i=EI\Sigma Bt’ffi$の$\ovalbox{\tt\small REJECT} Ji\mathbb{H}\Re:fffliW\cross の)_{l\llcorner\backslash \int\mp\exists}^{\backslash }rarrow,$” $E\neq 1ffffi\ovalbox{\tt\small REJECT}\ulcorner\overline{\equiv}\sim\neq\hat{=}\ovalbox{\tt\small REJECT},$

vol. 97, no. 10, pp. 876-882, _Oct.

2014.

[74] W. H\"ardle, H. Litmg, and J. Gao, Partially Linear Models. Heidelberg, Germany:

(13)

$[7_{\backslash J}^{\ulcorner]}$ M. Espinoza, J. A. K. Suykens, and B. D. Moor, (Kernel based partially linear

models and nonlinear identification,” IEEE $\mathcal{I}kans$. Autom. Control, vol. 50, no. 10,

pp. 1602-1606, Oct. 2005.

[76] Y.-L. Xu and D.-R.

_Chcn:

(

(Partially-linear least squares regularized regression $fo1^{\cdot}$

svstem identification IEEE $Tran6$. Autom.

Control

vol. 54, no. 11, pp. 2637-2641,

Nov.

2009.

[77] Y.-L. Xu, D.-R. Chen, H.-X. Li, and L. Liu, $\{(Le_{c\mathfrak{B}}t$ square regularized regression

in $SU\ln$ space IEEE Trans. Neural Networks and LearnMg Systems, vol. 24, no. 4, $1)p.$ $()3_{\backslash J}^{\ulcorner}-646$, Apr. 2013.

[78] R. Pokharel, J. Pr\’incipe, and S. Seth, “Mixture kernel leabt

mean

$S(1^{uare^{\grave{\prime}}’}$, in IEEE

IJCNN,

_2013.

[79] W. Gao, C. Richald, J.-C. M. Bermudez, and J. Huang, (Convex _combinations _of

kernel adaptive filters in IEEE Int. Workshop on MLSP, 2014.

[80] F. A. Tobar, S.-Y. Kung, and D. P. Mandic, ((

Multikernel least, $me_{(}tI1squar(^{\Delta}$

al-$g(1’$ithm, IEEE Trans. Neural Networks and Learning Systems, vol. 25, no. 2, pp.

265 277, Feb. 2014.

[81] $\backslash _{A}$

I. Yukawa and R. Ishii, (

$(An$ _{eﬃcient kernel} _adaptive _{filtering algorithm using}

hyperplane projection along aﬃne subspace,“‘ in Proc. EUSIPCO, 2012, pp. 2183-2187.

[82] M. $T_{c}\downarrow$kizawa and M. Yukawa, (An eﬃcient data-reusing kernel adaptive

filter-ing algorit$fi$ based on parallel hyperslab projection along aﬃne subspac$(^{\supset}s$,“ $inl$

Proc. IEEE ICASSP, 2013, pp. 35573561.

[83] –, (Adaptive nonlinear ebtimation based on parallel projection along aﬃne sub-$sp^{l}<1ces$ inreproducingkernelHilbert$s\tilde{p}ace$”, IEEE $T/un_{c}s$

.

Signal Proce.$s^{3}siT|g$, vol. 63,

no.

_16:

pp. 4257-4269, Aug. 2015.

[84] J. Platt, “A resource-allocating network for function interpolation,” Neural

Com-$putatior\iota$, vol. 3, no. 2, pp. 213-225, 1991.

[85] T. J. Dodd, V. Kadirkamanathan, $c\gamma nd$ R. F. Harrison, ((Function estimation in

Hilbert space using sequential projectio1ls, in IFAC

_Conf.

Intell. Control Syst.

Sig-$nal$ Process., 2003, pp.

113-118.

[86] M. $\ulcorner 1^{\neg}aki_{7}a\mathfrak{n}^{i}$ and $\backslash _{1}$

I. Yukawa, ‘An $efr_{\grave{1}C}$ient sparse kernel adaptive filtering

algo-rithm based on isomorphism between functional subspace atld Euclidean space in

(14)

[87] –, ’‘hﬃcient dictionary-refining kerneladaptivefilterwith fundamental insights

bublnitted for pulvlication.

[88] M. Elad, Spar,se and Redundant Representations: From Theory to Applications in

Signal and Ima.qc Processing. New York: Springer, 2010.

[89] J.-L. Starck, F. Murtagh, and J. M. Fadili, Sparse Image and Signal Processing:

Wavelets, Carvelets, Morphological Diversity. New York: Cambridge University

$Pr(ss$, 2010.

[90] S. $Fou(art$ _{and H.} _Rauhnlt, _{A Mathematical Introduction to Compress}$ive$ Sensing.

Birkh\"auser, 2013.

[91] S. Amari and M. Yukawa, (

(Minkovskian _{gradient for sparse} $optimi/_{\fbox{Error::0x0000}}’dtion’$’ IEEE

J. Selected Topi$(s$ in Signal Process., vol. 4, no.

4:

pp. 576-585, Aug.

2013.

[92] K. Jeong, $A\backslash I$. Yukawa, and S. Amari, $\zeta(Can$ critical-point paths under $1_{p^{-}}$

regularization

$(0<p< 1)$

reach the sparsest leabt squares solutions¿’ _IEEE

Trans. $Infor/r/$_{ation Theory, vol. 69,}

no.

5, $1$)$P\cdot 2960-2968,$ $\backslash _{\perp}/Iay$

2014.

$[9’3]$ M. Yukawa and S. Amari, $l_{p}$-regulaJjized least _{$sq_{11}are$}

$((]<p<1)$

and critical

$pat1_{1}$,“ IEEE $\mathcal{I}$

}$\cdot ar/s$.

Information

Theory, vol. 62, no. 1, pp. 488-502, Jan. 2016.

$[94]\perp\backslash I$. Yukawa nd R. Ishii,

(

(Online _{model selection and leal.ning by} $multik_{C1}\cdot ne1$

adap-$tiv^{Y}$ filtering,” in Proc. EUSIPCO, 2013.

[95] –, “On adaptivity ofonline model selection method based on multikernel

adap-tive filtering in Proc. APSIPA Annual Summit and Conference, 2013.

[96] O. Toda and M. Yukawa, Online $nl(del$_-selection _{nd learning for nonlinear}

esti-nlation })ased on nnlltikernel adaptive filtering $sub_{1}$ itted for publication.

[97] M. Kasparick, R. L.

G.

Cavalcante, _S. Valentin, S. Stanczak, and M. Yukawa,

Kelnel-based adaptive online reconstruction of coverage maps with side

informa-tion IEEE Tranb. Vehicular Technology, accepted.

[98] D. G. Luenlverger, 0ptimization by Vector Space Methods. New York: Wiley, 1969.

[99] H. Q. Minh, “Some $p^{lO}$perties of Gaussian reproducing kernel Hilbert spaces and

their implications for function approximation and learning theory,” Constr. Approx.,

vol. 32, no. 2, pp. 307 $338_{7}$ Oct. 2010.

[100] R. $Vc^{\Delta}rt$ and J. P. Vert, “Consistency and convergence rates ofone class SVMs and

(15)

[101] I. Steinwart, D. Hush, and

C.

Scovel, $(\langle An$explicit descriptionof the reprodncing

kcr-nel Hilbert spaces ofGaussian RBF kernels IEEE Trans.

_Inform.

Theory, vol. 52,

no.

10, pp. 4635-4643, Oct. 2006.

$\lfloor 102]$ A. Tanaka, H. Imai, M. Kudo, and M. Miyakoshi, ($(Th_{C^{\lrcorner}}or$

tical analyses on a clamss

of nested $RKHS’s,$’

in Proc. IEEE ICASSP, 2011, pp. 20722075.

Departinent ofElectronics and Electrical Engineering

$K(^{3}io$ Universitv

Kanagawa $223-8_{0}^{\ulcorner}22$

JAPAN

$E$-mail address:

[email protected]