# Augmented Arnoldi-Tikhonov Regularization Methods for Solving Large-Scale Linear Ill-Posed Systems

Authors: Yiqin Lin; Liang Bao; Yanhua Cao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We propose an augmented Arnoldi-Tikhonov regularization method for the solution of large-scale linear ill-posed systems. This method augments the Krylov subspace by a user-supplied low-dimensional subspace, which contains a rough approximation of the desired solution. The augmentation is implemented by a modified Arnoldi process. Some useful results are also presented. Numerical experiments illustrate that the augmented method outperforms the corresponding method without augmentation on some real-world examples.


---

## Body

## 1. Introduction

We consider the iterative solution of a large system of linear equations(1)Ax=b,
where A∈ℝn×n is nonsymmetric and nonsingular, and b∈ℝn. We further assume that the coefficient matrix A is of ill-determined rank; that is, all its singular values decay gradually to zero, with no gap anywhere in the spectrum. Such systems are often referred to as linear discrete ill-posed problems and arise from the discretization of ill-posed problems such as Fredholm integral equations of the first kind with a smooth kernel. The right-hand side b of (1) is assumed to be contaminated by an error e∈ℝn, which may stem from discretization or measurement inaccuracies. Thus, b=b^+e, where b^ is the unknown error-free right-hand side vector.We would like to compute the solutionx^ of the linear system of equations with the error-free right-hand side b^,
(2)Ax^=b^.
However, since the right-hand side in (2) is not available, we seek to determine an approximation of x^ by solving the available system (1) or a modification. Due to the ill conditioning of A, the system (1) has to be regularized in order to compute a useful approximation of x^. Perhaps the best known regularization method is Tikhonov regularization [1–3], which in its simplest form is based on the minimization problem
(3)minx∈ℝn{∥Ax-b∥2+1μ∥x∥2},
where μ>0 is a regularization parameter. Here and throughout this paper ∥·∥ denotes the Euclidean vector norm or the associated induced matrix norm.After regulating the system (1), we need to compute the solution xμ of the minimization problem (3). Such a vector xμ is also the solution of
(4)(ATA+1μI)x=ATb.
Here and in the following, I denotes the identity matrix, whose dimension is conformed with the dimension used in the context. If μ is far away from zero, then, due to the ill conditioning of A, xμ is badly computed while, if μ is close to zero, xμ is well computed, but the error xμ-x^ is quite large. Thus, the choice of a good value for μ is fairly important. Several methods have been proposed to obtain an effective value for μ. For example, if the norm of the error e or a fairly accurate estimate is known, the regularization parameter is quite easy to determine by application of the discrepancy principle. The discrepancy principle proposes that the regularization parameter μ can be chosen so that the discrepancy b-Axμ satisfies
(5)∥b-Axμ∥=ηε,
where ε=∥e∥ and η>1 is a constant; see, for example, [4] for further details on the discrepancy principle.The singular value decomposition [5] of A can be used to determine the solution xμ of the minimization problem (3). For an overview of numerical methods for computing the SVD, we refer to [6]. We remark that the computational effort required to compute the SVD is quite high even for moderately sized matrices.Many numerical methods using Krylov subspaces have been proposed for the solution of large-scale Tikhonov regularization problems (3). The main idea of such algorithms has been to first project the large problems onto some Krylov subspace to produce problems with small size and then solve the small-sized problems by the SVD. For instance, several well-established methods based on the Lanczos bidiagonalization process have been proposed for the solution of the minimization problem (3); see [7–10] and references therein. These methods use the Lanczos bidiagonalization process to construct a basis of the Krylov subspace:
(6)𝒦m(ATA,ATb)=span{ATb,ATAATb,…,(ATA)m-1ATb}.
We remark that each Lanczos bidiagonalization step needs two matrix-vector product evaluations, one with A and the other with AT. Other methods using the Krylov subspace
(7)𝒦m(A,Ab)=span{Ab,A2b,…,Amb}
as the projection subspace have been also designed. For example, Lewis and Reichel [11] proposed to exploit the Arnoldi process to produce a basis of the Krylov subspace 𝒦m(A,Ab) to obtain an approximation of the solution of the Tikhonov regularization problem (3). Since each Arnoldi decomposition step requires only one matrix-vector evaluation with A, the approach based on the Arnoldi process may require fewer matrix-vector product evaluations than that based on the Lanczos bidiagonalization process. Moreover, the methods based on the Arnoldi process do not require the adjoint matrix AT and, hence, are more appropriate to problems for which the adjoint is difficult to evaluate. For such problems we refer to [12]. A similar Tikhonov regularization method based on generalized Krylov subspace is proposed in [13].Some numerical methods without using the Tikhonov regularization technique have been already proposed to solve the large-scale linear discrete ill-posed problem (1). These methods include the range-restricted GMRES (RRGMRES) method [14, 15], the augmented range-restricted GMRES (ARRGMRES) method [16], and the flexible GMRES (FGMRES) method [17]. The RRGMRES method determines the mth approximation xm of (1) by solving the minimization problem
(8)minx∈𝒦m(A,Ab)∥Ax-b∥,m=1,2,…,x0=0.
The regularization is implemented by choosing a suitable dimension number m; see, for example, [18]. The ARRGMRES method augments the Krylov subspace 𝒦m(A,Ab) by a low-dimensional user-supplied subspace. The low-dimensional subspace is determined by vectors that are able to represent the known features of the desired solution. The augmented method can yield approximate solutions of higher accuracy than the RRGMRES method if the Krylov subspace 𝒦m(A,Ab) does not allow representation of the known features.In this paper, we propose a new iterative method, named augmented Arnoldi-Tikhonov regularization method, for solving large-scale linear ill-posed systems (1). The new method is deduced by combining the Tikhonov regularization technique and the augmentation technique. The augmentation is implemented by a modified Arnoldi process.The following summarizes the structure of this paper. Section2 describes the augmented Arnoldi-Tikhonov regularization method and some useful results. Some real-world examples are presented in Section 3. Section 4 contains the conclusions.


