# Fractional Gradient Descent-Based Auxiliary Model Algorithm for FIR Models with Missing Data

Authors: Jia Tang
Journal: Complexity
 (2023)

---

## Abstract

This study proposes a fractional gradient descent (FGD) algorithm for FIR models with missing data. By using the auxiliary model method, the missing data can be obtained. Then, the FGD algorithm is applied to update the parameters of the FIR models. Because of the fractional term in the conventional GD algorithm, the convergence rates of the GD algorithm can be increased. In addition, to avoid the step-size calculation, an Aitken FGD-based auxiliary model algorithm is also introduced. The convergence analysis and simulation examples are provided to show the effectiveness of the proposed algorithms.


---

## Body

## 1. Introduction

The gradient descent (GD) algorithm is a classical method which is widely used in system identification and parameter estimation [1–3]. Its basic idea is to assign a random initial parameter estimate and then force the estimate to move to another better estimate [4–6]. Clearly, the direction and step-size are the two factors in the GD algorithm designing. Owing to the zigzagging nature, the GD algorithm has a quite slow convergence rate [7–9]. To increase the convergence rates, one can modify the GD algorithm through two ways: (1) choose a better direction instead of using the negative direction; (2) calculate a suitable step-size.In the last few decades, there have been lots of modified GD algorithms, e.g., the forgetting factor GD algorithm [10], the multiinnovation GD algorithm [11, 12], the conjugate GD algorithm [13], and the momentum GD algorithm [14]. For example, Fan and Liu proposed a forgetting factor GD algorithm for input nonlinear FIR-MA systems, where the colored noise is transformed into a white noise by using the data filtering method [15]. Chen et al. developed a multidirection GD algorithm for ARX models, such an algorithm establishes a link between the GD and LS algorithms [16]. Xu et al. used a three-stage GD algorithm for exponential autoregressive time-series models [17]. Although these algorithms can increase the convergence rates, they bring other challenging issues: (1) heavy computational efforts, e.g., the multidirection GD algorithm; (2) less confidence of the convergence properties, e.g., the three-stage GD algorithm; and (3) large variance of the parameter estimates, e.g., the forgetting factor GD algorithm.The FGD algorithm proposed in [18, 19] is an outstanding alternative of the GD algorithm. Its basic idea is to add a fractional gradient direction to the GD algorithm [20–22]. With the help of the additional direction, the convergence rates of the GD algorithm are increased. Recently, a two-stage fractional least mean square identification algorithm is proposed for a large-scale linear system; this large-scale system is decomposed into two parts, and these two parts are iteratively identified [23]. Chaudhary et al. developed two FGD algorithms for signal modeling, where these two algorithms require less computational efforts [24]. Xu et al. provided a momentum-based FGD and an adaptive-based FGD algorithm for time-delayed ARX models; these two algorithms have fast convergence rates and less computational efforts [25]. Khan et al. proposed a fractional SGD algorithm for recommender systems, and this algorithm provides fast and accurate recommendations by using a time-varying learning rate [26]. However, the above work assumed that all the data from the models were available.Owing to the network congestion, some data of the dynamic systems are missing [27–29]. Usually, two standard tools are applied to systems with missing data: (1) the lifting technique, e.g., the polynomial transformation algorithm [30], whose key is to transform the system into a lifted system with high order and then estimate the parameters based on all the measurable data; (2) the imputation technique, e.g., the auxiliary model method [31], first estimates the missing data and then updates the parameters based on the measurable data and estimated data. Since the lifting method can enlarge the number of unknown parameters, this study focuses on the imputation method.This study proposes an FGD-based auxiliary model (FGD-AM) algorithm for FIR models with missing data. Based on the auxiliary model method and the FGD algorithm, the missing data and parameters can be iteratively estimated. In addition, to avoid calculating the step-size, an Aitken FGD-AM (A-FGD-AM) algorithm is also proposed. Compared with the traditional algorithms, the method in this study has the following contributions: (1) the method has faster convergence rates; (2) the method does not require calculating the step-size; and (3) the method avoids the matrix inverse calculation.The study is organized as follows. Section2 describes the FIR models with missing data. Section 3 proposes the FGD-AM algorithm. Section 4 gives the A-FGD-AM algorithm. Section 5 provides two simulation examples. Finally, conclusions and future directions are presented in Section 6.


## 2. Problem Statement

First, setup some notations. The norm of a matrixX is defined as X=λmaxXXT; λmaxXXT and λminXXT mean the maximum and minimum eigenvalues of matrix XXT, respectively; the norm of a vector z=z1,z2,…,znT∈Rn is defined as z=∑i=1nzi21/2; the superscript T denotes the matrix transpose.


### 2.1. FIR Model with Missing Data

Consider the following FIR model with missing data:(1)yt=Fzut+vt,where yt and ut are the system output and input, respectively, vt is the noise, and Fz is a polynomial which is written by(2)Fz=f1z−1+f2z−2+⋯+fnz−n.With the development of the communication network and sensor technologies, researchers usually use sensors to collect the data and then transmit them over a communication network. Some data are often missed due to the network congestion. In this study, we assume that some output data are missing, the data at the sampling instantsm1,m2,…,mq are missing, while the data at the other sampling instants t1,t2,…,tp are available. For instance, for the irregular sampling pattern in Figure 1, the available outputs are y0,y1,y3,y6,y10,y15,y16,y21,y28,…, namely, yt0,yt1,yt2,yt3,yt4,yt5,yt6,yt7,…, for t0=0,t1=1,t2=3,t3=6,t4=10,t5=15,t6=16,t7=21,t8=28,…. This is a general framework in which we assume the patterns with irregular sampling outputs availability. Specially, it includes all output availability as special cases when ti+1−ti=1 for all i. For parameter estimation, the number of the measurable data is larger than the number of the unknown parameters, that is p>n.Figure 1
The irregular sampling output.


