# A New Iterative Algorithm for Solving a Class of Matrix Nearness Problem

Authors: Xuefeng Duan; Chunmei Li
Journal: ISRN Computational Mathematics
 (2012)

---

## Abstract

Based on the alternating projection algorithm, which was proposed by Von Neumann to treat the problem of finding the projection of a given point onto the intersection of two closed subspaces,
we propose a new iterative algorithm to solve the matrix nearness problem associated with
the matrix equationsAXB=E, CXD=F, which arises frequently in experimental design. If
we choose the initial iterative matrix X0=0, the least Frobenius norm solution of these matrix
equations is obtained. Numerical examples show that the new algorithm is feasible and effective.


---

## Body

## 1. Introduction

Denoted byRm×n be the set of m×n real matrices, AT and A+ be the transpose and Moore-Penrose generalized inverse of the matrix A, respectively. For A,B∈Rm×n,  〈A,B〉=trace(BTA) denotes the inner product of the matrix A and B. The induced norm is the so-called Frobenius norm, that is, ∥A∥=〈A,A〉1/2; then Rm×n is a real Hilbert space. Let M be a closed convex subset in a real Hilbert space H and u be a point in H; then the point in M nearest to u is called the projection of u onto M and denoted by PM(u); that is to say, PM(u) is the solution of the following minimization problem (see [1, 2])
(1)min⁡x∈M‖x-u‖,
that is,
(2)‖PM(u)-u‖=min⁡x∈M‖x-u‖.The problem of finding a nearness matrixX̂ in a constraint matrix set to a given matrix X¯ is called the matrix nearness problem. Because the preliminary estimation X¯ is frequently obtained from experiments, it may not satisfy the given restrictions. Hence it is necessary to find a nearness matrix X̂ in this constraint matrix set to replace the estimation X¯ [3]. In the area of structure design, finite element model updating and control theory, and so forth, the matrix set is always the (constraint) solution set or the least square (constraint) solution set of some matrix equations [4–6]. Thus, the problem mentioned above is also called the matrix nearness problem associated with the matrix equation. Recently, there are many discussions on the matrix nearness problem associated with some matrix equations. For instance, see [4, 6–14].In this paper, we consider the following problem.Problem 1.
Given matricesA∈Rp×n,B∈Rn×q,C∈Rs×n,D∈Rn×t,E∈Rp×q,F∈Rs×t, and X¯∈Rn×n, find X̂∈Ω such that
(3)‖X̂-X¯‖=min⁡X∈Ω‖X-X¯‖,
where
(4)Ω={X∈Rn×n∣AXB=E,CXD=F}.
Obviously, Ω is the solution set of the matrix equations
(5)AXB=E,CXD=F,
and X̂ is the optimal approximate solution of (5) to the given matrix X¯. In particular, if X¯=0, then the solution X̂ of Problem 1 is just the least Frobenius norm solution of the matrix equations (5). It is easy to verify that Ω is convex set; then the solution of Problem 1 is unique.The matrix equations (5) and its matrix nearness problem have been extensively studied for the past 40 or more years. Wang [15] and Navarra et al. [16] gave some conditions for the existence of a solution and some representations of the general common solution to (5). By the projection theorem and matrix decompositions, Liao et al. [6] gave an analytical expression of the optimal approximate least square symmetric solution of (5). However, these direct methods may be less efficient for the large sparse coefficient matrices due to the limited storages and the speeds of the computers. Therefore, iterative methods for solving the matrix equations (5) have attracted much interests recently. Peng et al. [11] and Chen et al. [7] proposed some iterative methods to compute the symmetric solutions and optimal approximate symmetric solution of (5). An efficient iterative method was presented to solve the matrix nearness Problem 1 associated with the matrix equations (5) in [13]. Ding et al. [17] considered the unique solution of the matrix equations (5) and used gradient-based iterative algorithm to compute the unique solution. The (least square) solution and the optimal approximate (least square) solution of (5), which is constrained as bisymmetric, reflexive, generalized reflexive, generalized centrosymmetric, were studied in [7–10, 12].The alternating projection algorithm dates back to von Neumann [18], who treated the problem of finding the projection of a given point onto the intersection of two closed subspaces. Later, Bauschke and Borwein [1] extended the analysis of Von Neumann’s alternating projection scheme to the case of two closed affine subspaces. There are many variations and extensions of the alternating projection algorithm, and we can use them to find the projection of a given point onto the intersection of k(k≥2) closed subspaces [19] and k(k≥2) closed convex sets [20, 21]. For a complete discussion on the alternation projection algorithm see Deutsch [2].In this paper, we propose a new algorithm to solve Problem1. We state Problem 1 as the minimization of a convex quadratic function over the intersection of two closed affine subspaces in the vector space Rn×n. From this point of view, Problem 1 can be solved by the alternating projection algorithm. If we choose the initial iterative matrix X0=0, the least Frobenius norm solution of the matrix equations AXB=E,CXD=F is obtained. In the end, we use some numerical examples to show that the new algorithm is faster and lower computational cost for each step than the algorithm proposed by Sheng and Chen [13] to solve Problem 1. Especially, the CPU time and iteration steps of our algorithm increase slowly as the dimension of the matrix is increasing; so our algorithm is suitable for large-scale problems.


