# Nonlinear Least Square Based on Control Direction by Dual Method and Its Application

Authors: Zhengqing Fu; Guolin Liu; Lanlan Guo; Weike Liu; Hua Guo
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A direction controlled nonlinear least square (NLS) estimation algorithm using the primal-dual method is proposed. The least square model is transformed into the primal-dual model; then direction of iteration can be controlled by duality. The iterative algorithm is designed. The Hilbert morbid matrix is processed by the new model and the least square estimate and ridge estimate. The main research method is to combine qualitative analysis and quantitative analysis. The deviation between estimated values and the true value and the estimated residuals fluctuation of different methods are used for qualitative analysis. The root mean square error (RMSE) is used for quantitative analysis. The results of experiment show that the model has the smallest residual error and the minimum root mean square error. The new estimate model has effectiveness and high precision. The genuine data of Jining area in unwrapping experiments are used and the comparison with other classical unwrapping algorithms is made, so better results in precision aspects can be achieved through the proposed algorithm.


---

## Body

## 1. Introduction

During the course of data processing of measurement, most problems are nonlinear ones. In the classical least square, the nonlinear approximation function is expanded at the approximate value. This transformation can linearize the data; then the problem can be solved through the linear least square. The precondition of this model is that the initial value of parameter is sufficiently reaching the adjusted value. Otherwise the model error is hard to be ignored.NLS is one of the optimization methods. And NLS problem can be solved by the optimization method [1–3]. Primal-dual method is a very important and effective optimization method. NLS problems can be transformed into primal-dual model and then be solved.A direction controlled estimate model is proposed. The least square model is transformed into the primal-dual model [4]; then the direction of iteration can be controlled by duality. In the primal-dual method, a nonlinear optimization problem (primal problem) can be converted into another nonlinear optimization problem (dual problem). The solution of the primal model can be gotten through duality problem [5, 6]. The theory of primal-dual model is introduced and the algorithm is proposed. The model is contrasted with LS and the ridge estimate. The simulated data are used to check the model. The root mean square error (RMSE) and the deviation between estimated values and the true value are taken as the indexes. The results from the experiments show the feasibility and effectiveness of the model. Unwrapping experiments using genuine data of Jining area and comparing with LS unwrapping algorithms [7], the proposed algorithm achieved better results in precision aspects. Computation time, ε value, and the RMSE are taken as quantitative indexes. The dual method achieved better results with regard to all of computation time and the RMSE between rewrapped results and original wrapped phase and ε value.


## 2. Primal-Dual Models