### 2.2. FIR Model: A Common Model

FIR model is a common model, which can approximate the other kinds of models.


#### 2.2.1. ARX Model

Consider the following ARX model:(3)Azyt=Bzut+vt,which can be simplified as follows:(4)yt=BzAzut+1Azvt.Using the finite impulse response method, we can get(5)Fz=BzAz,=f1z−1+f2z−2+⋯+fpz−p.We define(6)wt=1Azvt.The ARX model can be simplified as the following FIR model:(7)yt=Fzut+wt.


#### 2.2.2. CARMA Model

The CARMA model is written by(8)Azyt=Bzut+Dzvt,which can be simplified as(9)yt=BzAzut+DzAzvt.Let(10)Fz=BzAz,wt=DzAzvt.Then, the CARMA model is simplified as an ARX model.


#### 2.2.3. OE Model

The OE model is written by(11)yt=BzAzut+vt.Let(12)Fz=BzAz,wt=vt.Clearly, the OE model is the same as the ARX model.Remark 1.
Since almost all the other kinds of models can be approximated by an FIR model, we can first estimate the parameters of the FIR model and then recover parameters of the original models.


## 2.1. FIR Model with Missing Data

Consider the following FIR model with missing data:(1)yt=Fzut+vt,where yt and ut are the system output and input, respectively, vt is the noise, and Fz is a polynomial which is written by(2)Fz=f1z−1+f2z−2+⋯+fnz−n.With the development of the communication network and sensor technologies, researchers usually use sensors to collect the data and then transmit them over a communication network. Some data are often missed due to the network congestion. In this study, we assume that some output data are missing, the data at the sampling instantsm1,m2,…,mq are missing, while the data at the other sampling instants t1,t2,…,tp are available. For instance, for the irregular sampling pattern in Figure 1, the available outputs are y0,y1,y3,y6,y10,y15,y16,y21,y28,…, namely, yt0,yt1,yt2,yt3,yt4,yt5,yt6,yt7,…, for t0=0,t1=1,t2=3,t3=6,t4=10,t5=15,t6=16,t7=21,t8=28,…. This is a general framework in which we assume the patterns with irregular sampling outputs availability. Specially, it includes all output availability as special cases when ti+1−ti=1 for all i. For parameter estimation, the number of the measurable data is larger than the number of the unknown parameters, that is p>n.Figure 1
The irregular sampling output.


## 2.2. FIR Model: A Common Model

FIR model is a common model, which can approximate the other kinds of models.


### 2.2.1. ARX Model

Consider the following ARX model:(3)Azyt=Bzut+vt,which can be simplified as follows:(4)yt=BzAzut+1Azvt.Using the finite impulse response method, we can get(5)Fz=BzAz,=f1z−1+f2z−2+⋯+fpz−p.We define(6)wt=1Azvt.The ARX model can be simplified as the following FIR model:(7)yt=Fzut+wt.


### 2.2.2. CARMA Model

The CARMA model is written by(8)Azyt=Bzut+Dzvt,which can be simplified as(9)yt=BzAzut+DzAzvt.Let(10)Fz=BzAz,wt=DzAzvt.Then, the CARMA model is simplified as an ARX model.


### 2.2.3. OE Model

The OE model is written by(11)yt=BzAzut+vt.Let(12)Fz=BzAz,wt=vt.Clearly, the OE model is the same as the ARX model.Remark 1.
Since almost all the other kinds of models can be approximated by an FIR model, we can first estimate the parameters of the FIR model and then recover parameters of the original models.


## 2.2.1. ARX Model

Consider the following ARX model:(3)Azyt=Bzut+vt,which can be simplified as follows:(4)yt=BzAzut+1Azvt.Using the finite impulse response method, we can get(5)Fz=BzAz,=f1z−1+f2z−2+⋯+fpz−p.We define(6)wt=1Azvt.The ARX model can be simplified as the following FIR model:(7)yt=Fzut+wt.


## 2.2.2. CARMA Model

The CARMA model is written by(8)Azyt=Bzut+Dzvt,which can be simplified as(9)yt=BzAzut+DzAzvt.Let(10)Fz=BzAz,wt=DzAzvt.Then, the CARMA model is simplified as an ARX model.


## 2.2.3. OE Model

The OE model is written by(11)yt=BzAzut+vt.Let(12)Fz=BzAz,wt=vt.Clearly, the OE model is the same as the ARX model.Remark 1.
Since almost all the other kinds of models can be approximated by an FIR model, we can first estimate the parameters of the FIR model and then recover parameters of the original models.


## 3. FGD-Based Auxiliary Model Algorithm

### 3.1. Fractional Derivative-Review

The traditional GD and Newton algorithms update the parameters with the first derivative and second derivative, respectively. Their corresponding convergence rates are linear convergent and quadratic convergent. Although the Newton method has faster convergence rates, it involves a matrix inverse calculation in each iteration which leads to heavy computational efforts. A nature question arises, can we use a fractional derivative to obtain an algorithm which has a faster convergence rate than the GD algorithm and has less computational efforts than the Newton method.There are three conventional fractional derivative methods [32–34]: (1) the Riemann–Liouville (RL) fractional derivative, (2) the Caputo (CAP) fractional derivative, and (3) the Grünwald–Letnikov (GL) fractional derivative.


