# Procrustes Problems for General, Triangular, and Symmetric Toeplitz Matrices

Authors: Juan Yang; Yuan-bei Deng
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The Toeplitz Procrustes problems are the least squares problems for the matrix equationAX=B over some Toeplitz matrix sets. In this paper the necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions of the Toeplitz Procrustes problems when the unknown matrices are constrained to the general, the triangular, and the symmetric Toeplitz matrices, respectively. The algorithms are designed and the numerical examples show that these algorithms are feasible.


---

## Body

## 1. Introduction

Consider the constrained least-squares optimization problems:(1)minX∈P∥AX-B∥F,
where A,B∈Rn×n, P⊆Rn×n, and ∥·∥F denotes the Frobenius norm
(2)∥A∥F=tr(ATA)=(∑i=1m‍∑j=1n‍aij2)1/2.These problems have been investigated by a series of literatures. For instance, whenP=Rn×n, then X=A+B is a solution (refer to [1]), while the symmetric matrix solution case and orthogonal matrix solution case are analyzed in [2] and [3] respectively. And the symmetric positive (semi-) definite least squares problem is discussed by Higham [4].In this paper, the following Toeplitz least-squares problem are analyzed:(3)min∥AX-B∥F2,s.t.X∈𝒯,
where A,B∈Rn×n and 𝒯⊂Rn×n are the set of Toeplitz matrices, and a matrix T is called a Toeplitz matrix if its entries satisfy T(i,j)=T(i+k,j+k), for all i, j, and k with 0⩽i+k⩽n-1, 0⩽j+k⩽n-1,
(4)T=(α0α1α2⋯αn-1α-1α0α1⋮⋮⋱⋱⋱α2⋱⋱α1α-(n-1)⋯α-1α0).In this work, we discuss problem (3) in details. In Section 2, the general Toeplitz problem is discussed, and in Section 3, the triangular Toeplitz problem and the symmetric Toeplitz problem are discussed, while in Section 4, we give algorithms and numerical examples.We give some definition and lemmas first.Definition 1 (see [5]).
MatrixGn×m is called {1} inverse matrix of Am×n when AGA=A, and it can be denoted by A- or A{1}.Lemma 2 (see [5]).
LetA∈Crm×n; if there exist nonsingular matrices P∈Cn×n and R∈Cm×m such that
(5)RAP=[Ir000],
then the sufficient and necessary condition of G∈A{1} is
(6)G=P[IrUVW]R,
where U∈Cr×(m-r),V∈C(n-r)×r, and W∈C(n-r)×(m-r).Remark 3.
WhenU=0, V=0, and W=0, G is denoted by A*-.Lemma 4 (see [6]).
A finite dimensional linear subspace of a normed linear space contains at least one point of minimum distance from a fixed point.Lemma 5 (see [7]).
Letf:Rn→R be a convex function continuously differentiable, and then any local minimum point is also a global minimum point. And x* is a solution of problem minf(x) if and only if x* satisfies ∇f(x*)=0, where ∇ means the gradient of function f.Lemma 6 (see [7]).
The quadratic functionf(x)=(1/2)XTQX+qTX+C is convex if and only if Q is positive semidefinite.


## 2. The General Toeplitz Problem

