Discrete Signal Representations (779441), страница 2
Текст из файла (страница 2)
. ,n:n(",'pj)=~ai(cpi,cpj),j=L...,n.(3.54)i=lIn matrix notation this is+a=p(3.55)58Chapter 3. Discrete Signal RepresentationsFigure 3.3. Reciprocal basis (The basis is ' p 1 = [0, 1IT, 'pz= [2, 1IT; the corresponding reciprocal basis is &= [-0.5, l]T , &= [0.5, OIT).9 is known as the Grammian matrix. Due tothe property 9 = a H .(vi,=vk)(vk,vi)*it hasThe disadvantage of the method considered above is that for calculatingthe representation (y. of a new X we first have to calculate P before (3.55) canbe solved.
Much more interesting is the computation of the representationa by means of the reciprocal basis {ei; i = 1 , 2 , 3 . . . n } , which satisfies thecondition(cpi,ej)=, i , j = 1 , . . . ,n,(3.57)sijwhich is known as the biorthogonality condition; Figure 3.3 illustrates (3.57)in the two-dimensional plane.Multiplying both sides of (3.52) withn(x,ej)=-Oj,j = 1 , . . . ,n leads toCai(vi,ej)= ai, j = 1 , .
. . , n ,i=l(3.58)6ijwhich means that, when using the reciprocal basis, we directly obtain therepresentation by forming inner products593.3. General Series ExpansionsA vectorXcan be represented as(3.60)and also as(3.61)Parseval’s relation holds onlyfor orthonormal bases. However, also forgeneral bases a relationship between the inner product of signals and theirrepresentations can be established. For this, one of the signals is representedby means of the basis {vl,..
. ,(P,} and a second signal by means of thecorresponding reciprocal basis {&, . . . , On}. For the inner product of twosignalscnX =( X ,( P i )Oi(3.62)i= 1and(3.63)we get(X7Y) =(3.64)In the last step, the property (pi, O k ) = Sik was used.Calculation of the Reciprocal Basis. Since pk, k = 1 , . . . , n as well as8 j , j = 1,.. . , n are bases for X , the vectors 8 j , j = 1,.. . , n can be writtenas linear combinations of ( P ~k ,= 1,..
. , n with the yet unknown coefficientsyjk:nej = E r j kpk,k=lj = l,...,n.(3.65)60RepresentationsChapterSignal3. DiscreteMultiplying this equation with p i , i = 1 , . . . ,n and using (3.57) leads toi , j = 1 , . . . ,n.(3.66)Wit h(3.67)and9T =(3.68)equation (3.66) can be written asrGT= I ,(3.69)so thatr=(9 ~ ) ~ ~ .(3.70)The reciprocal basis is obtained from (3.65), (3.67)and (3.70).3.3.2Orthogonal ProjectionWe consider the approximation of X E X by X E Mm, where Mm C X . Forthe signal spaces let X = span {vl,..
. ,vn}and Mm = span {vl,.. . , v,}with m < n.As we will see, the best approximation in the sense of(3.71)is obtained for(3.72)613.3. General Series Expansionswhere { e i ; i = 1 , . . . , m } is the reciprocal basis tothat the reciprocal basis satisfies{vi;i = 1 , . . . , m } . NoteMm = span {vl,. .
. ,v,} = span {el,. . . ,e,} .(3.73)Requiring only (pi,ej) = & j , i, j = 0 , 1 , . . . , m is not sufficient for 8j to formthe reciprocal basis.ofFirst we consider the expression ( 2 ,e j ) with 2 according to (3.72). Becausewe obtain(v,,e j ) = S i jei)v i, ej(X,i= 1)= (X,e j ) , j = 1 , . . . , m .(3.74)Hence,(z-2,0j)=0,j = 1 , ..., m.(3.75)Equation (3.75) shows thatr)=x-x(3.76)is orthogonal to all 8 j , j = 1 , .
. . , m. From (3.73) and (3.75) we conclude thatr ) is orthogonal to all vectors in M,:q 1% for all 5 E Mm.(3.77)This also means that X is decomposed into an orthogonal sumX = MmI@M:.(3.78)For the vectors we havex=2+q,2EMm, qEMA, X E X .(3.79)The approximation2 according to (3.72) is the orthogonal projectionof X E Xonto M,.In order to show that 2 according to (3.72) is the best approximation toX , we consider the distance between X and an arbitrary vector 5 E Mm andperform some algebraic manipulations:d2(X,0)= 112 - all2= ll(z - 2) - (a - 2)112= ((X - 2 ) - (a - g), (z- 2) - (a - 2 ) )= ( x - 2 , x - 2 ) - ( x - 2 , 5 - 2 ) - (9-2,x-2)+ (a-2,a-k).(3.80)62RepresentationsChapterSignal3. DiscreteBecause of (5- 2 ) E M , and (3.75), the second and third terms in (3.80)are zero, such thatThe minimum is achieved for 5 = P , so that (3.72) clearly yields the bestapproximation.A relationship between the norms ofX,&andv is obtained fromBecause of (3.79) the second and the third termin the last row are zero, and11412=1 1 4 2 + llv1I2(3.83)remains.3.3.3Orthogonal Projection of n-TuplesThe solutions to theprojection problem consideredso far hold for all vectors,including n-tuples, of course.
However, for n-tuples the projection can concisely be described with matrices, and we have a large number of methods athand for solving the problem.In the following, we consider the projection of X = [XI,.. . ,X,] T E C,onto subspaces M , = span { b l , . . . ,b,}, where m < n and bi E C,. WithB = [bl,. . . ,b,]nXm matrix(3.84)1 vector(3.85)anda = [ul,. . . ,u,lTmXthe approximation is given byx=Ba.Furthermore,theorthogonalmatrix P asprojection canbeX=Px.(3.86)described by a Hermitian(3.87)Series3.3.
General63ExpansionsInner Product without Weighting. To compute the reciprocal basis 0 =[e,,. . . ,e,] the relationships (3.70), (3.56) and (3.65) are used, which can bewritten asrT=+-l,a=BHB,o=BrT.(3.88)For the reciprocal basis we then geto = B [BHBI-'.(3.89)Observing that the inverse of a Hermitian matrix is Hermitian itself, therepresentation is calculated according to (3.59) asa = OH%= [ B H B ] - l B H z .(3.90)With (3.86) the orthogonal projection is2 = BIBHB]-lBHz.(3.91)If B contains an orthonormal basis, we have B H B = I,and the projectionproblem is simplified.Note that the representation according to (3.90) is the solution of theequation[B%] a = B H 2 ,(3.92)which is known as the normal equation.Inner Product with Weighting.
For an inner product with a weightingmatrix G , equations (3.70), (3.56) and (3.65) giverT+=@-l,= B~GB,(3.93)0 = B P .Thus, we obtain0 = B [BHGB]-l,(3.94)a = OHGx= [ B H G B ] - l B H G x ,(3.95)63 = BIBHGB]-lBHGx.(3.96)64Chapter 3. Discrete Signal RepresentationsAlternatively, G can be split intoa product G = H H H ,and the problem(3.97)can be transformed viaz = Ha:V=(3.98)HBinto the equivalent problem(3.99)The indices of the norms in (3.97) and (3.99) stand for the weighting matricesinvolved. Thus, the projection problem with weighting can be transformedinto one without weighting.
Splitting G into G = H H H can for instance beachieved by applying the Cholesky decomposition G = LLH or by a singularvalue decomposition. Both methods can be applied in all cases since G mustbe Hermitian and positive definite in order to be a valid weighting matrix.Note. The computation of the reciprocal basis involves the inversion of theGrammian matrix. If the Grammian matrix is poorly conditioned, numericalproblemsmayoccur.Robustmethodsof handling such cases are the QRdecomposition and theMoore-Penrose pseudoinverse, which will be discussedin the next section.3.43.4.1Mathematical ToolsThe QR DecompositionThe methods for solving the projection problem considered so far requirean inversion of the Grammian matrix. The inversion does not pose a majorproblem so long asthe vectors that span the subspace in question arelinearly independent.
However, because of finite-precision arithmetic, a poorlyconditioned Grammian matrix may lead to considerable errors, even if thevectors are linearly independent.A numerically robust solution of!= mina=a(3.100)653.4. Mathematical Toolsis obtained by carrying out a QR decomposition of B:B=QR.(3.101)Here, Q is a unitary matrix, and R has the following form:(3.102)The QR decomposition can, for instance, be computed by using Householder reflections or Givens rotations; see Sections 3.4.4 and 3.4.5.In the following we will show how (3.100) can be solved via &R decomposition. Substituting (3.101) in (3.100) yields(3.103)For (3.103) we can also writel= min,IIQHQRa- QHzll= IIRa - QHzllla = a(3.104)because a multiplication with a unitary matrix does not change the norm ofa vector.
Using the abbreviation y = Q H x ,we getY1.llRa - YII =.rmmYm(3.105)Ym+lYnWith, f=[yj;](3.106)(3.107)66RepresentationsChapterSignal3. DiscreteThe norm reaches its minimum if a = a is the solution ofX a=.%.(3.108)Note that X is an upper triangular matrix, so that a is easily computed byusing Gaussian elimination. For the norm of the error we have:(3.109)3.4.2The Moore-Penrose PseudoinverseWe consider the criterion(3.110)The solutions (3.90) and (3.91),a =[BHBI-l BHX,(3.111)5B [ B HBBH] -xl,(3.112)=can only be applied if [ B H B ] exists, that is, if the columns of B are linearlyindependent.
However, an orthogonal projection can also be carried out ifB contains linearly dependent vectors. A general solution to the projectionproblem is obtained by introducing a matrix B+ via the following fourequationsB+B = (B+B)H(3.113)BB+ = ( B B + ) ~(3.114)BB'B= BB+BB+ = B+.(3.115)(3.116)There is only one B+ that satisfies (3.113) - (3.116). This matrix is called theMoore-Penrose pseudoinverse [3]. The expressions B + B and B B + describeorthogonal projections, since under conditions (3.113) - (3.116) we have[X - BB+xIHBB+x = 0 ,(3.117)[a- B + B a ] H B + B a= 0.673.4. Mathematical ToolsAssuming that B is an nk = n, we haveXm matrix which either has rank k = m orB+ = [ B H B ] - l B H , 5 = m ,B+ = B[BHB H ] - l ,5 = n,(3.118)B+ can for instance be computed via the singular value decompositionB =UXVH.U and V are unitary.
For m< n, X(3.119)has the following form:(3.120)The non-zero valuesC T ~> 0. WithC T ~ arecalled the singular values of B . They satisfythe pseudoinverse B+ is given byB+ = V X + U H .(3.122)It can easily be shown that the requirements (3.113) - (3.116) with B+according to (3.122) are satisfied, so that (3.111) and (3.112) can be replacedbya= B+x,(3.123)2= BB+X.(3.124)Note that (3.123) is not necessarily the only solution to the problem(3.110). We will return to this topic in the next section.68Chapter 3. Discrete Signal RepresentationsBy taking the productsB H Band B B H we obtain equations for calculating the singular value decomposition.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
