  We present a new algorithm for incrementally updating the tensor train
decomposition of a stream of tensor data. This new algorithm, called the {\em
tensor train incremental core expansion} (TT-ICE) improves upon the current
state-of-the-art algorithms for compressing in tensor train format by
developing a new adaptive approach that incurs significantly slower rank growth
and guarantees compression accuracy. This capability is achieved by limiting
the number of new vectors appended to the TT-cores of an existing accumulation
tensor after each data increment. These vectors represent directions orthogonal
to the span of existing cores and are limited to those needed to represent a
newly arrived tensor to a target accuracy. We provide two versions of the
algorithm: TT-ICE and TT-ICE accelerated with heuristics (TT-ICE$^*$). We
provide a proof of correctness for TT-ICE and empirically demonstrate the
performance of the algorithms in compressing large-scale video and scientific
simulation datasets. Compared to existing approaches that also use rank
adaptation, TT-ICE$^*$ achieves $57\times$ higher compression and up to $95\%$
reduction in computational time.
