Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs
This work discusses tensor network embeddings, which are random matrices
($S$) with tensor network structure. These embeddings have been used to perform
dimensionality reduction of tensor network structured inputs $x$ and accelerate
applications such as tensor decomposition and kernel regression. Existing works
have designed embeddings for inputs $x$ with specific structures, such that the
computational cost for calculating $Sx$ is efficient. We provide a systematic
way to design tensor network embeddings consisting of Gaussian random tensors,
such that for inputs with more general tensor network structures, both the
sketch size (row size of $S$) and the sketching computational cost are low.
  We analyze general tensor network embeddings that can be reduced to a
sequence of sketching matrices. We provide a sufficient condition to quantify
the accuracy of such embeddings and derive sketching asymptotic cost lower
bounds using embeddings that satisfy this condition and have a sketch size
lower than any input dimension. We then provide an algorithm to efficiently
sketch input data using such embeddings. The sketch size of the embedding used
in the algorithm has a linear dependence on the number of sketching dimensions
of the input. Assuming tensor contractions are performed with classical dense
matrix multiplication algorithms, this algorithm achieves asymptotic cost
within a factor of $O(\sqrt{m})$ of our cost lower bound, where $m$ is the
sketch size. Further, when each tensor in the input has a dimension that needs
to be sketched, this algorithm yields the optimal sketching asymptotic cost. We
apply our sketching analysis to inexact tensor decomposition optimization
algorithms. We provide a sketching algorithm for CP decomposition that is
asymptotically faster than existing work in multiple regimes, and show
optimality of an existing algorithm for tensor train rounding.