The primal problem of quadratic optimization with equality constraints is defined as follows [8, 9]:(1)min⁡fx=12xTHx+pTxs.t.Ax=b,x≥0,where H∈Rn×n, p∈Rn×1, A∈Rm×n, and b∈Rm×1. H can be seen as a symmetric matrix.The Lagrange function of (1) is(2)Lx,u=12xTHx+pTx+uTAx-b.The dual problem of (1) is defined as follows:(3)gu=infx⁡Lx,u.IfH is a positive semidefinite matrix, then f(x) is a convex function. In this case, if there is at least one vector quantity x satisfying the equality constraints and f(x) is lower bounded in the feasible region then quadratic optimization has a global minimum. If H is the positive definite matrix then the quadratic optimization has a global unique minimum.Nonlinear model is defined as follows:(4)L=fx+Δ,where L=(L1,L2,…,Ln)T is n×1 vector; f is nonlinear function; X=(X1,X2,…,Xt)T is t×1 vector to be estimated; and Δ=(Δ1,Δ2,…,Δn)T is n×1 vector of observing error. The error equation of (4) is(5)Vx=fx-L.Least square principle needs to be satisfied; that is,(6)min⁡Fx=VTxPVx=fx-LTPfx-L.The second-order Taylor series expansion of (6) is(7)Fx=Fxk+Δxk≈Fxk+gkΔxk+12ΔxkTGkΔxk,where (8)gk=∂Fx∂x1∂Fx∂x2⋯∂Fx∂xtx=xkis Jacobi matrix which is the gradient of F(x) at xk.(9)
G
k
=
∂
2
F
x
∂
x
1
2
∂
2
F
x
∂
x
1
∂
x
2
⋯
∂
2
F
x
∂
x
1
∂
x
t
∂
2
F
x
∂
x
1
∂
x
2
∂
2
F
x
∂
x
2
2
⋯
∂
2
F
x
∂
x
2
∂
x
t
⋯
⋯
⋯
⋯
∂
2
F
x
∂
x
1
∂
x
t
∂
2
F
x
∂
x
2
∂
x
t
⋯
∂
2
F
x
∂
x
t
2
x
=
x
kis the Hessian matrix.Formula (7) can be converted into the quadratic optimization with equality constraints as follows [10]:(10)min⁡FΔxk=VTPVs.t.V=BxkΔxk+Cxk-L,where B(xk)=(∂f(x)/∂x)x=xk, C(xk)=f(xk), and the positive definite matrix P is weight matrix. Equation (10) is convex programing.The equivalent quadratic optimization of (10) can be expressed as follows [11]:(11)min⁡FΔxk=VTΔxkTP000VΔxks.t.I-BxkVΔxk+L-Cxk=0.The Lagrange function of (10) is(12)Lx,u=VTPV+uTBxkΔxk+Cxk-Land the dual model is(13)gu=infx⁡VTPV+uTBxkΔxk+Cxk-L.The Lagrange function of (11) is(14)Lx,u=VTΔxkTP000VΔxk+uTI-BxkVΔxk+L-Cxkand the dual model is(15)gu=infx⁡VTΔxkTP000VΔxk+uTI-BxkVΔxk+L-Cxk.The optimal solution of NLS can be gotten by solving quadratic program and its dual problem.Based on the primal-dual form to the problem (10) and (13), an iterative algorithm is proposed. This paper gives some matrixes and vectors as follows:(16)A=A1,A2,…,AmT,Ai=ai1,ai2,…,ain,b=b1,b2,…,bmT,x=x1,x2,…,xnT.The steps of algorithm are shown as follows:(1)
The initial values areQ(0)=H-1 and x(0)=-Q(0)p, the control error is ε(ε>0), and the number of iterations is k(k=0).(2)
The iterative formulas are represented as shown below:(17)xk+1=xk+AiQkAiT-1QkAiTbi-Aixk,Qk+1=Qk-AiQkAiT-1QkAiTAQk.(3)
Ifx(k+1)-x(k)≤ε, the result is x∗=x(k+1); otherwise return to (2) until the condition is met.Following the similar ideas of [12], if matrix H is positive definite, the algorithm is convergent. If matrix H is semipositive definite, but H+λ∑i=1mAiTAi is positive definite (λ is a constant), the algorithm is convergent.


## 3. Experiment Results and Analyses

### 3.1. Simulated Data

In this case,AX=b, where A=(ai,j)11×9 is a Hilbert matrix [13]. (18)aij=1i+j-1,i=1,2,…,11;j=1,2,…,9.The true value isX=1. There are two cases of noise in experiments: 1.0×10-5 and 1.0×10-2. The condition number of matrix is 8.9859×1016, so this is an ill-condition problem. By using the primal-dual method, LS method, and ridge estimate, the results are compared and analyzed.The evaluations of experiment are shown in Tables1 and 2 when the noise is 1.0×10-5.Table 1
The estimated value by dual method, LS method, and ridge estimate.
Comparison value True value Dual method LS method Ridge method ⁡X^ 1 1.0000 1.0001 1.0001 1 0.9999 0.9976 0.9994 1 0.9851 1.0163 1.0011 1 0.9826 0.9753 1.0011 1 0.9888 0.9526 0.9992 1 1.0000 1.0169 0.9979 1 1.0136 1.0833 0.9983 1 1.0283 0.7300 1.0001 1 1.0433 1.0032 1.0032Table 2
The error of dual method, LS method, and ridge estimate.
Dual method LS method Ridge method RMSE 0.0197 0.1136 1.2144 × 1 0 - 4 The standard deviation 0.0144 0.3370 0.0046The noise has small influence on estimates because it is very small. The estimates of three methods are very close to the true value, which illustrates that all of the methods can accurately estimate the solution. From the RMSE and the standard deviation, ridge estimate model is the best and the dual method is better than LS method.When the noise is1.0×10-2, the evaluations of experiment are shown in Tables 3 and 4.Table 3
The estimated value by dual method, LS method, and ridge estimate.
Comparison value True value Dual method LS method Ridge method ⁡X^ 1 1.0000 1.0079 1.0049 1 0.9709 0.7354 0.9366 1 0.9673 2.7178 1.1139 1 0.8735 −2.1462 1.1102 1 0.9103 −2.3567 0.9203 1 1.1105 9.7344 0.7954 1 0.9577 11.5079 0.8278 1 0.9885 −28.6162 1.0138 1 1.2147 14.4586 1.3164Table 4
The error of dual method, LS method, and ridge estimate.
Dual method LS method Ridge method RMSE 0.0979 11.8750 0.1518 The standard deviation 0.0691 9.4341 0.0987Dual method and ridge method can obtain accurate results. As the noise increases, the RMSE and the standard deviation of three methods are bigger. Dual method is the best. This illustrates that the dual method is better than other algorithms in stability.From both noises, the dual method not only obtains good results but also has better stability.


