# A Stochastic Total Least Squares Solution of Adaptive Filtering Problem

Authors: Shazia Javed; Noor Atinah Ahmad
Journal: The Scientific World Journal
 (2014)

---

## Abstract

An efficient and computationally linear algorithm is derived for total least
squares solution of adaptive filtering problem, when both input and output signals
are contaminated by noise. The proposed total least mean squares (TLMS) algorithm
is designed by recursively computing an optimal solution of adaptive TLS problem by
minimizing instantaneous value of weighted cost function. Convergence analysis of the
algorithm is given to show the global convergence of the proposed algorithm, provided that
the stepsize parameter is appropriately chosen. The TLMS algorithm is computationally
simpler than the other TLS algorithms and demonstrates a better performance as compared
with the least mean square (LMS) and normalized least mean square (NLMS) algorithms. It
provides minimum mean square deviation by exhibiting better convergence in misalignment
for unknown system identification under noisy inputs.


---

## Body

## 1. Introduction

Ordinary least squares methods are extensively used in many signal processing applications to extract the system parameters from input/output data [1, 2]. These methods yield an unbiased solution of adaptive least squares problem having no interference in both inputs and outputs or having interference only in the outputs of the unknown system and clean inputs. However, if interference exists in both input and output of the unknown system or adaptive filtering problem, the ordinary least squares solution gets biased [3].Total least squares (TLS) method [4] is an efficient technique to achieve an unbiased estimate of the system parameters when both input and output are contaminated by noise. Golub and Van Loan [5] provided an analytical procedure to get an unbiased solution of the TLS problem using singular value decomposition (SVD) of data matrices. This technique is extensively used in data processing and control applications [4, 6, 7]. However, application of TLS methods in signal processing is still limited because computation of SVD requires a high complexity of O(N3) for an N×N matrix.TLS solutions of adaptive filtering problem gained importance after the pioneer work done by Pisarenko [8]. He presented an efficient solution of adaptive TLS problem by adaptively computing the eigenvector corresponding to smallest eigenvalue of augmented input/output signal’s autocorrelation matrix. Since then, several algorithms have been proposed based on the adaptive implementations of Pisarenko. The adaptive TLS algorithms proposed in [9–11] are able to achieve an unbiased TLS solution of adaptive filtering problem with a complexity of O(N). However they are sensitive to the correlation properties of input signals and have a drawback of bad performance under correlated inputs.In this paper, an iterative algorithm is presented to find an optimal TLS solution of adaptive FIR filtering problem. A stochastic technique similar to that of least mean squares (LMS) algorithm of adaptive least squares filtering is employed to develop a total least mean squares (TLMS) algorithm for adaptive total least squares problem. Instead of basing the approach on the minimum mean squares error as the LMS algorithm does, the proposed (TLMS) algorithm is based on the total mean squares, obtained by minimizing the weighted cost function for the TLS solution of adaptive filtering problem. The proposed algorithm has maintained theO(N) complexity of adaptive TLS algorithms with an additional quality of having steady state convergence under correlated inputs. Convergence analysis is presented to show the global convergence of the proposed algorithm under all kinds of inputs provided the stepsize parameter is suitably chosen.This paper is outlined as follows: we start with a mathematical formulation of adaptive least squares problem in Section2 and derivation of the TLMS algorithm is given in Section 3, including its convergence analysis in Section 3.1. After that efficiency of the proposed algorithm is tested in Section 4 by applying it for an unknown system identification problem and comparing the results with conventional LMS and normalized LMS (NLMS) algorithms. Concluding remarks are given in Section 5.


## 2. Mathematical Formulation of Adaptive Total Least Squares Problem

