PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor Ring Decomposition

Qibin Zhao, Guoxu Zhou, Shengli Xie, Liqing Zhang, Andrzej Cichocki

arXiv:1606.05535v1math.NAcs.CVcs.DS

TL;DR

TT representations efficiently handle high-dimensional tensors but depend on strict core ordering and dimension permutations. This paper introduces tensor ring decomposition, using circular trace products over low-dimensional cores, and develops algorithms and core-level operations. TR provides circular permutation invariance, while the proposed algorithms differ in rank adaptation, stability, precision, and computational cost.

  • Problem

    TT decomposition's strictly sequential multilinear products and dependence on dimension permutations limit the flexibility of tensor representation.

  • Method

    The paper represents large-dimensional tensors with circular multilinear products over low-dimensional cores and proposes four optimization algorithms based on SVD and ALS techniques.

  • Results

    TR provides circular dimensional permutation invariance, and the paper reports efficient core-level multilinear operations with complexity scaling linearly in tensor order.

  • Takeaways & Limitations

    TR offers a symmetric, circular representation framework with algorithms that trade off stability, precision, manual or automatic rank adaptation, convergence, and computational cost.

  • Takeaways & Limitations

    TR-SVD may produce non-optimal, start-point-dependent TR-ranks, while adaptive ALS methods can require many iterations or relatively high computational cost.

Abstract

from arXiv · show

Tensor networks have in recent years emerged as the powerful tools for solving the large-scale optimization problems. One of the most popular tensor network is tensor train (TT) decomposition that acts as the building blocks for the complicated tensor networks. However, the TT decomposition highly depends on permutations of tensor dimensions, due to its strictly sequential multilinear products over latent cores, which leads to difficulties in finding the optimal TT representation. In this paper, we introduce a fundamental tensor decomposition model to represent a large dimensional tensor by a circular multilinear products over a sequence of low dimensional cores, which can be graphically interpreted as a cyclic interconnection of 3rd-order tensors, and thus termed as tensor ring (TR) decomposition. The key advantage of TR model is the circular dimensional permutation invariance which is gained by employing the trace operation and treating the latent cores equivalently. TR model can be viewed as a linear combination of TT decompositions, thus obtaining the powerful and generalized representation abilities. For optimization of latent cores, we present four different algorithms based on the sequential SVDs, ALS scheme, and block-wise ALS techniques. Furthermore, the mathematical properties of TR model are investigated, which shows that the basic multilinear algebra can be performed efficiently by using TR representaions and the classical tensor decompositions can be conveniently transformed into the TR representation. Finally, the experiments on both synthetic signals and real-world datasets were conducted to evaluate the performance of different algorithms.

1 INTRODUCTION

Tensor-network formats represent high-dimensional tensors through interconnected lower-order tensors, but TT decomposition imposes sequential core products and dimension ordering. The paper introduces TR decomposition to relax these constraints through trace-based circular products and develops algorithms and supporting tensor operations.

  • Tensor decompositions represent higher-order tensors through multilinear operations over latent factors for applications including machine learning, signal processing, and brain science.
  • Tensor networks transform large-scale optimization into sets of tractable small-scale problems by interconnecting lower-order tensors.
  • TT representation efficiently handles higher-dimensional tensors but requires strictly sequential products, making dimensional permutation important for finding suitable representations.
  • TR decomposition generalizes TT by relaxing boundary-rank constraints, alleviating strict core ordering, and treating cores symmetrically through the trace operation.
  • The paper presents four TR optimization algorithms, investigates multilinear algebra directly on TR representations, relates TR to existing decompositions, and evaluates the methods on synthetic and real-world datasets.

2 TENSOR RING MODEL

