# An Iterative Method for the Least-Squares Problems of a General Matrix Equation Subjects to Submatrix Constraints

Authors: Li-fang Dai; Mao-lin Liang; Yong-hong Shen
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

An iterative algorithm is proposed for solving the least-squares problem of a general matrix equation∑i=1t‍MiZiNi=F, where Zi (i=1,2,…,t) are to be determined centro-symmetric matrices with given central principal submatrices. For any initial iterative matrices, we show that the least-squares solution can be derived by this method within finite iteration steps in the absence of roundoff errors. Meanwhile, the unique optimal approximation solution pair for given matrices Z~i can also be obtained by the least-norm least-squares solution of matrix equation ∑i=1t‍MiZ-iNi=F-, in which Z-i=Zi-Z~i,F-=F-∑i=1t‍MiZ~iNi. The given numerical examples illustrate the efficiency of this algorithm.


---

## Body

## 1. Introduction

Throughout this paper, we denote the set of allm×n real matrices by Rm×n. The symbol AT represents the transpose of matrix A. Jn and In stand for the reverse unit matrix, and identity matrix, respectively. For A,B∈Rm×n, the inner product of matrices A and B is defined by 〈A,B〉=trace(BTA), which leads to the Frobenius norm, that is, ∥A∥=〈A,A〉.A matrixA=(aij)∈Rn×n, is called centro-symmetric (centro-skew symmetric) if and only if
(1)aij=an-i+1,n-j+1(aij=-an-i+1,n-j+1),i,j=1,2,…,n,
which can also be characterized equivalently by JnAJn=A(JnAJn=-A). The set of all centro-symmetric (centro-skew symmetric) matrices is denoted by CSRn×n(CASRn×n). This kind of matrices plays an important role in many applications (see, e.g., [1–4]), and has been frequently and widely investigated (see, e.g., [5–7]) by using generalized inverse, generalized singular value decomposition (GSVD) [8], and so forth. For more, we refer the readers to [9–16] and therein.We firstly introduce the concept of the central principal submatrix which is originally put forward by Yin [17].Definition 1.
LetA∈Rn×n, if n-p is even, a p×p central principal submatrix of A, denoted by A[p], is obtained by deleting the first and last (n-p)/2 rows and columns of A, namely, A[p]=(aij)(n-p)/2≤i,j≤n-(n-p)/2.Evidently, a matrix with odd (even) order only has central principal submatrices of odd (even) order.Now, the first problem to be studied here can be stated as follows.Problem 2.
GivenMi∈Rm×pi, Ni∈Rpi×n and 𝒳i∈CSRqi×qi (i=1,2,…,t), F∈Rm×n. Find the least-squares solution Zi∈Πi of matrix equation
(2)M1Z1N1+M2Z2N2+⋯+MtZtNt=F,
in which Πi={Zi|Zi∈CSRpi×pi with Zi[qi]=𝒳i}, pi>qi, i∈Γ≜{1,2,…,t}, and Zi[qi] represents the qi×qi central principal submatrix of Zi.Problem2 is the submatrix constrained problem of matrix equation (2), which originally arises from a practical subsystem expansion problem, and has been deeply investigated (see, e.g., [7, 18–22]). In these literatures, the generalized inverses or some complicated matrix decompositions such as canonical correlation decomposition (CCD) [23] and GSVD are employed. However, it is almost impossible to solve (2) by the above methods. The iterative method is an efficient approach. Recently, kinds of iteration methods have been constructed: Zhou and Duan [24] studied the generalized Sylvester matrix equation
(3)∑i=0ϕ‍AiXFi+∑k=0ψ‍BkYFk=R
by so-called generalized Sylvester mapping that has pretty properties. Wu et al. [25] presented an finite iterative method for a class of complex matrix equations including conjugate and transpose of unknown solution. Motivated by the well-known Jacobi and Gauss-Seidel iterations methods, Ding and Chen, in [26], proposed a general family of iterative methods to solve linear matrix equations; meanwhile, these methods were also extended to solve the following coupled Sylvester matrix equations
(4)∑j=1p‍AijXjBij=Cij,i=1,2,….Although these iterative algorithms are efficient, there still exist some handicaps when meeting the constrained matrix equation problem (i.e., to find the solution of matrix equation in some matrices sets with specifical structure, for instance, symmetric matrices, centro-symmetric matrices, and bi-symmetric matrices sets) and the submatrix constrained problem, since these methods cannot keep the special properties of the unknown matrix in the iterative process. Based on the classical conjugate gradient (CG) method, Peng et al. [27] gave an iterative method to find the bisymmetric solution of matrix equation (2). Similar method was constructed to solve matrix equations (4) with generalized bisymmetric Xj in [28]. In particular, Li et al. [29] proposed an elegant algorithm for solving the generalized Sylvester (Lyapunov) matrix equation AXB+CYD=E with bisymmetric X and symmetric Y, the two unknown matrices include the given central principal submatrix and leading principal submatrix, respectively. This method shunned the difficulties in numerical instability and computational complexity, and solved the problem, completely. By borrowing the thinking of this iterative algorithm, we will solve Problem 2 by iteration method.The second problem to be considered is the optimal approximation problem.Problem 3.
LetSE be the solutions set of Problem 2. For given matrices Z~i∈Rpi×pi, find Z^i such that
(5)∑i=1t‍∥Z^i-Z~i∥2=min(Z1,Z2,…,Zt)∈SE∑i=1t‍∥Zi-Z~i∥2.This problem occurs frequently in experimental design (see for instance [30]). Here, the preliminary estimation Z~i of the unknown matrix Zi can be obtained from experiments, but it may not satisfy the structural requirement and/or spectral requirement. The best estimation of Zi, is the matrix Z^i that satisfies both requirements, which is the optimal approximation of Zi (see, e.g., [31, 32]). About this problem, we also refer the authors to [9–11, 13, 15, 16, 20–23, 27–29, 33–36] and therein.The rest of this paper is outlined as follows. In Section2, an iterative algorithm will be proposed to solve Problem 2, and the properties of which will be investigated. In Section 3, we will consider the optimal approximation Problem 3 by using the iterative algorithm. In Section 4, some numerical examples will be given to verify the efficiency of this algorithm.