#### 3.1.1. RL Fractional Derivative Method

(13)DxαaRLfx≜DnDxα−nafx=1Γn−αdndxn∫axftx−tα−n+1dt,where Γα=α×Γα−1.


#### 3.1.2. CAP Fractional Derivative Method

(14)DxαaCfx=1Γn−α∫axfntx−tα+1−ndt.


#### 3.1.3. GL Fractional Derivative Method

(15)DxαaGLfx≜limh⟶01nα∑k=0x−a/h−1kΓα+1Γk+1Γα−k+1fx−kh=limh⟶01nα∑k=0x−a/hΓk−αΓk+1Γ−αfx−kh.Takefx=x, for example, the α-order fractional derivative of fx is written by(16)fαx=Γ2Γ2−αx1−α.


### 3.2. GD Algorithm and Newton Method

Assume that we have collectedL sets of data p+q=L. Define(17)YL=yL,yL−1,…,y1T∈RL,ΨL=ψL,ψL−1,…,ψ1∈Rn×L,ψL=uL−1,…,uL−nT∈RL,VL=vL,…,v1T∈RL.Then, the FIR model is written by(18)YL=ΨTLϑ+VL,ϑ=f1,f2,…,fnT∈Rn.Define the cost function as(19)Jϑ=12YL−ΨTLϑ2.Using the GD algorithm for the FIR model, we have(20)ϑk=ϑk−1+γΨLYL−ΨTLϑk−1,0<γ<2λmaxΨLΨTL.Since the output vectorYL contains the missing outputs ym1,ym2,…,ymq, we use the auxiliary model to compute the missing outputs, that is, the missing outputs in iteration k are computed based on the parameter estimates in iteration k−1,(21)y^kmi=ψTmiϑk−1,i=1,2,…,q.Then, the GD-based auxiliary model (GD-AM) algorithm is listed as follows:(22)ϑk=ϑk−1+γΨLY^kL−ΨTLϑk−1,0<γ<2λmaxΨLΨTL,Y^kL=y^kL,y^kL−1,…,y^k1T,y^ki=yi,i=tj,j=1,2,…,p,y^ki,i=mo,o=1,2,…,q.Remark 2.
The GD-AM algorithm should compute the eigenvalues of the information matrix to choose a suitable step-size. Two shortcomings exist: (1) if the information matrix has a high order, to compute its eigenvalues is difficult; (2) if the information matrix is ill-conditioned, whatever the step-size is, the convergence rates are quite slow.
Different from the GD-AM algorithm, the Newton-based auxiliary model (NT-AM) method updates the parameters by(23)ϑk=ϑk−1+ΨLΨTL−1ΨLY^kL−ΨTLϑk−1,(24)Y^kL=y^kL,y^kL−1,…,y^k1T,y^ki=yi,i=tj,y^ki,i=mo.
Simplifying equation (23) yields(25)ϑk=ΨLΨTL−1ΨLY^kL.Remark 3.
From equation (25), we can conclude that the NT-AM algorithm is the same as the least squares algorithm. Therefore, the NT-AM algorithm has faster convergence rates than the GD-AM algorithm. However, the NT-AM algorithm needs to compute the inverse of a matrix. If the matrix has a high order, to compute its inverse is challenging.


### 3.3. FGD-Based Auxiliary Model Algorithm

The FGD algorithm takesα−th derivative of the cost function with the aim of increasing the convergence rates and avoiding the matrix inversion. Its basic idea is to add an additional direction behind the negative gradient direction. The FGD algorithm is written by(26)ϑk=ϑk−1−r1∂Jϑ∂ϑ−r2∂αJϑ∂ϑα,where(27)∂Jϑ∂ϑ=−ΨLY^kL−ΨTLϑk−1,is the gradient descent direction, and(28)∂αJϑ∂ϑα=−ΨLY^kL−ΨTLϑk−1∂αϑ∂ϑα,is the additional direction.Based on equation (16), it follows that(29)∂αϑ∂ϑα=1Γ2−αϑ1−α.Then, the FGD algorithm is transformed into(30)ϑk=ϑk−1+r1ΨLY^kL−ΨTLϑk−1+r2ΨLY^kL−ΨTLϑk−1∂αϑ∂ϑα=ϑk−1+r1+r21Γ2−αϑt−11−αΨLY^kL−ΨTLϑk−1.Clearly, the difference between the FGD and GD algorithms is the additional direction and its corresponding step-size. The additional direction can polish the negative gradient descent direction with the aim of obtaining a better direction.Substituting the parameter estimates at iterationk−1 with the estimates at iteration k−2 into the second part of the right side of equation (30) yields(31)ϑk=ϑk−1+r1ΨLY^kL−ΨTLϑk−1+r2ΨLY^kL−ΨTLϑk−2∂αϑ∂ϑα,and let(32)γ1=r1,γ2=r2∂αϑ∂ϑα.It gives rise to(33)ϑk=ϑk−1+γ1ΨLY^kL−ΨTLϑk−1+γ2ΨLY^kL−ΨTLϑk−2.Remark 4.
Equation (33) is equivalent to the conjugate gradient direction (C-GD) algorithm. Therefore, the FGD algorithm can be regarded as a modified C-GD algorithm.