## 2. Augmented Arnoldi-Tikhonov Regularization Method

We attempt to improve the Arnoldi-Tikhonov regularization method proposed in [11] by augmenting the Krylov subspace 𝒦m(A,Ab) by a k-dimensional subspace 𝒲, which contains a rough approximation of the desired solution of (2). Then, the subspace of projection we will exploit in the following is of the form
(9)𝒦m(A,Ab)+𝒲=span{Ab,A2b,…,Amb}+𝒲.LetW be the n by k matrix whose columns form an orthonormal basis of the space 𝒲. For the purpose of augmentation by 𝒲, we apply the modified Arnoldi process [16] to construct the modified Arnoldi decomposition
(10)A[W,Vm]=[U,Vm+1]H,
where U∈ℝn×k, Vm+1∈ℝn×(m+1), [U,Vm+1] has orthonormal columns, and H∈ℝ(m+k+1)×(m+k) is an upper Hessenberg matrix. We point out that the leading principal k by k submatrix of H is the upper triangular matrix in the QR factorization [5] of AW; that is, H is of the form(11)H=[h11h12⋯h1kh1,k+1h1,k+2⋯h1,k+m⋱⋱⋮⋮⋮⋯⋮hk-1,k-1hk-1,khk-1,k+1hk-1,k+2⋯hk-1,k+mhkkhk,k+1hk,k+2⋯hk,k+mhk+1,k+1hk+1,k+2⋯hk+1,k+mhk+2,k+1hk+2,k+2⋯hk+2,k+m⋱⋱⋮hk+m,k+m-1hk+m,k+mhk+m+1,k+m].The modified Arnoldi relation (10) is shared by other methods such as GMRES-E [19] and FGMRES [20], which are also augmented type methods.The modified Arnoldi process is outlined in Algorithm1. We remark that the modified Arnoldi process in this paper is slightly different from the one used by Morgan [19] to augment the Krylov subspace with some approximate eigenvectors. In his method, the augmenting vectors are put after the Krylov vectors while in Algorithm 1, the augmenting subspace containing a rough approximation solution is included in the projection subspace from the beginning. In general, this can give better results at the start of the regularization method proposed in this paper.Algorithm 1:Modified Arnoldi process.
Input: A∈ℝn×n, b∈ℝn, W∈ℝn×k, m.
Output: U∈ℝn×k, Vm+1∈ℝn×(m+1), H∈ℝ(m+k+1)×(m+k).
(1) Compute QR-factorizationAW=UH.
(2)  Computev1=Ab-U(UTAb), v1=v1/∥v1∥, and set V1=[v1].
(3)  Forj=1,2,…,m Do:
vj+1:=Avj;
For i=1,2,…,k Do:
hi,j+k:=U(:,i)Tvj+1;
vj+1:=vj+1-hi,j+kU(:,i);
End For
For i=1,2,…,j Do:
hi+k,j+k:=viTvj+1;
vj+1:=vj+1-hi+k,j+kvi;
End For
hj+k+1,j+k:=vj+1/∥vj+1∥;
vj+1:=vj+1/hj+k+1,j+k;
Vj+1:=[Vj,vj+1];
End ForWe remark that a loss of orthogonality can occur when the algorithm progresses; see [21]. A remedy is the so-called reorthogonalization where the current vector has to be orthogonalized against previously created vectors. One can choose between a selective reorthogonalization or a full reorthogonalization against all vectors in the current augmented subspace. In this paper we only use the full reorthogonalization. The full reorthogonalization can be done as a classical or modifed Gram-Schmidt orthogonalization; see [21] for details.We now seek to determine an approximate solutionxμ,m of (3) in the augmented Krylov subspace 𝒦m(A,Ab)+𝒲. After computing the QR factorization [W,Vm]=QR with Q∈ℝn×(m+k) having orthonormal columns and R∈ℝ(m+k)×(m+k) being an upper triangular matrix, we substitute x=[W,Vm]y, y∈ℝm+k, into (3). It yields the reduced minimization problem
(12)miny∈ℝm+k{∥A[W,Vm]y-b∥2+1μ∥[W,Vm]y∥2}=miny∈ℝm+k{∥[U,Vm+1]Hy-b∥2+1μ∥QRy∥2}=miny∈ℝm+k{1μ∥Hy-[U,Vm+1]Tb∥2+∥(I-P)b∥2+1μ∥Ry∥2},
in which P=[U,Vm+1][U,Vm+1]T is an orthogonal projector onto span([U,Vm+1]). Obviously, the reduced minimization problem (12) is equivalent to
(13)miny∈ℝm+k{∥Hy-[U,Vm+1]Tb∥2+1μ∥Ry∥2}=miny∈ℝm+k∥[H1μR]y-[[U,Vm+1]Tb0]∥2.
The normal equations of the minimization problem (13) is
(14)(HTH+1μRTR)y=HT[U,Vm+1]Tb.
We denote the solution of the minimization problem (13) by yμ,m. Then, from (14) it follows that
(15)yμ,m=(HTH+1μRTR)-1HT[U,Vm+1]Tb.
The approximate solution of (3) is
(16)xμ,m=[W,Vm]yμ,m.Since the matrixHTH+(1/μ)RTR has a larger condition number than the matrix [HT,(1/μ)RT]T, we apply the QR factorization of [HT,(1/μ)RT]T to obtain the solution yμ,m of (13) instead. The QR factorization of [HT,(1/μ)RT]T can be implemented by a sequence of Givens rotations.Define(17)ϕm(μ)=∥b-Axμ,m∥2.
Substituting xμ,m=[W,Vm]yμ,m into (17) and using the modified Arnoldi decomposition (10)  yield
(18)ϕm(μ)=∥b-A[W,Vm]yμ,m∥2=∥b-[U,Vm+1]Hyμ,m∥2=∥[U,Vm+1]Tb-Hyμ,m∥2+∥(I-P)b∥2.
Substituting yμ,m in (15) into (18), we obtain
(19)ϕm(μ)=∥[I-H(HTH+1μRTR)-1HT][U,Vm+1]Tb∥2+∥(I-P)b∥2.
Note that
(20)I-H(HTH+1μRTR)-1HT=[μHR-1(HR-1)T+I]-1.
Therefore, the function ϕm(μ) can be expressed as
(21)ϕm(μ)=∥[μHR-1(HR-1)T+I]-1[U,Vm+1]Tb∥2+∥(I-P)b∥2.Concerning the properties ofϕm(μ), we have the following results, which are similar to those of Theorem 2.1 in [11] for the Arnoldi-Tikhonov regularization method.Theorem 1.
The functionϕm(μ) has the representation
(22)ϕm(μ)=bT[U,Vm+1][μHR-1(HR-1)T+I]-2×[U,Vm+1]Tb+∥(I-P)b∥2.
Assume that Ab≠0 and (HR-1)T[U,Vm+1]Tb≠0. Then ϕm is strictly decreasing and convex for μ≥0 with ϕm(0)=∥b∥2. Moreover, the equation
(23)ϕm(μ)=τ
has a unique solution μτ,m, such that 0<μτ,m<∞, for any τ with
(24)∥P𝒩((HR-1)T)[U,Vm+1]Tb∥2+∥(I-P)b∥2<τ<∥b∥2,
where P𝒩((HR-1)T) denotes the orthogonal projector onto 𝒩((HR-1)T).Proof.
The proof follows the same argument of the proof of Theorem 2.1 in [11] and therefore is omitted.We easily obtain the following theorem, of which the proof is almost the same as that of Corollary 2.2 in [11].Theorem 2.
Assume that the modified Arnoldi process breaks down at stepj. Then the sequence {si}i=0j defined by
(25)s0=∥b∥2,si=∥P𝒩((HR-1)T)[U,Vm+1]Tb∥2+∥(I-P)b∥2,0<i<j,sj=0,
is decreasing.We apply the discrepancy principle to the discrepancyb-Axμ,m to determine an appropriate regularization parameter μ so that it satisfies (5). To make the equation
(26)ϕm(μ)=η2ε2
have a solution, it follows from Theorem 1 that the input parameter m of the modified Arnoldi should be chosen so that sm<η2ε2. To simplify the computations, we ignore the first term in sm. Then, the smallest iterative step number, denoted by mmin, of the modified Arnoldi process is chosen so that
(27)∥(I-P)b∥2<η2ε2.
We can improve the quality of the computed solution by choosing the practical iterative step number m somewhat larger than mmin.After choosing the numberm of the modified Arnoldi iterative steps, the regularization parameter μm is determined by solving the nonlinear equation ϕm(μ)=η2ε2. Many numerical methods have been proposed for the solution of a nonlinear equation, including Newton's method [22], super-Newton's [23] method, and Halley's method [24]. For the specific nonlinear equation ϕm(μ)=η2ε2, Reichel and Shyshkov proposed a new zero-finder method in their new paper [25]. In this paper, we still make use of Newton's method to obtain the regularization parameter μm.In Algorithm2, we outline the augmented Arnoldi-Tikhonov regularization method, which is used to solve large-scale linear ill-posed systems (1).Algorithm 2:Augmented Arnoldi-Tikhonov regularization method.
Input: A∈ℝn×n, b∈ℝn, W∈ℝn×k, ε, η, m0.
Output: xμ,m, μm, m=mmin+m0.
(1) Compute the modified Arnoldi decompositionA[W,Vm]=[U,Vm+1]H, with m=mmin+m0,
wheremmin is the smallest number such that ∥(I-P)b∥2<η2ε2.
(2) Compute the solutionμm of the equation ϕm(μ)=η2ε2 by Newton's method.
(3) Compute the solutionyμ,m of the least-squares problem (13) and obtain the approximate
solutionxμ,m=[W,Vm]yμ,m.Newton's method requires to evaluateϕm(μ) and its first derivative with respect to μ for computing approximations μm(j) of μm for j=0,1,2,…. Let
(28)zμ,m=[μHR-1(HR-1)T+I]-1[U,Vm+1]Tb;
that is, zμ,m satisfies the system of linear equations
(29)[μHR-1(HR-1)T+I]z=[U,Vm+1]Tb.
Note that the above linear system is the normal equations of the least-squares problem
(30)minz∈ℝm+k+1∥[μ1/2(HR-1)TI]z-[0(U,Vm+1)Tb]∥.
For numerical stability, we compute the vector zμ,m by solving the least-squares problem. Then, the ϕm(μ) is evaluated by computing
(31)ϕm(μ)=zμ,mTzμ,m+∥(I-P)b∥2.
It is easy to show that the first derivative of ϕm′(μ) can be written as
(32)ϕm′(μ)=-2zμ,mTwμ,m,
where
(33)wμ,m=[μHR-1(HR-1)T+I]-1HR-1(HR-1)Tzμ,m.
Hence, we may compute wμ,m by solving a least-squares problem analogous to the above with the vector [U,Vm+1]Tb replaced by HR-1(HR-1)Tzμ,m.The algorithm for implementing the Newton iteration for solving the nonlinear equationϕm(μ)=η2ε2 is presented in Algorithm 3.Algorithm 3:Newton's method for ϕm(μ)=η2ε2.
(1) Setμ0=0 and i=0.
(2)  Solve the least-squares problem
minz∈ℝm+k+1∥[μi1/2(HR-1)TI]z-[0(U,Vm+1)Tb]∥
to obtainzμi,m.
(3)  Computeϕm(μi)=zμi,mTzμi,m+∥(I-P)b∥2.
(4)  Solve the least-squares problem
minz∈ℝm+k+1∥[μi1/2(HR-1)TI]z-[0HR-1(HR-1)Tzμi,m]∥
to obtainwμi,m.
(5)  Computeϕm′(μi)=-2zμi,mTwμi,m.
(6)  Compute the new approximation
μi+1=μi-ϕm(μi)-η2ε2ϕm′(μi).
(7)  If|μi+1-μi|<10-6, stop; else μi:=μi+1, i:=i+1, and go to 2.Letxm be the mth iterate produced by the augmented RRGMRES in [16]. Then, xm satisfies
(34)∥Axm-b∥2=minx∈𝒦m(A,Ab)+𝒲∥Ax-b∥2=miny∈ℝm+k∥A[W,Vm]y-b∥2=miny∈ℝm+k∥[U,Vm+1]Hy-b∥2=miny∈ℝm+k∥Hy-[U,Vm+1]Tb∥2+∥(I-P)b∥2.
As μ→∞, the reduced minimization problem (12) is the same as the above minimization problem, which shows that
(35)xm=limμ→∞xμ,m.
Therefore, we obtain the following result.Theorem 3.
Letxm be the mth iterate determined by augmented RRGMRES applied to (1) with initial iterate x0=0. Then
(36)∥Axm-b∥2=ϕm(∞).


