2022/11/22 by Aksoy, Doruk, Gorsich, David J., Veerapaneni, Shravan +1
#15A23 #15A69 #65-04 #65F55 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2211.12487
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× higher compression and up to 95% reduction in computational time.