### 3.4. Properties of the FGD Algorithm

Subtracting the true valuesϑ on both sides of equation (30) obtains(34)ek=ek−1+r1ΨLY^kL−ΨTLϑk−1+r2ΨLY^kL−ΨTLϑk−1∂αϑ∂ϑα=ek−1−r1+r21Γ2−αϑk−11−αΨLΨTLek−1=I−r1+r21Γ2−αϑk−11−αΨLΨTLek−1.To keep the FGD algorithm convergent, one should guarantee that(35)I−r1+r21Γ2−αϑk−11−αΨLΨTL<1.Assume that the eigenvalues of the matrixΨLΨTL are 0⩽λ1⩽λ2⩽⋯⩽λn, then we can get(36)I−r1+r21Γ2−αϑk−11−αΨLΨTL=P−1I−βdiagλ1,λ2,…,λnP,where P is a nonsingular matrix, and β=r1+r21/Γ2−αϑk−11−α. Since(37)I−βdiagλ1,λ2,…,λn=1−βλ10⋯001−βλ2⋯0⋮⋮⋱⋮00⋯1−βλn.Therefore, to keep the FGD algorithm convergent, the step-sizeβ should satisfy(38)0<β<2λn,and the best step-size is(39)β=2λn+λ1.For the best step-size, the convergence factor is(40)μ=η−1η+1,where η is the condition number and is written by(41)η=λnλ1.Remark 5.
The same as the GD algorithm, if the condition numberη of the information matrix is large, no matter what the step-size is, the convergence rates of the FGD algorithm are quite slow.


## 3.1. Fractional Derivative-Review

The traditional GD and Newton algorithms update the parameters with the first derivative and second derivative, respectively. Their corresponding convergence rates are linear convergent and quadratic convergent. Although the Newton method has faster convergence rates, it involves a matrix inverse calculation in each iteration which leads to heavy computational efforts. A nature question arises, can we use a fractional derivative to obtain an algorithm which has a faster convergence rate than the GD algorithm and has less computational efforts than the Newton method.There are three conventional fractional derivative methods [32–34]: (1) the Riemann–Liouville (RL) fractional derivative, (2) the Caputo (CAP) fractional derivative, and (3) the Grünwald–Letnikov (GL) fractional derivative.


### 3.1.1. RL Fractional Derivative Method

(13)DxαaRLfx≜DnDxα−nafx=1Γn−αdndxn∫axftx−tα−n+1dt,where Γα=α×Γα−1.


### 3.1.2. CAP Fractional Derivative Method

(14)DxαaCfx=1Γn−α∫axfntx−tα+1−ndt.


### 3.1.3. GL Fractional Derivative Method

(15)DxαaGLfx≜limh⟶01nα∑k=0x−a/h−1kΓα+1Γk+1Γα−k+1fx−kh=limh⟶01nα∑k=0x−a/hΓk−αΓk+1Γ−αfx−kh.Takefx=x, for example, the α-order fractional derivative of fx is written by(16)fαx=Γ2Γ2−αx1−α.


## 3.1.1. RL Fractional Derivative Method

(13)DxαaRLfx≜DnDxα−nafx=1Γn−αdndxn∫axftx−tα−n+1dt,where Γα=α×Γα−1.


## 3.1.2. CAP Fractional Derivative Method

(14)DxαaCfx=1Γn−α∫axfntx−tα+1−ndt.


## 3.1.3. GL Fractional Derivative Method

(15)DxαaGLfx≜limh⟶01nα∑k=0x−a/h−1kΓα+1Γk+1Γα−k+1fx−kh=limh⟶01nα∑k=0x−a/hΓk−αΓk+1Γ−αfx−kh.Takefx=x, for example, the α-order fractional derivative of fx is written by(16)fαx=Γ2Γ2−αx1−α.


## 3.2. GD Algorithm and Newton Method

Assume that we have collectedL sets of data p+q=L. Define(17)YL=yL,yL−1,…,y1T∈RL,ΨL=ψL,ψL−1,…,ψ1∈Rn×L,ψL=uL−1,…,uL−nT∈RL,VL=vL,…,v1T∈RL.Then, the FIR model is written by(18)YL=ΨTLϑ+VL,ϑ=f1,f2,…,fnT∈Rn.Define the cost function as(19)Jϑ=12YL−ΨTLϑ2.Using the GD algorithm for the FIR model, we have(20)ϑk=ϑk−1+γΨLYL−ΨTLϑk−1,0<γ<2λmaxΨLΨTL.Since the output vectorYL contains the missing outputs ym1,ym2,…,ymq, we use the auxiliary model to compute the missing outputs, that is, the missing outputs in iteration k are computed based on the parameter estimates in iteration k−1,(21)y^kmi=ψTmiϑk−1,i=1,2,…,q.Then, the GD-based auxiliary model (GD-AM) algorithm is listed as follows:(22)ϑk=ϑk−1+γΨLY^kL−ΨTLϑk−1,0<γ<2λmaxΨLΨTL,Y^kL=y^kL,y^kL−1,…,y^k1T,y^ki=yi,i=tj,j=1,2,…,p,y^ki,i=mo,o=1,2,…,q.Remark 2.
The GD-AM algorithm should compute the eigenvalues of the information matrix to choose a suitable step-size. Two shortcomings exist: (1) if the information matrix has a high order, to compute its eigenvalues is difficult; (2) if the information matrix is ill-conditioned, whatever the step-size is, the convergence rates are quite slow.
Different from the GD-AM algorithm, the Newton-based auxiliary model (NT-AM) method updates the parameters by(23)ϑk=ϑk−1+ΨLΨTL−1ΨLY^kL−ΨTLϑk−1,(24)Y^kL=y^kL,y^kL−1,…,y^k1T,y^ki=yi,i=tj,y^ki,i=mo.
Simplifying equation (23) yields(25)ϑk=ΨLΨTL−1ΨLY^kL.Remark 3.
From equation (25), we can conclude that the NT-AM algorithm is the same as the least squares algorithm. Therefore, the NT-AM algorithm has faster convergence rates than the GD-AM algorithm. However, the NT-AM algorithm needs to compute the inverse of a matrix. If the matrix has a high order, to compute its inverse is challenging.


