Stochastic analysis of the least mean fourth algorithm for non-stationary white Gaussian inputs

Abstract

This paper studies the stochastic behavior of the least mean fourth (LMF) algorithm for a system identification framework when the input signal is a non-stationary white Gaussian process. The unknown system is modeled by the standard random-walk model. A theory is developed which is based upon the instantaneous average power and the instantaneous average squared power in the adaptive filter taps. A recursion is derived for the instantaneous mean square deviation of the LMF algorithm. This recursion yields interesting results about the transient and steady-state behaviors of the algorithm with time-varying input power. The theory is supported by Monte Carlo simulations for sinusoidal input power variations.

Appendices

Appendix 1

Justification of (6) and (7)

Justification of (6):

We have

$$\begin{aligned} \hbox {Tr}\left\{ {{R}_{X} ( {n} ){K}_{VV} ( {n} )} \right\} =\sum _{{i=1}}^{N} {{k}_{ i} ( {n} ){r}_{i} ( {n} )} \end{aligned}$$

(45)

where ${k}_{i} ( {n} )$ and ${r}_{i} ( {n} )$ denote the diagonal elements of ${K}_{VV} ( {n} )$ and ${R}_{ X} ( {n} )$, respectively. From (4), ${r}_{i} ( {n} )=\sigma _{X}^2 \left( {{n-i+1}} \right)$.

Now the cross-correlation between two deterministic sequences ${a}_{ i}, {b}_{ i}$ is given by

$$\begin{aligned} {C}_{{a,b}} =\overline{{ab}} -\overline{a} \overline{b} \end{aligned}$$

(46)

where the long-term averages $\overline{a} , \overline{b}$ and $\overline{ab}$ are given by

$$\begin{aligned}&\!\!\!\!\overline{a} ={\hbox {lim}}_{{N}\rightarrow \infty } \frac{1}{{N}}\sum _{{ i=1}}^{N} {{a}_{ i} } ,\quad \overline{b} = {\hbox {lim}}_{{N}\rightarrow \infty } \frac{1}{{N}}\sum _{{ i=1}}^{N} {{b}_{ i} }\,\quad \hbox {and}\, \nonumber \\&\!\!\!\!\overline{{ab}} ={\hbox {lim}}_{{N}\rightarrow \infty } \frac{1}{{N}}\sum _{{ i=1}}^{N} {{a}_{i}{b}_{i}}. \end{aligned}$$

(47)

Consider now the hint given by (46) and (47) for the sequences ${k}_{i}(n)$ and ${r}_{ i} ( {n} )$ in (45). For a fixed time n, ${k}_{i}({n})$ is the mean-square value of the $i$th component of $V(n)$, while ${r}_{i} ({n})({n})$ is the variance of the input signal at time $n-i+1$. Loosely speaking, this implies that ${k}_{ i} ( {n} )$ and ${r}_{ i} ( {n} )$ are independent and thus the covariance ${C}_{{a,b}}$ is equal to zero. Thus, $\overline{ab} = \overline{a} \overline{b}$, and therefore, for sufficiently large N,

$$\begin{aligned} \frac{1}{{N}}\sum _{{ i=1}}^{N} {{k}_{ i} ( {n} ){r}_{ i} ( {n} )} \approx \frac{1}{{N}}\sum _{{ i=1}}^{N} {{k}_{ i} ( {n} )\frac{1}{{N}}\sum _{{ i=1}}^{N} {{r}_{ i} ( {n} )} }. \end{aligned}$$

(48)

To illustrate (48), consider (48) for two extreme cases of slow and fast variations in the input power. For slow variations in the input power, the individual terms ${r}_{ i} \left( {n} \right)$ in (48) will be almost equal. Thus, (48) follows immediately. For fast variations in the input power, ${k}_{ i} ( {n} )$ will have a weak algebraic dependence upon ${r}_{ i} ( {n} )$. This is because ${K}_{VV} ( {n} )$ is a weighted time average of ${R}_{X} \left( {j} \right)$, $j <n$. The weak algebraic dependence of ${k}_{ i} ( {n})$ on ${r}_{ i} ( {n} )$ implies the weak coupling of their time averages, which implies (48).

Finally, Eqs. (45), (48) and (8) imply that

$$\begin{aligned} \hbox {Tr}\left[ {{R}_{x} ( {n} ){K}_{VV} \left( {n} \right) } \right] \approx \varphi ({n})\hbox {Tr}\left[ {{K}_{VV} \left( {n} \right) } \right] . \end{aligned}$$

(49)

Justification of (7):

We have

$$\begin{aligned} \hbox {Tr}\left\{ {{R}_{x}^2 {(n)K}_{VV} {(n)}} \right\} =\sum _{{ i}=1}^{N} {{k}_{ i} {(n)r}_{ i}^2 {(n)}}. \end{aligned}$$

(50)

Using the same reasoning above (48), we obtain

$$\begin{aligned} \frac{1}{{N}}\sum _{{ i}=1}^{N} {{k}_{ i} {(n)r}_{ i}^2 {(n)}} \approx \left[ {\frac{1}{{N}}\sum _{{ i}=1}^{N} {{k}_{ i} {(n)}} } \right] \left[ {\frac{1}{{N}}\sum _{{ i}=1}^{N} {{r}_{ i}^2 {(n)}} } \right] . \end{aligned}$$

