Dynamic Systems and Applications 15 (2006) 205-226

CONTINUOUS-TIME ADAPTIVE FILTERING ALGORITHMS USING SIGN OPERATORS

C. ION, G. YIN, F. LIN, AND L.Y. WANG

Department of Mathematics, Wayne State University Detroit, MI 48202 Department of Electrical & ComputerEng., Wayne State University Detroit, MI 48202

ABSTRACT. In this paper, we develop a continuous-time adaptive filtering algorithm. The use of continuous-time algorithms stems from the needs of treating problems with high sampling rates. Under the assumption of uniform mixing signals, we prove the convergence of the sign-regressor algorithm and derive its asymptotic normality. Representation of the asymptotic covariance is also derived. The stability of the algorithm is obtained via the use of Lyapunov function method. In addition, we demonstrate that the use of iterate averaging improves the asymptotic efficiency. AMS (MOS) subject classifications. 62L20, 93E25.

1. INTRODUCTION

In view of the recent progress [4, 25], our main objective here is to develop a continuous-time version of adaptive filtering algorithms using sign operators. Compared with that of the usual LMS algorithms, one of the features of the algorithms considered is its use of the sign operator, resulting in reduced computational complexity. The algorithms are in continuous time. In addition to the mathematical interest, the reasons for considering continuous-time version algorithms stem from the fact that they are good approximations to discrete-time problems when the sampling frequency is very high. In such high sampling rate cases, it is important to establish that the algorithms continue to perform well; see the description given in [17] for least squares types of estimation schemes; see also [24] for related problems in continuous-time stochastic procedures.

Owing to its importance and various applications in adaptive signal processing, learning, and estimation and detection, adaptive filtering algorithms have received much attention; see [6, 8, 13, 16, 21, 22, 23] among others. In addition to the traditional areas of applications such as adaptive control, signal processing, system identification, pattern classifications etc., emerging applications have been found in blind multiuser detection [9], wireless communications [10, 25], and learning [15]. The basic setup of such algorithms is a stochastic recursive procedure. The premise is that given sequences of reference and output signals, one adaptively adjusts a parameter process so that the weighted signals best approximate the reference signals in an appropriate sense. By best approximation, it is meant that a cost function is minimized. To describe the ideas, let us begin with discrete-time problems and consider the following scenario. Suppose that x_{n} and s_{n} are ℝ^{r}-valued output and real-valued reference signals, respectively. If the cost function is taken to be in the mean squares sense, one adaptively adjusts an ℝ^{r}-valued parameter H so that E|H′x_{n} − s_{n}|^{2} is minimized. The resulting algorithm is the so-called LMS algorithm

Received April 30, 2004           1056-2176 $15.00 \begin{matrix}c \\ ◯ \end{matrix}Dynamic Publishers, Inc.

(1.1)  H_{n+1} = H_{n} + a_{n}x_{n}(s_{n} − x′_{n}H_{n}),

where {a_{n}} is a sequence of positive real numbers (step sizes) tending to 0 as n → ∞ and satisfying ∑_{n} a_{n} = ∞. If however, one uses the cost function E|H′x_{n} − s_{n}|, one gets the sign-error algorithm

(1.2)  H_{n+1} = H_{n} + a_{n}x_{n}sign (s_{n} − x′_{n}H_{n}),

where for each y ∈ ℝ,

sign(y) = \begin{cases}1, & if y > 0, \\ −1, & if y < 0, \\ 0, & if y = 0. \end{cases}

Note that the sign-error algorithm is easily implementable having reduced computational complexity compared with the LMS algorithms, whereas LMS uses past information more fully resulting in less variations. It is ideal to develop an algorithm that is close to the performance of LMS with reduced complexity. One of such algorithms is the so-called sign-regressor scheme. It takes the sign of the vector regressor and use it in the recursion. As it was demonstrated, the performance of using sign-regressor algorithms can be further improved via the use of iterate averaging.

In this work, by considering the high sampling cases, we treat continuoustime sign-regressor algorithms. We prove the convergence, ascertain the convergence rate, and demonstrate the improvement of asymptotic efficiency via averaging. As a by-product, we also examine briefly the sign-error algorithms.

The rest of the paper is organized as follows. Section 2 provides the formulation and the algorithms. Asymptotic properties of the algorithms are presented in Section 3. Section 4 deals with constant step algorithms and Section 5 presents sign-error algorithms. Section 6 concludes the paper with a few more remarks. Throughout the paper, we use z′ to denote the transpose of z ∈ ℝ^{ℓ×r} for ℓ, r ≥ 1, and use |z| to denote the norm of z. For notational simplicity, K denotes a generic positive constant whose values may vary for different usages. For a square matrix B, by B > 0 we mean that it is positive definite.

2. ALGORITHMS

As alluded to in the introduction, to take advantage of both the LMS and sign-error algorithms, we treat sign-regressor algorithms in this paper, which takes the sign of the regressor vector componentwise. Suppose that x_{t} ∈ ℝ^{r} and s_{t} ∈ ℝ are sequences of measured output and reference signals, respectively. Assume that the sequence {s_{t}, x_{t}} is stationary. By adjusting the system parameter H ∈ ℝ^{r} adaptively, one aims to make the weighted output H′x_{t} best match the reference signal s_{t} as well as possible so that a cost function is minimized. The use of the sign operator makes the algorithm easily implementable so it is appealing in various applications; see [6, 8] and the references therein for a discrete-time version of the algorithms. Recently, in [4], by treating a sign-error algorithm with randomly generated truncation bounds, we obtained with probability (w.p.1) convergence of the algorithm by assuming only the ergodicity and finite second moments of the signals. The condition used is close to the minimal requirement needed. In addition to proving convergence, we also examined the rate of convergence of the algorithm by weak convergence methods, which was identified as an open problem in the previous work. Local analysis was carried out in the rates of convergence study. In [25], we have suggested an averaging algorithm using iterate averaging ideas of [18, 19] (see also [2, 14, 15]). Asymptotic optimality is obtained; applications to multiuser detection (see [9, 10, 20] and the references therein) has also been investigated. In this paper, we will examine sign-regressor algorithms, which have reduced complexity in comparison to the LMS algorithm and better performance than the signerror algorithm [4].

Consider the following algorithm

(2.1)  \begin{matrix}Ḣ_{t} = a_{t}sgn(x_{t})(s_{t} − x′_{t}H_{t}), \\ Ĥ_{t} = \frac{1}{t} ∫_{0}^{t} H_{u}du, \end{matrix}

where

a_{t} ≥ 0, a_{t} → 0 as t → ∞, and ∫_{0}^{∞} a_{t}dt = ∞,
∫_{1}^{∞} a_{t}^{2}(log_{2} t)^{2}dt < ∞,

and

sgn(x) = (sign(x_{1}), …, sign(x_{r}))′.

For asymptotic analysis purposes, we need the following assumptions.

(A) The sequence {s_{t}, x_{t}} is stationary such that (a) Esgn(x_{0})x′_{0} = D, Esgn(x_{0})s_{0} = b;

(b) −D is Hurwitz (all eigenvalues have negative real parts);

(c) the sequence {s_{t}, x_{t}} is bounded and uniformly mixing with mixing measure φ_{t} satisfying ∫_{0}^{∞} φ_{t}^{1/2}dt < ∞. [For a definition of the mixing measure φ_{t}, see [1, p. 166] or [5, p. 348].] Remark 2.1. The conditions cover a large class of random processes. Condition (A) (b) is a stability requirement. Such a condition is needed in establishing tightness of iterates. Condition (A) (c) focuses on uniform mixing processes. One can deal with martingale difference processes or moving averaging processes with finite lags as treated in [23]. Although for brevity, we will not dwell on it here.

