TSQR

TSQR是針對高瘦(tall and skinny)矩陣QR的分解。這類矩陣有着行(Row)遠大於列(Column)的特點， 高瘦(TS)矩陣往往常見於評價系統，評價的項目少於評價的人數等。

TSQR分解和普通的QR分解的區別在於，TSQR的分解可以進行並行加速。

TS矩陣

TS矩陣的特點是行(Row) $\gg$ 列(Column)。 如下圖$A$就是一個典型的TS矩陣。

$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\gg n$。

TSQR分解的方法優劣比較

TSQR分解主要依賴於QR分解，有以下三種方法的詳細介紹和例子說明，以下將詳細比較三種方法的優劣勢作用於TS矩陣。

Householder變換

針對Householder變換，其優勢在於計算的時間複雜度較低，一次變換可以將一整個列除了首個元素都化成0，但是對數據的依賴度較高，不容易進行並行化計算，但是該方法對於稠密矩陣，相比於以下兩種方法，計算效率會更高。

豪斯霍爾德變換示意圖：向量x在豪斯霍爾德向量v的超平面$\mathbf {v} ^{\perp }$上的鏡像是Hx，H是豪斯霍爾德矩陣。

吉文斯旋轉

針對吉文斯旋轉，其優勢在於對於數據的依賴性較低，可以很好的並行化，對於稀疏矩陣有很大的優勢。缺點在於其時間複雜度較高，一次只能對兩行做吉文斯旋轉。

格拉姆-施密特正交化方法

格拉姆-施密特正交化方法對於並行化計算並不友好，它的優勢在於算法理解其他直觀，時間複雜度介於Householder變換和吉文斯旋轉之間。

並行TSQR分解

基本思想

利用矩陣分塊的思想，對於TS矩陣進行切割，從而對若干個子塊矩陣進行分而治之。

TSQR分解算法

$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\times n}$拆成若干個子矩陣（這裏拆成2個）$A_{1}{m_{1}\times n_{1}}$和 $A_{2}$，$A_{1},A_{2}$的維度分別是$m_{1}\times n_{1},m_{2}\times n_{2}$, 注意拆開的子矩陣要保證行數仍然大於列數，即 $m_{1}>n_{1},m_{2}>n_{2}$。

我們分別對$A_{1}$和 $A_{2}$做QR分解。

$A_{1}=Q_{1}R_{1}$

$A_{2}=Q_{2}R_{2}$

此時的QR分解是完全可以並行的。 我們再將$R_{1},R_{2}$合併並驚醒QR分解

${\hat {R}}={\begin{bmatrix}R_{1}\\R_{2}\end{bmatrix}}=Q_{11}{\begin{bmatrix}R_{11}\\0\end{bmatrix}}$

此時的 $R_{11}$ 便是我們所需要的最後分解所得的 $R$。

例子

我們現在需要分解如下矩陣

$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}$，並對其做相應的QR分解。

$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}={\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}}$

那麼

${\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}}$

我們對${\hat {R}}$進行QR分解，

${\hat {R}}=Q_{11}R_{11}=Q_{11}$

$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\times n}$求解其SVD，我們可以先對矩陣$A$做TSQR分解。那麼

$A=QR$

我們在對$R$做SVD分解 ,相比於直接做SVD，這樣做的好處在於$R$的維度是 $n\times n$, 所以速度會快很多。

$R={\tilde {U}}\Sigma V$

所以最後只需要$U$計算

$U=Q{\tilde {U}}$

就可以得到所有的特徵量向量