QR分解及其应用

《矩阵分析与应用》专题报告——QR分解及应用学生姓名：卢楠、胡河群、朱浩2015年11月25日目录1引言..............................................................32QR分解...........................................................42.1QR分解的性质................................................42.2QR分解算法.................................................52.2.1采用修正Gram-Schmidt法的QR分解......................52.2.2HouseholderQR分解...................................62.2.3采用Givens旋转的QR分解..............................83QR分解在参数估计中的应用.........................................93．1基于QR分解的参数估计问题................................93.2基于Householder变换的快速时变参数估计....................123.3基于Givens旋转的时变参数估计.............................144QR分解在通信系统中的应用........................................164.1基于QR分解的稳健干扰对齐算法..............................164.2基于QR分解的MIMO置信传播检测器........................19总结...............................................................21参考文献...........................................................221引言矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质的若干矩阵之积或之和，大体上可以分为满秩分解、QR分解和奇异值分解。矩阵分解在矩阵分析中占有很重要的地位，常用来解决各种复杂的问题。而QR分解是工程中应用最为广泛的一类矩阵分解。QR分解是目前求一般矩阵全部特征值的最有效并广泛应用的方法，一般矩阵先经过正交相似变换成为Hessenberg矩阵，然后再应用QR分解求特征值和特征向量。它是将矩阵分解成一个正交矩阵Q与上三角矩阵R，所以称为QR分解。参数估计是在已知系统模型结构时，用系统的输入与输出数据计算系统模型参数的过程。它在系统辨识和无线通信领域有着广泛的应用。18世纪末德国数学家C.F.高斯首先提出参数估计的方法，他用最小二乘法计算天体运行的轨道。20世纪60年代，随着电子计算机的普及，参数估计有了迅猛的发展。参数估计有很多方法，如矩估计、极大似然法、一致最小方差无偏估计、最小风险估计、同变估计、最小二乘法、贝叶斯估计、极小极大熵法等。其中最基本的是最小二乘法和极大似然法。本文将重点介绍QR分解及其在参数估计和通信系统中的应用。2QR分解2.1QR分解的性质定理2.1.1（QR分解）若mnRA，且mn，则存在列正交矩阵mnRQ和上三角矩阵mnRR使得A=QR。当mn时，Q是正交矩阵。如果A是非奇异的nn矩阵，则R的所有对角线元素均为正，并且在这种情况下Q和R二者是唯一的。若A是复矩阵，则Q和R取复值。注意到TTTAA=(QR)(QR)=RR,因此可以得出结论：TG=R是TAA的下三角Cholelskey因子。由于这个原因，在关于估计的文献中，矩阵R常称为平方根滤波器（算子）。下面的引理称为矩阵分解引理，它在矩阵的QR分解的应用中是一个很有结果。引理2.2.1若A和B是任意两个mn矩阵，则HHAA=BB(2.1.1)当且仅当存在一个mm酉矩阵Q，使得QA=B(2.1.2)证明充分性证明：若QA=B，并且Q是酉矩阵，则HHHHBB=AQQA=AA。必要性证明：令A和B的奇异值分解分别为HAAAA=UVHBBBB=UV式中，AU和BU均为mm酉矩阵；AV和BV都是nn酉矩阵；而mn矩阵A和B分别包含了矩阵A和B的非负奇异值。由于HHHAAAAAA=VVHHHBBBBBB=VV若HHAA=BB,则有ABV=V和AB。定义矩阵HBAQ=UU易知HHHHBABAAAABBBQA=UUA=UUUV=UV=B这就证明了引理的必要条件[10]。2.2QR分解算法2.2.1采用修正Gram-Schmidt法的QR分解矩阵A的QR分解可以利用Gram-Schmidt正交化方法实现。Gram-Schmidt正交化方法原本是一种由n个向量12na,a,...,a构造互相正交且范数为1的向量12nq,q,...,q的方法。将向量1a标准正交化的结果取作1q，即1111RR111aqq(2.2.1)然后，从2a中除去与1a平行的向量，再进行标准正交化，并将结果取作2q，则有1222121222()RRRRRH1221221qaaqqaq(2.2.2)进而，又从3a除去与1a和2a平行的两个分量，再进行标准正交化，并使用该结果作3q，即有1323331323132333()RRRRRRRRH13H233123312qaqaaqqqaqq(2.2.3)如此继续，则对于(2)kknq有111331,1jk1R()HjkjkkkkkjjkjkkkjjkjRRRRqaaqqaq(2.2.4)容易验证，iq是标准正交基，即满足ijijHqq(2.2.5)其中，ij为Kronecker函数。如果令mn矩阵A的列向量,,,12naa...a，则以1,2,,nqq...q为列向量的矩阵Q与A之间有下列关系：A=QR(2.2.6)又由于iq组成标准正交基，所以HnQQ=I将A与Q重写在同一矩阵，应用以上Gram-Schmidt正交化的方法叫做经典Gram-Schmidt正交化法[6]。2.2.2HouseholderQR分解Householder变换可以实现任意mn矩阵A的QR分解，其原理是使用变维向量的Householder变换，使得该向量除第一个元素外，其他元素皆为0。根据Householder变换的相关知识，欲使一个p维向量12,,...,xTpxxx的第1个元素后面的所有元素变为0，则p维的Householder向量应取1()x1xew(2.2.7)式中111,xxxxx(2.2.8)假定mn矩阵A的列分块形式为1,2,,...mnnAaaa首先令111,21,,1...maaaTxa，并取pm，则按照式(2.2.7)和式(2.2.8)，可以计算得到1muw。此时，(1)(1)(1)1111112,,,nTHIuuAHAaa...a(2.2.9)变换后，矩阵1A的第1列(1)1a的第一个元素等于1222211211...amaa，而该列的其他元素全部为0。第二步针对矩阵1A的第2列(1)2a，令1pm和(1)(1)(1)22322,,...,maaaTx又可按照式(2.2.7)和式(2.2.8)求出（m-1）维向量1mw。此时，取210muw，又可得到(1)(2)(2)2222212112,,,nTHIuuAHAHHAaa...a(2.2.10)变换后，矩阵2A的第1列与1A的第1列相同，而第2列(1)1a的第一个元素等于(1)12a，第二个元素等于12222(1)(1)(1)22322...amaa，而该列的其他元素全部为0。类似地，又可针对矩阵2A的第3列设计Householder变换矩阵3H，使得2A的第一、二个元素保持不变，其他元素组成的m-2维向量(2)(2)(2)33433,,...,maaaTx变换为除第一个元素外的全部元素变为0。假定矩阵A经过k-1次Householder变换后，已变成(1)kA，即(1)(2)111(1)(1)(1)12...,,...,,k=2,3,...kkkkkkknAHAHHAaaa并且其前k-1列具有以下变换结果:(1)(1)(1)1,...,,0,...,0,j=1,2,...k-1kkkjjjjTaaa因此，第k次Householder变换的目的就是保持前k-1列不变，实现(1)kA列第k列的下述变换：(1)(),,(1)1,(1),00kkkkkkkkkkkmkaaaaH这相当于对矩阵(1)kA进行Householder变换(1)kkHA时取1kkkI0H0Hn次Householder变换后，即可实现QR分解。2.2.3采用Givens旋转的QR分解Givens旋转也可以用来计算QR分解。这里以43矩阵为例，说明GivensQR分解的思想：(3,4)(2,3)(1,2)(3,4)(2,3)(3,4)000000000000000000000其中，表示用Givens旋转进行变化你的元素。从上述说明中易得出结论：如果令jG代表约化过程中的第j次Givens旋转，则TQA=R是上三角矩阵，其中tt-11Q=GGLG，而t是总的旋转次数。3QR分解在参数估计中的应用3．1基于QR分解的参数估计问题现在以系统辨识为例，说明如何利用矩阵的QR分解进行系统参数的递推估计。令系统在k时刻的输入为xk，系统输出的观测值由卷积方程0pTkiiykxkekxkiekekxθ(3.1.1)给出，其中，表示离散卷积，ek代表k时刻的观测误差，且01,1,,,,,TkTpxkxkxkpxθ(3.1.2)若将1,2,,kn的所有观测数据组成一向量，则nnnyAθe(3.1.3)式中，1,2,,Tnyyyny，1,2,,Tneeene，1,2,,TnxxxnA。系统辨识问题的提法是：已知系统输入xk和输出观测值yk，其中，1,2,,kn，估计系统参数向量θ[7]。在时变系统的辨识中，则要求在已估计n时刻的系统参数向量nθ的情况下，使用增加的1,1xnyn值，通过简单的运算，递推出1n时刻的系统参数向量1n。n时刻的系统辨识问题可以简化为最小二乘问题22minnnnnθAθy(3.1.4)求解，并且其解由“法方程”TTnnnnnxxnnAAθAyRθr或(3.1.5)确定。式中，TxxnnRAA代表系统输入xk的协方差矩阵，TnnnrAy。直接求解式(3.1.5)的方法叫做协方差方法。例如，先计算协方差矩阵xxR的Cholesky分解TxxGGR,然后利用回带法解三角矩阵1TnnGθGR直接得到nθ。然而，由于TxxnnRAA的条件数是nA的条件数的