We transform problem (3) into the following equivalent form:
(7)F≡12∥AX-B∥F2=min,X=∑p=-(n-1)(n-1)‍αpGp,
where αp∈R, Gp∈Rn×n are defined as
(8)(Gp)ij={1ifj=i+p,0otherwise,p=-(n-1),…,(n-1).
The objective function F can be rewritten as
(9)F=12tr[(AX-B)T(AX-B)]=12tr(XTATAX)+[-tr(BTAX)+12tr(BTB)]=F1+F2.
The first term of the right side in (9) can be expressed as
(10)F1=12tr(XTATAX)=12tr((∑l=-(n-1)(n-1)‍αlGl)TATA(∑k=-(n-1)(n-1)‍αkGk))=12∑l,k=-(n-1)(n-1)‍tr(GlTATAGk)αlαk=12∑l,k=-(n-1)(n-1)‍tr(GlTATAGk)+tr(GkTATAGl)2αlαk=12yTCy,
where
(11)yT=(α-(n-1),α-(n-2),…,α0,…,α(n-1)),C=(Clk)(2n-1)×(2n-1),Clk=12(tr(GlTATAGk)+tr(GkTATAGl)),2222222.222222l,k=-(n-1),…,(n-1).
Also the second term of the right side in (9) can be expressed as
(12)F2=-tr(BTAX)+12tr(BTB)=-∑l=-(n-1)(n-1)‍tr(BTAGl)αl+12tr(BTB)=-bTy+12tr(BTB),
where bT=(tr(BTAG-(n-1)), tr(BTAG-(n-2)),…, tr(BTAG(n-1)).It thus yields that(13)F=12yTCy-bTy+12tr(BTB).Taking partial derivative onF about αl gives
(14)∂F∂αl=∂F1∂αl+∂F2∂αl=(Cl,-(n-1),Cl,-(n-2),…,Cl,(n-1))y-tr(BTAG(l))=ClTy-bl,l=-(n-1),…,(n-1).By the first order necessary condition,(15)∂F∂α-(n-1)=0,⋮∂F∂α(n-1)=0,
we obtain
(16)Cy=b.
Therefore the following theorem holds.Theorem 7.
The solution of problem (3) exists, and its general form can be expressed as
(17)X=∑l=-(n-1)(n-1)‍αlGl,
where (α-(n-1),α-(n-2),…,α0,…,α(n-1))T=y=C-b+(I-C-C)z, for all z∈Rn,C- means {1} inverse of C.Proof.
Let𝒯′={T∈Rn×n∣T=A∑p=-(n-1)(n-1)αpGp}, where αp∈R, and then the subspace 𝒯′ is a normed linear space under Frobenius norm. It follows from Lemma 4 that there exists at least one matrix T in 𝒯′ such that ∥AX-B∥F2=min. So, by the definition of T, there exists at least one scalar αT=(α-(n-1),α-(n-2),…,α0,…,α(n-1)) constituting matrix T, which means we can rewrite T as T=AX, where X∈𝒯. Therefore the solution of problem (3) exists.
It is apparent from (13) that the objective function F is a quadratic function. Besides, by the following discussion, F is also a convex function. Since ATA is positive semi-definite, it follows that, for any X∈Rn×n, the expression of F1 in (10) holds
(18)F1=12yTCy=12tr(XTATAX)⩾0.
In other words, C is a positive semidefinite matrix. Then according to Lemma 6, F is a convex function. Since F is continuously differentiable, we then get that any solution of (16) is also a solution of (7) by Lemma 5. Clearly, the solution of linear system of (16) is
(19)y=C-b+(I-C-C)z,∀z∈R2n-1
(see [5]). The required solution X of problem (7) is then given by X=∑l=-(n-1)(n-1)αlGl, where y=(α-(n-1),α-(n-2),…,α0,…,α(n-1))T. The theorem follows by the equivalence of problem (3) and problem (7).Theorem 8.
Problem (3) has a unique solution if and only if C has full rank. In this case, the unique solution is
(20)X=∑l=-(n-1)(n-1)‍αlGl,
where (α-(n-1),α-(n-2),…,α0,…,α(n-1))T=y=C-1b.Proof (necessity).
IfC has full rank, then the linear system of (16) has a unique solution y=C-1b; therefore the solution X of problem (7) is determined uniquely, so is problem (3).
Sufficiency follows from the conversely procedure of necessity.Corollary 9.
If A has full rank in column, then the solution of problem (3) is unique.


## 3. The Triangular Toeplitz Problem and the Symmetric Toeplitz Problem

In this section, we discuss the triangular Toeplitz problem and symmetric Toeplitz problem.


### 3.1. The Triangular Toeplitz Problem

By the upper triangular Toeplitz problem, as the definition of [6], we mean the minimization problem
(21)min∥AX-B∥F2s.t.X∈𝒯u,
where A,B∈Rm×n, 𝒯u are the subspace of upper triangular Toeplitz matrices, with elements of the general form
(22)X=(α1α2α3⋯αn0α1α2⋮⋮⋱⋱⋱α3⋱⋱α20⋯0α1).We transform problem (21) into the following problem
(23)F≡12∥AX-B∥F2=min,X=∑p=1n‍αpHp,
where
(24)(Hp)ij={1ifj=i+p-1,0otherwise,p=1,…,n.
The proof procedure is similar to that in problem (7). In this case, the related function F, the unknown y, the linear system of equations, and the matrix C as well as the scalar b can be expressed as
(25)F=12yTCuy-buTy+12tr(BTB),Cuy=bu,yT=(α1,α2,…,αn),Cu=(Clk)n×n,Clk=12(tr(HlTATAHk)+tr(HkTATAHl)),222222222222222222222222l,k=1,2,…,n,bu=(tr(BTAH1),tr(BTAH2),…,tr(BTAHn)).Therefore we obtain a conclusion on upper triangular Toeplitz problem as follows.Theorem 10.
The solution of problem (21) exists, and its general form can be expressed as
(26)X=∑l=1n‍αlHl,
where (α1,α2,…,αn)T=yu=Cu-bu+(I-Cu-Cu)z, for all z∈Rn, Cu- means {1} inverse of Cu.Theorem 11.
Problem (21) has a unique solution if and only if Cu has full rank. In this case, the unique solution is
(27)X=∑l=1n‍αlHl,
where (α1,α2,…,αn)T=Cu-1bu.Corollary 12.
If A has full rank in column, then the solution of problem (21) is unique.Similarly, we can solve the lower triangular Toeplitz problem.


### 3.2. The Symmetric Toeplitz Problem

The symmetric Toeplitz problem is the following minimization problem:(28)min∥AX-B∥F2s.t.X∈𝒯s,
where A,B∈Rm×n, 𝒯s are the subspace of symmetric Toeplitz matrices, with elements of the general form:
(29)X=(α1α2α3⋯αnα2α1α2⋮α3α2⋱⋱α3⋮⋱⋱α2αn⋯α3α2α1).
We consider the following objective function:
(30)F≡12∥AX-B∥F2=min,X=∑p=1n‍αpQp,
where
(31)(Qp)ij={1if|j-i|=p-1,0otherwise,p=1,…,n.In this case, the related functionF, the unknown y, the linear system of equations, and the matrix C as well as the scalar b can be expressed as
(32)F=12yTCsy-bsTy+12tr(BTB),Csy=bs,yT=(α1,α2,…,αn),Cs=(Clk)n×n,Clk=12(tr(QlTATAQk)+tr(QkTATAQl)),222222222222222222222222l,k=1,2,…,n,bs=(tr(BTAQ1),tr(BTAQ2),…,tr(BTAQn)).Therefore we obtain a conclusion about the symmetric Toeplitz problem.Theorem 13.
The solution of problem (28) exists, and its general form can be expressed as
(33)X=∑l=1n‍αlQl,
where (α1,α2,…,αn)T=y=Cs-bs+(I-Cs-Cs)z, for all z∈Rn, and Cs- means {1} inverse of Cs.Theorem 14.
Problem (28) has a unique solution if and only if Cs has full rank. In this case, the unique solution is
(34)X=∑l=1n‍αlQl,
where (α1,α2,…,αn)T=y=Cs-1bs.Corollary 15.
If A has full rank in column, then the solution of problem (28) is unique.


## 3.1. The Triangular Toeplitz Problem

By the upper triangular Toeplitz problem, as the definition of [6], we mean the minimization problem
(21)min∥AX-B∥F2s.t.X∈𝒯u,
where A,B∈Rm×n, 𝒯u are the subspace of upper triangular Toeplitz matrices, with elements of the general form
(22)X=(α1α2α3⋯αn0α1α2⋮⋮⋱⋱⋱α3⋱⋱α20⋯0α1).We transform problem (21) into the following problem
(23)F≡12∥AX-B∥F2=min,X=∑p=1n‍αpHp,
where
(24)(Hp)ij={1ifj=i+p-1,0otherwise,p=1,…,n.
The proof procedure is similar to that in problem (7). In this case, the related function F, the unknown y, the linear system of equations, and the matrix C as well as the scalar b can be expressed as
(25)F=12yTCuy-buTy+12tr(BTB),Cuy=bu,yT=(α1,α2,…,αn),Cu=(Clk)n×n,Clk=12(tr(HlTATAHk)+tr(HkTATAHl)),222222222222222222222222l,k=1,2,…,n,bu=(tr(BTAH1),tr(BTAH2),…,tr(BTAHn)).Therefore we obtain a conclusion on upper triangular Toeplitz problem as follows.Theorem 10.
The solution of problem (21) exists, and its general form can be expressed as
(26)X=∑l=1n‍αlHl,
where (α1,α2,…,αn)T=yu=Cu-bu+(I-Cu-Cu)z, for all z∈Rn, Cu- means {1} inverse of Cu.Theorem 11.
Problem (21) has a unique solution if and only if Cu has full rank. In this case, the unique solution is
(27)X=∑l=1n‍αlHl,
where (α1,α2,…,αn)T=Cu-1bu.Corollary 12.
If A has full rank in column, then the solution of problem (21) is unique.Similarly, we can solve the lower triangular Toeplitz problem.


## 3.2. The Symmetric Toeplitz Problem

The symmetric Toeplitz problem is the following minimization problem:(28)min∥AX-B∥F2s.t.X∈𝒯s,
where A,B∈Rm×n, 𝒯s are the subspace of symmetric Toeplitz matrices, with elements of the general form:
(29)X=(α1α2α3⋯αnα2α1α2⋮α3α2⋱⋱α3⋮⋱⋱α2αn⋯α3α2α1).
We consider the following objective function:
(30)F≡12∥AX-B∥F2=min,X=∑p=1n‍αpQp,
where
(31)(Qp)ij={1if|j-i|=p-1,0otherwise,p=1,…,n.In this case, the related functionF, the unknown y, the linear system of equations, and the matrix C as well as the scalar b can be expressed as
(32)F=12yTCsy-bsTy+12tr(BTB),Csy=bs,yT=(α1,α2,…,αn),Cs=(Clk)n×n,Clk=12(tr(QlTATAQk)+tr(QkTATAQl)),222222222222222222222222l,k=1,2,…,n,bs=(tr(BTAQ1),tr(BTAQ2),…,tr(BTAQn)).Therefore we obtain a conclusion about the symmetric Toeplitz problem.Theorem 13.
The solution of problem (28) exists, and its general form can be expressed as
(33)X=∑l=1n‍αlQl,
where (α1,α2,…,αn)T=y=Cs-bs+(I-Cs-Cs)z, for all z∈Rn, and Cs- means {1} inverse of Cs.Theorem 14.
Problem (28) has a unique solution if and only if Cs has full rank. In this case, the unique solution is
(34)X=∑l=1n‍αlQl,
where (α1,α2,…,αn)T=y=Cs-1bs.Corollary 15.
If A has full rank in column, then the solution of problem (28) is unique.


## 4. Computation and Examples

The derivation of general Toeplitz problem leads to the following computational algorithm.Algorithm 16.
(1)
Generate matricesGi(i=-(n-1),…,(n-1)) according to the definition in (7).
(2)
Compute the matrixC and scalar b by formula (11) and (12).
(3)
IfC is of full rank, then solving the linear system of (16) directly, to obtain the solution y=C-1b; else calculate C-, forming y=C-b+(I-C-C)z, for all z∈Rn. In general, let U, V and W in Lemma 2 equal to 0, we can obtain one of {1} inverse of C, that is C*-.
(4)
ComputeX from X=∑l=-(n-1)(n-1)αlGl, where (α-(n-1),…,α(n-1))=yT.The algorithms for other special Toeplitz problems can be designed similarly.We mention that, in the beginning of this paper, solutions for that two instances are actually obtained based on Algorithm16. We can give another example of Toeplitz problem with matrix A of full rank in column as follows. According to Corollaries 9, 12, and 15, the solution is unique.Example 17.
Consider the following(35)A=(-220-1100222132-2-1-1-1-121),B=(0-2-321-2-3100-3-32022320-3).
Using the algorithms mentioned above, computing the Toeplitz problems by Matlab, we obtain the following results.
The general Toeplitz matrix solution is(36)X*=(-0.40791-0.837960.080264-0.041414-0.55794-0.40791-0.837960.0802640.62335-0.55794-0.40791-0.837960.306560.62335-0.55794-0.40791).
The upper triangular Toeplitz matrix solution is
(37)Xu=(-0.37531-0.76827-0.069704-0.0798900.0-0.37531-0.76827-0.0697040.00.0-0.37531-0.768270.00.00.0-0.37531),
and the symmetric Toeplitz matrix solution is
(38)Xs=(-0.46064-0.644770.356590.27712-0.64477-0.46064-0.644770.356590.35659-0.64477-0.46064-0.644770.277120.35659-0.64477-0.46064).


## 5. Conclusions

We have discussed the Toeplitz Procrustes problem including the general, triangular, and symmetric cases. After transforming the origin problem into a quadric form, we gain the general or unique solution with facility, by solving the linear system of equations.



---

*Source: 696019-2013-12-30.xml*