TSQR 是针对高瘦(tall and skinny)矩阵QR的分解。这类矩阵有着行(Row)远大于列(Column)的特点, 高瘦(TS)矩阵往往常见于评价系统,评价的项目少于评价的人数等。
TSQR分解和普通的QR分解的区别在于,TSQR的分解可以进行并行加速。
TS矩阵
TS矩阵的特点是行(Row)
≫
{\displaystyle \gg }
列(Column)。 如下图
A
{\displaystyle A}
就是一个典型的TS矩阵。
A
m
×
n
=
[
a
11
⋯
a
1
i
⋯
a
i
n
⋮
⋱
⋮
⋮
a
i
1
⋯
a
i
i
⋯
a
i
n
⋮
⋮
⋱
⋮
a
j
1
⋯
a
j
i
⋯
a
j
n
⋮
⋮
⋮
a
m
1
⋯
a
m
i
⋯
a
m
n
]
{\displaystyle A_{m\times n}={\begin{bmatrix}a_{11}&\cdots &a_{1i}&\cdots &a_{in}\\\vdots &\ddots &\vdots &&\vdots \\a_{i1}&\cdots &a_{ii}&\cdots &a_{in}\\\vdots &&\vdots &\ddots &\vdots \\a_{j1}&\cdots &a_{ji}&\cdots &a_{jn}\\\vdots &&\vdots &&\vdots \\a_{m1}&\cdots &a_{mi}&\cdots &a_{mn}\end{bmatrix}}}
这里
m
≫
n
{\displaystyle m\gg n}
。
TSQR分解的方法优劣比较
TSQR分解主要依赖于QR分解 ,有以下三种方法的详细介绍和例子说明,以下将详细比较三种方法的优劣势作用于TS矩阵。
Householder变换
针对Householder变换 ,其优势在于计算的时间复杂度较低,一次变换可以将一整个列除了首个元素都化成0,但是对数据的依赖度较高,不容易进行并行化计算,但是该方法对于稠密矩阵,相比于以下两种方法,计算效率会更高。
豪斯霍尔德变换示意图:向量x 在豪斯霍尔德向量v的超平面
v
⊥
{\displaystyle \mathbf {v} ^{\perp }}
上的镜像是Hx ,H 是豪斯霍尔德矩阵。
吉文斯旋转
针对吉文斯旋转,其优势在于对于数据的依赖性较低,可以很好的并行化,对于稀疏矩阵 有很大的优势。缺点在于其时间复杂度较高,一次只能对两行做吉文斯旋转。
格拉姆-施密特正交化方法
格拉姆-施密特正交化 方法对于并行化计算并不友好,它的优势在于算法理解其他直观,时间复杂度介于Householder变换和吉文斯旋转之间。
并行TSQR分解
基本思想
利用矩阵分块的思想,对于TS矩阵进行切割,从而对若干个子块矩阵进行分而治之。
TSQR分解算法
A
m
×
n
=
[
a
1
,
1
⋯
a
1
,
n
⋮
⋮
a
i
,
1
⋯
a
i
,
n
a
i
+
1
,
1
⋯
a
i
+
1
,
n
⋮
⋮
a
m
,
n
⋯
a
m
,
n
]
{\displaystyle A_{m\times n}={\begin{bmatrix}a_{1,1}&\cdots &a_{1,n}\\\vdots &&\vdots &\\a_{i,1}&\cdots &a_{i,n}\\a_{i+1,1}&\cdots &a_{i+1,n}\\\vdots &&\vdots &\\a_{m,n}&\cdots &a_{m,n}\end{bmatrix}}}
我们将
A
m
×
n
{\displaystyle A_{m\times n}}
拆成若干个子矩阵(这里拆成2个)
A
1
m
1
×
n
1
{\displaystyle A_{1}{m_{1}\times n_{1}}}
和
A
2
{\displaystyle A_{2}}
,
A
1
,
A
2
{\displaystyle A_{1},A_{2}}
的维度分别是
m
1
×
n
1
,
m
2
×
n
2
{\displaystyle m_{1}\times n_{1},m_{2}\times n_{2}}
, 注意拆开的子矩阵要保证行数仍然大于列数,即
m
1
>
n
1
,
m
2
>
n
2
{\displaystyle m_{1}>n_{1},m_{2}>n_{2}}
。
我们分别对
A
1
{\displaystyle A_{1}}
和
A
2
{\displaystyle A_{2}}
做QR分解。
A
1
=
Q
1
R
1
{\displaystyle A_{1}=Q_{1}R_{1}}
A
2
=
Q
2
R
2
{\displaystyle A_{2}=Q_{2}R_{2}}
此时的QR分解是完全可以并行的。
我们再将
R
1
,
R
2
{\displaystyle R_{1},R_{2}}
合并并惊醒QR分解
R
^
=
[
R
1
R
2
]
=
Q
11
[
R
11
0
]
{\displaystyle {\hat {R}}={\begin{bmatrix}R_{1}\\R_{2}\end{bmatrix}}=Q_{11}{\begin{bmatrix}R_{11}\\0\end{bmatrix}}}
此时的
R
11
{\displaystyle R_{11}}
便是我们所需要的最后分解所得的
R
{\displaystyle R}
。
例子
我们现在需要分解如下矩阵
A
=
[
0
3
1
0
4
−
2
2
1
1
1
2
4
0
0
5
0
3
6
]
{\displaystyle A={\begin{bmatrix}0&3&1\\0&4&-2\\2&1&1\\1&2&4\\0&0&5\\0&3&6\\\end{bmatrix}}}
现在将其分解成两个矩阵
A
1
,
A
2
{\displaystyle A_{1},A_{2}}
,并对其做相应的QR分解。
A
1
=
Q
1
R
1
=
[
0
3
−
4
0
4
3
5
0
0
]
[
2
1
2
0
5
−
1
0
0
−
2
]
{\displaystyle A_{1}=Q_{1}R_{1}={\begin{bmatrix}0&3&-4\\0&4&3\\5&0&0\\\end{bmatrix}}{\begin{bmatrix}2&1&2\\0&5&-1\\0&0&-2\\\end{bmatrix}}}
A
2
=
Q
2
R
2
=
[
1
0
0
0
0
1
0
1
0
]
[
1
2
4
0
3
6
0
0
5
]
{\displaystyle A_{2}=Q_{2}R_{2}={\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\\\end{bmatrix}}{\begin{bmatrix}1&2&4\\0&3&6\\0&0&5\\\end{bmatrix}}}
那么
R
^
=
[
R
1
R
2
]
=
[
2
1
2
0
5
−
1
0
0
−
2
1
2
4
0
3
6
0
0
5
]
{\displaystyle {\hat {R}}={\begin{bmatrix}R_{1}\\R_{2}\end{bmatrix}}={\begin{bmatrix}2&1&2\\0&5&-1\\0&0&-2\\1&2&4\\0&3&6\\0&0&5\\\end{bmatrix}}}
我们对
R
^
{\displaystyle {\hat {R}}}
进行QR分解,
R
^
=
Q
11
R
11
=
Q
11
{\displaystyle {\hat {R}}=Q_{11}R_{11}=Q_{11}}
R
=
Q
11
=
[
−
2.2360
−
1
,
7888
−
3.5777
0
−
5.9833
−
2.7743
0
0
8.0933
]
{\displaystyle R=Q_{11}={\begin{bmatrix}-2.2360&-1,7888&-3.5777\\0&-5.9833&-2.7743\\0&0&8.0933\\\end{bmatrix}}}
优势
上述的TSQR和普通的QR分解的优势在于:
1)不同于QR分解,此类的QR分解是可以高度并行化的;
2)在并行阶段,其特殊的上三角形式也可以用并行的方式进行加速。
用途
快速求解奇异值分解(SVD)
对于一个TS矩阵
A
m
×
n
{\displaystyle A_{m\times n}}
求解其SVD,我们可以先对矩阵
A
{\displaystyle A}
做TSQR分解。那么
A
=
Q
R
{\displaystyle A=QR}
我们在对
R
{\displaystyle R}
做SVD分解 ,相比于直接做SVD,这样做的好处在于
R
{\displaystyle R}
的维度是
n
×
n
{\displaystyle n\times n}
, 所以速度会快很多。
R
=
U
~
Σ
V
{\displaystyle R={\tilde {U}}\Sigma V}
所以最后只需要
U
{\displaystyle U}
计算
U
=
Q
U
~
{\displaystyle U=Q{\tilde {U}}}
就可以得到所有的特征量向量
外部連結
[ 1]
[ 2]
[ 3]
[ 4]
^ M. Anderson; G. Ballard, J. Demmel and K. Keutzer. Communication-Avoiding QR Decomposition for GPUs. 2011 IEEE International Parallel & Distributed Processing Symposium: 48–58. 2011. doi:10.1109/IPDPS.2011.15 .
^ MIT. QR Decomposition . [2020-07-01 ] . (原始内容存档 于2020-07-27).
^ N.-Y. Cheng and M.-S. Chen. Exploring Dual-Triangular Structure for Efficient R-initiated Tall-skinny QR on GPGPU. Pacific-Asia Conf. on Knowledge Discovery and Data Mining. April 14-17, 2019.
^ A. Rafique, N. Kapre and G. A. Constantinides. Enhancing performance of Tall-Skinny QR factorization using FPGAs. International Conference on Field Programmable Logic and Applications: 443–450.