## 2. Alternating Projection Algorithm for Solving Problem1

In this section, we apply the alternating projection algorithm to solve Problem1. We begin with two lemmas.Lemma 1 (see [1, Theorem  4.1]).
LetM1=a+M̃1,M2=b+M̃2 be closed affine subspaces in a Hilbert space H and u be a point in H. Here, M̃1 and M̃2 are closed subspaces and a,b∈H. If M1∩M2≠∅, then the sequences {xk} and {yk} generated by the alternating projection algorithm
(6)x0=u,yk+1=PM1(xk),xk+1=PM2(yk+1),k=0,1,2,…
both converge to the projection of the point u onto the intersection of M1 and M2, that is,
(7)xk⟶PM1∩M2(u),yk⟶PM1∩M2(u),k⟶+∞.Lemma 2 (see [22, Theorem  9.3.1]).
LetA∈Rp×n,B∈Rn×q and E∈Rp×q, be known matrices. Then the matrix equation AXB=E has a solution if and only if
(8)AA+EB+B=E,
and the representation of the solution is
(9)X=A+EB++Y-A+AYBB+,
where Y∈Rn×n is arbitrary.Lemma 3 (see [22, Theorem  9.3.2]).
GivenZ∈Rn×n, set
(10)R={X∈Rn×n∣AXB=E,A∈Rp×n,B∈Rn×q,E∈Rp×q},
then the solution X̂ of the following problem
(11)min⁡X∈R‖X-Z‖
is
(12)X̂=Z+A+(E-AZB)B+,
that is,
(13)‖X̂-Z‖=min⁡X∈R‖X-Z‖.Now we begin to use the alternating projection algorithm (6) to solve Problem 1. Firstly, we define two sets
(14)Ω1={X∈Rn×n∣AXB=E},Ω2={X∈Rn×n∣CXD=F}.
It is easy to know that Ω=Ω1∩Ω2, and if the set Ω is nonempty, then
(15)Ω=Ω1∩Ω2≠∅.
And by Lemma 2, the sets Ω1 and Ω2 can be equivalently written as
(16)Ω1={X∣AXB=E}={X=A+EB++Y-A+AYBB+∣Y∈Rn×n}=A+EB++{Y-A+AYBB+∣Y∈Rn×n},Ω2={X∣CXD=F}={X=C+FD++Y-C+CYDD+∣Y∈Rn×n}=C+FD++{Y-C+CYDD+∣Y∈Rn×n}.
Hence, Ω1 and Ω2 are closed affine subspaces.After defining the setsΩ1 and Ω2, Problem 1 can be rewritten as finding X̂∈Ω=Ω1∩Ω2, such that
(17)‖X̂-X¯‖=min⁡X∈Ω1∩Ω2‖X-X¯‖.
Noting the equalities (17) and (2), it is easy to find that
(18)X̂=PΩ1∩Ω2(X¯).
Therefore, Problem 1 can be converted equivalently into finding the projection PΩ1∩Ω2(X¯) of a given matrix X¯ onto the intersection set Ω1∩Ω2. Now we will use alternating projection algorithm (6) to compute the projection PΩ1∩Ω2(X¯). Consequently, we can get the solution X̂ of Problem 1.By (6) we can see that the key problems to realize the alternating projection algorithm (6) are how to compute the projections PΩ1(Z),PΩ2(Z) of a matrix Z onto Ω1 and Ω2, respectively. Such problems are perfectly solvable in the following theorems.Theorem 1.
Suppose that the setΩ1 is nonempty. For a given n×n matrix Z, we have
(19)PΩ1(Z)=Z+A+(E-AZB)B+.Proof.
By (1) and (2), we know that the projection PΩ1(Z) is the solution of the following minimization problem
(20)min⁡X∈Ω1‖X-Z‖,
and according to Lemma 3 we know that the solution of the minimization problem (20) is Z+A+(E-AZB)B+. Hence,
(21)PΩ1(Z)=Z+A+(E-AZB)B+.Theorem 2.
Suppose that the setΩ2 is nonempty. For a given n×n matrix Z, we have
(22)PΩ2(Z)=Z+C+(F-CZD)D+.Proof.
The proof is similar to that of Theorem1 and is omitted here.By the alternation projection algorithm (6) and Theorems 1 and 2, we get a new algorithm to solve Problem 1 which can be stated as follows.Algorithm 1.
One has(1)
setÃ=A+,B̃=B+,C̃=C+,D̃=D+;(2)
setX0=X¯;(3)
fork=0,1,2,3,…(23)Yk+1=PΩ1(Xk)=Xk+Ã(E-AXkB)B̃,Xk+1=PΩ2(Yk+1)=Yk+1+C̃(F-CYk+1D)D̃,
end.
By Lemma1 and (15) and (16), we get the convergence theorem for Algorithm 1.Theorem 3.
If the setΩ is nonempty, then the matrix sequences {Xk} and {Yk} generated by Algorithm 1 both converge to the projection PΩ1∩Ω2(X¯) of  X¯ onto the intersection of Ω1 and Ω2, that is,
(24)Xk⟶PΩ1∩Ω2(X¯),Yk⟶PΩ1∩Ω2(X¯),k⟶+∞.Proof.
If the setΩ is nonempty, by (15) we have
(25)Ω1∩Ω2≠∅.
And noting (16), we know that the sets Ω1 and Ω2 are closed affine subspaces in Hilbert space Rm×n. Hence, by Lemma 1 we derive that the matrix sequences {Xk} and {Yk} generated by Algorithm 1 both converge to the projection PΩ1∩Ω2(X¯) of X¯ onto the intersection of Ω1 and Ω2, that is,
(26)Xk⟶PΩ1∩Ω2(X¯),Yk⟶PΩ1∩Ω2(X¯),k⟶+∞.Combining Theorem3 and the equalities (18) and (17), we have the following.Theorem 4.
If the setΩ is nonempty, then the matrix sequence {Xk} and {Yk} generated by Algorithm 1 both converge to the unique solution of Problem 1. Moreover, if the initial matrix X0=X¯=0, then the matrix sequence {Xk} and {Yk} both converge to the least Frobenius norm solution of the matrix equations AXB=E,CXD=F.


