论文标题
低级矩阵分解的随机排名QLP
Randomized Rank-Revealing QLP for Low-Rank Matrix Decomposition
论文作者
论文摘要
旋转的QLP分解是通过两个连续的QR分解来计算的，并为单数值分解提供了近似值。这项工作与通过随机化计算的低级矩阵的部分QLP分解有关，称为随机未分散的QLP（RU-QLP）。像旋转的QLP一样，RU-QLP是级别的，但它利用随机列采样和未分解的QR分解。后者的修改使RU-QLP在现代计算平台上可以高度平行。我们提供了RU-QLP的分析，在频谱中得出界限，并在：i）范围范围的属性上； ii）近似子空间与确切的单数子空间和向量之间的主要角度； iii）低级别近似错误。通过数值测试来说明边界的有效性。我们进一步使用配备GPU的现代多功能机器来证明RU-QLP的效率。我们的结果表明，与随机SVD相比，RU-QLP在CPU上达到了高达7.1倍的加速度，使用GPU的加速度高达2.3倍。
The pivoted QLP decomposition is computed through two consecutive pivoted QR decompositions, and provides an approximation to the singular value decomposition. This work is concerned with a partial QLP decomposition of low-rank matrices computed through randomization, termed Randomized Unpivoted QLP (RU-QLP). Like pivoted QLP, RU-QLP is rank-revealing and yet it utilizes random column sampling and the unpivoted QR decomposition. The latter modifications allow RU-QLP to be highly parallelizable on modern computational platforms. We provide an analysis for RU-QLP, deriving bounds in spectral and Frobenius norms on: i) the rank-revealing property; ii) principal angles between approximate subspaces and exact singular subspaces and vectors; and iii) low-rank approximation errors. Effectiveness of the bounds is illustrated through numerical tests. We further use a modern, multicore machine equipped with a GPU to demonstrate the efficiency of RU-QLP. Our results show that compared to the randomized SVD, RU-QLP achieves a speedup of up to 7.1 times on the CPU and up to 2.3 times with the GPU.
