Tensor Random Projection for Low Memory Dimension Reduction
  Random projections reduce the dimension of a set of vectors while preserving
structural information, such as distances between vectors in the set. This
paper proposes a novel use of row-product random matrices in random projection,
where we call it Tensor Random Projection (TRP). It requires substantially less
memory than existing dimension reduction maps. The TRP map is formed as the
Khatri-Rao product of several smaller random projections, and is compatible
with any base random projection including sparse maps, which enable dimension
reduction with very low query cost and no floating point operations. We also
develop a reduced variance extension. We provide a theoretical analysis of the
bias and variance of the TRP, and a non-asymptotic error analysis for a TRP
composed of two smaller maps. Experiments on both synthetic and MNIST data show
that our method performs as well as conventional methods with substantially
less storage.