Consider an unknown system to be identified by adaptive FIR filter of lengthN and response vector wn, at time n, with an assumption that both input and output are corrupted by an additive white Gaussian noise (AWGN). The noise free input vector an∈ℛN is formed from the input signals u(n), such that
(1)an=[u(n),u(n-1),…,u(n-N+1)]T∈ℛN.
The desired output of the unknown system is then given by
(2)s~(n)=s(n)+Δs(n),
where s(n)=wnTan is system’s output and Δs(n) an added white Gaussian noise of zero mean and variance σΔs2.The primary assumption of an adaptive least squares (ALS) problem is that perturbations occur in the output signals only and that the input signals are exactly known. This assumption is not practical enough, because perturbations due to sampling or modeling or measurement errors affect the input signals too. A sensible choice to overcome such situations is to introduce perturbations in input signals in addition to perturbations of output signals. A schematic diagram of an adaptive filter with perturbed input is depicted in Figure1.Figure 1
An unknown system identification model for adaptive filtering of noisy input signals.IfΔan=[Δu(n),Δu(n-1),…,Δu(n-N+1)]T∈ℛN, denote the perturbations in input vector an, where Δu(n) is an additive white Gaussian noise (uncorrelated from the output noise) of zero mean and variance σΔu2, then noisy input vector is
(3)a~n=an+Δan.
It is clear from Figure 1 that for every input signal u~(n)=u(n)+Δu(n), the filter produces an estimated output y(n)=wnTa~n, which is compared with s~(n) to produce a least squares error signal e(n)=y(n)-s~(n). Define the autocorrelation matrix Ra~n of noisy input vector a~n as Ra~n=E{a~na~nT} and the cross-correlation vector of output signal with a~n as pa~n=E{s~(n)a~n}.At this stage the least squares solution, obtained by minimizing the cost functionJ=E{e2(n)}, gives a poor estimation of the solution of adaptive filtering problem because of the presence of noise in filter input. Casting adaptive filtering problem as total least squares problem can, however, restructure the poor estimation of solution under noisy input [10, 11]. The following definition is made to adopt a more general signal model for ATLS-based filtering.Definition 1 (augmented data vector).
Define an(N+1)×1 augmented data vector z~n as
(4)z~n=[a~nT:s~(n)]T=(a~ns~(n)).An alternate form ofe(n), in terms of augmented data vector of Definition 1, is obtained as follows:
(5)e(n)=y(n)-s~(n)=wnTa~n-s~(n)=[wnT-1](a~ns~(n))=w~nTz~n,
where w~n=[wnT-1]T denote the (N+1)×1 extended parameter vector.The TLS solution of adaptive filtering problem is an eigenvector associated with the smallest eigenvalue of extended autocorrelation matrixR~n:
(6)R~n=E{z~nz~nT}=(Ra~npa~npa~nTσs~(n)2),
where σs~(n)2=E{s~(n)s~(n)}.Instead of minimizing the mean square errorE{e2(n)}, adaptive total least squares problem is concerned with minimizing the total mean square error E{η2(n)} and cost function J(w~n)=E{e2(n)}, where the total error η(n) is given by
(7)η(n)=e(n)w~nTw~n=w~nTz~nw~nTw~n=z~nTw~nw~nTw~n.The TLS cost functionJ~(w~n) is then defined in terms of total error as
(8)J~=E{η2(n)}=E{w~nTz~nz~nTw~nw~nTw~n}=w~nTR~nw~nw~nTw~n.
The adaptive total least squares problem is a minimization problem of the form [10, 11]:
(9)minw~n∈ℛN+1J~=minw~n∈ℛN+1w~nTR~nw~nw~nTw~n.Note that an optimal solutionwopt of the TLS problem (9) is an eigenvector corresponding to the smallest eigenvalue of R~n. In practice SVD technique is used to solve TLS problems since it offers lower sensitivity to the computational errors; however, it is computationally expensive [5]. An alternate choice to estimate eigenvector corresponding to smallest eigenvalue is to use an adaptive algorithm [1, 2].


## 3. Derivation of Total LMS Algorithm for Adaptive Filtering Problem