TR represents each tensor element through the trace of circularly multiplied core slices, forming a ring of third-order latent tensors. This construction supports circular dimension shifts and gives a parameter-efficient representation whose rank and core structure are explicitly defined.

  • TR representation: TR decomposes a dth-order tensor into a sequence of third-order cores Z_k ∈ R^{r_k×n_k×r_{k+1}} multiplied circularly.
  • Element-wise formulation: Each tensor element is computed as T(i_1, ..., i_d) = Tr{Z_1(i_1)Z_2(i_2) ··· Z_d(i_d)}, where each Z_k(i_k) is a lateral-slice matrix.
  • Circular structure: The trace operation connects the final core back to the first and makes the product a square-matrix operation, with r_{d+1}=r_1.
  • TR ranks and complexity: TR-ranks are the core dimensions collected as r = [r_1, r_2, ..., r_d]^T, and the representation uses O(dnr^2) parameters, linear in tensor order.
  • Circular invariance: Circular dimensional permutation invariance allows a shifted tensor to use the correspondingly shifted core sequence, unlike TT's strictly sequential ordering.

3 LEARNING ALGORITHMS

The paper develops four approaches for learning low-rank tensor-ring cores, combining sequential SVD, ALS, adaptive-rank, and block-wise ALS strategies. These methods differ in rank selection, convergence behavior, and dependence on initialization choices.

  • Learning objective: TR decomposition seeks minimum ranks subject to a prescribed relative Frobenius-norm approximation error.The objective constrains ||T − ℜ(Z1, ..., Zd)||F to be at most ϵp||T||F.
  • TR-SVD: TR-SVD computes the cores using d sequential SVDs without iterative convergence steps.The procedure sequentially reshapes truncated-SVD factors to obtain all d cores and produces left-orthogonal intermediate cores.
  • TR-SVD: TR-SVD can depend on the selected starting mode and may produce non globally optimal TR-ranks.Different starting modes can yield different representations, motivating algorithms independent of the start point.
  • ALS methods: ALS with adaptive ranks can target arbitrary approximation error through rank adaptation, but increasing ranks one at a time may require many iterations.The procedure is described as intuitive and heuristic.
  • Block-wise ALS: TR-BALS adapts ranks by splitting a block core into two cores with truncated SVD and is reported to find optimum ranks efficiently.The discussion contrasts this with TR-ALSAL, which adapts ranks but requires many iterations.

4 PROPERTIES OF TR REPRESENTATION

TR representations support efficient tensor operations by applying multilinear manipulations to individual cores, with complexity scaling linearly in tensor order. They also provide explicit constructions for addition, Hadamard products, inner products, multilinear products, and related operations.

  • Operations on TR cores: TR representations enable tensor addition by merging corresponding cores, although the resulting core sizes are generally nonoptimal.A rounding procedure can address the increased core sizes.
  • Operations on TR cores: Multilinear products between a TR tensor and vectors can be computed through multilinear products on each core.The resulting scalar operation can also be expressed as an inner product with a rank-1 tensor.
  • Computational complexity: For multilinear products, TR reduces the original O(dn^d) computation to O(dnr^2 + dr^3), which is linear in tensor order d.The reduction follows from expressing the operation through contractions of the TR cores.
  • Operations on TR cores: Hadamard products remain in TR format by forming Kronecker products of corresponding lateral slices, with computational cost O(dnq^2).The new ring dimensions satisfy q_k = r_k * s_k.
  • Computational complexity: TR inner products and Frobenius norms can be computed through TR operations with complexity O(dnq^2 + dq^3), rather than O(n^d).These operations combine Hadamard products with multilinear products against vectors of ones.

5 RELATION TO OTHER MODELS

