# On Optimal Backward Perturbation Analysis for the Linear System with Skew Circulant Coefficient Matrix

Authors: Juan Li; Zhaolin Jiang; Nuo Shen; Jianwei Zhou
Journal: Computational and Mathematical Methods in Medicine
 (2013)

---

## Abstract

We first give the style spectral decomposition of a special skew circulant matrixC and then get the style decomposition of arbitrary skew circulant matrix by making use of the Kronecker products between the elements of first row in skew circulant and the special skew circulant C. Besides that, we obtain the singular value of skew circulant matrix as well. Finally, we deal with the optimal backward perturbation analysis for the linear system with skew circulant coefficient matrix on the base of its style spectral decomposition.


---

## Body

## 1. Introduction

A skew circulant matrix with the first row(a1,a2,…,an) is a square matrix of the form
(1)(a1a2⋯an-1an-ana1a2⋯an-1⋮⋱⋱⋱⋮-a3⋯-ana1a2-a2-a3⋯-ana1)n×n,
denoted by  SCirc(a1,a2,…,an).Skew circulant matrices have important applications in various disciplines including image processing, signal processing, solving Toeplitz matrix problems, and preconditioner. The skew circulant matrices are considered as preconditioners for linear-multistep-formulae (LMF-) based ordinary differential equations (ODEs) codes; Hermitian and skew-Hermitian Toeplitz systems are considered in [1–4]. Lyness and Sörevik [5] employed a skew circulant matrix to construct s-dimensional lattice rules. Spectral decompositions of skew circulant and skew left circulant matrices are discussed in [6]. Akhondi and Toutounian [7] presented a new iteration method for the numerical solution of Hermitian positive definite Toeplitz systems of linear equations. Narasimha [8] believed that the linear convolution required in block filtering can be decomposed into a sum of skew-circulant convolutions and such convolutions can be realized efficiently with half-length complex transforms when the signals are real. Liu and Vaidyanathan [9] presented a new family of normal form state-space structures, the method used allows people to synthesize in normal form, most IIR transfer functions, and the state transition matrices involved are either circulant or skew circulant matrices. Vaidyanathan and Pal [10] examined a case where two arrays are generated by matrices that are adjugates of each other; in this case, it is possible to obtain a dense rectangular tiling of the 2D frequency plane from a pair of coarse 2D DFT filter banks; the special case where the adjugate pairs are generated by skew circulant matrices has some advantages, which are examined in detail. An additional convolution-multiplication property for the skew-circulant convolution operation y=hⓈx=Hsx, where Hs is a skew-circulant matrix; besides, skew-circulant convolution is the underlying form of convolution in half of the 40 cases of symmetric convolution, and the convolution is an extension of a result Vernet's [11], Foltz and Welsh provided the convolution performed between h and x is skew-circulant rather than circulant in [12].Liu and Guo [13] gave the optimal backward perturbation analysis for a linear system with block circulant coefficient matrix. The optimal backward perturbation bound for underdetermined systems is studied by J.-G. Sun and Z. Sun in [14]. Some new theorems generalizing a result of Oettli and Prager are applied to the a posteriori analysis of the compatibility of a computed solution to the uncertain data of a linear system by Rigal and Gaches in [15].In this paper, we first give the style spectral decomposition of a special skew circulant matrixC and then get the style spectral decomposition of arbitrary skew circulant matrix by making use of Kronecker products between the elements of first row in skew circulant and the special skew circuant C. Besides that, we obtain the singular value of skew circulant matrix as well. Finally, we deal with the optimal backward perturbation analysis for the linear system with skew circulant coefficient matrix on the base of its style spectral decomposition.


## 2. The Style Spectral Decomposition of Skew Circulant Matrix

### 2.1. Style Spectral Decomposition of a Special Skew Circulant Matrix