## 3.3. FGD-Based Auxiliary Model Algorithm

The FGD algorithm takesα−th derivative of the cost function with the aim of increasing the convergence rates and avoiding the matrix inversion. Its basic idea is to add an additional direction behind the negative gradient direction. The FGD algorithm is written by(26)ϑk=ϑk−1−r1∂Jϑ∂ϑ−r2∂αJϑ∂ϑα,where(27)∂Jϑ∂ϑ=−ΨLY^kL−ΨTLϑk−1,is the gradient descent direction, and(28)∂αJϑ∂ϑα=−ΨLY^kL−ΨTLϑk−1∂αϑ∂ϑα,is the additional direction.Based on equation (16), it follows that(29)∂αϑ∂ϑα=1Γ2−αϑ1−α.Then, the FGD algorithm is transformed into(30)ϑk=ϑk−1+r1ΨLY^kL−ΨTLϑk−1+r2ΨLY^kL−ΨTLϑk−1∂αϑ∂ϑα=ϑk−1+r1+r21Γ2−αϑt−11−αΨLY^kL−ΨTLϑk−1.Clearly, the difference between the FGD and GD algorithms is the additional direction and its corresponding step-size. The additional direction can polish the negative gradient descent direction with the aim of obtaining a better direction.Substituting the parameter estimates at iterationk−1 with the estimates at iteration k−2 into the second part of the right side of equation (30) yields(31)ϑk=ϑk−1+r1ΨLY^kL−ΨTLϑk−1+r2ΨLY^kL−ΨTLϑk−2∂αϑ∂ϑα,and let(32)γ1=r1,γ2=r2∂αϑ∂ϑα.It gives rise to(33)ϑk=ϑk−1+γ1ΨLY^kL−ΨTLϑk−1+γ2ΨLY^kL−ΨTLϑk−2.Remark 4.
Equation (33) is equivalent to the conjugate gradient direction (C-GD) algorithm. Therefore, the FGD algorithm can be regarded as a modified C-GD algorithm.


## 3.4. Properties of the FGD Algorithm

Subtracting the true valuesϑ on both sides of equation (30) obtains(34)ek=ek−1+r1ΨLY^kL−ΨTLϑk−1+r2ΨLY^kL−ΨTLϑk−1∂αϑ∂ϑα=ek−1−r1+r21Γ2−αϑk−11−αΨLΨTLek−1=I−r1+r21Γ2−αϑk−11−αΨLΨTLek−1.To keep the FGD algorithm convergent, one should guarantee that(35)I−r1+r21Γ2−αϑk−11−αΨLΨTL<1.Assume that the eigenvalues of the matrixΨLΨTL are 0⩽λ1⩽λ2⩽⋯⩽λn, then we can get(36)I−r1+r21Γ2−αϑk−11−αΨLΨTL=P−1I−βdiagλ1,λ2,…,λnP,where P is a nonsingular matrix, and β=r1+r21/Γ2−αϑk−11−α. Since(37)I−βdiagλ1,λ2,…,λn=1−βλ10⋯001−βλ2⋯0⋮⋮⋱⋮00⋯1−βλn.Therefore, to keep the FGD algorithm convergent, the step-sizeβ should satisfy(38)0<β<2λn,and the best step-size is(39)β=2λn+λ1.For the best step-size, the convergence factor is(40)μ=η−1η+1,where η is the condition number and is written by(41)η=λnλ1.Remark 5.
The same as the GD algorithm, if the condition numberη of the information matrix is large, no matter what the step-size is, the convergence rates of the FGD algorithm are quite slow.


## 4. Aitken FGD-AM Algorithm

In the FGD-AM algorithm, one should compute the eigenvalues of the matrixΨLΨTL to obtain a suitable step-size. If the matrix has a large condition number, the convergence rate of the FGD algorithm is slow. In this section, we introduce the Aitken FGD-AM (A-FGD-AM) algorithm to increase the convergence rate of the FGD-AM algorithm.


### 4.1. Aitken Acceleration Method

