TSQR 是針對高瘦(tall and skinny)矩陣QR的分解。這類矩陣有着行(Row)遠大於列(Column)的特點, 高瘦(TS)矩陣往往常見於評價系統,評價的項目少於評價的人數等。
TSQR分解和普通的QR分解的區別在於,TSQR的分解可以進行並行加速。
TSQR分解主要依賴於QR分解 ,有以下三種方法的詳細介紹和例子說明,以下將詳細比較三種方法的優劣勢作用於TS矩陣。
針對Householder變換 ,其優勢在於計算的時間複雜度較低,一次變換可以將一整個列除了首個元素都化成0,但是對數據的依賴度較高,不容易進行並行化計算,但是該方法對於稠密矩陣,相比於以下兩種方法,計算效率會更高。
豪斯霍爾德變換示意圖:向量x 在豪斯霍爾德向量v的超平面
v
⊥
{\displaystyle \mathbf {v} ^{\perp }}
上的鏡像是Hx ,H 是豪斯霍爾德矩陣。
針對吉文斯旋轉,其優勢在於對於數據的依賴性較低,可以很好的並行化,對於稀疏矩陣 有很大的優勢。缺點在於其時間複雜度較高,一次只能對兩行做吉文斯旋轉。
格拉姆-施密特正交化 方法對於並行化計算並不友好,它的優勢在於算法理解其他直觀,時間複雜度介於Householder變換和吉文斯旋轉之間。
利用矩陣分塊的思想,對於TS矩陣進行切割,從而對若干個子塊矩陣進行分而治之。
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)在並行階段,其特殊的上三角形式也可以用並行的方式進行加速。
[ 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.