Let(2)C=(010⋯0001⋯0⋮⋱⋱⋱⋮0⋯001-10⋯00).
Some properties of this matrix are given in the following theorem.Lemma 1.
(1)  The eigenvalues of matrixC are
(3)λj=ei((2j-1)/n)π,j=1,2,…,n.
(2)  Ifn is even, the matrix C has no real eigenvalue and
(4)λj=λ¯n+1-j,j=1,2,…,n2.
The basis of the associated two-dimensional invariant subspace can be taken as(5)xj(1)=(1cosθj⋮cos(n-1)θj),xj(2)=(0sinθj⋮sin(n-1)θj),θj=2j-1nπ,j=1,2,…,n2.
(3)  Ifn is odd, the matrix C has only one real eigenvalue λ(n+1)/2=-1, and the associated eigenvector is
(6)x(n+1)/2=(1-11-1⋮1),λj=λ¯n+1-j,j=1,2,…,n-12.
The basis of the associated two-dimensional invariant subspace can be taken as(7)xj(1)=(1cosθj⋮cos(n-1)θj),xj(2)=(0sinθj⋮sin(n-1)θj),θj=2j-1nπ,j=1,2,…,n-12.
Specially, ifn is even, then xj(1) and xj(2) span the two-dimensional invariant subspace associated with λj and λj¯.Lemma 2.
(1)xj(1) and xj(2) are orthogonal.
(2)xj(l) and xk(s) are orthogonal (j≠k) (l,s=1,2).
(3)  Also∥x(n+1)/2∥2=n, ∥xj(1)∥2=∥xj(2)∥2=n/2,
(8)∥(1λj⋮λjn-1)∥2=n.LetQ=[q1,q2,…,qn], where
(9)q2j-1=2nxj(1),q2j=2nxj(2)(j=1,2,…,[n2]),qn=1n(1-11-1⋮1)(nisodd).
Then Q is an orthogonal matrix, and if n is even,
(10)C=Q(C1C2⋱Cn/2)QT,
where Cj=(cosθjsinθj-sinθjcosθj)(j=1,2,…,n/2).Whenn is odd,
(11)C=Q(C1⋱C(n-1)/2-1)QT,
where Cj=(cosθjsinθj-sinθjcosθj)(j=1,2,…,(n-1)/2).In fact, (10) and (11) are the style spectral decomposition of the matrix C.


### 2.2. The Style Spectral Decomposition of the Skew Circulant Matrix

We have(12)A=(a1a2⋯an-1an-ana1a2⋯an-1⋮⋱⋱⋱⋮-a3⋯-ana1a2-a2-a3⋯-ana1)=a1·C0+a2·C1+⋯+an·Cn-1=a1·(QC00QT)+⋯+an·(QC0n-1QT)=Q(a1·C00)QT+⋯+Q(an·C0n-1)QT(13)=Q(∑k=1n‍ak·C0k-1)QT,
where
(14)C0=(C1C2⋱Cn/2)
(n  is even, the same case as  (10)),
(15)C0=(C1⋱C(n-1)/2-1)
(n  is odd, the same case as  (11)).Noticing thatQ is an orthogonal matrix, hence (13) is the style spectral decomposition of the matrix A.The following are the computation formulae of the factors in (13):
(16)Cjk=(coskθjsinkθj-sinkθjcoskθj).
Hence, when n is even,
(17)∑k=1n‍ak·C0k-1=(A~1A~2⋱A~n/2),
where, for arbitrary j=1,2,…,n/2,
(18)A~j=(∑k=1n‍akcoskθj∑k=1n‍aksinkθj-∑k=1n‍aksinkθj∑k=1n‍akcoskθj).
When n is odd,
(19)∑k=1n‍ak·C0k-1=(A~1⋱A~(n-1)/2A*),
where A~j is defined by (18), and
(20)A*=(-1)k∑k=1n‍ak.Hence the style spectral decomposition of the matrixA is
(21)A=Q(∑k=1n‍akC1k-1∑k=1n‍akC2k-1⋱⋱)QT.


## 2.1. Style Spectral Decomposition of a Special Skew Circulant Matrix