Rewrite the FGD algorithm as follows:(42)ϑk=ϑk−1+βΨLY^kL−ΨTLϑk−1.Let(43)ϑk=fk1,fk2,…,fknT.Using the Aitken method to obtain a new estimate sequence,(44)f¯ki=fki−fk+1i−fki2fk+2i+fki−2fk+1i,i=1,2,…,n.Theorem 1.
Assume that the parameter estimateϑk is updated by the FGD algorithm in (42), and the estimate sequence ϑ¯k is computed by the Aitken method in (44). Then, the sequence ϑ¯k is at least quadratic convergent.Proof.
The FGD algorithm in equation (42) can be rewritten as(45)ϑk=gϑk−1.
Then, the iterative function of the Aitken method can be expressed as(46)hϑ¯k−1=ϑk−1−gϑk−1−ϑk−12ggϑk−1+ϑk−1−2gϑk−1.
Clearly, the derivative of the iterative functionhϑ¯k−1 is(47)h′ϑ¯k−1=0.
If(48)h″ϑ¯k−1≠0,the sequence ϑ¯k is quadratic convergent; otherwise, the sequence is at least third-order convergent. This completes the proof.
The steps of the A-FGD-AM algorithm are listed as follows:(1)
To initialize, letϑ0=1/p0, with 1 being a column vector whose entries are all unity and p0=106, and yt=0,ut=0,t⩽0.(2)
Collect the input datau1,u2,…,uL, and the measurable output data yo1,yo2,…,yop(3)
Letk=1(4)
Use the auxiliary model method to compute the missing output datay^km1,y^km2,…,y^kmq(5)
FormY^kL(6)
Update the parameter estimation vectorϑk by (30)(7)
Use the Aitken method to obtain the parameter estimation vectorϑ¯k(8)
Compareϑ¯k and ϑ¯k−1: if they are sufficiently close, or for some preset small ε, if ϑ¯k−ϑ¯k−1⩽ε, then terminate the procedure and obtain the estimate ϑ¯k; otherwise, increase k by 1 and go to step 4.Remark 6.
By using the Aitken method, one does not require to compute the eigenvalues of the information matrix. That is, the A-FGD-AM algorithm is robust to the step-size.


### 4.2. Summary

Based on the discussion above, the properties of these three algorithms are summarized as follows:GD-AM algorithmAdvantage. It has less computational efforts than the NT-AM algorithm.Disadvantage. It has the slowest convergence rates and is difficult to compute the step-size.NT-AM AlgorithmAdvantage. It has the fastest convergence rates among these three algorithmsDisadvantage It needs to compute the inverse of an information matrix and has the heaviest computational efforts among these three algorithmsFGD-AM AlgorithmAdvantage. It has faster convergence rates than the GD-AM algorithm, has less computational efforts than the NT-AM algorithm, and can use the Aitken acceleration technique to increase the convergence rates.Disadvantage. It has heavier computational efforts than the GD-AM algorithm.


## 4.1. Aitken Acceleration Method

Rewrite the FGD algorithm as follows:(42)ϑk=ϑk−1+βΨLY^kL−ΨTLϑk−1.Let(43)ϑk=fk1,fk2,…,fknT.Using the Aitken method to obtain a new estimate sequence,(44)f¯ki=fki−fk+1i−fki2fk+2i+fki−2fk+1i,i=1,2,…,n.Theorem 1.
Assume that the parameter estimateϑk is updated by the FGD algorithm in (42), and the estimate sequence ϑ¯k is computed by the Aitken method in (44). Then, the sequence ϑ¯k is at least quadratic convergent.Proof.
The FGD algorithm in equation (42) can be rewritten as(45)ϑk=gϑk−1.
Then, the iterative function of the Aitken method can be expressed as(46)hϑ¯k−1=ϑk−1−gϑk−1−ϑk−12ggϑk−1+ϑk−1−2gϑk−1.
Clearly, the derivative of the iterative functionhϑ¯k−1 is(47)h′ϑ¯k−1=0.
If(48)h″ϑ¯k−1≠0,the sequence ϑ¯k is quadratic convergent; otherwise, the sequence is at least third-order convergent. This completes the proof.
The steps of the A-FGD-AM algorithm are listed as follows:(1)
To initialize, letϑ0=1/p0, with 1 being a column vector whose entries are all unity and p0=106, and yt=0,ut=0,t⩽0.(2)
Collect the input datau1,u2,…,uL, and the measurable output data yo1,yo2,…,yop(3)
Letk=1(4)
Use the auxiliary model method to compute the missing output datay^km1,y^km2,…,y^kmq(5)
FormY^kL(6)
Update the parameter estimation vectorϑk by (30)(7)
Use the Aitken method to obtain the parameter estimation vectorϑ¯k(8)
Compareϑ¯k and ϑ¯k−1: if they are sufficiently close, or for some preset small ε, if ϑ¯k−ϑ¯k−1⩽ε, then terminate the procedure and obtain the estimate ϑ¯k; otherwise, increase k by 1 and go to step 4.Remark 6.
By using the Aitken method, one does not require to compute the eigenvalues of the information matrix. That is, the A-FGD-AM algorithm is robust to the step-size.


## 4.2. Summary

Based on the discussion above, the properties of these three algorithms are summarized as follows:GD-AM algorithmAdvantage. It has less computational efforts than the NT-AM algorithm.Disadvantage. It has the slowest convergence rates and is difficult to compute the step-size.NT-AM AlgorithmAdvantage. It has the fastest convergence rates among these three algorithmsDisadvantage It needs to compute the inverse of an information matrix and has the heaviest computational efforts among these three algorithmsFGD-AM AlgorithmAdvantage. It has faster convergence rates than the GD-AM algorithm, has less computational efforts than the NT-AM algorithm, and can use the Aitken acceleration technique to increase the convergence rates.Disadvantage. It has heavier computational efforts than the GD-AM algorithm.


## 5. Examples

### 5.1. Example 1

