Block Subsampled Randomized Hadamard Transform for Nystru00f6m Approximation on Distributed Architectures
Oleg Balabanov,u00a0Matthias Beaupu00e8re,u00a0Laura Grigori,u00a0Victor Lederer
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. 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 computing a low-rank approximation of a large-scale matrix, such as the Nystru00f6m method. For completeness, we revisit this method with a discussion of its implementation on distributed architectures.