Let(2)C=(010⋯0001⋯0⋮⋱⋱⋱⋮0⋯001-10⋯00).
Some properties of this matrix are given in the following theorem.Lemma 1.
(1)  The eigenvalues of matrixC are
(3)λj=ei((2j-1)/n)π,j=1,2,…,n.
(2)  Ifn is even, the matrix C has no real eigenvalue and
(4)λj=λ¯n+1-j,j=1,2,…,n2.
The basis of the associated two-dimensional invariant subspace can be taken as(5)xj(1)=(1cosθj⋮cos(n-1)θj),xj(2)=(0sinθj⋮sin(n-1)θj),θj=2j-1nπ,j=1,2,…,n2.
(3)  Ifn is odd, the matrix C has only one real eigenvalue λ(n+1)/2=-1, and the associated eigenvector is
(6)x(n+1)/2=(1-11-1⋮1),λj=λ¯n+1-j,j=1,2,…,n-12.
The basis of the associated two-dimensional invariant subspace can be taken as(7)xj(1)=(1cosθj⋮cos(n-1)θj),xj(2)=(0sinθj⋮sin(n-1)θj),θj=2j-1nπ,j=1,2,…,n-12.
Specially, ifn is even, then xj(1) and xj(2) span the two-dimensional invariant subspace associated with λj and λj¯.Lemma 2.
(1)xj(1) and xj(2) are orthogonal.
(2)xj(l) and xk(s) are orthogonal (j≠k) (l,s=1,2).
(3)  Also∥x(n+1)/2∥2=n, ∥xj(1)∥2=∥xj(2)∥2=n/2,
(8)∥(1λj⋮λjn-1)∥2=n.LetQ=[q1,q2,…,qn], where
(9)q2j-1=2nxj(1),q2j=2nxj(2)(j=1,2,…,[n2]),qn=1n(1-11-1⋮1)(nisodd).
Then Q is an orthogonal matrix, and if n is even,
(10)C=Q(C1C2⋱Cn/2)QT,
where Cj=(cosθjsinθj-sinθjcosθj)(j=1,2,…,n/2).Whenn is odd,
(11)C=Q(C1⋱C(n-1)/2-1)QT,
where Cj=(cosθjsinθj-sinθjcosθj)(j=1,2,…,(n-1)/2).In fact, (10) and (11) are the style spectral decomposition of the matrix C.


## 2.2. The Style Spectral Decomposition of the Skew Circulant Matrix

We have(12)A=(a1a2⋯an-1an-ana1a2⋯an-1⋮⋱⋱⋱⋮-a3⋯-ana1a2-a2-a3⋯-ana1)=a1·C0+a2·C1+⋯+an·Cn-1=a1·(QC00QT)+⋯+an·(QC0n-1QT)=Q(a1·C00)QT+⋯+Q(an·C0n-1)QT(13)=Q(∑k=1n‍ak·C0k-1)QT,
where
(14)C0=(C1C2⋱Cn/2)
(n  is even, the same case as  (10)),
(15)C0=(C1⋱C(n-1)/2-1)
(n  is odd, the same case as  (11)).Noticing thatQ is an orthogonal matrix, hence (13) is the style spectral decomposition of the matrix A.The following are the computation formulae of the factors in (13):
(16)Cjk=(coskθjsinkθj-sinkθjcoskθj).
Hence, when n is even,
(17)∑k=1n‍ak·C0k-1=(A~1A~2⋱A~n/2),
where, for arbitrary j=1,2,…,n/2,
(18)A~j=(∑k=1n‍akcoskθj∑k=1n‍aksinkθj-∑k=1n‍aksinkθj∑k=1n‍akcoskθj).
When n is odd,
(19)∑k=1n‍ak·C0k-1=(A~1⋱A~(n-1)/2A*),
where A~j is defined by (18), and
(20)A*=(-1)k∑k=1n‍ak.Hence the style spectral decomposition of the matrixA is
(21)A=Q(∑k=1n‍akC1k-1∑k=1n‍akC2k-1⋱⋱)QT.


## 3. The Structured Perturbation Analysis

In this section we give the structured perturbation analysis for linear systems with skew circulant coefficient matrix.


### 3.1. Condition Number and  Relative Error of Linear Skew Circulant Equation System