Consider an FIR model with missing data:(49)yt=f1ut−1+f2ut−2+f3ut−3+f4ut−4+f5ut−5+vt,ϑ=f1,f2,f3,f4,f5T,=0.2,−0.3,0.4,0.3,0.1T,ut∼N0,1,vt∼N0,0.12.In simulation, we collect 500 sets of input and output data, where all the input data are measurable and the output data at the sampling instantst=4,8,12,…,500 are missing. Let α=1.2.Use the GD-AM, NT-AM, and FGD-AM algorithms for this FIR model. The parameter estimates and their estimation errorsτ=ϑk−ϑ/ϑ are shown in Table 1 and Figure 2. The output estimates are shown in Figure 3.Table 1
The parameter estimates and their estimation errors.
Algorithmskf1f2f3f4f5τ%GD-AM10.01816−0.027900.037700.026320.0104790.7640020.03461−0.053130.071890.050330.0198282.3872950.07528−0.115310.156470.110500.0422861.64713100.12134−0.185210.252370.180410.0662138.09592150.14958−0.227610.311180.224580.0796823.62824200.16691−0.253340.347240.252460.0872114.74477NT-AM10.18741−0.288700.378230.292850.083555.2666920.19988−0.301380.398330.300920.092841.2066850.20088−0.301990.399630.300900.093791.06486100.20088−0.301990.399630.300900.093791.06478150.20088−0.301990.399630.300900.093791.06478200.20088−0.301990.399630.300900.093791.06478FGD-AM10.11235−0.160650.191410.133520.0282851.5080920.16286−0.235920.290320.207230.0509227.0470750.19881−0.295280.383110.284050.083844.59820100.20102−0.301830.398830.299890.093111.16937150.20089−0.301980.399580.300840.093751.07048200.20088−0.301990.399630.300890.093791.06513True values0.20000−0.300000.400000.300000.10000Figure 2
The parameter estimation errors.Figure 3
The true outputs and estimated outputs.In addition, we apply the FGD-AM algorithm with different noise to signal ratios for this FIR model (FGD-AM-1,vt∼N0,0.12; FGD-AM-2, vt∼N0,0.22; and FGD-AM-3, vt∼N0,0.32). The estimation errors τ=ϑk−ϑ/ϑ are shown in Figure 4.Figure 4
The parameter estimation errors with different noise-to-signal ratios.From this simulation, we can get the following findings:(1)
The parameter estimates of these three algorithms can asymptotically converge to the true values(2)
The NT-AM algorithm has the fastest convergence rates, then is the FGD-AM algorithm, and the GD-AM algorithm has the slowest convergence rates;(3)
The estimated outputs of these three algorithms can catch the true outputs(4)
The larger the noise to signal ratio is, the larger estimation errors the FGD-AM algorithm will have


### 5.2. A Water Tank System

Consider a simple water tank system in Figure5, where ut is the position of the inlet water valve, and yt is the level of Tank 2. We try to keep the level of Tank 2 in a fixed number; if the level is larger than the fixed number, we will turn ut down; on the other hand, we should turn ut up. The outputs (the true level of Tank 2) are transmitted over the communication network, and some data are missing due to network congestion. Assume that the system is modeled by the following FIR model:(50)yt=0.4732ut−1+0.3216ut−2−0.4574ut−3+0.2352ut−4+vt.Figure 5
A water tank system.In simulation, we use a random binary sequence generated by Matlab as the input signalu=idinput320,′rbs′,0,1,−1.5,1.5 and assign α=1.4. Assume the outputs at the sampling instants t=3,6,9,…,300 are missing, while the other outputs are measurable.Apply the FGD-AM and A-FGD-AM algorithms with different step-sizes for this model. The parameter estimation errorsτ=ϑk−ϑ/ϑ are shown in Figures 6 and 7. The output estimates are shown in Figures 8 and 9. In addition, use the A-FGD-AM and NT-AM algorithms for the water tank system, where the A-FGD-AM algorithm chooses the optimal step-size γ=2/λmaxΨLΨTL+λminΨLΨTL. The parameter estimation errors are shown in Figure 10, and their elapsed times are shown in Table 2.Figure 6
The parameter estimation errorsγ=1/λmaxΨLΨTL.Figure 7
The parameter estimation errorsγ=2.01/λmaxΨLΨTL.Figure 8
The true outputs and estimated outputsγ=1/λmaxΨLΨTL.Figure 9
The true outputs and estimated outputsγ=2.01/λmaxΨLΨTL.Figure 10
The parameter estimation errors.Table 2
The elapsed times of these two algorithms.
AlgorithmNT-AMA-FGD-AMElapsed times (second)0.2390.202This simulation example shows that the A-FGD-AM algorithm has faster convergence rates than the FGD-AM algorithm; the A-FGD-AM algorithm is robust to the step-size, while the FGD-AM algorithm is sensitive to the step-size; and the A-FGD-AM algorithm has almost the same convergence rates as the NT-AM algorithm, but it has less computational efforts than the NT-AM algorithm.


## 5.1. Example 1

