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，但是对数据的依赖度较高，不容易进行并行化计算，但是该方法对于稠密矩阵，相比于以下两种方法，计算效率会更高。

吉文斯旋转
针对吉文斯旋转，其优势在于对于数据的依赖性较低，可以很好的并行化，对于稀疏矩阵有很大的优势。缺点在于其时间复杂度较高，一次只能对两行做吉文斯旋转。
格拉姆-施密特正交化方法
格拉姆-施密特正交化方法对于并行化计算并不友好，它的优势在于算法理解其他直观，时间复杂度介于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}
就可以得到所有的特征量向量

外部連結