3. ASYMPTOTIC RESULTS

In what follows, we shall concern ourselves with the convergence and asymptotic efficiency of the algorithm. Along this line, we also obtain the rate of convergence of the algorithm. The entire section is divided into three subsections. The first subsection is concerned with convergence of the algorithm, the second one concentrates on asymptotic normality, and the third one presents asymptotic efficiency and optimality.

3.1. Convergence. To study the asymptotic properties we first prove H_{t} → H_{∗} w.p.1.

Theorem 3.1. Under (A), both H_{t} and Ĥ_{t} converge to H_{∗} = D^{−1}b w.p.1 as t → ∞.

We will use the ODE method to obtain the result. This method combines analytic techniques with probability arguments. It uses compactness in an essential way. Loosely, as time increases the effects of the noise will be averaged out, and the sequence of iterates will eventually follow the “mean trajectory.” Working with a sequence of functions in an appropriate function space, we first show that the underlying sequence is uniformly bounded and equicontinuous. Then we use Arzela-Ascoli theorem to extract a convergent subsequence. Next we show that the limit satisfies a certain ordinary differential equation. Finally, by using stability of the ODE, we show that the sequence of iterates tends to the asymptotically stable equilibrium point of the ODE. Proof. First define a noise sequence

(3.1)  ξ_{t} = sgn(x_{t})s_{t} − sgn(x_{t})x′_{t}H_{∗}.

One of the crucial steps in applying the ODE method is to show that the noise is averaged out in a suitable way. To be more specific, define

(3.2)  α(t) = ∫_{0}^{t} a_{s}ds, β(t) = α^{−1}(t).

We claim that

(3.3)  lim_{n→∞} P (sup_{j≥n} max_{t≤T} | ∫_{α(jT)}^{α(jT +t)} a_{s}ξ_{s}ds| ≥ η) = 0,

for some T > 0 and all η > 0. Note that by (20.23) of [1],

|Eξ′_{s}ξ_{t} − Eξ′_{s}Eξ_{t}| ≤ 2φ_{t−s}^{1/2}E^{1/2}|ξ_{s}|^{2}E^{1/2}|ξ_{t}|^{2}.

Thus,

E |∫_{0}^{∞} a_{t}ξ_{t}dt|^{2}

= E ∫_{0}^{∞} ∫_{0}^{∞} a_{t}a_{s}Eξ′_{s}ξ_{t}dsdt

≤ K ∫_{0}^{∞}(a_{s}^{2} + a_{t}^{2})ds ∫_{s}^{∞} |Eξ′_{s}ξ_{t} − Eξ′_{s}Eξ_{t}|dt

≤ K ∫_{0}^{∞} a_{s}^{2}ds ∫_{s}^{∞} φ_{t−s}^{1/2}dt ≤ K.

As a result, the conditions in [12, Theorem 2.3.4] are verified. By virtue of that theorem, condition (3.3) is verified. According to Theorem 7.1 of Kushner and Yin [15, p. 190], the recurrence condition, namely, “for each 0 < ρ < 1, there exists a compact set R_{ρ} such that for large t, H_{t} ∈ R_{ρ} i.o. with probability at least ρ” needs to be verified. A sufficient condition that guarantees the recurrence is: {H_{t}} is bounded in probability (or tight). Therefore, we need only verify that for any ε > 0, there is a K_{ε} such that

P (sup_{t} |H_{t}| ≥ K_{ε}) ≤ ε.

By Tchebyshev’s inequality, this can be achieved if sup_{t} E|H_{t}|^{2} < ∞. Thus, we need only verify the finite second moment condition, which can be done by using the perturbed Lyapunov function method. Since we will prove another results (in fact sharper bounds) via perturbed Lyapunov function methods, we omit the verbatim proof here for brevity.

Once the recurrence condition is verified, [15, p. 190] implies that sup_{t} |H_{t}| < ∞ w.p.1. Thus the uniform (in t) boundedness of the dynamic system is established. The rest of the proof follows essentially the same as in [12, Theorem 2.3.3]. Thus we have H_{t} → H_{∗} w.p.1 as t → ∞. The definition of Ĥ_{t} implies that Ĥ_{t} → H_{∗} w.p.1 as well.

Remark 3.2. Intuitively, corresponding to algorithm (2.1), there is an associated ordinary differential equation

(3.4)  ḣ = b − Dh.

The stationary point of the ODE is exactly H_{∗}, which is the optimal weight vector we are searching for.

3.2. Asymptotic Normality. Next, we consider the asymptotic distribution of the sign-regressor algorithm. Following the approach of [15, Chapter 10], our analysis consists of two parts. In the first part, we derive an upper bound on the estimation error E|H_{t} − H_{∗}|^{2}. In the second part, we show that a suitably scaled sequence converges to the solution of a stochastic differential equation. In fact we obtain a more interesting functional invariance theorem. In what follows, we will use a_{t} = 1/t^{γ}, 2/3 < γ < 1 as the step size of the algorithm in (2.1).

Take for instance, a_{t} = 1/t^{γ} with 0 < γ < 1. For stochastic recursive algorithms, the rate of convergence is concerned with a centered and scaled sequence u_{t} = t^{κ}(H_{t} − H_{∗}). The definition of the rate of convergence can be stated as: Find the largest κ such that u_{t} has a nontrivial limit in an appropriate sense; see [15, Chapter 10] for more details. The largest κ together with the corresponding asymptotic covariance gives us the rate of convergence. The scaling factor reveals how the errors vary with respect to t, and the asymptotic covariance gives the variation of the centered sequence.

Remark 3.3. The sequence {1/t^{γ}; 2/3 < γ < 1} is referred to as a sequence of slowly varying gains since it goes to 0 slower than O(1/t). Note that the use of larger than O(1/t) step sizes forces the iterates to move towards a neighborhood of the true parameter H_{∗} faster than that of using step sizes of the order O(1/t). Nevertheless, a larger step size produces more variations. To reduce variations due to noise, we take an iterate average.

3.2.1. Estimate of E|H_{t} − H_{∗}|^{2}. To carry out the analysis we now need to verify that with appropriate scaling, the sequence of estimation errors {H_{t} − H_{∗}} is bounded (tight) in some appropriate sense. As a preamble for further study, first a order of magnitude estimate or a stability result on {H_{t}} is proved. The technique of perturbed Lyapunov functions is employed here. To obtain the desired estimate we add a number of small perturbations to the Lyapunov function so that they will result in needed cancellations. For future use, define H̃_{t} = H_{t} − H_{∗}. Then

(3.5)  ˙  H̃_{t} = −\frac{1}{t^{γ}} DH̃_{t} + \frac{1}{t^{γ}} (D − sgn(x_{t})x′_{t})H̃_{t} + \frac{1}{t^{γ}} ξ_{t}.

First, we establish how the centered estimation errors vary with respect to t. To obtain the desired estimate, define V (H̃) = (H̃′H̃)/2.

Theorem 3.4. Assume (A). Then EV (H̃_{t}) = O(1/t^{γ}).

Proof. Henceforth, we use E_{t} to denote the conditional expectation with respect to F_{t}, the σ-algebra generated by {H_{0}, s_{u}, x_{u}, u ≤ t}. Note that

