TSQR

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

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

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

这里 。

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

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

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

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

并行TSQR分解

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

TSQR分解算法 

我们将拆成若干个子矩阵（这里拆成2个）和 ，的维度分别是, 注意拆开的子矩阵要保证行数仍然大于列数，即
。

我们分别对和 做QR分解。

此时的QR分解是完全可以并行的。
我们再将合并并惊醒QR分解

此时的  便是我们所需要的最后分解所得的 。

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

 

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

那么

我们对进行QR分解，

优势 
上述的TSQR和普通的QR分解的优势在于:

1）不同于QR分解，此类的QR分解是可以高度并行化的； 

2）在并行阶段，其特殊的上三角形式也可以用并行的方式进行加速。

用途

快速求解奇异值分解（SVD）
对于一个TS矩阵求解其SVD，我们可以先对矩阵做TSQR分解。那么

我们在对做SVD分解 ,相比于直接做SVD，这样做的好处在于的维度是 , 所以速度会快很多。

所以最后只需要计算

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

外部連結 

線性代數
数据挖掘