### 3.2. Phase Unwrapping Experiment

The data that were plugged into this experiment came from ALOS satellite. The area which this paper studied is located in Jining, Shandong province of China. Figure1 shows the study area and its surrounding enhanced thematic mapper (ETM) stack digital elevation model (DEM) three-dimensional diagrams.Figure 1
Study area and the surrounding terrain map. (a) Sketch map of study area. (b) Study area and its surrounding ETM stack DEM three-dimensional diagram.
(a) (b)Table5 shows the basic parameters of ALOS satellite data.Table 5
The basic parameters of ALOS satellite data.
Number Satellite Date Orbit Path/frame Polarization Track Latitude of centre Longitude of centre Observation mode 1 PALSAR 22/12/2007 10175 448/700 HH A 35.654 117.061 FBS 2 PALSAR 06/02/2008 10846 448/700 HH A 35.639 117.074 FBSFigure2 shows the map of wrapped phase. The sizes of images are 140 pixels × 120 pixels.Figure 2
The map of wrapped phase.
(a)
Unfiltered (b)
FilteredFrom the map of wrapped phase, the interference fringes are clear. Because of the noise, the lower-right sections are discontinuous. After being filtered, the fringes are enhanced, but the noise is still obvious.Figure3 shows the unwrapping results after the different algorithm.Figure 3
Comparison of different algorithms unwrapping results.
(a)
LS method (b)
Dual methodBoth unwrapping methods can run successfully. LS method does well in the relatively noise-free area. In high noise area, the unwrapping results are unsatisfactory. Not only is error transfer clear, but also the incoherent area becomes bigger. The dual method can reduce phase transmission error and get better unwrapping results.Table6 shows computation time, ε value, and the RMSE between rewrapped results and original wrapped phase.Table 6
Computation time andε value and RMSE between rewrapped results and original wrapped phase.
Computation time ε (rad) RMSE (rad) LS method 66.22 0.0089 7.5326 Dual method 58.41 0.0066 3.2105The computation time of LS method is slightly more compared to dual method, which illustrates that both algorithms are at the same complicated degree. The RMSE andε value of dual method are smaller compared to LS method, which illustrates that the difference between rewrapped results and original wrapped phase is small. Thus the unwrapping phases of dual method are smoother and more reliable.


## 3.1. Simulated Data

