TSQR

Template:Citation style TSQR是针对高瘦(tall and skinny)矩阵QR的分解。这类矩阵有着行(Row)远大于列(Column)的特点， 高瘦(TS)矩阵往往常见于评价系统，评价的项目少于评价的人数等。

TSQR分解和普通的QR分解的区别在于，TSQR的分解可以进行并行加速。

TS矩阵

TS矩阵的特点是行(Row) $\gg$ 列(Column)。 如下图$A$就是一个典型的TS矩阵。

$A_{m\times n}=\left[\begin{array}{ccccc}{a}_{11}& \cdots & a_{1i}& \cdots & a_{in}\\ ⋮& \ddots & ⋮& & ⋮\\ a_{i1}& \cdots & a_{ii}& \cdots & a_{in}\\ ⋮& & ⋮& \ddots & ⋮\\ a_{j1}& \cdots & a_{ji}& \cdots & a_{jn}\\ ⋮& & ⋮& & ⋮\\ a_{m1}& \cdots & a_{mi}& \cdots & a_{mn}\end{array}\right]$

这里 $m\gg n$。

TSQR分解的方法优劣比较

TSQR分解主要依赖于QR分解，有以下三种方法的详细介绍和例子说明，以下将详细比较三种方法的优劣势作用于TS矩阵。

Householder变换

针对Householder变换，其优势在于计算的时间复杂度较低，一次变换可以将一整个列除了首个元素都化成0，但是对数据的依赖度较高，不容易进行并行化计算，但是该方法对于稠密矩阵，相比于以下两种方法，计算效率会更高。

豪斯霍尔德变换示意图：向量x在豪斯霍尔德向量v的超平面${𝐯}^{\perp }$上的镜像是Hx，H是豪斯霍尔德矩阵。

吉文斯旋转

针对吉文斯旋转，其优势在于对于数据的依赖性较低，可以很好的并行化，对于稀疏矩阵有很大的优势。缺点在于其时间复杂度较高，一次只能对两行做吉文斯旋转。

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

格拉姆-施密特正交化方法对于并行化计算并不友好，它的优势在于算法理解其他直观，时间复杂度介于Householder变换和吉文斯旋转之间。

并行TSQR分解

基本思想

利用矩阵分块的思想，对于TS矩阵进行切割，从而对若干个子块矩阵进行分而治之。

TSQR分解算法

$A_{m\times n}=\left[\begin{array}{ccc}{a}_{1,1}& \cdots & a_{1,n}\\ ⋮& & ⋮& \\ a_{i,1}& \cdots & a_{i,n}\\ a_{i+1,1}& \cdots & a_{i+1,n}\\ ⋮& & ⋮& \\ a_{m,n}& \cdots & a_{m,n}\end{array}\right]$

我们将$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}=\left[\begin{array}{c}{R}_1\\ R_2\end{array}\right]=Q_{11}\left[\begin{array}{c}{R}_{11}\\ 0\end{array}\right]$

此时的 $R_{11}$ 便是我们所需要的最后分解所得的 $R$。

例子

我们现在需要分解如下矩阵

$A=\left[\begin{array}{ccc}0& 3& 1\\ 0& 4& -2\\ 2& 1& 1\\ 1& 2& 4\\ 0& 0& 5\\ 0& 3& 6\end{array}\right]$

现在将其分解成两个矩阵$A_1,A_2$，并对其做相应的QR分解。

$A_1=Q_1{R}_1=\left[\begin{array}{ccc}0& 3& -4\\ 0& 4& 3\\ 5& 0& 0\end{array}\right]\left[\begin{array}{ccc}2& 1& 2\\ 0& 5& -1\\ 0& 0& -2\end{array}\right]$

$A_2=Q_2{R}_2=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}1& 2& 4\\ 0& 3& 6\\ 0& 0& 5\end{array}\right]$

那么

$\hat{R}=\left[\begin{array}{c}{R}_1\\ R_2\end{array}\right]=\left[\begin{array}{ccc}2& 1& 2\\ 0& 5& -1\\ 0& 0& -2\\ 1& 2& 4\\ 0& 3& 6\\ 0& 0& 5\end{array}\right]$

我们对$\hat{R}$进行QR分解，

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

$R=Q_{11}=\left[\begin{array}{ccc}-2.2360& -1,7888& -3.5777\\ 0& -5.9833& -2.7743\\ 0& 0& 8.0933\end{array}\right]$

优势

上述的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}\mathrm{\Sigma }V$

所以最后只需要$U$计算

$U=Q\tilde{U}$

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