Consider an FIR model with missing data:(49)yt=f1ut−1+f2ut−2+f3ut−3+f4ut−4+f5ut−5+vt,ϑ=f1,f2,f3,f4,f5T,=0.2,−0.3,0.4,0.3,0.1T,ut∼N0,1,vt∼N0,0.12.In simulation, we collect 500 sets of input and output data, where all the input data are measurable and the output data at the sampling instantst=4,8,12,…,500 are missing. Let α=1.2.Use the GD-AM, NT-AM, and FGD-AM algorithms for this FIR model. The parameter estimates and their estimation errorsτ=ϑk−ϑ/ϑ are shown in Table 1 and Figure 2. The output estimates are shown in Figure 3.Table 1
The parameter estimates and their estimation errors.
Algorithmskf1f2f3f4f5τ%GD-AM10.01816−0.027900.037700.026320.0104790.7640020.03461−0.053130.071890.050330.0198282.3872950.07528−0.115310.156470.110500.0422861.64713100.12134−0.185210.252370.180410.0662138.09592150.14958−0.227610.311180.224580.0796823.62824200.16691−0.253340.347240.252460.0872114.74477NT-AM10.18741−0.288700.378230.292850.083555.2666920.19988−0.301380.398330.300920.092841.2066850.20088−0.301990.399630.300900.093791.06486100.20088−0.301990.399630.300900.093791.06478150.20088−0.301990.399630.300900.093791.06478200.20088−0.301990.399630.300900.093791.06478FGD-AM10.11235−0.160650.191410.133520.0282851.5080920.16286−0.235920.290320.207230.0509227.0470750.19881−0.295280.383110.284050.083844.59820100.20102−0.301830.398830.299890.093111.16937150.20089−0.301980.399580.300840.093751.07048200.20088−0.301990.399630.300890.093791.06513True values0.20000−0.300000.400000.300000.10000Figure 2
The parameter estimation errors.Figure 3
The true outputs and estimated outputs.In addition, we apply the FGD-AM algorithm with different noise to signal ratios for this FIR model (FGD-AM-1,vt∼N0,0.12; FGD-AM-2, vt∼N0,0.22; and FGD-AM-3, vt∼N0,0.32). The estimation errors τ=ϑk−ϑ/ϑ are shown in Figure 4.Figure 4
The parameter estimation errors with different noise-to-signal ratios.From this simulation, we can get the following findings:(1)
The parameter estimates of these three algorithms can asymptotically converge to the true values(2)
The NT-AM algorithm has the fastest convergence rates, then is the FGD-AM algorithm, and the GD-AM algorithm has the slowest convergence rates;(3)
The estimated outputs of these three algorithms can catch the true outputs(4)
The larger the noise to signal ratio is, the larger estimation errors the FGD-AM algorithm will have


## 5.2. A Water Tank System

Consider a simple water tank system in Figure5, where ut is the position of the inlet water valve, and yt is the level of Tank 2. We try to keep the level of Tank 2 in a fixed number; if the level is larger than the fixed number, we will turn ut down; on the other hand, we should turn ut up. The outputs (the true level of Tank 2) are transmitted over the communication network, and some data are missing due to network congestion. Assume that the system is modeled by the following FIR model:(50)yt=0.4732ut−1+0.3216ut−2−0.4574ut−3+0.2352ut−4+vt.Figure 5
A water tank system.In simulation, we use a random binary sequence generated by Matlab as the input signalu=idinput320,′rbs′,0,1,−1.5,1.5 and assign α=1.4. Assume the outputs at the sampling instants t=3,6,9,…,300 are missing, while the other outputs are measurable.Apply the FGD-AM and A-FGD-AM algorithms with different step-sizes for this model. The parameter estimation errorsτ=ϑk−ϑ/ϑ are shown in Figures 6 and 7. The output estimates are shown in Figures 8 and 9. In addition, use the A-FGD-AM and NT-AM algorithms for the water tank system, where the A-FGD-AM algorithm chooses the optimal step-size γ=2/λmaxΨLΨTL+λminΨLΨTL. The parameter estimation errors are shown in Figure 10, and their elapsed times are shown in Table 2.Figure 6
The parameter estimation errorsγ=1/λmaxΨLΨTL.Figure 7
The parameter estimation errorsγ=2.01/λmaxΨLΨTL.Figure 8
The true outputs and estimated outputsγ=1/λmaxΨLΨTL.Figure 9
The true outputs and estimated outputsγ=2.01/λmaxΨLΨTL.Figure 10
The parameter estimation errors.Table 2
The elapsed times of these two algorithms.
AlgorithmNT-AMA-FGD-AMElapsed times (second)0.2390.202This simulation example shows that the A-FGD-AM algorithm has faster convergence rates than the FGD-AM algorithm; the A-FGD-AM algorithm is robust to the step-size, while the FGD-AM algorithm is sensitive to the step-size; and the A-FGD-AM algorithm has almost the same convergence rates as the NT-AM algorithm, but it has less computational efforts than the NT-AM algorithm.


## 6. Conclusions

An FGD-AM algorithm is proposed for FIR models with missing data. By adding an additional direction to the conventional GD-AM algorithm, the convergence rates can be increased. Since the FGD-AM algorithm involves the step-size calculation in each iteration, an A-FGD-AM algorithm is developed. The A-FGD-AM algorithm has several advantages over the FGD-AM algorithm and the NT-AM algorithm, e.g., it has faster convergence rates, is robust to the step-size, and does not require matrix inverse calculation. Therefore, the A-FGD-AM algorithm can be used in a wide range of cutting-edge applications.Although the FGD-AM algorithm has several advantages over the conventional GD-AM algorithm, some interesting topics about the FGD-AM algorithm need to be further discussed. For example, how to choose an optimal fractional order in each iteration and how to avoid the outliers in the Aitken FGD-AM algorithm.



---

*Source: 7527478-2023-02-09.xml*