(3.6)  \begin{aligned}\frac{d}{dt}V (H̃_{t}) & = V′_{H}(H̃_{t}) ˙H̃_{t} + ∫_{0}^{1} ˙ H̃′_{t}V_{HH}(H̃_{t} + s ˙H̃_{t}) ˙H̃_{t}ds \\ & = H̃′_{t} [−\frac{1}{t^{γ}} DH̃_{t} + \frac{1}{t^{γ}} (D − sgn(x_{t})x′_{t})H̃_{t} + \frac{1}{t^{γ}} ξ_{t}] \\ & +O(t^{−2γ})(1 + V (H̃_{t})). \end{aligned}

To proceed, we introduce two perturbations of the Lyapunov function V (·) as

(3.7)  \begin{matrix}V_{1}(H̃, t) = ∫_{t}^{∞} \frac{1}{s^{γ}} E_{t}H̃′ψ_{s}H̃ds, \\ V_{2}(H̃, t) = ∫_{t}^{∞} \frac{1}{s^{γ}} E_{t}H̃′ξ_{s}ds, \end{matrix}

where

ψ_{t} = D − sgn(x_{t})x′_{t}.

These perturbations are small in magnitude and result in the desired cancellations. Noting that ψ_{t} is ϕ-mixing with zero mean, by virtue of the well-known mixing inequality (see [1, 5]),

∫_{t}^{∞} E|E_{t}ψ_{s}| = ∫_{t}^{∞} E|E_{t}ψ_{s} − Eψ_{s}|ds
≤ K ∫_{t}^{∞} ϕ_{s−t}ds
< ∞

for each H̃,

(3.8)  \begin{aligned}E|V_{1}(H̃, t)| & ≤ K \frac{|H̃|^{2}}{t^{γ}} ∫_{t}^{∞} E|E_{t}ψ_{s}|ds \\ & = O(\frac{1}{t^{γ}})(1 + V (H̃)). \end{aligned}

Similarly, since ξ_{t} is ϕ-mixing with zero mean,

(3.9)  \begin{aligned}E|V_{2}(H̃, t)| & ≤ K \frac{|H̃|}{t^{γ}} ∫_{t}^{∞} E|E_{t}ξ_{s}|ds \\ & = O(\frac{1}{t^{γ}})(1 + V (H̃)). \end{aligned}

Thus, the perturbations are small (in mean or L_{1} sense). We next show that the desired cancellations take place. In fact, because of the boundedness and the mixing inequalities,

(3.10)  \begin{matrix}\frac{d}{dt}EV_{1}(H̃_{t}, t) = −\frac{1}{t^{γ}} EH̃′_{t}ψ_{t}H̃_{t} + O(\frac{1}{t^{2γ}})(1 + EV (H̃_{t})) \\ \frac{d}{dt}EV_{2}(H̃_{t}, t) = −\frac{1}{t^{γ}} EH̃′_{t}ξ_{t} + O(\frac{1}{t^{2γ}}). \end{matrix}

Define

W (H̃_{t}, t) = V (H̃_{t}) + V_{1}(H̃_{t}, t) + V_{2}(H̃_{t}, t).

The Hurwitz assumption on −D implies that there is a λ such that

H̃′_{t}(−D)H̃_{t} ≤ −λV (H̃_{t}).

Using the estimates obtained thus far,

(3.11)  \begin{aligned}\frac{d}{dt}EW (H̃_{t}, t) & ≤ −\frac{λ}{t^{γ}} EV (H̃_{t}) + O(\frac{1}{t^{2γ}})(1 + EV (H̃_{t})) \\ & ≤ −\frac{λ}{t^{γ}} EW (H̃_{t}, t) + O(\frac{1}{t^{2γ}})(1 + EW (H̃_{t}, t)) \\ & ≤ −\frac{λ_{0}}{t^{γ}} EW (H̃_{t}, t) + O(\frac{1}{t^{2γ}}), \end{aligned}

for some 0 < λ_{0} < λ. Solving this differential inequality yields

(3.12)  \begin{aligned}EW (H̃_{t}, t) ≤ & e^{\frac{−λ_{0}}{1−γ} t^{1−γ}}EW (H̃_{0}, 0) \\ & +K ∫_{0}^{t} \frac{1}{s^{2γ}} e^{\frac{−λ_{0}}{1−γ} (t^{1−γ}−s^{1−γ})}ds. \end{aligned}

Using integration by parts we obtain the following estimate

(3.13)  \begin{matrix}∫_{0}^{t} \frac{1}{s^{2γ}} e^{\frac{−λ_{0}}{1−γ} (t^{1−γ}−s^{1−γ})}ds \\ = \frac{1}{λ_{0}s^{γ}} e^{\frac{−λ_{0}}{1−γ} (t^{1−γ}−s^{1−γ})}|_{0}^{t} + ∫_{0}^{t} \frac{γ}{λ_{0}s^{γ+1}} e^{\frac{−λ_{0}}{1−γ} (t^{1−γ}−s^{1−γ})}ds \\ = O(\frac{1}{t^{γ}}). \end{matrix}

Then,

EW (H̃_{t}, t) = O(\frac{1}{t^{γ}}).

Finally, applying (3.8) and (3.9) again, we obtain

EV (H̃_{t}) = O(\frac{1}{t^{γ}}).

This concludes the proof.

3.2.2. Asymptotic Normality. In order to further study the rate of convergence, define

(3.14)  \overline{H}_{t} = \frac{1}{t} ∫_{0}^{t} H̃_{s}ds,

and consider the scaled sequence \sqrt{t} \overline{H}_{t}. Our goal is to show that \sqrt{t} \overline{H}_{t} is asymptotically normal with the optimal (“smallest”) covariance. Choose v so that v = v(t), v(t) → ∞ but v(t)/\sqrt{t} → 0, as t → ∞. Solving the differential equation (3.5) yields

(3.15)  \begin{aligned}H̃_{t} & = e^{\frac{−D}{1−γ} (t^{1−γ}−v^{1−γ})}H̃_{v} \\ & + ∫_{v}^{t} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (t^{1−γ}−s^{1−γ})}ξ_{s}ds \\ & + ∫_{v}^{t} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (t^{1−γ}−s^{1−γ})}(D − sgn(x_{s})x′_{s})H̃_{s}ds. \end{aligned}

Using (3.15), (3.16)

\sqrt{t} \overline{H}_{t} = \frac{1}{\sqrt{t}} ∫_{0}^{v} H̃_{s}ds + \frac{1}{\sqrt{t}} ∫_{v}^{t} e^{\frac{−D}{1−γ} (u^{1−γ}−v^{1−γ})}H̃_{v}du

+\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (u^{1−γ}−s^{1−γ})}ξ_{s}dsdu

−\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (u^{1−γ}−s^{1−γ})}(sgn(x_{s})x′_{s} − D)H̃_{s}dsdu.

We next show that three of the terms (the first, the second, and the fourth terms) on the right-hand side tend to 0 in probability. That is, they are asymptotically unimportant. First, since H̃_{t} is bounded w.p.1,

(3.17)  E |\frac{1}{\sqrt{t}} ∫_{0}^{v} H̃_{s}ds| ≤ K \frac{v}{\sqrt{t}} → 0 as t → ∞

by the choice of v. By the stability of −D, |exp(−Dt)| ≤ K exp(−λt) for some λ > 0. Letting λ_{1} = λ/(1 − γ), we can derive a bound for the second term on the right-hand side of (3.16):