## 3. Numerical Experiments

In this section, we present some numerical examples to illustrate the performance of the augmented Arnoldi-Tikhonov regularization method for the solution of large-scale linear ill-posed systems. We compare the augmented Arnoldi-Tikhonov regularization method implemented by Algorithm2 to the Arnoldi-Tikhonov regularization method proposed in [11]. The Arnoldi-Tikhonov regularization method is denoted by ATRM while the augmented Arnoldi-Tikhonov regularization method is denoted by AATRM. In all the following tables, we denote by MV the number of matrix-vector products and by RERR the relative error ∥xμ,m-x^∥/∥x^∥, where x^ is the exact solution of the linear error-free system of (2). Note that the number of matrix-vector products in Algorithm 2 is k+mmin+m0. In all the examples, η=1.01.All the numerical experiments are performed in Matlab on a PC with the usual double precision, where the floating point relative accuracy is2.22·10-16.Example 4.
The first example considered is the Fredholm integral equation of the first kind, which takes the generic form(37)∫01‍k(s,t)x(t)dt=b(s),0≤s≤1.
Here, both the kernel k(s,t) and the right-hand side b(s) are known functions, while x(t) is the unknown function. For test, the kernel k(s,t) and the right-hand side b(s) are chosen as
(38)k(s,t)={s(t-1),s<t,t(s-1),s≥t,b(s)=s3-s6.
With this choice, the exact solution of (37) is t. We use the Matlab program deriv2 from the regularization package [26] to discretize the integral equation (37) and to generate a system of linear equations (2) with the coefficient matrix A∈ℝ200×200 and the solution x^∈ℝ200. The condition number of A is 4.9·104. The right-hand side b is given by b=Ax^+e, where the elements of the error vector e are generated from normal distribution with mean zero and the norm of e is 10-2·∥Ax^∥. The augmentation subspace is one-dimensional and is spanned by the vector w=[1,2,…,200]T. Numerical results for the example are reported in Table 1 for several choice of the number m0 of additional iterations.Table 1
Computational results of Example4.
Method
m
0
MV
RERR
AATRM
0
2
1.95
·
1
0
-
2
AATRM
1
3
1.17
·
1
0
-
2
AATRM
2
4
6.25
·
1
0
-
2
AATRM
3
5
1.19
·
1
0
-
1
ATRM
0
4
3.14
·
1
0
-
1
ATRM
1
5
2.94
·
1
0
-
1
ATRM
2
6
2.87
·
1
0
-
1
ATRM
3
7
2.89
·
1
0
-
1From Table1, we can see that for 0≤m0≤3, AATRM has smaller relative errors than ATRM, and the smallest relative error is given by AATRM with m0=1. The exact solution x^ and the approximate solutions generated by AATRM and ARTM with m0=1 are depicted in Figure 1.Figure 1
Example4. Exact solution x^; approximation solutions with m0=1.Example 5.
This example comes again from the regularization package [26] and is the inversion of Laplace transform
(39)∫0∞‍e-stx(s)ds=b(t),t≥1,
where the right-hand side b(t) and the exact solution x(t) are given by
(40)b(t)=1t+1/2,x(t)=e-t/2.
The system of linear equations (2) with the coefficient matrix A∈ℝ250×250 and the solution x^∈ℝ250 is obtained by using the Matlab program ilaplace from the regularization package [26]. In the same way as Example 4, we construct the right-hand side b of the system of linear equations (1). The augmentation subspace is also one-dimensional and is spanned by the vector w=[1,1/2,…,1/250]T. Numerical results for the example are reported in Table 2 for m0=1,2,3. Table 2 shows that AATRM with m0=2 has the smallest relative error, and AARTM works slightly better than ATRM for this problem.Table 2
Computational results of Example5.
Method
m
0
MV
RERR
AATRM
1
5
3.3
·
1
0
-
1
AATRM
2
6
9.1
·
1
0
-
2
AATRM
3
7
2.7
·
1
0
-
1
ATRM
1
6
5.7
·
1
0
-
1
ATRM
2
7
3.1
·
1
0
-
1
ATRM
3
8
4.5
·
1
0
-
1Example 6.
This example considered here is the same as Example5 except that the right-hand side b(t) and the exact solution x(t) are given by
(41)b(t)=2(t+1/2)3,x(t)=t2e-t/2.
By using the same Matlab program as Example 5, we generate a system with A∈ℝ1000×1000. The augmentation subspace is one-dimensional and is spanned by the vector w=[1,1,…,1]T. In Table 3, we report numerical results for m0=1,2,3.Table 3
Computational results of Example6.
Method
m
0
MV
RERR
AATRM
1
10
2.2
·
1
0
-
1
AATRM
2
11
1.1
·
1
0
-
1
AATRM
3
12
2.1
·
1
0
-
1
ATRM
1
10
4.9
·
1
0
-
1
ATRM
2
11
1.2
·
1
0
-
1
ATRM
3
12
2.3
·
1
0
-
1We observe from Table3 that for this example AATRM has almost the same relative errors as ATRM, and the approximate solution can be slightly improved by the augmentation space spanned by w=[1,1,…,1]T.


## 4. Conclusions

In this paper we propose an iterative method for solving large-scale linear ill-posed systems. The method is based on the Tikhonov regularization technique and the augmented Arnoldi technique. The augmentation subspace is a user-supplied low-dimensional subspace, which should contain a rough approximation of the desired solution. Numerical experiments show that the augmented method is effective for some practical problems.



---

*Source: 548487-2013-04-09.xml*