Consider the following:(22)Ax=b,
where A is defined in (2).From (13), we know that the style spectral decomposition of the matrix A is
(23)A=Q(A11⋱Att)QT.
When n is even and t=n/2,
(24)Ajj=∑k=1n‍ak(cos(k-1)θjsin(k-1)θj-sin(k-1)θjcos(k-1)θj),θj=2j-1nπ,j=1,2,…,t.
When n is odd and t=(n-1)/2+1, Ajj is defined in (24) (j=1,2,…,(n-1)/2) and
(25)Att=(-1)k∑k=1n‍ak.Lemma 3.
A is an invertible matrix if and only if f(ωj)≠0(j=1,2,…,n), where
(26)f(ωj)=∑k=1n‍akωjk-1,ωj=ei((2j-1)/n)π,j=1,2,…,n.Let(27)σj=|f(ωj)|,j=1,2,…,n,𝒦=max{σj}min{σj}.Remark 4.
The singular values of matrixA are σ1,σ2,…,σn.The proof of Lemma3 and Remark 4 is given in the following:
(28)A=∑k=1n‍akCk-1.
Consequently, the spectral decomposition of the matrix A (by using the complex style spectral decomposition of C=Q0(ω1⋱ωn)Q0*) is
(29)A=Q0(f(ω1)f(ω2)⋱f(ωn))Q0*,
where Q0 is a unitary matrix.LetΔA, Δb be the perturbation of the coefficient matrix A and vector b, respectively, where
(30)ΔA=(δa1δa2⋯δan-1δan-δanδa1δa2⋯δan-1⋮⋱⋱⋱⋮-δa3⋯-δanδa1δa2-δa2-δa3⋯-δanδa1).
Let
(31)A^=A+ΔA,b^=b+δb,f^(ωj)=∑k=1n‍(ak+δak)ωjk-1.
If
(32)∑k=1n‍|δak|<min1≤j≤n{σj},
then
(33)|f^(ωj)|≥|∑k=1n‍akωjk-1|-∑k=1n‍|δak||ωj|k-1≥min1≤j≤n{σj}-∑k=1n‍|δak|>0.
Hence A^ is an invertible matrix. Let
(34)σmin=min1≤j≤n{σj},Δ=∑k=1n‍|δak|.
By Ax=b and A^x^=b^, we get
(35)x^-x=A^-1b^-A-1b=A^-1(b+δb)-A-1b=A^-1δb+(A^-1-A-1)b=A^-1δb+(A^-1-A-1)Ax=A^-1δb+A^-1(A-A^)x,∥x^-x∥2≤∥A^-1∥2∥δb∥2+∥A^-1∥2∥A^-A∥2∥x∥2≤∥δb∥2σmin-Δ+∥A^-A∥2∥x∥2σmin-Δ,∥x^-x∥2∥x∥2≤∥δb∥2(σmin-Δ)∥x∥2+∥A^-A∥2σmin-Δ≤∥A∥2σmin-Δ(∥δb∥2∥b∥2+∥A^-A∥2∥A∥2),
where
(36)∥A∥2=max1≤j≤n{σj}.
Notice that A^-A=ΔA is a skew circulant matrix, and ∥A-A^∥2=|-1|∥A^-A∥2=∥A^-A∥2. So we get
(37)∥A^-A∥2=max1≤j≤n|∑k=1n‍δakωjk-1|≤∑k=1n‍|δak||ωj|k-1=∑k=1n‍|δak|=Δ.
Hence we have the following theorem.Theorem 5.
LetA, A^, δb, Δ, and σmin be defined as above. If Δ<σmin, then
(38)∥x^-x∥2∥x∥2≤σmaxσmin-Δ(∥δb∥2∥b∥2+Δσmax),
where
(39)σmax=∥A∥2.Remark 6.
From (38) and (39), the condition number of the skew circulant system can be defined as 𝒦=max{σj}/min{σj}. It is easily computed, as well as the bound of perturbation (38).


### 3.2. Optimal Backward Perturbation Bound of the Linear Skew Circulant Equation System