(3.18)  \begin{matrix}E |\frac{1}{\sqrt{t}} ∫_{v}^{t} e^{\frac{−D}{1−γ} (u^{1−γ}−v^{1−γ})}H̃_{v}du| ≤ \frac{K}{\sqrt{t}} ∫_{v}^{t} e^{−λ_{1}(u^{1−γ}−v^{1−γ})}du \\ = \frac{K}{\sqrt{t}} ∫_{0}^{t^{1−γ}−v^{1−γ}} e^{−λ_{1}s}[\frac{1}{1 − γ} (s + v^{1−γ})^{\frac{1}{1−γ} −1}]ds \\ ≤ \frac{K}{\sqrt{t}} ∫_{0}^{t^{1−γ}−v^{1−γ}} e^{−λ_{1}s}[\frac{2^{\frac{1}{1−γ}} − 1}{1 − γ}(s^{\frac{1}{1−γ} −1} + v^{γ})]ds. \end{matrix}

Note that

(3.19)  \frac{K}{\sqrt{t}} ∫_{0}^{t^{1−γ}−v^{1−γ}} e^{−λ_{1}s}s^{\frac{1}{1−γ} −1}ds ≤ \frac{K}{\sqrt{t}}Γ(\frac{1}{1 − γ}).

where Γ(·) is the Gamma function and

(3.20)  \begin{matrix}\frac{1}{\sqrt{t}} ∫_{0}^{t^{1−γ}−v^{1−γ}} e^{−λ_{1}s}v^{γ}ds = \frac{v^{γ}}{\sqrt{t}} ∫_{0}^{t^{1−γ}−v^{1−γ}} e^{−λ_{1}s}ds \\ ≤ \frac{v^{γ}}{\sqrt{t}} ∫_{0}^{t^{1−γ}} e^{−λ_{1}s}ds = \frac{v^{γ}}{\sqrt{t}}(e^{−λ_{1}t^{1−γ}} − 1) \\ ≤ \frac{v^{γ}}{\sqrt{t}}e^{−λ_{1}t^{1−γ}} ≤ \frac{v^{γ}}{\sqrt{t}} ≤ \frac{v}{\sqrt{t}} → 0 as t → ∞. \end{matrix}

Therefore, the second term on the right-hand side of (3.16) goes to zero. As for the third term, we shall proceed as in [24]. By interchanging the order of integrations, we have that

(3.21)  \begin{matrix}\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (u^{1−γ}−s^{1−γ})}ξ_{s}dsdu \\ = \frac{1}{\sqrt{t}} ∫_{v}^{t}(∫_{s}^{t} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (u^{1−γ}−s^{1−γ})}ξ_{s}du)ds. \end{matrix}

Dividing the resulting inner integral in two parts to be evaluated separately we obtain

(3.22)  \frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (u^{1−γ}−s^{1−γ})}ξ_{s}dsdu = \frac{D^{−1}}{\sqrt{t}} ∫_{v}^{t} ξ_{s}ds + o(1),

where o(1) → 0 in probability as t → ∞. We now consider the remaining terms. Similar to the derivation of (3.22) and by Theorem 3.4, (3.23)

lim_{t→∞} E |\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{−D}{1−γ} (u^{1−γ}−s^{1−γ})}ψ_{s}H̃_{s}dsdu|^{2}

= lim_{t→∞} E |\frac{D^{−1}}{\sqrt{t}} ∫_{v}^{t} ψ_{s}H̃_{s}ds|^{2}

≤ lim_{t→∞} \frac{K}{t} ∫_{v}^{t} ∫_{v}^{t} EH̃′_{s}ψ′_{s}ψ_{u}H̃_{u}dsdu

≤ lim_{t→∞} \frac{K}{t} ∫_{v}^{t} EH̃′_{s}ψ′_{s} (∫_{v}^{t} ψ_{u}H̃_{u}du) ds

≤ lim_{t→∞} \frac{K}{t} ∫_{v}^{t} EH̃′_{s}ψ′_{s} (∫_{s}^{t} E_{s}ψ_{u}(H̃_{u} − H̃_{v})du + ∫_{v}^{t} E_{s}H̃_{v}ψ_{u}du) ds

≤ lim_{t→∞} \frac{K}{t} ∫_{v}^{t} EH̃′_{s}ψ′_{s} ∫_{s}^{t} E_{s} ∫_{s}^{u} \frac{1}{τ^{γ}} E_{τ} ψ_{u}sgn(x_{τ})(s_{τ} − x′_{τ} H_{τ})dτduds

≤ lim_{t→∞} K ∫_{v}^{t} \frac{1}{s^{γ}} E^{1/2}|H̃_{s}|^{2} ∫_{v}^{t} E^{1/2}|E_{τ} ψ_{u} − Eψ_{u}|^{2}duds

≤ lim_{t→∞} Kt^{1−3γ/2} ∫_{v}^{t} ϕ^{1/2}(u)du

= 0.

To arrive at the next to the last line above, we have used the inequality (6.6) in [11, p. 82]. Thus, the first part of the following proposition has been proven. The derivation of the second part is similar but is notationally more complex and we shall omit it here.

Proposition 3.5.

(3.24)  \sqrt{t} \overline{H}_{t} = \frac{D^{−1}}{\sqrt{t}} ∫_{0}^{t} ξ_{s}ds + o(1),

where o(1) → 0 in probability as t → ∞. Furthermore, define

(3.25)  τ\sqrt{t} \overline{H}_{t} = Δ_{t}(τ) for each τ ∈ [0, 1].

Then,

(3.26)  Δ_{t}(τ) = \frac{D^{−1}}{\sqrt{t}} ∫_{0}^{tτ} ξ_{s}ds + o(1),

where o(1) → 0 uniformly in τ.

Next, define

(3.27)  ω_{t}(τ) = \frac{1}{\sqrt{t}} ∫_{0}^{tτ} ξ_{s}ds for τ ∈ [0, 1].

Lemma 3.6. As t → ∞, ω_{t}(·) converges weakly to a Brownian motion ω(·) with covariance Στ, where

(3.28)  Σ = ∫_{0}^{∞} Eξ_{0}ξ′_{s}ds + ∫_{0}^{∞} Eξ_{s}ξ′_{0}ds.

Now, we can derive the rate of convergence result which establishes the desired asymptotic optimality.

Theorem 3.7. Assume that the conditions in Proposition 3.5 are satisfied. Then Δ_{t}(·) converges weekly to a Brownian motion Δ(·) such that Δ(τ) = D^{−1}ω(τ) with ω(τ) given by Lemma 3.6. Moreover,

(3.29)  \sqrt{t} \overline{H}_{t} ∼ N(0, D^{−1}Σ(D^{−1})′),

where Σ is as in (3.28).

Proof. Owing to Proposition 3.4 and Lemma 3.5, to derive the first assertion, we need only examine the term D^{−1}ω_{t}(τ). By Lemma 3.5, ω_{t}(·) converges weekly to ω(·). Slutsky’s theorem then yields that D^{−1}ω_{t}(·) converge weekly to D^{−1}ω(·) = Δ(·) which has the covariance D^{−1}Σ(D^{−1})′τ. Then, (3.29) follows by using the weak convergence of Δ_{t}(·) and setting τ = 1.

