  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\"{o}m approximation,
with a discussion of their accuracy and implementation on distributed
architectures.
