QR分解及其应用.doc

矩阵分析与应用专题报告QR分解及应用学生姓名：卢楠、胡河群、朱浩2015年11月25日目录1 引言32 QR分解32.1QR分解的性质32.2 QR分解算法42.2.1 采用修正Gram-Schmidt法的QR分解42.2.2 Householder QR分解52.2.3 采用Givens旋转的QR分解63 QR分解在参数估计中的应用731 基于 分解的参数估计问题73. 2基于 变换的快速时变参数估计93. 3基于 旋转的时变参数估计114 QR分解在通信系统中的应用124.1 基于QR分解的稳健干扰对齐算法124.2基于 分解的 置信传播检测器14总结16参考文献171 引言 矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质的若干矩阵之积或之和，大体上可以分为满秩分解、QR分解和奇异值分解。矩阵分解在矩阵分析中占有很重要的地位，常用来解决各种复杂的问题。而QR分解是工程中应用最为广泛的一类矩阵分解。QR分解是目前求一般矩阵全部特征值的最有效并广泛应用的方法，一般矩阵先经过正交相似变换成为Hessenberg矩阵，然后再应用QR分解求特征值和特征向量。它是将矩阵分解成一个正交矩阵Q与上三角矩阵R，所以称为QR分解。 参数估计是在已知系统模型结构时，用系统的输入与输出数据计算系统模型参数的过程。它在系统辨识和无线通信领域有着广泛的应用。18世纪末德国数学家C.F.高斯首先提出参数估计的方法，他用最小二乘法计算天体运行的轨道。20世纪60年代，随着电子计算机的普及，参数估计有了迅猛的发展。参数估计有很多方法，如矩估计、极大似然法、一致最小方差无偏估计、最小风险估计、同变估计、最小二乘法、贝叶斯估计、极小极大熵法等。其中最基本的是最小二乘法和极大似然法。 本文将重点介绍QR分解及其在参数估计和通信系统中的应用。2 QR分解2.1QR分解的性质定理2.1.1（QR分解）若，且，则存在列正交矩阵 和上三角矩阵 使得 。当时，是正交矩阵。如果 是非奇异的 矩阵，则 的所有对角线元素均为正，并且在这种情况下 和 二者是唯一的。若 是复矩阵，则 和 取复值。 注意到 ,因此可以得出结论： 是 的下三角 因子。由于这个原因，在关于估计的文献中，矩阵 常称为平方根滤波器（算子）。 下面的引理称为矩阵分解引理，它在矩阵的QR分解的应用中是一个很有结果。 引理2.2.1 若 和 是任意两个 矩阵，则 (2.1.1)当且仅当存在一个 酉矩阵 ，使得 (2.1.2) 证明 充分性证明：若 ，并且 是酉矩阵，则 。 必要性证明：令 和 的奇异值分解分别为 式中， 和 均为 酉矩阵； 和 都是 酉矩阵；而 矩阵 和 分别包含了矩阵 和 的非负奇异值。由于 若 ,则有 和 。定义矩阵 易知 这就证明了引理的必要条件10。 2.2 QR分解算法2.2.1 采用修正Gram-Schmidt法的QR分解矩阵 的QR分解可以利用Gram-Schmidt正交化方法实现。Gram-Schmidt正交化方法原本是一种由n个向量 构造互相正交且范数为1的向量 的方法。将向量 标准正交化的结果取作 ，即 (2.2.1)然后，从 中除去与 平行的向量，再进行标准正交化，并将结果取作 ，则有 (2.2.2)进而，又从 除去与 和 平行的两个分量，再进行标准正交化，并使用该结果作 ，即有 (2.2.3)如此继续，则对于 有 (2.2.4)容易验证， 是标准正交基，即满足 (2.2.5)其中， 为Kronecker 函数。如果令 矩阵 的列向量 ，则以 为列向量的矩阵 与 之间有下列关系： (2.2.6)又由于 组成标准正交基，所以 将 与 重写在同一矩阵，应用以上Gram-Schmidt正交化的方法叫做经典Gram-Schmidt正交化法6。2.2.2 Householder QR分解Householder变换可以实现任意 矩阵 的QR分解，其原理是使用变维向量的Householder变换，使得该向量除第一个元素外，其他元素皆为0。根据Householder变换的相关知识，欲使一个 维向量 的第1个元素后面的所有元素变为0，则 维的Householder向量应取 (2.2.7)式中 (2.2.8) 假定 矩阵 的列分块形式为 首先令 ，并取 ，则按照式和式，可以计算得到 。此时， (2.2.9)变换后，矩阵 的第1列 的第一个元素等于 ，而该列的其他元素全部为0。 第二步针对矩阵 的第2列 ，令 和 又可按照式和式求出（m-1）维向量 。此时，取 ，又可得到 (2.2.10)变换后，矩阵 的第1列与 的第1列相同，而第2列 的第一个元素等于 ，第二个元素等于 ，而该列的其他元素全部为0。 类似地，又可针对矩阵 的第3列设计Householder变换矩阵 ，使得 的第一、二个元素保持不变，其他元素组成的m-2维向量 变换为除第一个元素外的全部元素变为0。 假定矩阵 经过k-1次Householder变换后，已变成 ，即 并且其前k-1列具有以下变换结果: 因此，第k次Householder变换的目的就是保持前k-1列不变，实现 列第k列的下述变换： 这相当于对矩阵 进行Householder变换 时取 n次Householder变换后，即可实现QR分解。2.2.3 采用Givens旋转的QR分解 Givens旋转也可以用来计算QR分解。这里以 矩阵为例，说明Givens QR分解的思想： 其中， 表示用Givens旋转进行变化你的元素。 从上述说明中易得出结论：如果令 代表约化过程中的第j次Givens旋转，则 是上三角矩阵，其中 ，而t是总的旋转次数。3 QR分解在参数估计中的应用31 基于 分解的参数估计问题现在以系统辨识为例，说明如何利用矩阵的 分解进行系统参数的递推估计。令系统在 时刻的输入为 ，系统输出的观测值由卷积方程 (3.1.1)给出，其中， 表示离散卷积， 代表 时刻的观测误差，且 (3.1.2)若将 的所有观测数据组成一向量，则 (3.1.3)式中， ， ， 。系统辨识问题的提法是：已知系统输入 和输出观测值 ，其中， ，估计系统参数向量 7。在时变系统的辨识中，则要求在已估计 时刻的系统参数向量 的情况下，使用增加的 值，通过简单的运算，递推出 时刻的系统参数向量 。 时刻的系统辨识问题可以简化为最小二乘问题 (3.1.4)求解，并且其解由“法方程” (3.1.5)确定。式中， 代表系统输入 的协方差矩阵， 。 直接求解式的方法叫做协方差方法。例如，先计算协方差矩阵 的 分解 ,然后利用回带法解三角矩阵 直接得到 。然而，由于 的条件数是 的条件数的平方，因此，直接计算式的得到的解有可能是严重病态的（即条件数很大），即使 本身的条件数并不大，不是严重病态的。 在系统参数向量 的自适应递推辨识中，标准的递推最小二乘 法和 分解法都是针对协方差矩阵 进行更新的。虽然 分解（其中， 为上三角矩阵， 为对角矩阵）在数值上比较稳定，但是这些递推辨识方法也同样存在条件数变大的毛病。相比之下， 的 分解可以保持原问题的条件数不变。不妨令 (3.1.6)式中， 是 正交矩阵， 是 上三角矩阵，而 为 维零矩阵。由于正交变换可以保持被变换向量的 长度或范数不变，所以式的最小二乘问题可等价写作 (3.1.7)或 (3.1.8)式中 (3.1.9)且 为 向量， 为 向量，它们可以从 直接分块得到。 一旦获得了 ，即可由 得到 。解此方程需要 次计算，并且最小残差值等于 。 假定增加了两个已知数值 和 ，我们来讨论如何更新系统参数的估计，即使用已估计的参数向量 和简单的运算，得到 时刻的新估计 。为了减少过去数据数据对参数估计的影响，对数据 和 采取指数加权，即 时刻的数据矩阵和观测数据向量分别取作 (3.1.10)式中， 称为遗忘因子，且 。于是，可以写出式在 时刻的形式为 (3.1.11)乍一看，上式似乎没有什么特别吸引人之处，其实不然。这是因为，如同下面的引理所述，式的极小化变量等价为下述式的极小化变量，而后者非常适合于递推更新。引理3.1.2r若 ， ，其中， 是正交矩阵， 是上三角矩阵，则式的极小化变量等同于下式的极小化变量： (3.1.12)证明见。如果将式的极小化变量记作 ，则以上讨论可总结为 的自适应递推估计算法如下。算法1（系统参数的自适应估计算法）步骤1 对矩阵 进行 分解，得 (3.1.13)式中， 是 正交矩阵， 为 上三角矩阵，且 是 零矩阵。步骤二 进行分块运算 (3.1.14)其中， 为 向量， 为 向量。步骤三 切结三角矩阵方程 得到 。3.2基于 变换的快速时变参数估计考察 矩阵 的 分解，即 (3.2.1)显然，只需要进行 次 变换即可。换言之，为了得到上述 分解，应该选择 为 个 变换矩阵之积，即 (3.2.2)式中 (3.2.3)是对矩阵 第 列向量 进行的 变换矩阵，其参数选择方法为 (3.2.4)其中 (3.2.5)并且 (3.2.6)递推的 分解算法如下：基于 分解的自适应参数估计算法一般由两个分开的过程组成：（1）递推更新 分解 中的上三角矩阵 ；（2）用回代法求解三角矩阵方程。由于直接的回代需要 次运算（ 为数据长度）。因此，即便 变换再快速，整个自适应算法也至少需要 次运算。文献将上述快速 分解算法和求解三角矩阵方程的回代法综合起来考虑，提出了只具有 复杂度的快速自适应算法。3.3基于 旋转的时变参数估计现在考虑另外一种递推方法，递推求解 的变化量 ，而不是直接递推求 本身。换句话说，令 (3.3.1)问题是如何更新 。假定正交矩阵 为已知，它满足 (3.3.2)由式，式和式易知， 是下式的极小化变量： (3.3.3)此式又可化简为 (3.3.4)式中， 。因此， 可以从三角矩阵方程 (3.3.5)解出，其中， 满足 (3.3.6)为了求出满足式的 ，可以使用 平面旋转进行清零，将式中的行向量 的全部元素变成零。由于 必须左乘式，所以对增广的矩阵 (3.3.7)执行所需要的清零。综合以上分析，在每一步递推更新中需要的步骤如下5：（1）计算预测误差 ；（2）形成式中的 矩阵；（3）利用一系列 旋转将上述矩阵最底一行的左边 个元素扫除为零；（4）解上三角矩阵方程得到 。利用 旋转求解方程 的递推最小二乘算法的程序见文献。该算法中，同时对矩阵 和向量 应用旋转，因此无需存储正交矩阵 。4 QR分解在通信系统中的应用4.1 基于QR分解的稳健干扰对齐算法 考虑K用户MIMO干扰信道，每个发送端的天线数为 ，每个接收端的天线数为 ，每个用户对应的自由度为 ，此处的自由度代表每个用户能使用的独立数据流个数。为了让系统自由度达到最大值，即 ，那么每个发送端所提供的信号空间的维数应该相等，故此处不妨设 ，并假设在同一时刻同一频率上的各个发送接收对之间的信道是平坦衰落的，且信道系数独立同分布。在一个特定的时频资源上，接收端 的接收信号可以表示为 (4.1.1)其中维数为 的 和 分别是发送端 和 到接收端 的信道矩阵。 和 分别是发送端 和 对应接收端 和 的预编码矩阵，且满足 ， 。维数为 的 是接收端 的下行数据矢量信号，且满足功率约束 。维数为 的 是均值为0，方差为1的加性高斯白噪声噪声，且 。 干扰对齐往往要求完美的 ，但在实际通信系统中，发送端得到 常常是有误差的。为了构建稳健的干扰对齐算法，此处引入信道误差变量 ， 表示真实的信道矩阵， 表示具有误差的信道矩阵，并且假设的元素服从均值为0，方差为 的循环对称复高斯分布（GSCG），即满足 。故式变为 (4.1.2)此时整个系统的联合接收信号可以表示为 (4.1.3)对得到的误差联合信道矩阵 进行QR分解有 (4.1.4)其中，Q是维数为 的酉矩阵，R是维数为 的上三角矩阵。因为Q是酉矩阵，根据矩阵理论可知R和 有相同的统计特性，所以定义R为系统的误差等效联合信道矩阵。 根据式，式可以改写为 (4.1.5)这是考虑联合接收，对式的联合信号接收信号进行左乘 的预处理，得到如下的联合接收信号： (4.1.6) 因为 是酉矩阵，于是 和 有相同的统计特性，同理 和 有相同的统计特性。通过式，在接收端 经过干扰抑制矩阵 处理后，接收端 的接收信号为 (4.1.7) 通过稳健干扰对齐算法得到最优干扰对齐矩阵 和 ，具体算法流程总结为8：（1） 初始化 ，这里可以随机选择均值为0，方差为1的矩阵 。（2） 计算出，并且单位化 （3） 计算出，并且单位化 （4） 重复步骤（2）和（3），直到收敛。4.2基于 分解的 置信传播检测器在一个 个发射天线和 个接收天线的 系统中， 是 传输信号向量。系统的输入输出关系可以写为 (4.2.1)其中， 是 接收信号向量， 是 噪声向量， 的元素是零均值、方差 的独立同分布（i.i.d）复高斯随机变量。 是 的 信道矩阵， 。由 分解， 信道矩阵 可以写为 ,其中 是 酉矩阵， 是 非零矩阵， 是 上三角矩阵 (4.2.2)由于 , 是非零矩阵， 。式可以写为 (4.2.3)这样， 相比于由 得出的全连接的偶图就是一个包含更少的边数和环数的的偶图。如下图所示。图中， , 。在第一次迭代前，全部 初始化为0，其中 且 。在第 次迭代时，每一个 可以由最大对数近似得到 (4.2.4)其中， 和 是 中的第 比特和第 比特对应的 中的第 比特和第 比特， 表示第 次迭代时第 节点发出、第 节点检测的消息。计算出 后，有 (4.2.5)其中 且 。第 次迭代后 的软输出 是 (4.2.6)其中， 。这样，给出的 检测器就由上三角信道矩阵 得出的偶图来进行操作。上述 的计算复杂度主要由式中的线性变换和式中 的计算决定。线性变换的复杂度开销主要来自于 分解，它的复杂度是 3。另外， 的计算的大部分复杂度开销来自 的计算。文献1给出了 次迭代后该算法的计算复杂度是 .所以给出的 检测器的计算复杂度小于文献1中标准 检测器的复杂度 。总结 通过此次文献调研，我们获益匪浅。首先，我们了解了矩阵分解和矩阵变换，学习了QR分解、Householder变换、Givens旋转。其次，我们通过文献调研，了解了QR分解算法在实际中的应用，如参数估计，实际的MIMO系统等。最后，我们也从中学到了团队分工和协作的重要性。 参考文献1 Hu, J., and Duman, T.M.: Graph-based detection algorithms for layered space-time architectures, IEEE J. Sel. Areas Commun., 2008, 26, (2),pp. 2692802 Sangjoon P. and Sooyong C., QR decomposition aided belief propagation detector for MIMO systems, IET Journals & Magazines Electronics Letters,2015,51,(11),pp.873-8743 Kim, T.: Low-complexity sorted QR decomposition for MIMO systems based on pairwise column symmetrization, IEEE Trans. Wirel. Commun., 2014, 13, (3), pp. 138813964 Bobrow J.E., Murray W., An algorithm for RLS identification of parameters that vary quickly with time,IEEE Trans Automatic Control,993,38:351-3545 Jianwen Gao,Quasi-Orthogonal Space-time Block Code with Givens Rotation for OFDM System,IEEE Letters,2013,pp.64706 Jian Wu and Shu fang ,QR decomposition and gram Schmidt orthogonalization based low-complexity multi-user MIMO precoding,IEEE conference,2014，pp.129613047 Syed A.Raza,Direct and parallel QR based subspace decomposition methods for system identification,IEEE conference 2014，pp.4714808 谢显中，一种基于QR分解的稳健干扰对齐算法，2015（08）195719649 陈慧，基于稀疏矩阵表示的MIMO雷达多目标定位2015（06）26026710 张贤达，矩阵分析与应用