3.2.3. Asymptotic Optimality. Adaptive estimation has a vast literature. Much work has been devoted to improving the rate of convergence and reducing the asymptotic covariance. The investigation of the issue of asymptotic optimality can be traced back to the early 50’s. One way to achieve asymptotic efficiency is by using step size adaptation. To illustrate, consider an algorithm of the form

Ḣ_{t} = a_{t}sgn(x_{t})(s_{t} − x′_{t}H_{t}),

with step sizes a_{t} = 1/t^{γ} for some 2/3 < γ ≤ 1. Similar to the previous development, it can be shown that t^{γ/2}(H_{t} − H_{∗}) is asymptotically normal. It is clear, by the central limit theorem, among the γ’s given above, the best one is γ = 1. If one uses a matrix-valued parameter Γ and a_{t} = Γ/t, then it can be demonstrated that the asymptotic covariance depends on Γ and that the best choice of Γ is D^{−1}. One may think that the problem is solved. Nevertheless D is usually not available, so additional estimates of D are needed. As a remedy, one constructs an adaptive procedure

Ḣ_{t} = \frac{Γ̂_{t}}{t} sgn(x_{t})(s_{t} − x′_{t}H_{t}),

using a sequence of estimates Γ̂_{t} in lieu of Γ such that as t → ∞, Γ̂_{t} → D^{−1} and H_{t} → H_{∗}, and that

\sqrt{t}(H_{t} − H_{∗}) ∼ N(0, D^{−1}Σ(D^{−1})′),

where Σ is the covariance of the signals involved. That is, the algorithm so constructed is asymptotically optimal. Despite the appealing asymptotic optimality feature, for multidimensional problems these algorithms are difficult to implement since the computation task involved is very intensive no matter what types of procedures are used for estimating Γ. For further discussions, see [15, Chapter 11]. Also, from a computational point of view, one may not wish to use a rapidly decreasing sequence of step sizes such as a_{t} = O(1/t) since this results in a very slow movement in the initial approximation. One wishes that the iterates move to a neighborhood of the true parameter H_{∗} reasonably fast. But larger step sizes result in larger variations and slower rate of convergence. There seems to be a dilemma. Inspired by the iterate averaging method [18, 19], we have used a sequence of step sizes larger than O(1/t) in the estimation together with taking averages of iterates. The use of the averaging approach allows the iterates to get to a vicinity of the true parameter H_{∗} faster, mean while, it yields the best scaling factor \sqrt{t} as well as the smallest possible covariance.

The scaling factor together with the asymptotic covariance constitutes a measure of the rate of convergence of the algorithm. As a consequence of Theorem 3.7 and the results mentioned in the above discussion, the proposed algorithm achieves the optimal rate of convergence and hence is asymptotically efficient.

4. CONSTANT-STEP-SIZE ALGORITHMS

This section is devoted to constant-step-size algorithms of the form

(4.1)  Ḣ_{t} = εsgn(x_{t})(s_{t} − x′_{t}H_{t}),

where ε > 0 is a small parameter. We will assume the same conditions as in (A) hold. Such algorithms are useful when tracking slowly varying parameter variations. In what follows, we illustrate how this algorithm can be analyzed. Now appropriate notion of convergence is in the sense of weak convergence of probability measures [15, Chapters 7 and 8]. We shall not go over the verbatim proof, but rather outline the main ideas.

The functions α(t) and β(t) defined in (3.2) now become α(t) = α^{ε}(t) = εt and β(t) = β^{ε}(t) = t/ε. Define h^{ε}(t) = H_{β^{ε}(t)}. Then h^{ε}(t) = H_{t/ε}. We first note that

E|h^{ε}(t)|^{2} = E|H_{t/ε}|^{2}
= E |ε ∫_{0}^{t/ε} sgn(x_{u})(s_{n} − x′_{u}H_{u})du|^{2}

= ε^{2} ∫_{0}^{t/ε} ∫_{0}^{t/ε} E[sgn(x_{u})(s_{u} − x′_{u}H_{u})]′[sgn(x_{τ})(s_{τ} − x′_{τ} H_{τ})]dudτ

≤ Kε^{2} ∫_{0}^{t/ε} ∫_{0}^{t/ε}(1 + E|H_{u}|^{2} + E|H_{τ} |^{2})dudτ
≤ Kε ∫_{0}^{t/ε}(1 + E|H_{u}|^{2})du.

Then the Grownwall’s inequality yields that

(4.2)  sup_{0≤t≤T} E|h^{ε}(t)|^{2} = sup_{0≤t/ε≤T/ε} E|H_{t/ε}|^{2} ≤ K exp(KT) < ∞.

Using (4.2) and the mixing condition, we can then verify for any t, s > 0, t + s ≤ T, and any δ > 0 with s ≤ δ,

lim_{δ→0} lim sup_{ε→0} E|h^{ε}(t + s) − h^{ε}(t)|^{2} = 0.

Thus by the tightness criterion, {h^{ε}(·)} is tight. By Prohorov’s theorem, we can extract a convergent subsequence with limit h(·). Without loss of generality, we may still denote the subsequence by h^{ε}(·). By Skorohod representation, without loss of generality, we may assume that h^{ε}(·) converges to h(·) w.p.1, and the convergence is uniform on any bounded interval.

We proceed to characterize the limit process. Choose a sequence δ_{ε} → 0 as ε → 0 such that T_{ε} = δ_{ε}/ε → ∞. Observe that via a change of variable (from u to u/ε), (4.3)

\begin{aligned}h^{ε}(t + s) − h^{ε}(t) & = ∫_{t/ε}^{(t+s)/ε} sgn(x_{u})(s_{u} − x′_{u}H_{εu})du \\ & = ∑_{εv_{ε}=t}^{t+s} δ_{ε}[\frac{1}{T_{ε}} ∫_{v_{ε}}^{v_{ε}+δ_{ε}/ε} sgn(x_{u})(s_{u} − x′_{u}h^{ε}(εu))du], \end{aligned}

where v_{ε} → ∞ as ε → 0. Then note that in the integration interval, h^{ε}(εu) changes much slower than the signals. Thus, it can be shown that as εv_{ε} → v, the limit of

\frac{1}{T_{ε}} ∫_{v_{ε}}^{v_{ε}+δ_{ε}/ε} sgn(x_{u})(s_{u} − x′_{u}h^{ε}(εu))du

is the same as that of

\begin{matrix}\frac{1}{T_{ε}} ∫_{v_{ε}}^{v_{ε}+δ_{ε}/ε} sgn(x_{u})(s_{u} − x′_{u}h^{ε}(εv_{ε}))du \\ → b − Dh(v) as ε → 0. \end{matrix}

Thus, (4.3) leads to

h(t + s) − h(t) = ∫_{t}^{t+s}[b − Dh(v)]dv.

Thus the limit h(·) is a solution of (3.4).

Using perturbed Lyapunov function argument similar to that of Theorem 3.4, we can establish that {H_{t}} is tight. Then via a stability argument, we can show that h^{ε}(·+t_{ε}) converges weakly to H_{∗}, where t_{ε} → ∞ as ε → 0. Define H̃ = H − H_{∗}. Then,

EV (H̃_{t}) = O(ε), for t ≥ q_{ε}, where V (H̃) = H̃′H̃/2.

In addition, we analyze sequence of normalized errors, u^{ε}(t) = (H_{t/ε} − H_{∗})/\sqrt{ε} for t/ε ≥ q_{ε}, and prove under suitable conditions u^{ε}(·) converges weakly to u(·), which is the solution of a stochastic differential equation.