Letx^ be an approximate solution to Ax=b and let
(40)Ω≡{(ΔA,Δb)∣(A+ΔA)x^=b+Δb},η(x^)≡inf(ΔA,Δb)∈Ω∥[ΔA,Δb]∥,(A+ΔA)x^=b+Δb
which is equivalent to
(41)(ΔA,Δb)(x^-1)=b-Ax^.
Due to [15], we have
(42)η(x^)=∥b-Ax^∥21+∥x^∥22(∥·∥beingunitaryinvariantnorm).If the recycling property ofA is not utilized in the algorithm in forming x^, then η(x^) can be used to estimate the backward stability for this algorithm.Letx^ be an approximate solution to Ax=b, where A is defined in (2):
(43)Ω≡{(ΔA,Δb)∣(A+ΔA)x^=b+Δb,ΔAisaskewcirculantmatrix}η(x^)≡inf(ΔA,Δb)∈Ω{∥(ΔA,Δb)∥F}.
Then Ω≠ϕ (such that  ΔA=0 is a skew circulant matrix, and Δb=Ax^-b) and
(44)η2(x^)=inf(ΔA,Δb)∈Ω{∥ΔA∥F2+∥ΔAx^+Ax^-b∥F2}.
Since
(45)ΔA=∑k=1n‍δakCk-1,
so
(46)∥ΔA∥F2=n∑k=1n‍(δak)2.
Besides that, we can get
(47)∥ΔAx^+Ax^-b∥F2=∥QC*QTx^+Ax^-b∥F2=∥(∑k=1n‍δakC1k-1x1(0)⋮∑k=1n‍δakCtk-1xt(0))-r0∥F2=∥G0(δa1⋮δan)-r0∥F2,
where
(48)C*=(∑k=1n‍δakC1k-1⋱∑k=1n‍δakCtk-1),r0=QT(b-Ax^),QTx^=(x1(0)⋮xt(0)),G0=(C10x1(0)⋯C1n-1x1(0)⋮⋱⋮Ct0xt(0)⋯Ctn-1xt(0)).Let(49)f(δa1,…,δan)=n∑k=1n‍(δak)2+∥G0(δa1⋮δan)-r0∥F2;
then
(50)∂f∂δak=0
which is equivalent to
(51)(2nIn+2G0TG0)(δa1⋮δan)-2G0Tr0=0.∂2f∂(δak)2=2nIn+2G0TG0>0,
Hence the f is a convex function about (δa1,…,δan), and the point of minimal value is
(52)(δa1⋮δan)=(nIn+G0TG0)-1G0Tr0.
Substituting it back into (49), we can get the following.Theorem 7.
One has(53)η(x^)2=nr0TG0(nIn+G0TG0)-2G0Tr0+∥[G0(nIn+G0TG0)-1G0T-In]r0∥F2.LetG0=UΣV* be the singular value decomposition of G0, where U and V are unitary (in fact, U and V can be real orthogonal), Σ=diag(σ1′,…,σn′), and σj′≥0(j=1,2,…,n). Hence we have
(54)η(x^)2=nr0TUΣVT(nIn+Σ2)-2VΣUTr0+∥[UΣVT(nIn+Σ2)-1VΣUT-In]r0∥F2=nr1TΣ(nIn+Σ2)-2Σr1+∥[Σ(nIn+Σ2)-1Σ-In]r0∥F2=nr1TΣ(nIn+Σ2)-2Σr1+∥[Σ(nIn+Σ2)-1Σ-In]r1∥F2=nr1TΣ(nIn+Σ2)-2Σr1+n2r1T(nIn+Σ2)-2r1=r1T(d1⋱dn)r1,
where r1=UTr0, and dj=(nσj′2+n2)/(n+σj′2)2=n/(n+σj′2).Remark 8.
Byσj′2≤∥G0∥F2=n∥x^∥22, we get 1+(σj′2/n)≤1+∥x^∥22, and hence 1/(1+∥x^∥22)≤n/(n+σj′2).Algorithm 9.
Step  1. Form the block style spectral decomposition of the matrix C(55)C=Q(C1⋱Ct)QT.
Step  2. Compute r=b-Ax^.
Step  3. Compute r0=QTr.
Step  4. Compute QTx^=(x1(0)⋮x1(0)).
Step  5. Form G0.
Step  6. Compute η2(x^).


## 3.1. Condition Number and  Relative Error of Linear Skew Circulant Equation System

