Effective algorithms for tensor train decomposition via the UTV framework

Yuchao Wang, Maolin Che, Yimin Wei

Abstract

The tensor train (TT) decomposition is used to compress large tensors into a more compact form by exploiting their inherent data structures. A fundamental approach for constructing the TT format is the TT-SVD, which extracts the TT-cores by the singular value decompositions (SVDs) sequentially. But in practical applications, it is often not necessary to compute full SVDs. In this article, we therefore propose a new method called the TT-UTV. It utilizes the virtues of rank-revealing UTV decomposition to compute the TT format for a large-scale tensor, hence requires less computational cost. We analyze the error bounds on the accuracy of these algorithms both in the URV and ULV cases, then recommend different sweep patterns for these two cases. We perform numerical experiments on some applications, including magnetic resonance imaging (MRI) data completion, to illustrate their good performance in practice.

Introduction

In the era of big data, high-dimensional arrays known as tensors are ubiquitous, representing complex datasets like video sequences, medical imaging, and genetic information. However, as the number of dimensions increases, the storage and computational requirements grow exponentially—a phenomenon termed the "curse of dimensionality."

The Tensor Train (TT) decomposition offers a powerful solution by breaking a high-dimensional tensor into a chain of low-order "cores." Traditionally, the TT-SVD algorithm has been the standard for this decomposition. While accurate, TT-SVD relies on the Singular Value Decomposition (SVD), which is computationally expensive, difficult to update, and often inefficient on modern parallel hardware. This paper introduces the TT-UTV framework to address these bottlenecks.

Methodology: The TT-UTV Framework

The core innovation of this work is the replacement of SVD with rank-revealing UTV decompositions. In a UTV decomposition, a matrix $A$ is factored into $UTV^T$, where $U$ and $V$ are orthogonal matrices and $T$ is a triangular matrix (either upper $R$ or lower $L$).

Tensor Train (TT) decomposition of a d-order tensor into a sequence of cores.

The authors propose two variants:

  1. TT-ULV: Employs lower-triangular matrices and is optimized for a left-to-right sweep to maintain left-orthogonality of the cores.
  2. TT-URV: Employs upper-triangular matrices and is best suited for a right-to-left sweep to ensure right-orthogonality.

Theoretical analysis confirms that the approximation error for TT-UTV is bounded similarly to TT-SVD. Furthermore, rank-adaptive versions allow the algorithm to automatically determine the necessary compression level based on a target accuracy.

Experimental Results

The TT-UTV framework was evaluated across several domains, including video recovery, image compression, and MRI data completion.

Computational Efficiency

In video processing tasks (tensor dimensions $11,271 \times 72 \times 128$), the TT-UTV algorithms demonstrated significant speedups. With a fixed rank of 5, TT-ULV and TT-URV completed the decomposition in approximately 41 and 39 seconds respectively, compared to 86 seconds for TT-SVD—representing a more than 2x performance gain.

Accuracy and Recovery

Despite the reduced computational cost, accuracy remained high. In MRI completion tasks using the BrainWeb dataset ($181 \times 217 \times 181$) with 70% missing data, the TT-UTV algorithms achieved a Peak Signal-to-Noise Ratio (PSNR) of approximately 30.02. This performance is on par with SVD-based methods, proving that the triangular representation in UTV captures essential subspace information effectively.

Conclusion

The TT-UTV framework provides a faster, more hardware-friendly alternative to traditional TT-SVD without sacrificing accuracy. By leveraging the efficiency of triangular matrix structures and optimizing sweep directions, it enables the processing of larger-scale tensors. Future work will explore fully parallelized implementations and the integration of randomized UTV variants to further scale these capabilities for extreme-scale data.

Summary updated

Abstract

The tensor train (TT) decomposition is used to compress large tensors into a more compact form by exploiting their inherent data structures. A fundamental approach for constructing the TT format is the TT-SVD, which extracts the TT-cores by the singular value decompositions (SVDs) sequentially. But in practical applications, it is often not necessary to compute full SVDs. In this article, we therefore propose a new method called the TT-UTV. It utilizes the virtues of rank-revealing UTV decomposition to compute the TT format for a large-scale tensor, hence requires less computational cost. We analyze the error bounds on the accuracy of these algorithms both in the URV and ULV cases, then recommend different sweep patterns for these two cases. We perform numerical experiments on some applications, including magnetic resonance imaging (MRI) data completion, to illustrate their good performance in practice.
BibTeX
@misc{wang2025effective,
  author = {Yuchao Wang and Maolin Che and Yimin Wei},
  title = {{Effective algorithms for tensor train decomposition via the UTV framework}},
  year = {2025},
  eprint = {2501.07904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.07904},
}

Loading related content...

Figure