In adaptive least squares problem, conventional LMS algorithm is a steepest descent method which uses an instantaneous cost functionJ=e2(n) for computation of gradient vector [1]. Using a similar implementation in TLS problem, the total LMS (TLMS) algorithm is obtained by having an instantaneous estimate of the cost function (8) as   J~=η2(n). The recursive update equation of TLMS algorithm is then given as
(10)w~n+1=w~n-μ∇w~nJ~,
where μ is the stepsize parameter or convergence parameter. Note that
(11)∇w~nJ~=∂∂w~n(η(n)2)=2η(n)∂∂w~nη(n)=2η(n)∂∂w~n(w~nTz~nw~nTw~n)=2η(n)w~nTw~n{z~nw~nTw~n-w~nTz~nw~nw~nTw~n}=2η(n)(w~nTw~n)3/2{z~n·w~nTw~n-w~nTz~n·w~n}.
Using e(n)=z~nTw~n=w~nTz~n and ∥w~n∥=w~nTw~n, then above equation becomes
(12)∇w~nJ~=2∥w~n∥4{∥w~n∥2e(n)·z~n-e(n)2·w~n}.
Substituting (12) in (10), the updated equation of TLMS algorithm becomes
(13)w~n+1=w~n+2e(n)·μ∥w~n∥4{e(n)·w~n-∥w~n∥2z~n}.
Once w~n+1 is computed using (13), the TLS solution update wn+1 is obtained by the following formula:
(14)wn+1=-w~n+1(1:N)w~n+1(N+1).
The detailed TLMS algorithm is summarized in Table 1. A complexity measure of the algorithms shows that it is a computationally linear algorithm, requiring a total of 6N+9 multiplications/divisions per iteration. This computational simplicity of adaptive TLMS algorithm makes it a better choice than computationally expensive SVD based TLS algorithm, which requires 6N3 computations per iteration [5].Table 1
LMS-total (TLMS) algorithm for adaptive filtering.
Algorithm
×
/
÷
+
/
-
Initialization
wo=0
…
…
w~o=[woT-1]T
…
…
Update
forn=0,1,2,…
z~n=[a~nT:s~(n)]T
…
…
e(n)=w~nTz~n
N
+
1
N
normsq=w~nTw~n
N
+
1
N
w
~
n
+
1
=
w
~
n
+
2
μ
e
(
n
)
norm
sq
2
{
e
(
n
)
·
w
~
n
-
norm
sq
·
z
~
n
}
3
N
+
7
2
N
+
2
wn+1=-w~n+1(1:N)w~n+1(N+1)
N
…
Total
6
N
+
9
4
N
+
2


### 3.1. Convergence Analysis

In (13), inner product with z~n yields,
(15)w~n+1Tz~n=(w~n+2e(n)·μ∥w~n∥4{e(n)·w~n-∥w~n∥2z~n})Tz~n=w~nTz~n+2e(n)·μ∥w~n∥4{e(n)·w~nTz~n-∥w~n∥2z~nTz~n}=e(n)+2e(n)·μ∥w~n∥4{|e(n)|2-∥w~n∥2∥z~n∥2}=e(n)+2e(n)·μ∥w~n∥2{|η(n)|2-∥z~n∥2}.
Since e(n)=w~nTz~n, Cauchy-Schwarz inequality [12] gives
(16)|e(n)|2≤∥w~n∥2∥z~n∥2;
that is,
(17)|e(n)∥w~n∥|2≤∥z~n∥2,|η(n)|2≤∥z~n∥2,|η(n)|2-∥z~n∥2≤0.
Let δn=∥z~n∥2-|η(n)|2≥0 then (15) becomes:
(18)w~n+1Tz~n=e(n)+2e(n)·μ∥w~n∥2{-δn}={1-2μδn∥w~n∥2}e(n)
or,
(19)w~n+1Tz~n={1-2μδn∥w~n∥2}w~nTz~n.
Since z~n≠0,
(20)w~n+1={1-2μδn∥w~n∥2}w~n
which shows that {w~n} is a geometric progression. It would converge to an optimal solution if
(21)|1-2μδn∥w~n∥2|<1
or
(22)0<μ∥w~n∥2<1δn.
This shows that the proposed algorithm is a variable stepsize algorithm, with μ~=μ/∥w~n∥2. An appropriate way to choose μ is to initialize the algorithm such that ∥wo-wopt∥ is less than 2∥wopt∥ [13]. According to this result for wo=0, ∥w~o∥=1 and μ~=μ, while δo=∥z~n∥2-s~(n)>0.


