An Incremental Tensor Train Decomposition Algorithm

DOI10.1137/22M1537734MaRDI QIDQ6418162zbMATH OpenFDO

Authors Doruk Aksoy, David Gorsich, Shravan Veerapaneni

Publication date 22 November 2022

Full work available at URL https://doi.org/10.1137/22M1537734

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: We present a new algorithm for incrementally updating the tensor-train decomposition of a stream of tensor data. This new algorithm, called the 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${}^{\ast }$). 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${}^{\ast }$ achieves 57$imes$ higher compression and up to 95% reduction in computational time.

Recommendations

• Streaming Tensor Train Approximation
• Incremental CP tensor decomposition by alternating minimization method
• Low-rank Tucker approximation of a tensor from streaming data
• Incremental algorithms for truncated higher-order singular value decompositions
• A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format

Cited in

(4)

• Incremental algorithms for truncated higher-order singular value decompositions
• A direct method for computing the complex-valued triple decomposition of third-order tensors
• Tensor-based Dinkelbach method for computing generalized tensor eigenvalues and its applications
• Discriminative tensor ring completion: a Laplace-based nonconvex surrogate for rank minimization

This page was built for publication: An Incremental Tensor Train Decomposition Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6418162)