TR relates systematically to classical tensor models: CPD, Tucker, and TT can be represented within the TR framework. Compared with TT, TR offers greater representation flexibility and can require smaller ranks for a given approximation level.

  • Relation to TT: TR has circular dimensional permutation invariance, whereas TT cores depend strongly on the strict ordering of tensor dimensions.TR ranks can also be distributed more evenly across cores than TT ranks.
  • Relation to classical decompositions: CPD is a special case of TR when every lateral slice is a diagonal r × r matrix.The resulting TR cores have size r × n_k × r.
  • Relation to classical decompositions: Tucker tensors can be represented in TR by representing the Tucker core with TR cores and multiplying each core along its mode-2 dimension by the corresponding factor matrix.The transformed cores are Z_k = V_k ×2 U^(k).
  • Relation to TT: TT is a special case of TR obtained by setting the first and last ring ranks to one, r1 = r_d+1 = 1.TR can also be rewritten with a trace over the product of its lateral slice matrices.
  • Relation to TT: TR can be interpreted as a sum of r1 TT representations that share the intermediate cores.This linear-combination structure gives TR greater representation power and, for a fixed approximation level, smaller required ranks than TT.
  • Functional-data experiment: Table 1 evaluates f1(x), f2(x), and f3(x) after tensorization into 10th-order tensors of size 4 × 4 × ... × 4 using relative error, average rank, and parameter count.The supplied passage identifies the table’s metrics and tensorization setting but does not provide numerical entries.

6 EXPERIMENTAL RESULTS

Experiments on synthetic functions, dimension-shifted tensors, synthetic higher-order tensors, COIL-100 images, and KTH videos evaluate TR algorithms against TT and CP methods. Across these settings, TR methods provide permutation-stable representations, adaptive rank selection, competitive or improved compression, and strong classification performance.

  • Synthetic functional data: TR-SVD and TT-SVD achieve comparable relative error, average rank, parameter count, and runtime on clean synthetic functions.TR-SVD outperforms TT-SVD on noisy f1(x), using fewer average TR-ranks and parameters while reducing overfitting.
  • Dimension shifts: TR representations remain consistent under dimension shifts, whereas TT representations are limited by strict rank and ordering constraints.The experiments consider all dimension shifts for a 10th-order tensor; TR-ALS uses shifted TR-ranks to achieve consistent results.
  • Synthetic higher-order tensors: TR-BALS adapts TR-ranks, estimates the true rank correctly on noisy synthetic tensors, and achieves compression comparable to manually ranked TR-ALS more efficiently than TR-ALSAR.By contrast, TT-SVD and TR-SVD have limitations for symmetric-rank data, especially under noise.
  • COIL-100 dataset: TR-SVD achieves 99.19% and 89.89% classification accuracy on COIL-100 with 50% and 10% training data, respectively, while preserving discriminative information at larger fitting error.These results are compared with TT-SVD and CP-ALS; the passage reports that TR decompositions provide the best classification and compression performance among the compared frameworks.
  • KTH video dataset: On KTH videos, TR-SVD requires rmax = 99 and average rank 34.2 at ϵ ≈0.2, versus TT-SVD values of 139 and 78, while TR-BALS achieves 87.0% accuracy.The best reported accuracies are 80.8% for CP-ALS, 84.8% for TT-SVD, 87.7% for TR-SVD, 87.3% for TR-ALS, 82.3% for TR-ALSAR, and 87.0% for TR-BALS.

7 CONCLUSION

The paper proposes tensor ring decomposition as an efficient large-dimensional tensor representation and develops four algorithms for optimizing its latent cores. It also establishes efficient multilinear operations and transformations from classical tensor decompositions, with experiments verifying the model and algorithms.

  • The proposed tensor ring model represents large-dimensional tensors with low-dimensional cores using O(dnr^2) parameters that scale linearly with tensor order.
  • Four optimization algorithms are presented: TR-SVD, TR-ALS, TR-ALSAR, and TR-BALS.TR-SVD is non-recursive, stable, and efficient; TR-ALS is precise but requires manually specified TR-ranks, while TR-ALSAR and TR-BALS adapt ranks automatically at higher computational cost.
  • The TR representation supports efficient basic multilinear algebra through direct operations on its cores.
  • Latent representations from traditional tensor decomposition models can be conveniently transformed into the TR model.
  • Experiments on synthetic and real-world data verify the effectiveness of the proposed TR model and algorithms.
Loading 1606.05535v1…