跳转到内容

TSQR

维基百科,自由的百科全书

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

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

TS矩阵

[编辑]

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

这里

TSQR分解的方法优劣比较

[编辑]

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

Householder变换

[编辑]

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

豪斯霍尔德变换示意图:向量x在豪斯霍尔德向量v的超平面上的镜像是HxH是豪斯霍尔德矩阵。

吉文斯旋转

[编辑]

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

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

[编辑]

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

并行TSQR分解

[编辑]

基本思想

[编辑]

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

TSQR分解算法

[编辑]

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

我们分别对做QR分解。

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

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

例子

[编辑]

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

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

那么


我们对进行QR分解,

优势

[编辑]

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

1)不同于QR分解,此类的QR分解是可以高度并行化的;

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

用途

[编辑]

快速求解奇异值分解(SVD)

[编辑]

对于一个TS矩阵求解其SVD,我们可以先对矩阵做TSQR分解。那么

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

所以最后只需要计算

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

外部連結

[编辑]

[1]

[2]

[3]

[4]

  1. ^ 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. 
  2. ^ MIT. QR Decomposition. [2020-07-01]. (原始内容存档于2020-07-27). 
  3. ^ 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. 
  4. ^ 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.