5. ITERATE-AVERAGING SIGN-ERROR ALGORITHMS

In this section we examine adaptive filtering algorithms resulted from the minimization of the cost function L(H) = E|s_{t} − H′x_{t}| = E|s_{1} − H′X_{1}|. Then, L_{H}(H) = −E(x_{1}sign(s_{1}−H′x_{1}) =^{def} −f(H), and a recursive algorithm of gradient descent type takes the form

(5.1)  Ḣ_{t} = a_{t}x_{t}sign(s_{t} − H′_{t}x_{t}),

where {a_{t}} is a sequence of step sizes satisfying a_{t} ≥ 0, a_{t} → 0 as t → ∞ and ∫_{0}^{∞} a_{t}dt = ∞. This algorithm is commonly referred to as a sign-error algorithm. As mentioned in the introduction, compared with the well-known LMS algorithm which arises from the use of a mean square cost function, algorithm (5.1) has reduced complexity. However, x_{t}sign(s_{t} − H′x_{t}) as a function of H is not continuous. Thus the analysis of such an algorithm is more difficult to undertake than that of the LMS-algorithm and the conditions posed are stronger. We now study a continuous-time variant of the sign-error algorithm with slowly varying gains and averaging of the iterates (see [25] for the discretetime version):

(5.2)  Ḣ_{t} = \frac{1}{t^{γ}} x_{t}sign(s_{t} − H′_{t}x_{t}), Ĥ_{t} = \frac{1}{t} ∫_{0}^{t} H_{u}du.

The following assumptions, that collect the conditions needed for both convergence and rate of convergence, are needed:

(A1) The sequence {(s_{t}, x_{t})} is stationary such that

(5.3)  E \binom{s_{1}}{x_{1}} (s_{1} x′_{1}) = R̃ > 0,

(A2) The cost function L(H) has a unique minimizer, denoted by H_{∗}. (A3) Use E_{t} to denote the conditional expectation with respect to F_{t}, the

σ-algebra generated by {H_{0}, s_{u}, x_{u}, u ≤ t}.

(a) There is an A_{t} ∈ ℝ^{r×r} such that for each H, (5.4)

f̃_{t}(H) − f̃_{t}(H_{∗}) = A_{t}(H − H_{∗}) + O(|H − H_{∗}|^{2}) a.s., and EA_{t} = A, where f̃_{t}(H) =^{def} E_{t}f_{t}(H) and f_{t}(H) =^{def} x_{t}sign(s_{t} − H′x_{t})

(b) The matrix A is stable (i.e., all of its eigenvalues have negative real parts).

(c) For each t, E_{t}f_{t}(H)f′_{t}(H) is continuous.

(d) {(s_{t}, x_{t})} is a bounded uniformly mixing sequence such that there is a deterministic sequence of real numbers {φ_{t}} satisfying φ_{t} ≥ 0 for each t and ∫_{0}^{∞} φ_{t}^{1/2}dt < ∞ such that for each u ≥ t,

(5.5)  |E_{t}A_{u} − A| ≤ Kφ_{u−t}^{1/2} and |E_{t}f_{u}(H_{∗})| ≤ Kφ_{u−t}^{1/2},

for some K > 0.

Remark 5.1. In the subsequent analysis, we need to consider the quadratic form H̃′AH̃. Condition (A3) (b) above implies that there is a λ > 0 such that H̃′AH̃ ≤ −λV (H̃).

It is interesting to note that although the function f_{t}(H) is not smooth, its conditional expectation can be a smooth function of H so the conditional expectation can be viewed as a smoothing tool. Condition (5.4) indicates that f̃_{t}(H) is locally (near H_{∗}) linearizable. We refer the reader to [25] for a discrete-time counter part for processes verifying the conditions.

Theorem 5.2. Assume (A1-A3). Then EV (H̃_{t}) = O(1/t^{γ}).

220 C. ION, G. YIN, F. LIN, AND L.Y. WANG

Proof. Using H̃ = H − H_{∗}, the recursion in (5.2) can be rewritten as

(5.6) ˙ H̃_{t} = \frac{1}{t^{γ}} x_{t}sign(s_{t} − H′_{t}x_{t}).

Using (A3)(a) and

f_{t}(H) = f_{t}(H_{∗}) + [f_{t}(H) − f_{t}(H_{∗})]

we rewrite the above equation as follows

(5.7) ˙ H̃_{t} = \frac{1}{t^{γ}} f_{t}(H_{∗}) + \frac{1}{t^{γ}} AH̃_{t} + \frac{1}{t^{γ}} [A_{t} − A]H̃_{t} + \frac{1}{t^{γ}} O(|H̃_{t}|^{2}) + \frac{1}{t^{γ}} δM_{t},

where

(5.8)  δM_{t} = [f_{t}(H) − f_{t}(H_{∗})] − [f̃_{t}(H) − f̃_{t}(H_{∗})].

Note that E_{t}δM_{t} = 0. To obtain the desired estimate, define V (H̃) = (H̃′H̃)/2. Note that

(5.9)

\frac{d}{dt}E_{t}V (H̃_{t}) = \frac{1}{t^{γ}} H̃′_{t}E_{t}x_{t}[sign(s_{t} − H′_{t}x_{t}) − sign(s_{t} − H′_{∗}x_{t})]

+\frac{1}{t^{γ}} H̃′_{t}E_{t}f_{t}(H_{∗}) + \frac{1}{2t^{2γ}} E_{t}x′_{t}x_{t}

= \frac{1}{t^{γ}} H̃′_{t}AH̃_{t} + \frac{1}{t^{γ}} H̃′_{t}(A_{t} − A)H̃_{t}

+\frac{1}{t^{γ}} o(|H̃_{t}|^{2}) + \frac{1}{t^{γ}} E_{t}H̃′_{t}f_{t}(H_{∗}) + \frac{1}{2t^{2γ}} E_{t}x′_{t}x_{t}.

To proceed, we introduce perturbations of the Lyapunov function V (·) as

(5.10)  \begin{matrix}V̄_{1}(H̃, t) = ∫_{t}^{∞} \frac{1}{s^{γ}} E_{t}H̃′[A_{s} − A]H̃ds, \\ V̄_{2}(H̃, t) = ∫_{t}^{∞} \frac{1}{s^{γ}} E_{t}H̃′f_{s}(H_{∗})ds. \end{matrix}

By virtue of (5.5),

(5.11)  \begin{aligned}|V̄_{1}(H̃, t)| & ≤ K \frac{(|H̃|^{2} + 1)}{t^{γ}} ∫_{t}^{∞} |E_{t}A_{s} − A|ds \\ & = O(\frac{1}{t^{γ}})(1 + V (H̃)). \end{aligned}

and

(5.12)  \begin{aligned}|V̄_{2}(H̃, t)| & ≤ K \frac{|H̃|}{t^{γ}} ∫_{t}^{∞} |E_{t}f_{s}(H_{∗})|ds \\ & = O(\frac{1}{t^{γ}})(1 + V (H̃)). \end{aligned}

Thus, the perturbations are small. We next show that the desired cancellations take place in the error estimate. Because of the boundedness and (5.5),

(5.13)  \begin{matrix}\frac{d}{dt}E_{t}V̄_{1}(H̃_{t}, t) = −\frac{1}{t^{γ}} H̃′_{t}[A_{t} − A]H̃_{t} + O(\frac{1}{t^{2γ}})(1 + V (H̃_{t})) \\ \frac{d}{dt}E_{t}V̄_{2}(H̃_{t}, t) = −\frac{1}{t^{γ}} H̃′_{t}f_{t}(H_{∗}) + O(\frac{1}{t^{2γ}}). \end{matrix}

According to Remark 5.1, there is a λ > 0 such that H̃′AH̃ ≤ −λV (H̃). It follows that there exist a λ_{0} such that 0 < λ_{0} < λ and

(5.14) (1/t^{γ})H̃′_{t}AH̃_{t} + (1/t^{γ})o(|H̃_{t}|^{2}) + O(1/t^{2γ})V (H̃_{t}) ≤ −\frac{λ_{0}}{t^{γ}} V (H̃_{t}).

Define

W (H̃_{t}, t) = V (H̃_{t}) + V̄_{1}(H̃_{t}, t) + V̄_{2}(H̃_{t}, t).

Putting together the estimates obtained thus far, we obtain

(5.15)  \frac{d}{dt}E_{t}W (H̃_{t}, t) ≤ −\frac{λ_{0}}{t^{γ}} V (H̃_{t}) + O(\frac{1}{t^{2γ}})(1 + E_{t}x′_{t}x_{t})

It follows from (5.11) and (5.12) that

(5.16) \frac{d}{dt}E_{t}W (H̃_{t}, t) ≤ −\frac{λ_{0}}{t^{γ}} E_{t}W (H̃_{t}, t)+O(\frac{1}{t^{2γ}})(1+E_{t}W (H̃_{t}, t)+E_{t}x′_{t}x_{t}).

Taking the expectation in (5.16),

(5.17)  \frac{d}{dt}EW (H̃_{t}, t) ≤ −\frac{λ_{1}}{t^{γ}} EW (H̃_{t}, t) + O(\frac{1}{t^{2γ}}),

for some 0 < λ_{1} < λ_{0}. Solving this differential inequality yields

(5.18)  \begin{aligned}EW (H̃_{t}, t) ≤ & e^{\frac{−λ_{1}}{1−γ} t^{1−γ}}W (H̃_{0}, 0) \\ & +K ∫_{0}^{t} \frac{1}{s^{2γ}} e^{\frac{−λ_{1}}{1−γ} (t^{1−γ}−s^{1−γ})}ds. \end{aligned}

Using integration by parts on the second term above,

(5.19)  \begin{matrix}∫_{0}^{t} \frac{1}{s^{2γ}} e^{\frac{−λ_{1}}{1−γ} (t^{1−γ}−s^{1−γ})}ds \\ = \frac{1}{λ_{1}s^{γ}} e^{\frac{−λ_{1}}{1−γ} (t^{1−γ}−s^{1−γ})}|_{0}^{t} + ∫_{0}^{t} \frac{γ}{λ_{1}s^{γ+1}} e^{\frac{−λ_{1}}{1−γ} (t^{1−γ}−s^{1−γ})}ds \\ = O(\frac{1}{t^{γ}}). \end{matrix}

Then,

EW (H̃_{t}, t) = O(\frac{1}{t^{γ}}).

Furthermore, by applying (5.11) and (5.12) again, we also obtain

EV (H̃_{t}) = O(\frac{1}{t^{γ}}).

This concludes the proof.

With this theorem, the recurrence condition needed for the proof of convergence is verified. Then proceeding as in [12, Theorem 2.3.3] we can prove that H_{t} → H_{∗} and Ĥ_{t} → H_{∗} where H_{∗} satisfies condition (A2). Intuitively, corresponding to algorithm (5.2), there is an associated ordinary differential equation ḣ = f(h). The stationary point of the ODE is exactly H_{∗}, which is the optimal weight vector we are searching for.

Our next goal is to show that the scaled sequence \sqrt{t}(Ĥ_{t}−H_{∗}) = \sqrt{t} \overline{H}_{t}, where \overline{H}_{t} = \frac{1}{t} ∫_{0}^{t} H̃_{s}ds, is asymptotically normal with optimal covariance. We shall not give the verbatim proof, but rather outline the main ideas. Choosing v as in the case of sign-regressor algorithm and solving the differential equation (5.7) yield

(5.20) \begin{aligned}H̃_{t} = e^{\frac{A}{1−γ} (t^{1−γ}−v^{1−γ})}H̃_{v} & + ∫_{v}^{t} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (t^{1−γ}−s^{1−γ})}f_{s}(H_{∗})ds \\ & + ∫_{v}^{t} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (t^{1−γ}−s^{1−γ})}(A_{s} − A)H̃_{s}ds \\ & + ∫_{v}^{t} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (t^{1−γ}−s^{1−γ})}O(|H̃_{s}|^{2})ds \\ & + ∫_{v}^{t} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (t^{1−γ}−s^{1−γ})}δM_{s}ds. \end{aligned}

