完整版QR分解及其应用.docx
《完整版QR分解及其应用.docx》由会员分享，可在线阅读，更多相关《完整版QR分解及其应用.docx（24页珍藏版）》请在冰点文库上搜索。
完整版QR分解及其应用
《矩阵分析与应用》专题报告
――QR分解及应用
学生姓名：
卢楠、胡河群、朱浩
2015年11月25日
1引言3
2QR分解4
2.1QR分解的性质4
2.2QR分解算法5
2.2.1采用修正Gram-Schmidt法的QR分解5
2.2.2HouseholderQR分解6
2.2.3采用Givens旋转的QR分解8
3QR分解在参数估计中的应用9
3．1基于QR分解的参数估计问题9
3.2基于Householder变换的快速时变参数估计12
3.3基于Givens旋转的时变参数估计14
4QR分解在通信系统中的应用16
4.1基于QR分解的稳健干扰对齐算法16
4.2基于QR分解的MIMO置信传播检测器19
总结21
参考文献22
1引言
矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质的若干矩阵之积或之和，大体上可以分为满秩分解、QR分解和奇异值分解。
矩阵分解在矩阵分析中占有很重要的地位，常用来解决各种复杂的问题。
而QR分解是工程中应用最
为广泛的一类矩阵分解。
QF分解是目前求一般矩阵全部特征值的最有效并广泛应用的方法，一般矩阵先经过正交相似变换成为Hessenberg矩阵，然后再应用QF分解求特征值和特征向量。
它是将矩阵分解成一个正交矩阵Q与上三角矩阵R,所以称为QR分解。
参数估计是在已知系统模型结构时，用系统的输入与输出数据计算系统模型参数的过程。
它在系统辨识和无线通信领域有着广泛的应用。
18世纪末德国数学家C.F.高斯首先提出参数估计的方法，他用最小二乘法计算天体运行的轨道。
20世纪60年代，随着电子计算机的普及，参数估计有了迅猛的发展。
参数估计有很多方法，如矩估计、极大似然法、一致最小方差无偏估计、最小风险估计、同变估计、最小二乘法、贝叶斯估计、极小极大熵法等。
其中最基本的是最小二乘法和极大似然法。
本文将重点介绍QR分解及其在参数估计和通信系统中的应用
2QR分解
2.1QR分解的性质
定理2.1.1（QR分解）若aRmn，且mn,则存在列正交矩阵QRmn和
上三角矩阵RRmn使得A=QR。
当mn时，Q是正交矩阵。
如果A是非奇异的nn矩阵，则R的所有对角线元素均为正，并且在这种情况下Q和R二者是唯一的。
若A是复矩阵，则Q和R取复值。
注意到AtA=（QR）t（QR）=RtR,因此可以得出结论：
G=Rt是AtA的
下三角Cholelskey因子。
由于这个原因，在关于估计的文献中，矩阵R常称为平方根滤波器（算子）。
下面的引理称为矩阵分解引理，它在矩阵的QR分解的应用中是一个很有结果。
引理2.2.1若A和B是任意两个mn矩阵，贝U
AHA=BHB（2.1.1）
当且仅当存在一个mm酉矩阵Q，使得
QA=B（2.1.2）
证明充分性证明：
若QA=B，并且Q是酉矩阵，则BHB=AHQHQA=AHA。
必要性证明：
令A和B的奇异值分解分别为
A=UAAVAH
B=UBBVBH
式中，UA
和UB均为mm酉矩阵；Va和Vb都是nn酉矩阵；而mn矩
阵a和b分别包含了矩阵A和B的非负奇异值。
由于
HHH
AA=VAAAVA
Q=UbUa
HhHh
易知QA=UbUaA=UbUaUaaVa=UbbVb=B
这就证明了引理的必要条件［10］。
2.2QR分解算法
2.2.1采用修正Gram-Schmidt法的QR分解矩阵A的QR分解可以利用Gram-Schmidt正交化方法实现。
Gram-Schmidt正交
1的向量
R1
q1
化方法原本是一种由n个向量a1,a2,...,an构造互相正交且范数为
则有
该结果作q3，即有
如此继续，则对于qk（2kn）有
RjkqjHak,1jk1
容易验证，qi是标准正交基，即满足
H
qiqju（225）
其中，ij为Kronecker函数。
如果令mn矩阵A的列向量ai，a2,...，an,则以qi,q2,...,qn为列向量的矩阵Q与A之间有下列关系：
A=QR（2.2.6）
又由于qi组成标准正交基，所以
QHQ=In
将A与Q重写在同一矩阵，应用以上Gram-Schmidt正交化的方法叫做经典
Gram-Schmidt正交化法⑹。
2.2.2HouseholderQR分解
Householder变换可以实现任意mn矩阵A的QR分解，其原理是使用变维向量的Householder变换，使得该向量除第一个元素外，其他元素皆为0。
根据Householder变换的相关知识，欲使一个p维向量xx1,x2,...,x^的
第1个元素后面的所有元素变为0，则p维的Householder向量应取
xe1
X1）
（2.2.7）
X1
X1
式中
（2.2.8）
假定mn矩阵A的列分块形式为
可以计算得到U1
Wm。
此时，
H
1Iu1u1T
A1H1Aa1
（1）,a2
（1）
a
（1）n
（2.2.9）
变换后，矩阵A1
的第1列a1⑴
的第一个元素等于a121
22
a21...am1
12
，而该
列的其他元素全部为0。
第二步针对矩阵
A1的第2列
aj，令Pm1和
xa2；）,a3；）,...
a
（1）T
am2
又可按照式（227）
和式（2.2.8）
求出（m-1）维向量Wm1
。
此时，取U2
0
Wm1
又可得到
h2I
T典
u?
u2A2
H2A1H2H1Aa1
（1）,
⑵
（2）
a2,...,an
（2.2.10）
首先令xai
ai1,a21,・・.,am1
T
，并取Pm，则按照式（227）和式（228）,
变换后，矩阵A2的第1列与Ai的第1列相同，而第2列ai⑴的第一个元素等
0。
akkk
0
M
0
（k1）ak,k
（k1）
H%%1,k
kM
a（k1）
m,k
这相当于对矩阵A（k1）进行Householder变换HkA（k1）时取
Ik10
0H%k
n次Householder变换后，即可实现QR分解。
223采用Givens旋转的QR分解
（3,4）
（2,3）
（1,2）0
（3,4）
0
0
0
0
0
0
（2,3）0
（3,4）0
0
0
0
0
0
0
00
0
0
00
其中，
表示用Givens
旋转进行变化你的元
素。
从上述说明中易得出结论：
如果令Gj代表约化过程中的第j次Givens旋转，
则QtA=R是上三角矩阵，其中Q=GtGt「LGi，而t是总的旋转次数。
3QR分解在参数估计中的应用
3.1基于QR分解的参数估计问题
现在以系统辨识为例，说明如何利用矩阵的QR分解进行系统参数的递推估计
单的运算，递推出n1时刻的系统参数向量n10n时刻的系统辨识问题可以简化为最小二乘问题
m6nAn6仆:
（3.1.4）
求解，并且其解由“法方程”
AnTAn6AnTyn或Rxx6n心（3.1.5）
确定。
式中，RxxAnTAn代表系统输入Xk的协方差矩阵，rn人.丁丫・
直接求解式（3.1.5）的方法叫做协方差方法。
例如，先计算协方差矩阵Rxx
的Cholesky分解RxxGG『,然后利用回带法解三角矩阵G也GRn直接得到6n。
然而，由于RxxAnTAn的条件数是An的条件数的平方，因此，直
接计算式（3.1.5）的得到的解有可能是严重病态的（即条件数很大），即使An本身的条件数并不大，不是严重病态的。
在系统参数向量9的自适应递推辨识中，标准的递推最小二乘RLS法和
分解（其中,
UtDU分解法都是针对协方差矩阵Rxx进行更新的。
虽然utdu
但是这些递推辨识方
U为上三角矩阵，D为对角矩阵）在数值上比较稳定,法也同样存在条件数变大的毛病。
p1维零矩阵。
的最小二乘冋题可等价与作
（3.1.8）
QnTyn
minRn9y
式中
（3.1.9）
得到。
计算，并且最小残差值等于|%|
指数加权，即n1时刻的数据矩阵和观测数据向量分别取作
可以写出式（3.1.4）在n1时刻的形式为
合于递推更新。
（3.1.12）
证明见［］。
递推估计算法如下。
算法1（系统参数的自适应估计算法）
零矩阵。
步骤二进行分块运算
3.2基于Householder变换的快速时变参数估计
考察np1矩阵
a11
a12
L
a1,p1
A
a21
a22
L
a2,p1
An
M
M
M
an,1
an,2
L
an,p1
的HouseholderQR分解，即
*
*
*
an
a12
L
a1,p1
0
*
a22
L
*
a2,p1
M
M
M
HnAn
0
0
L
*
ap1,p1
（3.2.1）
0
0
L
0
M
M
M
0
0
L
0
显然，只需要进行P次Householder变换即可。
换言之，为了得到上述QR分
解，应该选择Hn为p个Householder变换矩阵之积，即
式中
HnjIUjU；/j,j1,2,L,p（3.2.3）
:
...T
是对矩阵AnjHnj1Hn2Hn1An第j列向量印j禺,L曲进行的
Householder变换矩阵，其参数选择方法为
2
j
a
ij
j
0,ij
（3.2.6）
递推的HouseholderQR分解算法如下:
（1）递推更新
基于QR分解的自适应参数估计算法一般由两个分开的过程组成:
QR分解QtAR中的上三角矩阵R；
（2）用回代法求解三角矩阵方程。
由于直接的回代需要Om2次运算（m为数据长度）。
因此，即便Householder变换再快速，整个自适应算法也至少需要Om2次运算。
文献［］将上述快速
HouseholderQR分解算法和求解三角矩阵方程的回代法综合起来考虑，提出了
只具有0m复杂度的快速自适应算法
3.3基于Givens旋转的时变参数估计
现在考虑另外一种递推方法，递推求解
0n的变化量,而不是直接递推求
0n
也1本身。
换句话说，令
（3.3.1）
冋题是如何更新4。
此式又可化简为
（3.3.6）
Yn1
rn1
Rn
T
Xn1
[5]
对增广的矩阵
（3.3.7）
执行所需要的清零。
综合以上分析，在每一步递推更新中需要的步骤如下
1）计算预测误差yk1
（2）形成式（3.3.7）中的n1n1矩阵；
（3）利用一系列Givens旋转将上述矩阵最底一行的左边n个元素扫除为零；（4）解上三角矩阵方程（3.3.5）得到k。
利用Givens旋转求解方程A0y的递推最小二乘算法的程序见文献［］。
该算
法中，同时对矩阵A和向量y应用Givens旋转，因此无需存储正交矩阵q。
4QR分解在通信系统中的应用
4.1基于QF分解的稳健干扰对齐算法
考虑K用户MIMO干扰信道，每个发送端的天线数为Nt，每个接收端的天线数为M,每个用户对应的自由度为d「d2,L,dk，此处的自由度代表每个用户能使用的独立数据流个数。
为了让系统自由度达到最大值，即Kmin（Nr,Nt）：
2，那么每个发送端所提供的信号空间的维数应该相等，故此处不妨设did2LdKd，并假设在同一时刻同一频率上的各个发送接收对之间的信道是平坦衰落的，且信道系数独立同分布。
在一个特定的时频资源上，接收端i的接收信号可以表示为
K
yiHiiWsiHjiWjSjni（4.1.1）
j1,ji
其中维数为NrNt的Hii和Hji分别是发送端i和j到接收端i的信道矩阵。
WiHWiId，WjHWjIdj。
维数为di1的S是接收端i的下行数据矢量信号，且满足功率约束EsHSP（i）。
维数为Nr1的ni是均值为0，方差为1的加性高斯白噪声噪声，且En^i1比。
干扰对齐往往要求完美的CSI，但在实际通信系统中，发送端得到CSI常常是有误差的。
为了构建稳健的干扰对齐算法，此处引入信道误差变量EjiHjiHji，Hji表示真实的信道矩阵，Hji表示具有误差的信道矩阵，并
且假设Er的元素服从均值为0,方差为2的循环对称复高斯分布（GSC）即
H2
满足EEjiEjielNr。
故式（4.1.1）变为
_K
yi（HiiEii）WSii（HjiEji）WjSjni（4.1.2）
此时整个系统的联合接收信号可以表示为
y1
H11
H21
L
Hk1
W1S1
Y
y
H12
H22
L
Hk2
^V?
S2
I
M
M
M
O
M
M
yk
H1k
H2k
L
Hkk
WkSk
（4.1.3）
E
11
E21
L
Ek1
W1s1
E
12
E22
L
Ek2
W2s2
r
>2
M
M
O
M
M
M
E
1k
E2k
L
Ekk
WKSK
n
K
对得到的误差联合信道矩阵
H
进行QR分解有
Hii
H21
L
Hk1
R11
R21
L
Rk1
-Hi2
H22
L
Hk2
R22
L
Rk2
H12
Q
QR
（4.1.4）
M
M
O
M
O
M
H1k
H2k
L
Hkk
Rkk
其中，Q是维数为KNr
KNr
的酉矩阵，
R是维数为
KNr
KNt
的上三角矩阵。
因为Q是酉矩阵，根据矩阵理论可知R和H有相同的统计特性，所以定义R为系统的误差等效联合信道矩阵。
这是考虑联合接收，对式（4.1.5）的联合信号接收信号进行左乘Q1的预处理,得到如下的联合接收信号：
R11
R21
L
Rk1
W1s1
E11
E21
L
Ek1
W1s1
Y
R22
L
Rk2
W2s2
Q1E12
E22
L
Ek2
W2s2
1
O
M
M
M
M
O
M
M
Rkk
WKsK
E1k
E2k
L
Ekk
WKsK
⑴
R
11R
21L
Rk1WS[
1
rh
R
22L
Rk2W2s2
Q
（4.1.6）
M
O
MM
nK
RkkWKsK
E11
E21
L
Ek1
W1s1n1
E12
E22
L
Ek2
W2s2n2
M
M
O
M
MM
E1k
E2k
L
Ekk
WkSknK
因为Q1
是酉矩阵,
于是
Ej和Ej有相同的统计特性，同理nj和nj有相
同的统计特性。
通过式（4.1.6），在接收端i经过干扰抑制矩阵Ui处理后，接
收端i的接收信号为
W1s1
WKSK
（4.1.7）
WKSK
通过稳健干扰对齐算法得到最优干扰对齐矩阵uOpt和W°pt，具体算法流程总
结为⑹：
（1）初始化Wi，这里可以随机选择均值为0，方差为1的矩阵
Wi,i1,2,L,K,WiHWiIdio
（2）计算出Ui,i1,2,L,K，并且单位化Ui
（3）计算出Wi,i1,2,L,K，并且单位化Wi
（4）重复步骤
（2）和（3），直到收敛。
4.2基于QR分解的MIMO置信传播检测器
在一个N个发射天线和M个接收天线的MIMO系统中，s和K,snT是N1传输信号向量。
系统的输入输出关系可以写为
yHsn（4.2.1）
其中，y%,K,ym丁是M1接收信号向量，n是M1噪声向量，n的元
素是零均值、方差2的独立同分布（i.i.d）复高斯随机变量。
H是MN的
MIMO信道矩阵，rankHN。
T
由QR分解，MIMO信道矩阵H可以写为HQRtrT,其中Q是MM
酉矩阵，R。
是M
NN非零矩阵，
R
是N
N
上三角矩阵
AG
斤,2
L
r1,N
r20
R
MM
r2,2
O
L
O
r2,N
M
（4.2.2）
50
L
0
rN,N
由于QQIMM,
R。
是非零矩阵，
IN
Rt
N0
QHn
R。
式（4.2.1）
可以写
为
%INNR0
QHy
Rs
%
（4.2.3）
这样，R相比于由H得出的全连接的偶图就是一个包含更少的边数和环数的的偶图。
如下图所示。
图中，NM4,Q1。
在第一次迭代前，全部0m初始化为0,其中1nNQ且1mgn。
在第
l次迭代时，每一个鳥可以由最大对数近似得到
NQ
（424）
测的消息。
gn
（4.2.6）
l
kn
k1
其中,
1nNQ。
这样，给出的QRBP检测器就由上三角信道矩阵R得
l
mn
出的偶图来进行操作。
上述QRBP的计算复杂度主要由式（4.2.3）中的线性变换和式（4.2.4）中
的计算决定。
线性变换的复杂度开销主要来自于QR分解，，它的复杂度是
OMN2［3］。
另外，mn的计算的大部分复杂度开销来自%ma的计算。
M
文献［1］给出了次迭代后该算法的计算复杂度是OMN2m2mQ.所以
m1
给出的QRBP检测器的计算复杂度小于文献［1］中标准BP检测器的复杂度
OMN2nq。
总结
通过此次文献调研，我们获益匪浅。
首先，我们了解了矩阵分解和矩阵变换，学习了QR分解、Householder变换、Givens旋转。
其次，我们通过文献调研，了解了QR分解算法在实际中的应用，如参数估计，实际的MIMOS统等。
最后,
我们也从中学到了团队分工和协作的重要性。
参考文献
[1]Hu,J.,andDuman,T.M.:
‘Grap-baseddetectionalgorithmsforlayered
spacetimearchitecturesIEEEJ.Sei.AreasCommun.,2008,26,
（2）,pp.269-80
[2]SangjoonP.andSooyongC.,"QRdecompositionaidedbeliefpropagationdetectorforMIMOsystems",IETJournals&MagazinesElectronicsLetters,2015,51,（11）,pp.873-874
[3]Kim,T.:
‘LownplexitysortedQRdecompositionforMIMOsystemsbasedon
pairwisecolumnsymmetrization',IEEETrans.Wirel.Cc213rhun13,（3）,pp.1388-396
[4]BobrowJ.E.,MurrayW.,AnalgorithmforRLSidentificationofparametersthatvaryquicklywithtime,IEEETransAutomaticControl,993,38:
351-354
[5]JianwenGao,Quasi-OrthogonalSpace-timeBlockCodewithGivensRotationforOFDMSystem,IEEELetters,2013,pp.64—70
[6]JianWuandShufang,QRdecompositionandgramSchmidtorthogonalizationbasedlow-complexitymulti-userMIMOprecoding,IEEEconference,2014,pp.1296—1304
[7]SyedA.Raza,DirectandparallelQRbasedsubspacedecompositionmethodsforsystemidentification,IEEEconference2014pp.471—480
[8]谢显中，一种基于QR分解的稳健干扰对齐算法，2015（08）1957—1964
[9]陈慧，基于稀疏矩阵表示的MIMO雷达多目标定位2015（06）260—267
[10]张贤达，矩阵分析与应用
升级会员 