## 2. The Algorithm for Problem2 and Its Properties

According to the definition of centro-symmetric matrix, whenn-q is even, a centro-symmetric matrix Z∈CSRn×n can be divided into smaller submatrices, namely,(6)Z=(Z11Z12Z13Z21Z22JqZ21J(n-q)/2J(n-q)/2Z13J(n-q)/2J(n-q)/2Z12JqJ(n-q)/2Z11J(n-q)/2),where Z11∈R(n-q)/2×(n-q)/2, Z12∈R(n-q)/2×q, Z13∈R(n-q)/2×(n-q)/2, Z21∈Rq×(n-q)/2, and Z22∈CSRq×q.Now, for some fixed positive integeri∈Γ, we define two matrix sets.
(7)CSR⋆,qipi×pi={Zi∣Zi∈CSRpi×piwithZi[qi]=0},CSR⋄,qipi×pi={Zi∣Zi=(0000Xi0000)∈CSRpi×pi,ffXi=Zi[qi]∈CSRqi×qi(0000Xi0000)}.It is clear that bothCSR⋆,qipi×pi and CSR⋄,qipi×pi are linear subspaces of Rpi×pi.In addition, for any matrixX∈Rpi×pi, it has uniquely decomposition in direct sum, that is, X=X1⊕X2, here X1=(X+JpiXJpi)/2, X2=(X-JpiXJpi)/2. Furthermore, X1=X11+X12 is also the direct sum decomposition of X1 if X11∈CSR⋆,qipi×pi, Z12∈CSR⋄,qipi×pi, since 〈X11,X12〉=0. Hence, we obtain the following.Lemma 4.
ConsiderRpi×pi=CSR⋆,qipi×pi⊕CSR⋄,qipi×pi⊕CASRpi×pi.Lemma4 reveals that any matrix W∈Rpi×pi can be uniquely written as W=W1+W2+W3, where W1∈CSR⋆,qipi×pi, W2∈CSR⋄,qipi×pi, W3∈CASRpi×pi. Then, we can define the following linear projection operators:
(8)ℒi:Rpi×pi⟶CSR⋆,qipi×piW⟶W1
for i∈Γ.According to the definition ofℒi, if W∈Rpi×pi and Y∈CSR⋆,qipi×pi, we have
(9)〈W,Y〉=〈W1,Y〉=〈ℒi(W),Y〉.
This property will be employed frequently in the residual context.The following theorem is essential for solving Problem2, which transforms equivalently Problem 2 into solving the least-square problem of another matrix equation.Theorem 5.
Any solution group of Problem2 can be obtained by
(10)(Z1,Z2,…,Zt)=(Y1+Z1⋄,Y2+Z2⋄,…,Yt+Zt⋄),
where Yi∈CSR⋆,qipi×pi is the least-squares solution of matrix equation
(11)M1Y1N1+M2Y2N2+⋯+MtYtNt=G,G=F-(M1Z1⋄N1+M2Z2⋄N2+⋯+MtZt⋄Nt),Zi⋄=(0000𝒳i0000)∈CSR⋄,qipi×pi,𝒳i∈CSRqi×qi is the given central principal submatrix of Zi in Problem 2.Proof.
Noting that the definition ofCSR⋆,qipi×pi, we have
(12)minZi∈Πi∥∑i=1t‍MiZiNi-F∥⟺minYi∈CSR⋆,qipi×pi∥∑i=1t‍Mi(Yi+Z¯i)Ni-F∥⟺minYi∈CSR⋆,qipi×pi∥∑i=1t‍MiYiNi-G∥.
The proof is completed.Remark 6.
It follows, from Theorem5, that Problem 2 can be solved completely by finding the least-squares solution of matrix equations (11) in subspaces CSR⋄,qipi×pi.In the next part of this section, we will establish an iterative algorithm for (11) and analysis its properties. For the convenience of expression, we define a matrix function
(13)ℱ(Z1,Z2,…,Zt)=M1Z1N1+M2Z2N2+⋯+MtZtNt,
then matrix equation (11) can be simplified as
(14)ℱ(Z1,Z2,…,Zt)=G.
Moreover, we can easily verify that
(15)〈X,ℱ(Z1,Z2,…,Zt)〉=∑i=1t‍〈MiTXNiT,Zi〉
holds for arbitrary X∈Rm×n.The iterative algorithm for the least squares problem of matrix equations (11) can be expressed as follows.Algorithm 7.
Consider the following.
Step
1. Let Mi∈Rm×pi, Ni∈Rpi×n, F∈Rm×n and 𝒳i∈CSRqi×qi for i∈Γ.
Input arbitrary matricesYi(0)∈CSR⋆,qipi×pi.
Step
2. Calculate
(16)R0=G-ℱ(Y1(0),Y2(0),…,Yt(0)),Pi(0)=ℒi(MiTR0NiT),Qi(0)=Pi(0),k=0.
Step
3. Calculate
(17)Yi(k+1)=Yi(k)+αkQi(k),αk=∑i=1t‍∥Pi(k)∥2∥ℱ(Q1(k),Q2(k),…,Qt(k))∥2.
Step
4. Calculate
(18)Rk+1=G-ℱ(Y1(k+1),Y2(k+1),…,Yt(k+1))=Rk-αkℱ(Q1(k),Q2(k),…,Qt(k)),Pi(k+1)=ℒi(MiTRk+1NiT)=Pi(k)-αkℒi(MiTℱ(Q1(k),Q2(k),…,Qt(k))NiT),Qi(k+1)=Pi(k+1)+βkQi(k),βk=∑i=1t‍∥Pi(k+1)∥2∑i=1t‍∥Pi(k)∥2.
Step
5. If ∑i=1t‍∥Pi(k)∥2=0, stop. Otherwise, k:=k+1, go to Step 3.From Algorithm7, we can see that Yi(k),Pi(k),Qi(k),∈CSR⋆,qipi×pi. In particular, (Y1(k),Y2(k),…,Yt(k)) is a least-squares solution group belonging to matrix equation (11) if Pi(k)=0 for all i∈Γ. The following lemma gives voice to the reason.Lemma 8.
Ifℒi(MiTRkNiT)=0(i=1,2,…,t) hold simultaneously for some positive k, then (Y1(k),Y2(k),…,Yt(k)) generated by Algorithm 7 is a solution group of matrix equation (11).Proof.
Letℒ={L∣L=ℱ(Yi),Yi∈CSR⋆,qipi×pi} and G^=ℱ(Yi(k)). Obviously, G^∈ℒ. Then, from the Project Theorem, (Y1(k),Y2(k),…,Yt(k)) is a least-square solution group of matrix equation (11) if and only if G-G^⊥ℒ. That is to say, for any matrices Yi∈CSR⋆,qipi×pi, noting that Lemma 4, we have 〈G-G^,ℱ(Y1,Y2,…,Yt)〉=0, that is,
(19)〈G-G^,ℱ(Y1,Y2,…,Yt)〉=〈Rk+1,ℱ(Y1,Y2,…,Yt)〉=∑i=1t‍〈MiTRk+1NiT,Yi〉=∑i=1t‍〈ℒi(MiTRk+1NiT),Yi〉=0,
which completes the proof.In addition, the sequences{Yi(l)}, {Pi(l)}, {Qi(l)} generated by Algorithm 7 are self-orthogonal, that is, as follows.Lemma 9.
Suppose that the sequences{Yi(l)}, {Pi(l)}, {Qi(l)} generated by Algorithm 7 not equal null for l≤k, then
(20)(1)∑i=1t‍〈Pi(j),Pi(l)〉=0,(21)(2)∑i=1t‍〈Qi(j),Pi(l)〉=0,(22)(3)〈ℱ(Q1(j),Q2(j),…,Qt(j)),ℱ(Q1(l),Q2(l),…,Qt(l))〉=0,
where j,l=1,2,…,k, j≠l≤k.Proof.
In view of the symmetry of the inner product, we only prove (20)–(22) when j<l. According to Algorithm 7, when k=1, we have
(23)∑i=1t‍〈Pi(0),Pi(1)〉=∑i=1t‍〈Pi(0),Pi(0)-α0ℒiMiT(ℱ(Q1(0),Q2(0),…,Qt(0))NiT)〉=∑i=1t‍[〈Pi(0),Pi(0)〉fffff-α0〈Pi(0),ℒiMiT(ℱ(Q1(0),Q2(0),…,Qt(0))NiT)〉]=∑i=1t‍∥Pi(0)∥2-α0×∑i=1t‍〈Pi(0),MiTℱ(Q1(0),Q2(0),…,Qt(0))NiT〉=∑i=1t‍∥Pi(0)∥2-α0∑i=1t‍〈MiPi(0)Ni,ℱ(Q1(0),Q2(0),…,Qt(0))〉=∑i=1t‍∥Pi(0)∥2-α0∥ℱ(Q1(0),Q2(0),…,Qt(0))∥2=0,
which also deduces that
(24)∑i=1t‍〈Qi(0),Pi(1)〉=∑i=1t‍〈Qi(0),Pi(0)-α0ℒi(MiTℱ(Q1(0),Q2(0),…,Qt(0))NiT)〉=∑i=1t‍〈Qi(0),Pi(0)〉-α0×∑i=1t‍〈Qi(0),MiTℱ(Q1(0),Q2(0),…,Qt(0))NiT〉=∑i=1t‍〈Pi(0),Pi(0)〉-α0×∑i=1t‍〈MiQi(0)Ni,ℱ(Q1(0),Q2(0),…,Qt(0))〉=0,〈ℱ(Q1(0),Q2(0),…,Qt(0)),ℱ(Q1(1),Q2(1),…,Qt(1))〉=〈ℱ(Q1(0),Q2(0),…,Qt(0)),∑i=1t‍[Mi(Pi(1)+β0Qi(0))Ni]〉=〈ℱ(Q1(0),Q2(0),…,Qt(0)),ℱ(P1(1),P2(1),…,Pt(1))〉+β0∥ℱ(Q1(0),…,Qt(0))∥2=1α0〈R0-R1,ℱ(P1(1),P2(1),…,Pt(1))〉+β0∥ℱ(Q1(0),Q2(0),…,Qt(0))∥2=1α0[∑i=1t‍〈MiTR0NiT,Pi(1)〉-∑i=1t‍〈MiTR1NiT,Pi(1)〉]+β0∥ℱ(Q1(0),Q2(0),…,Qt(0))∥2=-1α0∑i=1t‍∥Pi(1)∥2+β0∥ℱ(Q1(0),Q2(0),…,Qt(0))∥2=0.
Assume that (20), (21), and (22) hold for positive integer s (<k), that is, for j=1,2,…,s-1,
(25)∑i=1t‍〈Pi(j),Pi(s)〉=0,∑i=1t‍〈Qi(j),Pi(s)〉=0,〈ℱ(Q1(j),Q2(j),…,Qt(j)),ℱ(Q1(s),Q2(s),…,Qt(s))〉=0.
Then, similar to the above proof, noting that the assumptions, we have
(26)∑i=1t‍〈Pi(j),Pi(s+1)〉=∑i=1t‍〈Pi(j),Pi(s)-αsℒi(MiTℱ(Q1(s),Q2(s),…,Qt(s))NiT)〉=∑i=1t‍〈Pi(j),Pi(s)〉-αs×∑i=1t‍〈Pi(j),ℒi(MiTℱ(Q1(s),Q2(s),…,Qt(s))NiT)〉=-αs∑i=1t‍〈MiPi(j)Ni,ℱ(Q1(s),Q2(s),…,Qt(s))〉=-αs∑i=1t‍〈Mi(Qi(j)-βj-1Qj-1,i)Ni,fffffffffffℱ(Q1(s),Q2(s),…,Qt(s))〉=-αs〈ℱ(Q1(j),Q2(j),…,Qt(j)),ℱ(Q1(s),Q2(s),…,Qt(s))〉+αsβj-1〈ℱ(Q1(j-1),Q2(j-1),…,Qt(j-1)),fffffffffffffℱ(Q1(s),Q2(s),…,Qt(s))〉=0.
Furthermore,
(27)∑i=1t‍〈Qi(j),Pi(s+1)〉=∑i=1t‍〈Qi(j),Pi(s)-αsℒi(MiTℱ(Q1(s),Q2(s),…,Qt(s))NiT)〉=∑i=1t‍〈Pi(j),Pi(s)〉-αs×∑i=1t‍〈MiQi(j)Ni,ℱ(Q1(s),Q2(s),…,Qt(s))〉=0,〈ℱ(Q1(j),Q2(j),…,Qt(j)),ℱ(Q1(s+1),Q2(s+1),…,Qt(s+1))〉=〈ℱ(Q1(j),Q2(j),…,Qt(j)),ℱ(P1(s+1),P2(s+1),…,Pt(s+1))〉+βs〈ℱ(Q1(j),Q2(j),…,Qt(j)),ℱ(Q1(s),Q2(s),…,Qt(s))〉=1αj〈Rj-Rj+1,ℱ(P1(s+1),P2(s+1),…,Pt(s+1))〉=1αj[∑i=1t‍〈MiTRjNiT,Pi(s+1)〉-∑i=1t‍〈MiTRj+1NiT,Pi(s+1)〉]=1αj[∑i=1t‍〈Pi(j),Pi(s+1)〉-∑i=1t‍〈Pj+1,i,Pi(s+1)〉]=0.
The last equal sign “=” holds due to ∑i=1t‍〈Pi(s),Pi(s+1)〉=0. In fact, from the hypothesis, we deduce
(28)∑i=1t‍〈Pi(s),Pi(s+1)〉=∑i=1t‍〈Pi(s),Pi(s)-αsℒi(MiTℱ(Q1(s),Q2(s),…,Qt(s))NiT)〉=∑i=1t‍∥Pi(s)∥2-αs∑i=1t‍〈Mi(Qi(s)-βs-1Qi(j-1))Ni,ℱ(Q1(s),Q2(s),…,Qt(s))〉=∑i=1t‍∥Pi(s)∥2-αs∥ℱ(Q1(s),Q2(s),…,Qt(s))∥2+αsβs-1〈ℱ(Q1(s-1),Q2(s-1),…,Qt(s-1)),fffffffffffℱ(Q1(s),Q2(s),…,Qt(s))〉=0.
Moreover,
(29)∑i=1t‍〈Qi(s),Pi(s)〉=∑i=1t‍〈Pi(s)+βs-1Qi(s-1),Pi(s)〉=∑i=1t‍∥Pi(s)∥2+βs-1∑i=1t‍〈Qi(s-1),Pi(s)〉=∑i=1t‍∥Pi(s)∥2.
It follows from (29) that
(30)∑i=1t‍〈Qi(s),Pi(s+1)〉=∑i=1t‍〈Qi(s),Pi(s)-αsℒi(MiTℱ(Q1(s),Q2(s),…,Qt(s))NiT〉=∑i=1t‍[〈Qi(s),Pi(s)〉dddddd-αs〈Qi(s),MiTℱ(Q1(s),Q2(s),…,Qt(s))NiT〉]=∑i=1t‍∥Pi(s)∥2-αs∥ℱ(Q1(s+1),Q2(s+1),…,Qt(s+1))∥2=0,〈ℱ(Q1(s),Q2(s),…,Qt(s)),ℱ(Q1(s+1),Q2(s+1),…,Qt(s+1))〉=〈ℱ(Q1(s),…,Qt(s)),ℱ(P1(s+1),P2(s+1),…,Pt(s+1))〉+βs∥ℱ(Q1(s),…,Qt(s))∥2=1αs〈Rs-Rs+1,ℱ(P1(s+1),P2(s+1),…,Pt(s+1))〉+βs∑i=1t‍∥MiQi(s)Ni∥2=-1αs∑i=1t‍〈MiTRs+1NiT,Pi(s+1)〉+βs∑i=1t‍∥MiQi(s)Ni∥2=0.
Therefore, for arbitrary integers number l, the conclusions hold. The proof is completed.Remark 10.
We know from Lemma4 that the matrices sequences
(31)(P0,1⋱P0,t),(P1,1⋱P1,t),…,(Pk,1⋯Pk,t),…
are orthogonal to each other. Hence, it can be regarded as an orthogonal basis of matrix space R∑i=1t‍pi×∑i=1t‍pi. Hence, the iteration will be terminated at most ∑i=1t‍(pi+qi)(pi-qi)/2 steps in the absence of roundoff errors. Therefore, there exists a positive integer k≤∑i=1t‍(pi+qi)(pi-qi)/2 such that ∑i=1t‍∥Pi(k)∥2=0, in this case, (Y1(k),Y2(k),…,Yt(k)) can be regarded as a least-squares solution group of matrix equation (11).
In addition, we should point out that ifαk=0 or ∞, the conclusions may not be true, and the iteration will break down before Pi(k)=0 for k<∑i=1t‍(pi+qi)(pi-qi)/2. Actually, αk=0 implies that ∑i=1t‍∥Pi(k)∥2=0, so Pi(k)=0 for i∈Γ. While αk=∞ leads to ℱ(Q1(k),Q2(k),…,Qt(k))=0, making inner product with Ri by both sides, it follows from Algorithm 7 that
(32)〈Ri,ℱ(Q1(k),Q2(k),…,Qt(k))〉=∑i=1t‍〈Pi(k),Pi(k)+βk-1Qi(k-1)〉=∑i=1t‍∥Pi(k)∥2+βk-1∑i=1t‍〈Pi(k),Qi(k-1)〉=∑i=1t‍∥Pi(k)∥2=0,
which also implies the same situation as αk=0. Hence, if there exists a positive integer s such that the coefficient αs=0 or αs=∞, then the corresponding matrix group Y1(s),Y2(s),…,Yt(s) is just the solution of matrix equation (11).Together with the above analysis and Lemma9, we can conclude the following theorem.Theorem 11.
For any initial iteration matricesYi(0)∈CSR⋆,qin×n, i=1,2,…,t, the least-squares solution of matrix equation (11) can be obtained within finite iteration steps. Moreover, Suppose that (Y˘1,Y˘2,…,Y˘t) is a least-squares solution group of (11), then the general solution to Problem 2 can be expressed as Zi=Y˘i+Xi+Zi⋄(i=1,2,…,t), where Xi∈CSR⋆,qin×n satisfy homogeneous equation
(33)ℱ(X1,X2,…,Xt)=0,Zi⋄ as in Theorem 5.In order to show the validity of Theorem11, it is adequate to prove the following conclusion.Proposition 12.
The least-squares solution group(Y˘1,Y˘2,…,Y˘t) of matrix equation (11) can be expressed as Y˘i+Xi, where Xi satisfy equality (33).Proof.
According to the assumptions, we obtain(34)minYi∈CSR⋆,qin×n∥ℱ(Y1,Y2,…,Yt)-G∥=∥ℱ(Y˘1,Y˘2,…,Y˘t)-G∥.
On the other hand, noting that ℱ(X1,X2,…,Xt)=0, then
(35)∥ℱ(Y˘1+X1,Y˘2+X2,…,Y˘t+Xt)-G∥2=∥ℱ(Y˘1,Y˘2,…,Y˘t)-G+ℱ(X1,X2,…,Xt)∥2=∥ℱ(Y˘1,Y˘2,…,Y˘t)-G∥2.
The proof is completed.Next, we will show that the unique least norm solution of matrix equation (11) can be derived by choosing a special kind of initial iteration matrices.Theorem 13.
Let the initial iteration matricesYi(0)=ℒi(MiTHNiT) with arbitrary H∈Rm×n, i=1,2,…,t, and then (Y1*,Y2*,…,Yt*) generated by Algorithm 7 is the least-norm least-squares solution group of matrix equation (11). Furthermore, the least-norm solution group to Problem 2 can be expressed by
(36)(Z1*,Z2*,…,Zt*)=(Y1*+Zi⋄,Y2*+Z2⋄,…,Yt*+Zt⋄).Proof.
From Algorithm7 and Theorem 11, for initial iteration matrices Yi(0)=ℒi(MiTHNiT), we can obtain a least-squares solution Yi* of matrix equation (11) and there exists a matrix H* such that Yi*=ℒi(MiTH*NiT). Hence, it is enough to prove that the Yi* is the least-norm solution. In fact, noting that (33) and Proposition 12, we have
(37)∑i=1t‍∥Yi*+Xi∥2=∑i=1t‍(∥Yi*∥2+∥Xi∥2+2〈Yi*,Xi〉)=∑i=1t‍∥Yi*∥2+∑i=1t‍∥Xi∥2+2∑i=1t‍〈ℒi(MiTH*NiT),Xi〉≥∑i=1t‍∥Yi*∥2,
as required.Theorems11 and 13 display the efficiency of Algorithm 7. Actually, the iteration sequence {Yi(k)} converges smoothly to the solution Yi, that is the minimization property of Algorithm 7.Theorem 14.
For any initial iteration matricesYi(0), the Yi(k) generated by Algorithm 7 satisfy the minimization problem
(38)∥ℱ(Y1(k),Y2(k),…,Yt(k))-G∥=minYi∈𝕃i∥ℱ(Y1,Y2,…,Yt)-G∥,
where 𝕃i=Yi(0)+span{Qi(0),Qi(1),…,Qi(k-1)}, i=1,2,…,t.Proof.
From the definition of𝕃i, there exist a series of real numbers a0,a1,…,ak-1 such that Yi=Yi(0)+∑l=0k-1‍alQi(l).
Define a function ofk variables f(a0,a1,…,ak-1), that is,
(39)f(a0,a1,…,ak-1)=∥∑i=1t‍[Mi(Yi(0)+∑l=0k-1‍alQi(l))Ni-G]∥2.
In addition, from Algorithm 7, we know that
(40)R0=Rl+αl-1ℱ(Q1(l-1),Q2(l-1),…,Qt(l-1))+⋯+α0ℱ(Q1(0),Q2(0),…,Qt(0)).
Noting that (22) and making the inner product with ℱ(Q1(l),Q2(l),…,Qt(l)) on both sides of (40) yield
(41)〈ℱ(Q1(l),Q2(l),…,Qt(l)),R0〉=〈ℱ(Q1(l),Q2(l),…,Qt(l)),Rl〉.
Hence, by simple calculation, (40) and (41), the function can be rewritten as
(42)f(a0,a1,…,ak-1)=∥R0∥2+∑l=0k-1‍al2∥ℱ(Q1(l),Q2(l),…,Qt(l))∥2-2∑l=0k-1‍al〈ℱ(Q1(l),Q2(l),…,Qt(l)),Rl〉.
Then,
(43)minalf(a0,a1,…,ak-1)⟺minYi∈𝕃i∥ℱ(Y1,Y2,…,Yt)-G∥.
Sincef(a0,a1,…,ak-1)=min only if ∂f/∂al=0, it follows from (29) that
(44)al=〈ℱ(Q1(l),Q2(l),…,Qt(l)),Rl〉∥ℱ(Q1(l),Q2(l),…,Qt(l))∥2=∑i=1t‍〈Qi(l),Pl,i〉∥ℱ(Q1(l),Q2(l),…,Qt(l))∥2=∑i=1t‍∥Pl,i∥2∥ℱ(Q1(l),Q2(l),…,Qt(l))∥2=αl.
Combined with (43), we complete the proof.Theorem14 reveals that the sequence
(45){∥ℱ(Y1(k),Y2(k),…,Yt(k))-G∥}
monotonically decreases with respect to increasing integer k. The descent property of the residual norm of matrix equation (11) leads to the smoothly convergence of Algorithm 7.


## 3. The Solution of Problem3

In this section, we discuss the optimal approximation Problem3. Since the least squares problem is always consistent, it is easy to verify that the solution set SE of Problem 2 is a nonempty convex cone, so the optimal approximation solution is unique.Without loss of generality, we can assume that the given matricesZ~i∈CSR⋆,qipi×pi. In fact, from Lemma 4, arbitrary Z~i∈Rpi×pi can be divided into
(46)Z~i=Z~i1+Z~i2+X~i3,withZ~i1∈CSR⋆,qipi×pi,hhhhhhhhZ~i2∈CSR⋄,qipi×pi,Z~i3∈CASRpi×pi.
Furthermore, if Zi∈CSR⋆,qipi×pi, then
(47)∥Zi-Z~i∥2=∥Zi-Z~i1∥2+∥Z~i2∥2+∥Z~i3∥2,
which meets the claim.DenoteZ¯i=Zi-Z~i, F¯=F-ℱ(Z~1,Z~2,…,Z~t), then to solve Problem 3 is equivalent to find the least-norm solution of the new matrix equation
(48)ℱ(Z¯1,Z¯2,…,Z¯t)=F¯.
Furthermore, similar to the construction of (11), Problem 2 is transformed equivalently into finding the least-norm least-squares solution of matrix equation
(49)ℱ(Y¯1,Y¯2,…,Y¯t)=G¯,withY¯i∈CSR⋆,qipi×pi,
in which G¯=F¯-ℱ(Z1⋄,Z2⋄,…,Zt⋄).Therefore, we can apply Algorithm7 to derive the required solution of matrix equation (49). Virtually, it follows from Theorem 13 that if let the initial iteration matrices Y¯i(0)=ℒi(MiTH~NiT) with arbitrary H~∈Rm×n, or especially Y¯i(0)=0∈Rpi×pi, then the iteration solutions Y¯i* consist of the least-norm least-squares solution of which. In this case, the unique optimal approximation solution to Problem 3 can be obtained by
(50)(Z^1,Z^2,…,Z^t)=(Y¯1*+Z~1+Z1⋄,Y¯2*+Z~2+Z2⋄,…,Y¯t*+Z~t+Zt⋄).


## 4. Numerical Example

In this section, we illustrate the efficiency and reliability of Algorithm7 by some numerical experiments.All the numerical experiments are performed by using Matlab 6.5. In addition, because of the influence of the roundoff errors,Pi(k) may not equal zero within finite iteration steps, so the iteration will be terminated if ∑i=1t‍∥Pi(k)∥2<ϵ, for example, let ϵ=1.0e-008. At this time, (Y1(k),Y1(k),…,Yt(k)) can be regarded as a solution of matrix equation (11), and Yi(k)+Zi⋄ (i=1,2,…,t) consist of the solution group to Problem 2. In particular, let the initial iteration matrices Yi(0)=0, then we will obtain the least-norm solution by (36).Example 1.
Input matricesM1, M2, M3, N1, N2, N3, and F as follows:
(51)M1=[hilb(r2)ones(r2)hankel(1:r2)zeros(r2)],M2=[toeplitz(1:r2)hilb(r2)ones(r2)hankel(1:r2)],M3=[zeros(r2)hankel(1:r2)hilb(r2)ones(r2)],N1=eye(r),N2=ones(r),N3=tridiag([7,1,-1],r),F=[3-2-1-23-2⋱-1-2⋱-2-1⋱-23-2-1-23],where toeplitz(k), hilb(k), hankel(k), zeros(k), and eye(k) denote the Toeplitz matrix, Hilbert matrix, Hankel matrix, null matrix, identity matrix with orders k, and the elements of matrix ones(·) are one, tridiag([7,1,-1],r) represents r×r tri-diagonal matrix produced by vector [7,1,-1].Let the given central principal matrices(52)𝒳1=zeros(r2),𝒳2=ones(r2)*10,𝒳3=toeplitz(1:r2).
By using the Algorithm 7, we obtain the solution to Problem 2. To save space, we shall not report the explicit datum of the solution, but the bars graphs of the components for the solution matrices will be given. Let r=20, Figure 1 shows the bars graphs of Z1, Z2, Z3 when we choose the initial iterative matrices
(53)Yi=(ones(r-q2)ones(r-q2,q)ones(r-q2)ones(q,r-q2)zeros(r2)ones(q,r-q2)ones(r-q2)ones(r-q2,q)ones(r-q2)),hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhi=1,2,3,
and the terminal condition ∥P1(k)∥+∥P2(k)∥+∥P3(k)∥<ϵ=1.0e-012.The bars graphs ofZi when r=20.
(a)
(b)
(c)Moreover, whenr=20 and r=40, the convergence curves for the Frobenius norm of the residual denoted by RES=∥Rk∥ and the termination condition denoted by TC=∥P1(k)∥+∥P2(k)∥+∥P3(k)∥ are plotted in Figures 2 and 3, respectively.Figure 2
The convergence curve of the Frobenius norm of the residual.Figure 3
The convergence curve of the Frobenius norm of the terminated condition.From Figure2, we can see that the residual norm of Algorithm 7 is monotonically decreasing, which is in accordance with the theory established in Theorem 14, namely, this algorithm is numerical stable. While Figure 3 shows that the terminated condition ∥P1(k)∥+∥P2(k)∥+∥P3(k)∥ is oscillating back and forth and approaches to zero as iterative process. Hence, the iterative Algorithm 7 is efficient, but it lacks of smooth convergence. Of course, for a problem with large and sparse matrices, Algorithm 7 may not terminate in a finite number of steps because of roundoff errors. How to establish an efficient and smooth algorithm is an important problem which we should study in a future work.



---

*Source: 697947-2013-11-21.xml*