论文标题
块亚采样随机hadamard变换，用于在分布式体系结构上进行低级近似值
Block subsampled randomized Hadamard transform for low-rank approximation on distributed architectures
论文作者
论文摘要
本文介绍了一种新型的结构化随机矩阵，该矩阵由二键采样的随机HADAMARD变换（SRHT）组成。与尺寸相比，在分布式体系结构上，块SRHT有望超过众所周知的降低缩小图，包括SRHT和Gaussian矩阵。我们证明，具有足够行的块SRHT是一个遗忘的子空间嵌入，即，对于具有很高概率的任意低维度子空间的近似等轴测图。我们对所需行数的估计与标准SRHT相似。这表明这两个变换应提供算法中近似值相同的准确性。块SRHT可以很容易地将其纳入随机方法中，例如计算大型矩阵的低级别近似值。为了完整性，我们对此问题进行了一些常见的随机方法，例如随机奇异值分解和NyStröm近似，讨论了它们对分布式体系结构的准确性和实现。
This article introduces a novel structured random matrix composed blockwise from subsampled randomized Hadamard transforms (SRHTs). The block SRHT is expected to outperform well-known dimension reduction maps, including SRHT and Gaussian matrices, on distributed architectures with not too many cores compared to the dimension. We prove that a block SRHT with enough rows is an oblivious subspace embedding, i.e., an approximate isometry for an arbitrary low-dimensional subspace with high probability. Our estimate of the required number of rows is similar to that of the standard SRHT. This suggests that the two transforms should provide the same accuracy of approximation in the algorithms. The block SRHT can be readily incorporated into randomized methods, for instance to compute a low-rank approximation of a large-scale matrix. For completeness, we revisit some common randomized approaches for this problem such as Randomized Singular Value Decomposition and Nyström approximation, with a discussion of their accuracy and implementation on distributed architectures.