## 3.1. Convergence Analysis

In (13), inner product with z~n yields,
(15)w~n+1Tz~n=(w~n+2e(n)·μ∥w~n∥4{e(n)·w~n-∥w~n∥2z~n})Tz~n=w~nTz~n+2e(n)·μ∥w~n∥4{e(n)·w~nTz~n-∥w~n∥2z~nTz~n}=e(n)+2e(n)·μ∥w~n∥4{|e(n)|2-∥w~n∥2∥z~n∥2}=e(n)+2e(n)·μ∥w~n∥2{|η(n)|2-∥z~n∥2}.
Since e(n)=w~nTz~n, Cauchy-Schwarz inequality [12] gives
(16)|e(n)|2≤∥w~n∥2∥z~n∥2;
that is,
(17)|e(n)∥w~n∥|2≤∥z~n∥2,|η(n)|2≤∥z~n∥2,|η(n)|2-∥z~n∥2≤0.
Let δn=∥z~n∥2-|η(n)|2≥0 then (15) becomes:
(18)w~n+1Tz~n=e(n)+2e(n)·μ∥w~n∥2{-δn}={1-2μδn∥w~n∥2}e(n)
or,
(19)w~n+1Tz~n={1-2μδn∥w~n∥2}w~nTz~n.
Since z~n≠0,
(20)w~n+1={1-2μδn∥w~n∥2}w~n
which shows that {w~n} is a geometric progression. It would converge to an optimal solution if
(21)|1-2μδn∥w~n∥2|<1
or
(22)0<μ∥w~n∥2<1δn.
This shows that the proposed algorithm is a variable stepsize algorithm, with μ~=μ/∥w~n∥2. An appropriate way to choose μ is to initialize the algorithm such that ∥wo-wopt∥ is less than 2∥wopt∥ [13]. According to this result for wo=0, ∥w~o∥=1 and μ~=μ, while δo=∥z~n∥2-s~(n)>0.


## 4. Application of TLMS Algorithm in System Identification

To examine the performance of proposed TLMS algorithm, an unknown system identification model, shown in Figure2, is used.Figure 2
An unknown system identification model for adaptive filtering of correlated noisy signals.A white Gaussian input signal of varianceσ2=1 is passed through a coloring filter with frequency response [1]:
(23)H(z)=1-α21-αz-1,
where |α|<1, α is a correlation parameter and controls the eigenvalue spread of input signals. α=0 corresponds to the case when eigenvalue spread of input signals is close to 1, and eigenvalue spread increases with an increase in the value of α.A white Gaussian noise of SNR = 30 dB is added in the input signalu(n) to get noisy signal u~(n), and an output signal s~(n) is obtained by corrupting the output signal s(n) with an additive white Gaussian noise of SNR 30 dB. Proposed TLMS algorithm is compared with LMS and NLMS algorithms of [1] to get an FIR vector for a filter of length N=10. Least squares misalignment ∥wn-wopt∥ is compared with the total least squares misalignment ∥wn-wopt∥/w~nTw~n, and simulations results are recorded for 2000 iterations with an ensemble average of 1000 independent runs.


### 4.1. Convergence Behavior Corresponding to Stepsize Parameterμ

Although TLMS algorithm converges for all values ofμ, satisfying (22), but steady state convergence TLMS algorithm is observed when stepsize parameter μ is a power of 2. In Figures 3(b)–3(d), four learning curves of total misalignment of TLMS algorithm are shown, corresponding to μ=0.5,0.25,0.125, and 0.0625, and it is observed that robustness increases uniformly with an increase in the value of μ. On the other hand if μ is chosen randomly, then a change in the convergence behavior is random, though Figure 3(a) shows that algorithm still converges.Learning curves of total misalignment of TLMS algorithm.
(a)
Randomly chosenμ, and α=0.3
(b)
μ as power of 2, and α=0.3
(c)
μ as power of 2, and α=0.6
(d)
μ as power of 2, and α=0.9


### 4.2. Convergence Behavior Corresponding to Correlation Parameterα