Consider the following:(22)Ax=b,
where A is defined in (2).From (13), we know that the style spectral decomposition of the matrix A is
(23)A=Q(A11⋱Att)QT.
When n is even and t=n/2,
(24)Ajj=∑k=1n‍ak(cos(k-1)θjsin(k-1)θj-sin(k-1)θjcos(k-1)θj),θj=2j-1nπ,j=1,2,…,t.
When n is odd and t=(n-1)/2+1, Ajj is defined in (24) (j=1,2,…,(n-1)/2) and
(25)Att=(-1)k∑k=1n‍ak.Lemma 3.
A is an invertible matrix if and only if f(ωj)≠0(j=1,2,…,n), where
(26)f(ωj)=∑k=1n‍akωjk-1,ωj=ei((2j-1)/n)π,j=1,2,…,n.Let(27)σj=|f(ωj)|,j=1,2,…,n,𝒦=max{σj}min{σj}.Remark 4.
The singular values of matrixA are σ1,σ2,…,σn.The proof of Lemma3 and Remark 4 is given in the following:
(28)A=∑k=1n‍akCk-1.
Consequently, the spectral decomposition of the matrix A (by using the complex style spectral decomposition of C=Q0(ω1⋱ωn)Q0*) is
(29)A=Q0(f(ω1)f(ω2)⋱f(ωn))Q0*,
where Q0 is a unitary matrix.LetΔA, Δb be the perturbation of the coefficient matrix A and vector b, respectively, where
(30)ΔA=(δa1δa2⋯δan-1δan-δanδa1δa2⋯δan-1⋮⋱⋱⋱⋮-δa3⋯-δanδa1δa2-δa2-δa3⋯-δanδa1).
Let
(31)A^=A+ΔA,b^=b+δb,f^(ωj)=∑k=1n‍(ak+δak)ωjk-1.
If
(32)∑k=1n‍|δak|<min1≤j≤n{σj},
then
(33)|f^(ωj)|≥|∑k=1n‍akωjk-1|-∑k=1n‍|δak||ωj|k-1≥min1≤j≤n{σj}-∑k=1n‍|δak|>0.
Hence A^ is an invertible matrix. Let
(34)σmin=min1≤j≤n{σj},Δ=∑k=1n‍|δak|.
By Ax=b and A^x^=b^, we get
(35)x^-x=A^-1b^-A-1b=A^-1(b+δb)-A-1b=A^-1δb+(A^-1-A-1)b=A^-1δb+(A^-1-A-1)Ax=A^-1δb+A^-1(A-A^)x,∥x^-x∥2≤∥A^-1∥2∥δb∥2+∥A^-1∥2∥A^-A∥2∥x∥2≤∥δb∥2σmin-Δ+∥A^-A∥2∥x∥2σmin-Δ,∥x^-x∥2∥x∥2≤∥δb∥2(σmin-Δ)∥x∥2+∥A^-A∥2σmin-Δ≤∥A∥2σmin-Δ(∥δb∥2∥b∥2+∥A^-A∥2∥A∥2),
where
(36)∥A∥2=max1≤j≤n{σj}.
Notice that A^-A=ΔA is a skew circulant matrix, and ∥A-A^∥2=|-1|∥A^-A∥2=∥A^-A∥2. So we get
(37)∥A^-A∥2=max1≤j≤n|∑k=1n‍δakωjk-1|≤∑k=1n‍|δak||ωj|k-1=∑k=1n‍|δak|=Δ.
Hence we have the following theorem.Theorem 5.
LetA, A^, δb, Δ, and σmin be defined as above. If Δ<σmin, then
(38)∥x^-x∥2∥x∥2≤σmaxσmin-Δ(∥δb∥2∥b∥2+Δσmax),
where
(39)σmax=∥A∥2.Remark 6.
From (38) and (39), the condition number of the skew circulant system can be defined as 𝒦=max{σj}/min{σj}. It is easily computed, as well as the bound of perturbation (38).


## 3.2. Optimal Backward Perturbation Bound of the Linear Skew Circulant Equation System