## 3. Numerical Experiments

In this section, we give some numerical examples to illustrate that the new algorithm is feasible and effective to solve Problem1. All programs are written in MATLAB 7.8. We denote
(27)Error=‖E-AXB‖+‖F-CXD‖,
and use the practical stopping criterion Error≤1.0×10-10.Example 1.
Consider Problem1 with
(28)A=(131313-73-7311611611-55-55-59494913131),B=(-14-14-15-15-15-1-2-1-2-1393937-87-87),E=(1171811718117-65-10-65-10-655859058590585-65-10-65-10-6545570455704551171811718117),C=(3-53-57-43-2953-53-57),D=(54-1514-235-25335-13-153-6323-611971719),F=(30753927457511027514399165275307539274575).
Here we use ones(n) and zeros(n) to stand for n×n matrix of ones and zeros. It is easy to verify that X=ones(5) is a solution of the matrix equations (5); that is to say, the set Ω is nonempty. Therefore we can use Algorithm 1 to solve Problem 1.LetX0=X¯=zeros(5). After 5 iterations of Algorithm 1, we get the optimal approximate solution
(29)X̂≈X5=(-0.68170.7813-0.55030.96370.78080.01520.8185-0.28660.96990.81810.01130.8178-0.29170.96980.81730.60910.92800.48930.99800.92780.94970.99070.93420.99850.9907),
which is also the least Frobenius norm solution of the matrix equations (5), and its residual error(30)Error≈‖E-AX5B‖+‖F-CX5D‖=2.78×10-11.
By concrete computations, we know that the distance from X¯ to the solution set Ω is
(31)min⁡X∈Ω‖X-X¯‖=‖X̂-X¯‖≈‖X5-X¯‖=3.9057.LetX0=X¯=ones(5). After 6 iterations of Algorithm 1, we get the optimal approximate solution
(32)X̂≈X6=(5.74671.87477.20131.14521.87704.93921.72596.14631.12051.72784.95481.72886.16681.12091.73072.56361.28813.04271.4781.28891.20131.03711.26301.00621.372),
and its residual error
(33)Error≈‖E-AX6B‖+‖F-CX6D‖=3.89×10-11.
By concrete computations, we know that the distance from X¯ to the solution set Ω is
(34)min⁡X∈Ω‖X-X¯‖=‖X̂-X¯‖≈‖X6-X¯‖=16.0902.Example1 shows that Algorithm 1 is feasible to solve Problem 1.Example 2.
Consider Problem1 with
(35)A=rand(100,n),B=rand(n,150),E=A*ones(n)*B,C=rand(70,n),D=rand(n,120),F=C*ones(n)*D,
where rand(s,t) stand for s×t random matrix. Let the given matrix X¯=zeros(n). It is easy to verify that X=ones(n) is the solution of the matrix equations (5); that is, the set Ω is nonempty; therefore, we can use Algorithm 1 and the following algorithm proposed by Sheng and Chen [13] to solve Problem 1.Algorithm 2.
One has(1)
inputA,B,C,D,E,F and X0;(2)
calculate(36)R0=E-AX0B,r0=F-CX0D,P0=ATR0BT,Q0=CTr0DT;(3)
ifRk=0,r0=0, then stop; else, k:=k+1;(4)
calculate(37)Xk=Xk-1+∥Rk-1∥2+∥rk-1∥2∥Pk-1+Qk-1∥2(Pk-1+Qk-1),Rk=E-AXkB,rk=F-CXkD,Pk=ATRkBT+∥Rk∥2+∥rk∥2∥Rk-1∥2+∥rk-1∥2,Qk=CTrkDT+∥Rk∥2+∥rk∥2∥Rk-1∥2+∥rk-1∥2Qk-1;(5)
go to step 3.It is easy to see that Algorithm1 has lower computational cost for each step in the comparison with Algorithm 2. Experiments show that Algorithm 1 and Algorithm 2 are feasible to solve Problem 1. We list the iteration steps (denoted by IT), CPU time (denoted by CPU), residual error (denoted by ERR), and the distance ∥XIT-X¯∥ (denoted by DIS) in Table 1.Table 1Algorithm1Algorithm2n=50IT536CPU0.0192620.125212ERR3.46×10-119.01×10-10DIS50.0050.00n=80IT8167CPU0.0963354.660955ERR2.31×10-109.26×10-10MIN80.0080.0010n=100IT161673CPU0.16851117.604961ERR5.21×10-109.8×10-10MIN99.9997100.0001n=150IT79—CPU2.589103—ERR5.21×10-10—MIN150.0261—From Table1, we can see that Algorithm 1 outperforms Algorithm 2 in iteration step and CPU time. Therefore our algorithm is faster than the algorithm proposed by Sheng and Chen [13]. Especially, the CPU time and iteration steps of our algorithm increase slowly as the dimension n is increasing; so our algorithm is suitable for large-scale problems.


## 4. Conclusion

The alternating projection algorithm dates back to von Neumann [18], who treated the problem of finding the projection of a given point onto the intersection of two closed subspace. In this paper, we first apply the alternating projection algorithm to solve Problem 1, which occurs frequently in experimental design [23]. If we choose the initial matrix X0=0, the least Frobenius norm solution of the matrix equations AXB=E,CXD=F can be obtained. Numerical examples show that the new algorithm is faster and lower computational cost for each step than the algorithm proposed by Sheng and Chen [13] to solve Problem 1. Especially, the CPU time and iteration steps of the new algorithm increase slowly as the matrix’s dimension is increasing; so the alternating projection algorithm is suitable for large-scale matrix nearness problems.



---

*Source: 126908-2011-12-08.xml*