Then,

(5.21)  \begin{aligned}\sqrt{t} \overline{H}_{t} & = \frac{1}{\sqrt{t}} ∫_{0}^{v} H̃_{s}ds + \frac{1}{\sqrt{t}} ∫_{v}^{t} e^{\frac{A}{1−γ} (u^{1−γ}−v^{1−γ})}H̃_{v}du \\ & +\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (u^{1−γ}−s^{1−γ})}f_{s}(H_{∗})dsdu \\ & +\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (u^{1−γ}−s^{1−γ})}(A_{s} − A)H̃_{s}dsdu \\ & +\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (u^{1−γ}−s^{1−γ})}O(|H̃_{s}|^{2})dsdu \\ & +\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (u^{1−γ}−s^{1−γ})}δM_{s}dsdu. \end{aligned}

As in the proof of Proposition 3.5, we can show that only the third term in the right-hand side of (5.21) is asymptotically important, the others being convergent to zero in probability. For example, using E|H̃_{t}|^{2} = O(t^{−γ}) and interchanging the order of integrations, we can prove that the fifth term of on the right-hand side of (5.21) tends to zero in probability.

(5.22)  \begin{matrix}E |\frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} e^{\frac{A}{1−γ} (u^{1−γ}−s^{1−γ})}O(|H̃_{s}|^{2})| dsdu \\ ≤ \frac{1}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{γ}} |e^{\frac{A}{1−γ} (u^{1−γ}−s^{1−γ})}| O(E|H̃_{s}|^{2})dsdu \\ ≤ \frac{K}{\sqrt{t}} ∫_{v}^{t} ∫_{v}^{u} \frac{1}{s^{2γ}} e^{−λ_{1}(u^{1−γ}−s^{1−γ})}dsdu \\ ≤ \frac{K}{\sqrt{t}} ∫_{v}^{t} \frac{1}{s^{2γ}} (∫_{s}^{t} e^{−λ_{1}(u^{1−γ}−s^{1−γ})}du) ds \\ = O(t^{(1/2)−γ}), \end{matrix}

where λ_{1} is chosen such that λ_{1} = λ/(1−γ), with λ > 0 such that exp(At) ≤ K exp(−λt). Thus, we can derive the following proposition.

Proposition 5.3.

(5.23)  \sqrt{t}\overline{H}_{t} = −\frac{A^{−1}}{\sqrt{t}} ∫_{0}^{t} f_{s}(H_{∗})ds + o(1),

where o(1) → 0 in probability as t → ∞.

We proceed to obtain a functional central theorem or an invariance theorem. The proof is standard (see [1, 5, 15]).

Lemma 5.4. For τ ∈ [0, 1], ω_{t}(τ) = \frac{1}{\sqrt{t}} ∫_{0}^{tτ} f_{s}(H_{∗}) converges weakly to a Brownian motion ω(·) with covariance Στ, where