Letx^ be an approximate solution to Ax=b and let
(40)Ω≡{(ΔA,Δb)∣(A+ΔA)x^=b+Δb},η(x^)≡inf(ΔA,Δb)∈Ω∥[ΔA,Δb]∥,(A+ΔA)x^=b+Δb
which is equivalent to
(41)(ΔA,Δb)(x^-1)=b-Ax^.
Due to [15], we have
(42)η(x^)=∥b-Ax^∥21+∥x^∥22(∥·∥beingunitaryinvariantnorm).If the recycling property ofA is not utilized in the algorithm in forming x^, then η(x^) can be used to estimate the backward stability for this algorithm.Letx^ be an approximate solution to Ax=b, where A is defined in (2):
(43)Ω≡{(ΔA,Δb)∣(A+ΔA)x^=b+Δb,ΔAisaskewcirculantmatrix}η(x^)≡inf(ΔA,Δb)∈Ω{∥(ΔA,Δb)∥F}.
Then Ω≠ϕ (such that  ΔA=0 is a skew circulant matrix, and Δb=Ax^-b) and
(44)η2(x^)=inf(ΔA,Δb)∈Ω{∥ΔA∥F2+∥ΔAx^+Ax^-b∥F2}.
Since
(45)ΔA=∑k=1n‍δakCk-1,
so
(46)∥ΔA∥F2=n∑k=1n‍(δak)2.
Besides that, we can get
(47)∥ΔAx^+Ax^-b∥F2=∥QC*QTx^+Ax^-b∥F2=∥(∑k=1n‍δakC1k-1x1(0)⋮∑k=1n‍δakCtk-1xt(0))-r0∥F2=∥G0(δa1⋮δan)-r0∥F2,
where
(48)C*=(∑k=1n‍δakC1k-1⋱∑k=1n‍δakCtk-1),r0=QT(b-Ax^),QTx^=(x1(0)⋮xt(0)),G0=(C10x1(0)⋯C1n-1x1(0)⋮⋱⋮Ct0xt(0)⋯Ctn-1xt(0)).Let(49)f(δa1,…,δan)=n∑k=1n‍(δak)2+∥G0(δa1⋮δan)-r0∥F2;
then
(50)∂f∂δak=0
which is equivalent to
(51)(2nIn+2G0TG0)(δa1⋮δan)-2G0Tr0=0.∂2f∂(δak)2=2nIn+2G0TG0>0,
Hence the f is a convex function about (δa1,…,δan), and the point of minimal value is
(52)(δa1⋮δan)=(nIn+G0TG0)-1G0Tr0.
Substituting it back into (49), we can get the following.Theorem 7.
One has(53)η(x^)2=nr0TG0(nIn+G0TG0)-2G0Tr0+∥[G0(nIn+G0TG0)-1G0T-In]r0∥F2.LetG0=UΣV* be the singular value decomposition of G0, where U and V are unitary (in fact, U and V can be real orthogonal), Σ=diag(σ1′,…,σn′), and σj′≥0(j=1,2,…,n). Hence we have
(54)η(x^)2=nr0TUΣVT(nIn+Σ2)-2VΣUTr0+∥[UΣVT(nIn+Σ2)-1VΣUT-In]r0∥F2=nr1TΣ(nIn+Σ2)-2Σr1+∥[Σ(nIn+Σ2)-1Σ-In]r0∥F2=nr1TΣ(nIn+Σ2)-2Σr1+∥[Σ(nIn+Σ2)-1Σ-In]r1∥F2=nr1TΣ(nIn+Σ2)-2Σr1+n2r1T(nIn+Σ2)-2r1=r1T(d1⋱dn)r1,
where r1=UTr0, and dj=(nσj′2+n2)/(n+σj′2)2=n/(n+σj′2).Remark 8.
Byσj′2≤∥G0∥F2=n∥x^∥22, we get 1+(σj′2/n)≤1+∥x^∥22, and hence 1/(1+∥x^∥22)≤n/(n+σj′2).Algorithm 9.
Step  1. Form the block style spectral decomposition of the matrix C(55)C=Q(C1⋱Ct)QT.
Step  2. Compute r=b-Ax^.
Step  3. Compute r0=QTr.
Step  4. Compute QTx^=(x1(0)⋮x1(0)).
Step  5. Form G0.
Step  6. Compute η2(x^).


## 4. Conclusion

The related problems of skew-circulant matrix are considered in this paper. We not only present style spectral decomposition and singular value but also study backward perturbation analysis for the linear system with skew-circulant coefficient matrix. The reason why we focus our attentions on skew-circulant is to explore the application of skew circulant in the related field in medicine. Wittsack et al. in [16] validated a deconvolution method originating from magnetic resonance techniques and apply it to the calculation of dynamic contrast enhanced computed tomography perfusion imaging, and the application of a block circulant matrix approach for singular value decomposition renders the analysis independent of tracer arrival time to improve the results. On the basis of existing application situation, we conjecture that SVD decomposition of skew circulant matrix will play an important role in CT-perfusion imaging of human brain.



---

*Source: 707381-2013-11-28.xml*