Journal of Shanghai University (English Edition), 2004, 8(4): 391--396 Article ID: 1007-6417(2004)04-0391-06
A Backward Stable Hyperbolic QR Factorization Method for Solving Indefinite Least Squares Problem X U Hong-guo ( ~, ~,, ~ ) Department of Mathematics, University of Kansas, Lawrence, KS 66045, USA We present a numerical method for solving the indefinite least squares problem. We first normalize the coefficientmatrix. Then we compute the hyperbolicQR factorizationof the normalizedmatrix. Finally we compute the solution by solving several triangular systems. We give the first order error analysis to show that the method is backward stable. The method is more efficient than the backward stable method proposed by Chandrasekaran, Gu and Sayed. Abstract
Key words indefinite least squares, hyperbolic rotation, ~ p.q-orthogonai matrix, hyperbolicQR factorization, bidiagonalfactorization, backwardstability. MSC 2000 65F05,65F20,65G50
1 Introduction We consider the indefinite least squares (ILS) problem m i n ( A x - b ) T~,,p,q(Ax - b ) ,
(1)
X
where A E R Cp+q)×~ , b E R P÷q, and ~,,p,q =
0
-Iq
is a signature matrix. This problem has
several applications. Examples include the total least squares problems ( [ 1 ] ) and the H" smoothing problems ([2,a]). It is known that the ILS problem has a unique solution if and only if AT ~,p,qA > 0 ,
(2)
e . g . , [ 1 , 2 , 4 ] . In this note we assume that the condition (2) always holds. Note that under this condition we have p ~ n . The ILS problem is equivalent to its normal equation
A T ~ p , C 4 x = A T~,p.qb.
(3)
Since the normal equation is usually more ill-conditioned than the ILS problem, numerically, one prefers Received Dec. 1,2003 Proiect partially supported by the National Natural Science Foundation of China (Grant No. 0314427) and the University of Kansas General Research Fund Allocation (Grant No. 2301717) XU Hong-guo, Asso. Prof.,
[email protected],edu
to solve the problem by working on the original matrix A and the vector b directly. A typical example is the method that uses the QR factorization to solve the standard least squares problem (which is the special case of the ILS with q = 0 ) , see, e . g . , [ 5 , 6 ] , and [7,Sec. 5.3]. Following the idea of the OR factorization method, recently two methods were developed to solve the general ILS problem. The method proposed in [ 1 ] uses the OR factorization of A to solve the ILS problem. The precise procedure is as follows. First compute the compacted QR factorization
A =QR, where Q is orthonormal and R is square upper-triangular. Then compute the Cholesky factorization
LL w = QT~,p,qQ. Finally compute the solution x by solving three triangular systems successively,
Lz = QT~,,p.qb,
L Ty = z ,
R x = y.
It is easily verified that the solution ~¢ satisfies QT~_~p,qQRx = QW~,,p.qb. By pre-multiplying R T, it is just the normal equation ( 3 ) . In [ 1 ] it is shown that this method is numerically backward stable. The method proposed in [4] uses the hyperbolic QR factorization, an analog of the QR factorization, to solve the ILS problem. Definition 1
Let ~ p,q = [ "0
- 0Iq l
Journal of Shanghai University.
392 (1) The matrix H E R ( p + q) × ( p + q)
is
~ p, q-orthogo-
nal or hyperbolic if H T ~ p,q H = ~ p,q. (2) Let A E R (P+q)×'~. The factorization
where U, V are orthogonal and D is upper-bidiagonal. Compute d l = UTbl. Step 2 Solve the matrix equation
SD = A2 V
is called the hyperbolic QR factorization of A if H is N p,q-orthogonal and R is uppertriangular.
for S. Step 3
The method given in [4] consists of the following steps. First compute the hyperbolic factorization
f = [0
Compute In
- s T ] [ dl b2 1"
Compute the hyperbolic QR factorization and simultaneously update the vector
g= [In 0]/-ITNp,qb. Then compute x by solving the triangular system R~=g. This method is very similar to the QR factori~tion method for the standard least squares problem. Unlike the first method, which still needs to work on the product QT Np,qQ, this method directly work on A and b. Therefore it is less expensive (e.g. , [ 4 ] ) . In [4] it is also proved that under some mild assumptions the hyperbolic QR factori~tion method is forward stable. However, it is not clear whether the method is also backward stable. The main problem is that one can only show that the computed hyperbolic 0 R factorization and vector g satisfy a mixed backward-forward stable error model ( [ 4 ] ) . In this note we combine the ideas that were used for the previous two methods to develop the third method. We will also use the hyperbolic QR factorization. But for numerical stability we will compute the hyperbolic QR factorization of a normalized matrix. The general procedure of the method is given in the following algorithm. Algorithm 1
b=
[bl]ER"q b2
Given A = [ A A21 ] E R ( ' + q ) × n
,whereAIER'×"
,A2ERq~"
an d
,
b i E R P, b z E R q, and A T ~ p , q A > O , the algorithm computes the solution of the indefinite least squares problem (1). Step 1 Compute the permuted hidiagonal factorization
where H is ~ n,q-orthogonal and R is upper triangular. Step 4 Compute y by solving the triangular systems successively,
RTw = f ,
Rz = w ,
Dy = z.
Compute z = Vy. We will discuss the detailed computation process in the next section. In section 3 we will give the first order error analysis and show that the algorithm is numerically backward stable. For error analysis we will use the standard model of floating point arithmetic ( [8 ,pp. 44] ) :
f l ( a o b ) = (a + b ) ( l + ~), f/(~/-a ) = ~/-a (i + $),
I~l~
where u is the machine precision and o = + , - , x , / . The spectral norm for matrices and the 2-norm for vectors are denoted by {I • II • The £th column of the identity matrix I is denoted by e~.
2 Implementation Details In the algorithm Step 1 and 2 actually compute the factorization
A = 0
Iq
DvT"
Step 3 is equivalent to compute the hyperbolic QR factorization of the normalized matrix
[i1 0
Vol. 8 No. 4 Dec.2004
XU H G: A Backward Stable Hyperbolic QR Factorization Method for ...
By using these two forms the normal equation (3) becomes VDTRTRDVTx=
VDT[0
In
sT][
U 0] T 0 Iq ~_~p.qb,
which is euqivalent to RTRDVTx=[O
I,
- sTJl U 0
O] T Iq b = f .
The solution x is then obtained from Step 4. Note AT ~, p,qA > 0 =~ATA1 - A T A z > O =~DTD - VTATA2 V > 0 . So D is nonsingular, and from the last inequality we have I - s T s > 0 . This implies that [I S I[ <: 1. We will discuss Step 1 and Step 3 in details. Other steps are trivial. In Step I the factorization can be obtained by applying the bidiagonal factorization methods followed by a block row permutation. The Householder transformation method for computing the bidiagonal factorization can be found in [ 7, pp. 252 ]. Since U is only used for computing d~, we only need to apply the Householder transformations to b~ directly during the factorization process without storing U. The matrix V can be stored in the factored form, i. e . , only the vectors for the Householder transformations. When p >> n a faster method was proposed in [9]. It consists of two steps. First compute the QR factorization of At. Then compute the bidiagonal factorization of the upper-triangular factor. In Step 3 the hyperbolic QR factorization can be computed by the method as in [4]. But here the top block of the normalized matrix is In. So we can use the following simple version. We first introduce the hyperbolic rotation matrices Gij(a ,fl) : In. q + (a - 1)(e~ w + e f T) - fl(e~ T + e f T ) , where l ~ i ~ n , n + l~j~n + q and a ,fl satisfy a 2 _ f12 = 1. Clearly G~j ( a, fl) is ~ n.q-orthogonal. Givi n g a v e c t o r x E R n ÷ q with ] x i [ > [ x j l , where the integers i , j satisfy l ~ i ~ n and n + l ~ j ~ n + q, a hyperbolic rotation G~j ( a, fl) can be constructed to zero xj. The parameters a, fl may be chosen as a = We compute the hyperbolic QR factorization (4) by
393
applying the Householder transformations and the hyperbolic rotations to eliminate the entries of
S
umn by column. The algorithm is given below. In the algorithm we will use the Matlab forms to denote the entries, rows and columns of matrices. Algorithm for computing the hyperbolic QR factoriotio o StepO SOt R = In. Step 1 For k = 1 : n (1) Construct the Householder matrix Qk such that
QkS(:, k ) = x ~ l . Compute S ( : , k : n ) : = QkS ( :, k:n). (2) Construct the hyperbolic rotation Gk.,~+~ ( a k , ilk) to eliminate S (1, k ) ( = Xk). The parameter flk ( = Xkak ) is not needed. Compute R ( k , k ) = ~ / 1 - X2k, ak = l / R ( k , k ). S ' ÷ S " S ( 1 , k + l : n ) -- a k S ( 1 , k + l : n ) R(k,k+ l:n) = -XkS(1,k+ l:n). End for. Under the condition ( 2 ) , initially we have I - S r S > 0. Obviously the positive definiteness of R r R S r S is preserved during the reduction process. From this one can verify that I xkl < 1 for all l ~ k ~ n . So the algorithm will not break down. We discuss the cost of Algorithm 1. Step 1 It needs about 4 p n z - 4 n 3 / 3 flops for the bidiagonal factorisation. If the method in [9 ] is employed, it needs about 2 p n 3 + 2 n a flops. Computing dl needs about 4 p n flops. Step 2 It needs about 2qn 2 flops for computing A2 V, and about 3qn flops for solving the bidiagonal system for S. Step 3 It needs about 2qn flops for computing the vector f . It needs about 2qn 2 flops for computing R . The hyperbolic matrix H does not need to be updated. Step 4 It needs about 2 n 2 flops for solving three systems of equations to get y. Finally computing x needs about 2 n 2 flops. Table 1 compares the cbst of Algorithm 1 with the costs of the methods proposed in [ 1 ] and [ 4 ]. So about the cost Algorithm 1 is between other two methods.
394
J o u r n a l o f Shanghai University
Table 1
Costs of methods for solving the ILS problem
Algorithm 1
Algorithmin [1]
(S + A S l ) b = (A2 + AA2) V,
Algorithmin [4]
(4p + 4 q - 4 n / 3 ) n 2
or ( 2 p + 4 q + 2 n ) n z ( 5 p + 5 q - n ) n 2 ( 2 p + 2 q - 2 n / 3 ) n z p>>n
(2p + 4q)n z
(5p + 5q)n 2
(2p + 2q)n 2
p~n
(8n/3+4q)n z
(4n+Sq)n 2
(4n/3+2q)n z
where V is orthogonal, same as that in (5), II ~S~ II = O(u tl ~ II ), II aA2 II = O(u II A2 II ). In Step 3, the computed factor/~ in the hyperbolic factorization satisfies ( [4] ) [~:AR1
+AE1]
AS2]=Q[I 3
Error
Analysis
We will only consider the first order error bounds and ignore the possibility of overflow or underflow. We will use the letters with a hat for the matrices, vectors, or scalars computed in finite arithmetic. To show the backward stability we need the following two auxiliary results. L e m m a 2 Suppose D E R "× ~ is nonsingular upper bidiagonal and B E R q x 'L Let ~: be the numerical solution of the equation
(7)
0
(8)
,
where Q is orthogonal (which is related to H ), II ~R~ II , II AS2 II = O(u max{ II /~ II , I1 ~ II I),
II ZxE~ II = O(u). The computed vector )" satisfies y=[0
I,](cll+Adx)-(S+AS3)bz,
(9)
where II Ad~ II = 0 (u II da II = O (u II bl II ), II zxS3 II = O ( u II ~ II ) (See [8,pp. 76]). T h e v e c tots computed in Step 4 satisfy (/~ + A R 2 ) T w = f ,
(10)
(/~ + A R 3 ) z = W,
(11)
computed by forward substitution. Then ~: satisfies
(/~ + AD)y = z,
(12)
(f~ + A X ) D = B + AB,
where II AR2 II, II AR3 II ~ nu II /~ II , II A D II 3u II b II , s e e , e . g . , [ 8 , s e c . 8 . 1 ] . Finally the computed solution ~ satisfies
XD=B,
where II zxx II ~ 3 n u II ~ II, II AB II ~<3nu II B II • Proof. See Lemma 8 in [10]. Lemma 3 Suppose R , AR1, AR2 ~- R nxn , and [[ ARx 11 , I[ ARz 1[ = O(u [I R ][ ). Then the vector y = (R + AR1)a'(R + AR2)a: can be expressed as
g = (RTR + AR3) a:, where AR3 is O(u II R II 2).
symmetric
and
[1 AR3
= (V+AV)y,
where II ~ V II = O ( u ) , ( s e e [8,Lemma 18.2]). By using the formulas (10)-(13), and (6), (9), we have = (i~ + ARz)T(t¢ + A R a ) ( D
][
Proof. see [ 1].
=
where (5)
I.
U 0
+
A D ) ( V + AV)T~
0 TNp.q(b+Ab2 ) Iq '
Ab2 = [Abl + UAdl ] ,.So 0 J"
II Abz II = O(u II ba II ). where U, V are orthogonal and II ZXAx II = 0(ull A~ II ) , ( s e e , e . g . , [ 7 , s e c . 5 . 5 ] ) . The computed vector d 1 satisfies ~1 = U T ( b l + A b l ) ,
(6)
where U is orthogonal, same as that in ( 5 ) , and 11Ab~ II = O ( u [I bl 11 ) , ( [ 8 , 1 e m m a 1 8 . 3 ] ) . Based on the same error analysis for the product A2 V and using Lemma 2, the matrix ~ computed in Step 2 satisfies
(14)
+AS 3
The bidiagonal matrix /) computed in Step 1 satisfies
A~ + AAx = U[D ]VT ,
(13)
(15)
Taking (D + AD)( V + AV) T~ as a single vector, by Lemma 3 we have (/~ + AR2)T(/~ + AR3) (/) + AD)( V + Av)T~ = ( ~ r / ~ + AR4) ( b + AD)( V + AV)T~, where AR4 = (AR4) T and ]1 AR4 [I = O(u []/~ ]l 2). From (8) we have
(/~ + ~R1)r(/~ + AR1) + ($ + A S 2 ) r ( g + AS2) = (I. +AE1)T(I. +AEI). (16)
Vol. 8 No. 4 Dec.2004
XU H G: A Backward Stable HyperbolicQR Factorization Method for...
It can be rewritten as
395
~T/~ = In - (S + A s 1 ) T ( s +AS1) + A R s ,
Applying the same trick used in [1] to the right-hand side vector in (14),
where AS1 is defined in (7),
.~ =(~,-AF)T[ U 0 ] T
ARs = (AE1)W + AE1
-/~TAR1
0
-
(AR:)r/~ _
is symmetric. Then = I,, + AR4 + ARs - (S + AS1)T($ + ASl).
U ~'(F'TF') - I(AF)T) [ 0
II ~ II ~< 1 +
]1/XR,+txRs II < 1 ,
0
(17)
0] T Iq ~p,q(b+Ab2)
0 iq](lp+ q_
0 T U Iq] ~P'q( ~P'q[ o
__~T[0U
Note (16) also implies that II ~ II, O(u). So II A R 4 + ARs II = O(u). If
~p,q(b+Ab2)
= (~-'_ ZXF(~T~-~)- I~-,Tp)T[ U 0
s T ( A s 2 - AS1 ) - ( A S 2 - As1)T ~ + O(U2)
~T~ +~4
I¢
Iq
0 T
Iq] ~P'q(b+Ab2))
~p,q(b + Ab2- ~v,q 0 Iq " T
the matrix I, + AR4 + ARs is symmetric positive definite. In this case it is well known that I , + AR4 + ARs has a unique principle square root, i. e . , there exists a symmetric matrix AE2 such that
(I.
+ AE2) 2 =
and 1] AE2
In
+
F(FTF)-I(AF)T
0
l[ _~ <' 2! ]l AR4 + AR5 l] = O ( u ) . With this
form we have
where
0
: ~ / II ( p r ~ ) - i
II ~<1+ O(u).
I[b I[ II AF
+
?---- (~'T ~"~,p , k ) (D + AD)( V + Av)Tx.
0
(18)
The matrix
Iq
Np.q(b+Z~b).
(20)
By (18) and (20) we have ( ~ ' r N p . ~ ) (D + AD)( V + A v ) T )
~T~'~ = (tin + AE2)2 + (S + As1)T(~ + ASI)
=~T[ U 0
is positive definite. When (17) holds, we have II (FT~')-~ II <~ II ( I + A E z ) - z l l Denote
I°l AEz
=l+O(u).
(19)
.
Obviously II AF II = O ( u ) , and
0] T Io
~p,q(b+Ab).
Let
0
/AS1 - AS3J
Iq
Then by pre-multiplying ( V + A V ) ( b above equation, we have
~T~_~p,q~ --__~ ~_~p,q(b + Ab ). By using (5) and (7)
ti~
II = O(u II b II ).
Now we have
~SxJ
The first equation in (14) now becomes
+ASa
-1 ( A F ) T .
Iq
~,p.qb + 0(!12).
]] Ab l] <~ [] Ab2 [I
+ AE2 .
AF =
Iq
E
~]p,q
So by (15) and the fact that II AF [I = O ( u ) , we have
I: °l LS +
~p,qb + O(u2)).
Then by (19),
~ T ~ +AR4 = ( I . +AE2) 2 - (S + As1)T(s +AS1) = : FT ~,,p , k ,
~' =
Iq
Let Ab = Ab2 -
AR 4 + ARs,
0
=P-AF. Z~:=A-A--
~42
+
+
AD) T to the
396
U
[o
Journal of Shanghai University 0 Iq
References
]J IAE2bvT +b(AV)T 0 + ADVT1 + O(U2). ~
~ADVT+A2V(AV)T
[1]
J
Since [[/) [I = [[ A1 [[ + O ( u [ [ A1 [[ ), [[ AD j[ = O(u II / ) [ [ ) , [[ $ [[ ~ 1 + O(u), and [[ AE~_ [[ , II ~ y ][ = 0 ( u ) , we have
II
II = O(u II A II ).
[2]
[3]
T h e r e f o r e the solution ~ computed by Algorithm 1 satisfies [4]
(A + AA)T~p.q(A + AA)~ = (A + AA)W~p,q(b + Ab), or equivalently, ~ solves the perturbed ILS problem min ( ( A + A A ) x - ( b + A b ) ) W ~ p q ( ( A + A A ) x
[5]
-
z
( b + A b ) ) w,
[6]
where [[ AA [[ = O ( u I[ A [I ) and l[ Ab [I = O(u II b II ). So Algorithm 1 is backward stable. [7]
4
Conclusion
We proposed a numerically backward method for solving the indefinite least squares problem. This method employs the hyperbolic QR factorization. It is m o r e efficient than the backward stable method based on the QR and Cholesky factorizations. It is known that in general the hyperbolic QR factorization m e t h ods are mixed stable. But for the ILS problem by carefully implementing such a method, a backward stable algorithm still can be constructed.
[8]
[9]
[10]
Chandrasekaran S, Gu M, Sayed A H. A stable and efficient algorithm for the indefinite linear least-squares problem[J]. SIAM J. Matrix Anal. Appl. ,1998,20: 354 - 362. Hassibi B, Sayed A H, Kailath T. Linear estimation in Krein spaces, Part I: Theory [ J ]. 1EEE Trans. Automat. Control, 1996,41 : 18 - 33. Sayed A H, Hassibi B, Kailath T. Inertia properties of indefinite quadratic forms [ J 1. l~:b: Signal Process Lett., 1996,3:57 - 59. Bojanczyk A, Higham N J, Patel H. Solving the indefinite least squares problem by hyperbolic QR factorization [J ]. SIAM J. Matrix Anal. Appl. , 2003,24:914 931. BjSrck A. Numerical Method for Least Squares Problems [M]. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996. Lawson C L, Hanson R J. Solving Least Squares Problems[M]. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1995. Golub G H, Van Loan C F. Matrix Computations[M]. Johns Hopkins University Press, Baltimore, third edition, 1996. Higham N J. Accuracy and Stability of Numerical Algorithms[M]. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996. Chan T F. An improved algorithm for computing the singular value decomposition [ J ]. ACM Trans. Math. Soft. , 1982, $: 72 - 83. Byers R, Xu H. A rapidly converging, backward stable matrix sign function method for computing polar decomposition[J]. In progress. ( Executive editor SBNN Mei-fang)