  Tensor trains are a versatile tool to compress and work with high-dimensional
data and functions. In this work we introduce the Streaming Tensor Train
Approximation (STTA), a new class of algorithms for approximating a given
tensor $\mathcal T$ in the tensor train format. STTA accesses $\mathcal T$
exclusively via two-sided random sketches of the original data, making it
streamable and easy to implement in parallel -- unlike existing deterministic
and randomized tensor train approximations. This property also allows STTA to
conveniently leverage structure in $\mathcal T$, such as sparsity and various
low-rank tensor formats, as well as linear combinations thereof. When Gaussian
random matrices are used for sketching, STTA is admissible to an analysis that
builds and extends upon existing results on the generalized Nystr\"om
approximation for matrices. Our results show that STTA can be expected to
attain a nearly optimal approximation error if the sizes of the sketches are
suitably chosen. A range of numerical experiments illustrates the performance
of STTA compared to existing deterministic and randomized approaches.