(5.24)  Σ = ∫_{0}^{∞} Ef_{0}(H_{∗})f′_{s}(H_{∗})ds + ∫_{0}^{∞} Ef_{s}(H_{∗})f′_{0}(H_{∗})ds.

Now, we can derive the rate of convergence result which establishes the desired asymptotic optimality.

Theorem 5.5. Assume that the conditions in Proposition 5.3 are satisfied. Then

B_{t}(τ) = \frac{D^{−1}}{\sqrt{t}} ∫_{0}^{tτ} f_{s}(H_{∗})ds + o(1) in probability,

where o(1) → 0 uniformly in τ, converges weakly to a Brownian motion with covariance Σ^{∗}τ where Σ^{∗} = A^{−1}Σ(A^{−1})′ and Σ is as in (5.24).

Proof.The proof follows from Slutsky’s theorem; see the proof of Theorem 3.7.

As a consequence, the asymptotic normality of \sqrt{t}(Ĥ_{t} − H_{∗}) follows by using the weak convergence and setting τ = 1. We conclude that the averaging approach for sign-error algorithms also leads to asymptotic optimality.

6. FURTHER REMARKS

Several extensions or variants can be considered. We mention some of them briefly. Bounded mixing signals are treated here. Unbounded uncorrelated signals can also be considered, in which case the proofs are much simpler. Such a result can also be extended to moving average processes driven by uncorrelated noise. In addition, unbounded correlated signals can be treated by using a truncation/projection device; see [15], which is almost entirely devoted to projection or truncation algorithms. Only the step size {1/t^{γ}} is considered as the slowly varying gains, more general gain sequences can be considered similar to [3, 14, 15]. One may also consider a variant of the sign-regressor algorithm with averaging in both the iterates and observations given by the following class of integral equations:

\begin{aligned}H_{t} & = \frac{1}{t} ∫_{0}^{t} H_{u}du + \frac{1}{t^{γ}} ∫_{0}^{t} sgn(x_{u})(s_{u} − x′_{u}H_{u})du, \\ & = Ĥ_{t} + \frac{t}{t^{γ}} ŷ_{t}, 2/3 < γ < 1 \end{aligned}

where

Ĥ_{t} = \frac{1}{t} ∫_{0}^{t} H_{u}du, ŷ_{t} = \frac{1}{t} ∫_{0}^{t} sgn(x_{u})(s_{u} − x′_{u}H_{u})du.

Under (A), it can be shown that

\sqrt{t}\overline{H}_{t} = \frac{1}{\sqrt{t}} ∫_{0}^{t}(H_{u} − H_{∗})du ∼ N(0, D^{−1}Σ(D^{−1})′).

Thus, this algorithm is also asymptotically optimal. The additional average of the observations, namely, ŷ_{t} makes the resulting trajectories more smooth; these algorithms are sometimes referred to as smoothed stochastic approximation procedures (see [26] for a discrete-time algorithm). One may also consider L_{p} moment bounds (see [7] and the references therein) associated with the averaging procedures.

ACKNOWLEDGMENT

This research was supported in part by the National Science Foundation, and in part by Wayne State University.

REFERENCES

[1] P. Billingsley, Convergence of Probability Measures, J. Wiley, New York, 1968.

[2] H. F. Chen, Asymptotic efficient stochastic approximation, Stochastics Stochastics Rep., 45 (1993), 1-16.

[3] H. F. Chen, Continuous-time stochastic approximation: convergence and asymptotic efficiency, Stochastics Stochastics Rep., 51 (1994), 111–132.

[4] H. F. Chen and G. Yin, Asymptotic properties of sign algorithms for adaptive filtering, to appear in IEEE Trans. Automat. Control.

[5] S. N. Ethier and T. G. Kurtz, Markov Processes: Characterization and Convergence, J. Wiley, New York, 1986.

[6] E. Eweda, Convergence analysis of the sign algorithm without the independence and Gaussian assumptions, IEEE Trans. Signal Processing, 48 (2000), 2535-2544.

[7] L. Gerencsér, Rate of convergence of recursive estimators, SIAM J. Control Optim., 30 (1992), 1200-1227.

[8] A. Gersho, Adaptive filtering with binary reinforcement, IEEE Trans. Inform. Theory, IT-30 (1984), 191-199.

[9] M. L. Honig, U. Madhow, and S. Verdu, Adaptive blind multiuser detection, IEEE Trans. Inform. Theory, 41 (1995), 944-960.

[10] M.L. Honig and H.V. Poor, Adaptive interference suppression in wireless communication systems, in H.V. Poor and G.W. Wornell, Eds., Wireless Communications: Signal Processing Perspectives, Prentice Hall, 1998.

[11] H. J. Kushner, Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory, MIT Press, Cambridge, MA, 1984.

[12] H.J. Kushner and D.S. Clark, Stochastic Approximation Methods for Constrained and Unconstrained Systems, Springer-Verlag, 1978.

[13] H.J. Kushner and A. Shwartz, Weak convergence and asymptotic properties of adaptive filters with constant gains, IEEE Trans. Inform. Theory IT-30 (1984), 177-182.

[14] H.J. Kushner and J. Yang, Stochastic approximation with averaging of the iterates: optimal asymptotic rate of convergence for general processes, SIAM J. Control Optim. 31 (1993), 1045-1062.

[15] H.J. Kushner and G. Yin, Stochastic Approximation Algorithms and Applications, 2nd Ed., Springer-Verlag, New York, 2003.

[16] O. Macchi and E. Eweda, Convergence analysis of self-adaptive equalizers, IEEE Trans. Inform. Theory, IT-30 (1984), 161-176.

[17] J.B. Moore, Convergence of continuous time stochastic ELS parameter estimation, Stochastic. Process. Appl., 27 (1988), 195-215.

[18] B.T. Polyak, New method of stochastic approximation type, Automat. Remote Control, 51 (1990), 937-946.

[19] D. Ruppert, Stochastic approximation, in Handbook in Sequential Analysis, B.K. Ghosh and P.K. Sen Eds., Marcel Dekker, 503-529, New York, 1991.

[20] S. Verdu, Multiuser detection, in H.V. Poor and J.B Thomas, Eds., Advances in Statistical Signal Processing. JAI Press, Greenwich, CT., 1993.

[21] B. Widrow and S.D. Stearns, Adaptive Signal Processing, Prentice-Hall, Englewood, Cliffs, NJ, 1985.

[22] G. Yin, Asymptotic properties of an adaptive beam former algorithm, IEEE Trans. Inform. Theory, IT-35 (1989), 859-867.

[23] G. Yin, Adaptive filtering with averaging, in G. Goodwin K. Aström and P.R. Kumar, editors, IMA Volumes in Mathematics and Its Applications, Vol. 74, 375-396, Springer-Verlag, 1995.

[24] G. Yin and I. Gupta, On a continuous time stochastic approximation problem, Acta Appl. Math., 33 (1993), 3-20.

[25] G. Yin, V. Krishnamurthy, and C. Ion, Iterate-averaging sign algorithms for adaptive filtering with applications to blind multiuser detection, IEEE Trans. Inform. Theory, IT-49 (2003) 657-671.

[26] G. Yin and K. Yin, Asymptotically optimal rate of convergence of smoothed stochastic recursive algorithms, Stochastics Stochastic Reports, 47 (1994), 21-46.