Discrete Signal Representations (779441), страница 3
Текст из файла (страница 3)
With B according to (3.119) we haveB H B = V ~ ~ U H U ~= V vH[xHx]V H ,(3.125)B B =uxvHvxHuH~= U[xx "1uH.That is, thesquares of the singular values of B arethe eigenvalues ofB H B and at the same time of BB". Matrix V contains the orthonormaleigenvectors of B H B .Correspondingly, U contains theeigenvectors of B B H .Further methods of calculating the pseudoinverse are discussed in [3].Note. The pseudoinverse may be written asB+ = [ B H B ] +B".(3.126)++This property can be applied to continuous functions, and with rT =instead of rT = +-l we can compute a set of functions e,@), which is dualto a given set cpi(t);see (3.65) - (3.70).3.4.3The NullspaceLet us consider the problemBa=X,(3.127)where X = B B+x is the orthogonal projection of an arbitrary X onto thecolumn subspace of B .
It is easily observed that the solution to (3.127) also isthe solution to (3.110). Depending on B we either have a unique solution a ,or we have an infinite number of solutions. Finding all solutions is intimatelyrelated to finding the nullspace of matrix B .The nullspace of a matrix B consists of all vectors a such that B a = 0 .It is denoted by N ( B ) .In order to describe N ( B ) ,let us assume that Bis an n X m matrix that has rank T . If T = m then N ( B ) is only the nullvector, and a = B+$ = B+x is the unique solution to (3.127) and thus alsoto (3.110). If T < m then N ( B ) is of dimension m - T , which means thatN ( B )is spanned by m - T linearly independent vectors. These vectors can bechosen to form an orthonormal basis for the nullspace.
If we define a matrixN of size m X ( m - T ) whose column subspace is the nullspace of B thenBN=O.(3.128)The set of all solutions to (3.127) is then given bya =h+ Np,wherezi = B+X = B + x .(3.129)693.4. Mathematical ToolsIn (3.129) p is an arbitrary vector of length m - T . In some applications it isuseful to exploit the free design parameters in p in order to find a solutiona that optimizes an additional criterion. However, in most cases one will usethe solution 2i given by the pseudoinverse, because this is the solution withminimum Euclidean norm. In order to see this, let us determine the squarednorm of a:2llallezaHa= [B+x+ NpIH[B+x+ Np]=+++= x ~ ( B + ) ~ B +P z~ N ~ B + Zz ~ ( B + ) ~ NP P~ N ~ N P .(3.130)The second and third terms vanish, because B N = 0 implies that N H B +=0.
Thus, we get the vector a of shortest length for p = 0, that is for a = 6.The matrix N that contains the basis for the nullspace is easily foundfrom the singular value decompositionB =UXVH.(3.131)Let B have rank T and let the T nonzero singular values be the elements[X]1,1,.. . , [X]T,Tof matrix X. Then an orthonormal matrixN is given by thelast m - T columns of V.3.4.4The Householder TransformHouseholder transforms allow a simple and numerically robust wayof performing QR decompositions, and thus of solving normal equations. The QRdecomposition is carried out step by step by reflecting vectors at hyperplanes.Inorder to explain the basicidea of the Householder transforms weconsider two vectors X ,W E (En, and we look at the projection of X ontoa one-dimensional subspace W = span {W}:P,x=wHere,(En is-wHx.WHW(3.132)decomposed into the orthogonal sum(3.133)The Householder transform is given byH,x= X -2P,x.(3.134)70Chapter 3.
Discrete Signal Representations--Pwx=IWpw XWFigure 3.4. Householder reflection.It is also known as Householder reflection, because it is the reflection ofthe hyperplane W I , as depicted in Figure 3.4.XatWith P , according to (3.132) we getH,=I--2WWHWwH(3.135)for the Householder matrix H , .From (3.135) the following property of Householdermatricescanbeconcluded:H ~ H ,= H , H ,=[I - & W W H ] [I - & W W H ](3.136)= I.Hence H , is unitary and Hermitian. Furthermore we havedet{H,}(3.137) = -1.In order to make practical use of the Householder transform, we considera vector X and try to find that vector W for which only the ith component ofH,x is non-zero. We use the following approach:w=x+aei,where(3.138)713.4.
Mathematical Toolse: = [o, . . . , 0 , 1,O,.. . ,0] .(3.139)f ith elementFor H,x we getz-2-WWHO-(3.140)[x + a ei]=x - 2%=(1-2G) x-2aw H x ei.In order to achieve that only the ith component of H,x is non-zero, theexpression in parentheses in (3.140) must vanish:1-2-WHXWHW+ a*xi+ axg + a*xi +11x112=l-2llxll= 0,la12(3.141)where xi is the ithcomponent of x. As can easily be verified, (3.141) is satisfiedfor(3.142)In order to avoid W M 0 in the case ofpositive sign in (3.142) and obtainW=XX M Deixi llxll+-1% Ifor someER we choose the(3.143)ei.By substituting this solution into (3.140) we finally get(3.144)Applying the Householder transform to the QR Decomposition. Weconsider the probleml l ~v bll L min(3.145)withA=Ean,ill.
..anm(IFm,n>m(3.146)72Chapter 3. Discrete Signal Representationsand try to tackle the problem by applying the &R decomposition. First, wechoose z1 to be the first column of A(3.147)Multiplying A with the Householder matrix(3.148)where w1 is chosen as(3.149)yields a matrix where only r11 is non-zero in the first column:Then, we choose= I - w2wf2 7H 2W2 W2and obtainH2HlA=[rii0r12r13. . . rlrnV22r&* * *an3(3)...00anm(‘3)After maximally m steps we getHrn-**H2HlA=R,(3.151)where only the upper right-hand triangular matrixof R is non-zero. Thismeans that we have carried out the &R decomposition.Note.
If one of the values a::) becomes zero, wi is chosen as wi = zi+llzill ei.If IJzilJ= 0, the columns must be exchanged.733.4. Mathematical Tools3.4.5Givens RotationsBesides Householder reflections, rotations constitute a further possibility ofperforming QR decompositions. We first consider the rotationof a real-valuedvector X by an angle $ throughmultiplication of X with anorthonormalrotation matrix G . For(3.152)and(3.153)we get2’ = G X =r cos(a - $)r sin(a - $)1(3.154)’We observe that for $ = Q! a vector X’ is obtained whose second componentis zero. This special rotation matrix isG = [-Sc“1(3.155)cwithc =SCOS(Q!)== sin(a) =For the rotated vector we havex‘=Gx=[:l=[X1@Tg(3.156)X2Jm*1.JW(3.157)As can easily be verified, for complex-valued vectors we can apply therotation matrixG=[:*:](3.158)(3.159)in order to obtain X’ = [r,0lT.Note that G according to (3.
58) is unitary,G ~ =GI .We now consider a vector. . . ,xi-1, xi,Xi+l, . . . , xj-1, xj,Xj+l, . . . , X,] TX = [XI,(3.160)74Chapter 3. Discrete Signal Representationsand want to achieve a vector2'= [XI,.. . , X i - l ,T,Xi+l,.withr=. . , Xj-l,O, Xj+l,. . . ,X,] TJm(3.161)(3.162)by carrying out a rotation. The rotation is applied to the elements xi and xjonly. We have(3.163)with4iG=(3.164)+.iA QR decomposition of a matrixcan becarried out by repeated applicationof the rotations described above..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