In this case,AX=b, where A=(ai,j)11×9 is a Hilbert matrix [13]. (18)aij=1i+j-1,i=1,2,…,11;j=1,2,…,9.The true value isX=1. There are two cases of noise in experiments: 1.0×10-5 and 1.0×10-2. The condition number of matrix is 8.9859×1016, so this is an ill-condition problem. By using the primal-dual method, LS method, and ridge estimate, the results are compared and analyzed.The evaluations of experiment are shown in Tables1 and 2 when the noise is 1.0×10-5.Table 1
The estimated value by dual method, LS method, and ridge estimate.
Comparison value True value Dual method LS method Ridge method ⁡X^ 1 1.0000 1.0001 1.0001 1 0.9999 0.9976 0.9994 1 0.9851 1.0163 1.0011 1 0.9826 0.9753 1.0011 1 0.9888 0.9526 0.9992 1 1.0000 1.0169 0.9979 1 1.0136 1.0833 0.9983 1 1.0283 0.7300 1.0001 1 1.0433 1.0032 1.0032Table 2
The error of dual method, LS method, and ridge estimate.
Dual method LS method Ridge method RMSE 0.0197 0.1136 1.2144 × 1 0 - 4 The standard deviation 0.0144 0.3370 0.0046The noise has small influence on estimates because it is very small. The estimates of three methods are very close to the true value, which illustrates that all of the methods can accurately estimate the solution. From the RMSE and the standard deviation, ridge estimate model is the best and the dual method is better than LS method.When the noise is1.0×10-2, the evaluations of experiment are shown in Tables 3 and 4.Table 3
The estimated value by dual method, LS method, and ridge estimate.
Comparison value True value Dual method LS method Ridge method ⁡X^ 1 1.0000 1.0079 1.0049 1 0.9709 0.7354 0.9366 1 0.9673 2.7178 1.1139 1 0.8735 −2.1462 1.1102 1 0.9103 −2.3567 0.9203 1 1.1105 9.7344 0.7954 1 0.9577 11.5079 0.8278 1 0.9885 −28.6162 1.0138 1 1.2147 14.4586 1.3164Table 4
The error of dual method, LS method, and ridge estimate.
Dual method LS method Ridge method RMSE 0.0979 11.8750 0.1518 The standard deviation 0.0691 9.4341 0.0987Dual method and ridge method can obtain accurate results. As the noise increases, the RMSE and the standard deviation of three methods are bigger. Dual method is the best. This illustrates that the dual method is better than other algorithms in stability.From both noises, the dual method not only obtains good results but also has better stability.


## 3.2. Phase Unwrapping Experiment

The data that were plugged into this experiment came from ALOS satellite. The area which this paper studied is located in Jining, Shandong province of China. Figure1 shows the study area and its surrounding enhanced thematic mapper (ETM) stack digital elevation model (DEM) three-dimensional diagrams.Figure 1
Study area and the surrounding terrain map. (a) Sketch map of study area. (b) Study area and its surrounding ETM stack DEM three-dimensional diagram.
(a) (b)Table5 shows the basic parameters of ALOS satellite data.Table 5
The basic parameters of ALOS satellite data.
Number Satellite Date Orbit Path/frame Polarization Track Latitude of centre Longitude of centre Observation mode 1 PALSAR 22/12/2007 10175 448/700 HH A 35.654 117.061 FBS 2 PALSAR 06/02/2008 10846 448/700 HH A 35.639 117.074 FBSFigure2 shows the map of wrapped phase. The sizes of images are 140 pixels × 120 pixels.Figure 2
The map of wrapped phase.
(a)
Unfiltered (b)
FilteredFrom the map of wrapped phase, the interference fringes are clear. Because of the noise, the lower-right sections are discontinuous. After being filtered, the fringes are enhanced, but the noise is still obvious.Figure3 shows the unwrapping results after the different algorithm.Figure 3
Comparison of different algorithms unwrapping results.
(a)
LS method (b)
Dual methodBoth unwrapping methods can run successfully. LS method does well in the relatively noise-free area. In high noise area, the unwrapping results are unsatisfactory. Not only is error transfer clear, but also the incoherent area becomes bigger. The dual method can reduce phase transmission error and get better unwrapping results.Table6 shows computation time, ε value, and the RMSE between rewrapped results and original wrapped phase.Table 6
Computation time andε value and RMSE between rewrapped results and original wrapped phase.
Computation time ε (rad) RMSE (rad) LS method 66.22 0.0089 7.5326 Dual method 58.41 0.0066 3.2105The computation time of LS method is slightly more compared to dual method, which illustrates that both algorithms are at the same complicated degree. The RMSE andε value of dual method are smaller compared to LS method, which illustrates that the difference between rewrapped results and original wrapped phase is small. Thus the unwrapping phases of dual method are smoother and more reliable.


## 4. Conclusions

A direction controlled nonlinear least square (NLS) estimation algorithm using the primal-dual method is proposed. The least square model is transformed into the primal-dual model; then direction of iteration can be controlled by duality. Under mild conditions, the algorithm is global convergence. The Hilbert morbid matrix and phase unwrapping are used to verify the method. The proposed algorithm achieves better results, and the effectiveness is demonstrated.



---

*Source: 7094157-2016-10-30.xml*