To check effect of changes in correlation parameterα on the steady state convergence behavior of TLMS algorithm, different simulations are presented in Figure 3, each showing four learning curves of total misalignment of TLMS algorithm corresponding to μ=0.5,0.25,0.125, and 0.0625. In the first two simulations α=0.3 in Figures 3(a) and 3(b), it is 0.6 in Figure 3(c), and 0.9 in Figure 3(d). It is clear from the results of all these simulation curves that increase in correlation of data signals has not affected the steady state performance of the algorithm. Although the convergence speed seems to slow down, but all the curves converge to optimal solution.


### 4.3.  Comparison

Figure4 shows the comparison of misalignment of three algorithms, that is, LMS, NLMS, and TLMS algorithms. The first two compute a least squares solution of adaptive total least squares problem, while the third one computes TLS solution of adaptive total least squares problem. Taking α=0.3, stepsize parameter for LMS algorithm is chosen as 0.015, for NLMS algorithm as 0.3, and for TLMS algorithm, it is 0.25. The results in this simulation show that the convergence of TLMS algorithm increases with an increase in the iteration, and it presents a better solution of adaptive TLS problem.Figure 4
Comparison of TLMS, LMS, and NLMS algorithms.


## 4.1. Convergence Behavior Corresponding to Stepsize Parameterμ

Although TLMS algorithm converges for all values ofμ, satisfying (22), but steady state convergence TLMS algorithm is observed when stepsize parameter μ is a power of 2. In Figures 3(b)–3(d), four learning curves of total misalignment of TLMS algorithm are shown, corresponding to μ=0.5,0.25,0.125, and 0.0625, and it is observed that robustness increases uniformly with an increase in the value of μ. On the other hand if μ is chosen randomly, then a change in the convergence behavior is random, though Figure 3(a) shows that algorithm still converges.Learning curves of total misalignment of TLMS algorithm.
(a)
Randomly chosenμ, and α=0.3
(b)
μ as power of 2, and α=0.3
(c)
μ as power of 2, and α=0.6
(d)
μ as power of 2, and α=0.9


## 4.2. Convergence Behavior Corresponding to Correlation Parameterα

To check effect of changes in correlation parameterα on the steady state convergence behavior of TLMS algorithm, different simulations are presented in Figure 3, each showing four learning curves of total misalignment of TLMS algorithm corresponding to μ=0.5,0.25,0.125, and 0.0625. In the first two simulations α=0.3 in Figures 3(a) and 3(b), it is 0.6 in Figure 3(c), and 0.9 in Figure 3(d). It is clear from the results of all these simulation curves that increase in correlation of data signals has not affected the steady state performance of the algorithm. Although the convergence speed seems to slow down, but all the curves converge to optimal solution.


## 4.3.  Comparison

Figure4 shows the comparison of misalignment of three algorithms, that is, LMS, NLMS, and TLMS algorithms. The first two compute a least squares solution of adaptive total least squares problem, while the third one computes TLS solution of adaptive total least squares problem. Taking α=0.3, stepsize parameter for LMS algorithm is chosen as 0.015, for NLMS algorithm as 0.3, and for TLMS algorithm, it is 0.25. The results in this simulation show that the convergence of TLMS algorithm increases with an increase in the iteration, and it presents a better solution of adaptive TLS problem.Figure 4
Comparison of TLMS, LMS, and NLMS algorithms.


## 5. Conclusion

In this paper, an efficient TLMS algorithm is presented for the total least squares solution of adaptive filtering problem. The proposed algorithm is derived by using cost function of weighted instantaneous error signals and an efficient computation of misalignment in terms of mean squares deviation. TLMS algorithm has better ability to tackle with perturbations of both input and output signals, because it is chiefly derived for the purpose. Since in real life problems, both input and output signals are contaminated by noise, therefore TLMS algorithm has great applicability. Convergence analysis shows that the proposed algorithm has global convergence, provided that the stepsize parameter is chosen appropriately. Furthermore, it is computationally simple and requires onlyO(N) complexity, while other algorithms for TLS problems either require higher complexity or are sensitive to correlation properties of data signals.



---

*Source: 625280-2014-02-03.xml*