(51)

Then, (7) follows from (50) and (51).

Appendix 2

Proof of (19).

For convenience, we drop the time-index n in this appendix. We have

$$\begin{aligned} {E}\left[ {\left( {{X}^{T}{V}} \right) ^{6}{X}^{T}{X}} \right] =\sum _{{ i}=1}^{N} {{F}_{ i} } \end{aligned}$$

(52)

where

$$\begin{aligned} {F}_{ i} ={ E}\left[ {\left( {{X}^{T}{V}} \right) ^{6}{x}_{ i} ^{2}} \right] \end{aligned}$$

(53)

with ${x}_{{ i}}$ being the i-th element of the vector X. From Isserlis’ theorem [19], for zero-mean jointly Gaussian random variables ${a}_{1},{a}_{2},{ \ldots ., }{a}_{7}, {a}_{8}$, we have

$$\begin{aligned} {E}\left[ {{a}_1 {a}_2 {a}_3 {a}_4 {a}_5 {a}_6 {a}_7 {a}_8 } \right] =\sum {\prod {{E[a}_{ i} {a}_{j} ]} } \end{aligned}$$

(54)

over all distinct ways of partitioning ${a}_{1},{a}_{2},\ldots ., {a}_{7}, {a}_{8}$ into pairs. In our case, ${a}_{1}= {a}_{2}= {\ldots }.\,\, {a}_{6} = {a} = {X}^{T}{V}, {a}_{7}= {a}_{8}= {x}_{{ i}}$. The total number of terms in the summation in (54) is 105 terms: 15 terms including E[${a}_{7}{a}_{8}$] and 90 terms not including E[${a}_{7}{a}_{8}$]. Thus,

$$\begin{aligned} {F}_{ i} ={ 15 T}_1 \left( {i} \right) +90{T}_2 \left( {i} \right) \end{aligned}$$

(55)

where

$$\begin{aligned}&\!\!\!\!{T}_1 \left( {i} \right) ={ E}[ {{a}^{2}} ]{ E}[ {{a}^{2}} ]{ E}[ {{a}^{2}} ]{ E}[ {{a}_7 {a}_8} ]\end{aligned}$$

(56)

$$\begin{aligned}&\!\!\!\! {T}_2 \left( {i} \right) ={ E}[ {{a}^{2}} ]{ E}[ {{a}^{2}} ]{ E}[ {{aa}_7 } ]{ E}\left[ {{aa}_7 } \right] . \end{aligned}$$

(57)

From (56),

$$\begin{aligned} {T}_1 \left( {i} \right) =\{{E}[ {( {{X}^{T}{V}} )^{2}} ]\}^{3}{E}[ {{x}_{ i} ^{2}} ]=\{\hbox {Tr}\left( {{K}_{VV} {R}} \right) \}^{3}{E}[ {{x}_{ i} ^{2}} ]. \end{aligned}$$

(58)

Summing (58) over i, we get

$$\begin{aligned} \sum _{{i}=1}^{N} {{T}_1 {(i)}} =\{\hbox {Tr}\left( {{K}_{VV} {R}} \right) \}^{3}\hbox {Tr}\left( {R} \right) \approx {N}\varphi ^{4}({n}){y}^{3}( {n} ) \end{aligned}$$

(59)

where the last equality follows from (6) and the fact that (5) implies that Tr$(R)$ $\approx {N}\varphi ({n})$. From Isserlis’ theorem [19],

$$\begin{aligned} {E}\left[ {{aaa}_7 {a}_7 } \right] ={ E}\left[ {{aa}} \right] { E}\left[ {{a}_7 {a}_7 } \right] +{ 2 E}\left[ {{aa}_7 }\right] { E}\left[ {{aa}_7 } \right] . \end{aligned}$$

(60)

Summing over $i$, the LHS of this equation is the same as Eq. (21), while the first term on the RHS is $E[aa]\hbox {tr}(R)$. Then, (21) and (60) imply that

$$\begin{aligned} 2\psi ({n}){y}\left( {n} \right) \!+\!{ N}\varphi ^{2}({n}){y}\left( {n} \right) \!=\!{ N}\varphi ^{2}({n}){y}\left( {n} \right) \!+\!{ 2}\sum _{{i}={1}}^{N}{{E[aa}_7 {]E[aa}_7 {]}}. \nonumber \\ \end{aligned}$$

(61)

This implies that

$$\begin{aligned} \sum _{{i}={1}}^{N} {{E[aa}_7 {]E[aa}_7 {]}} =\psi ({n}){y(n)}. \end{aligned}$$

(62)

From (57) and (62),

$$\begin{aligned} \sum _{{i}= 1}^{N} {{T}_2 {(i)}}&= \psi ({n}){y}( {n} )\{{E}[{({{X}^{T}{V}} )^{2}} ]\}^{2}\!=\psi ({n}){y}( {n} )\{\hbox {Tr}\left( {{K}_{VV}{R}} \right) \}^{2} \nonumber \\&= \psi ({n})\varphi ^{2}({n}){y}^{3}\left( n\right) . \end{aligned}$$

(63)

Equations (52), (55), (59) and (63) imply (19).