PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-Tensor Product-Based Multi-Term Randomized T-SVD and Its Visual Applications

Xingchen Xiao, Feng Zhang, Wenjin Qin, Jianjun Wang

arXiv:2609.11168v1cs.LG

TL;DR

The paper addresses dimensional rigidity, limited accuracy of single-term tensor STP decompositions, and the computational cost of deterministic methods. It introduces transform-generalized tensor STP, multi-term MSTP-SVD, and randomized MRSTP-SVD, with experiments reporting effective reconstruction quality and efficiency across visual tasks.

  • Problem

    Standard t-products impose strict dimension matching, while existing tensor STP decompositions use single terms and deterministic methods are costly for large-scale data.

  • Method

    The paper develops tensor STP under arbitrary invertible transforms, combines multiple orthogonal terms in MSTP-SVD, and accelerates it with randomized projection and power iteration.

  • Results

    Experiments on image and video compression and tensor completion show superior or comparable reconstruction quality and computational efficiency against state-of-the-art baselines.

  • Takeaways & Limitations

    The proposed framework balances reconstruction fidelity and computational efficiency while extending tensor decomposition beyond rigid dimension matching.

  • Takeaways & Limitations

    The conclusion identifies dynamic acceleration, adaptive parameter tuning, and extensions to higher-order tensors and broader algebraic structures as future work.

Abstract

from arXiv · show

Tensor singular value decomposition (T-SVD), which is built upon the tensor-tensor product (t-product), has emerged as a powerful tool for processing high-dimensional visual data such as color images and videos. However, the standard t-product imposes strict dimensional compatibility constraints. Although extensions based on the semi-tensor product (STP) relax this restriction, their single-term formulations still suffer from limited approximation accuracy. Moreover, these deterministic methods incur high computational costs when processing large-scale tensor data. To address these issues, this paper introduces a novel semi-tensor product for third-order tensors under the t-product framework induced by arbitrary invertible linear transforms. The resulting tensor semi-tensor product breaks the rigid dimension matching requirement of the standard t-product, while retaining the closed-form property of T-SVD. Based on this construction, we develop a multi-term semi-tensor product singular value decomposition (MSTP-SVD), which integrates multiple orthogonal decomposition terms to significantly improve low-rank approximation accuracy compared with single-term schemes. To reduce the computational cost of multi-term modeling, we incorporate randomized projection and power iteration techniques into the MSTP-SVD framework, yielding an accelerated multi-term randomized semi-tensor product SVD (MRSTP-SVD) algorithm that achieves a balance between reconstruction accuracy and computational efficiency. Experiments on image and video compression and completion tasks demonstrate the effectiveness of the proposed method.

1. Introduction

T-SVD offers closed-form, optimally truncated tensor decompositions for visual data, but standard t-products require matched dimensions. The paper addresses this rigidity, single-term accuracy limits, and deterministic computational costs through a flexible multi-term randomized framework.

  • T-SVD provides closed-form factorization and Frobenius-norm optimal truncated approximation for high-dimensional visual data.Its theoretical properties support applications including image compression and video completion.
  • Standard t-products are defined only when the inner dimensions match, limiting T-SVD for tensors with incompatible modes.This constraint is explicitly expressed as n2 = m1 for X ∗ Y.
  • Existing tensor STP decompositions relax dimension constraints but use single-term orthogonal factors, limiting accuracy for complex correlations and slowly decaying singular values.The resulting approximations may fail to capture fine-grained structural information.
  • The paper targets three coupled challenges: dimensional rigidity, single-term approximation limits, and deterministic inefficiency in large-scale tensor decomposition.Relaxing dimensions can add algebraic complexity, while multi-term modeling increases computational cost.
  • The proposed framework uses arbitrary invertible transforms, multi-term STP-SVD, and randomized projection with power iteration to balance flexibility, accuracy, and efficiency.Experiments cover image compression, video compression, and tensor completion, reporting superior or comparable reconstruction quality and computational efficiency against state-of-the-art baselines.

2. Notations and Preliminaries

This section establishes notation and the algebraic foundations for tensor operations under an arbitrary invertible linear transform. It reviews vector and matrix semi-tensor products, transform-based t-products, tensor properties, and T-SVD.

  • The paper adopts the left semi-tensor product and notes that right and general-dimensional variants are outside its considered formulation.The term “semi-tensor product” subsequently refers to the left semi-tensor product.
  • Matrix STP extends multiplication to dimensionally mismatched matrices using block structures and reduces to ordinary multiplication when inner dimensions match.Its construction is connected to Kronecker products and uses the least common multiple of the relevant dimensions.
  • The transform-induced t-product multiplies tensors with compatible second and first modes, producing a tensor with the remaining outer dimensions.Tensor transpose, identity, f-diagonal, and orthogonality are defined consistently with this product.
  • The T-SVD theorem factors a tensor into orthogonal tensors and an f-diagonal tensor under any invertible linear transform.The factorization supplies the theoretical basis for the paper’s later semi-tensor-product decompositions.

3. Semi-tensor product of tensors via arbitrary invertible linear transforms

The paper defines a tensor semi-tensor product induced by any invertible linear transform, using block-diagonal transform-domain operations to relax dimension matching. The construction preserves associativity and reduces to the standard t-product when dimensions match.

  • The tensor STP is defined under arbitrary invertible linear transforms, extending the transform-based t-product framework.The construction is introduced as a new tensor operation for third-order tensors.
  • The construction accommodates mismatched inner dimensions through least-common-multiple-based identity tensors.The relevant identity tensors have sizes determined by t = lcm(n2, m1).
  • When the inner dimensions match, tensor STP reduces exactly to the standard t-product.For n2 = m1, the Kronecker identity factors become trivial and A ⋉_L B = A ∗_L B.
  • Tensor STP is computed as slice-wise matrix STP operations in the transform domain followed by the inverse transform.Its equivalent block-diagonal representation connects the tensor operation directly to matrix STP.
  • Tensor STP satisfies an associative law whenever the involved semi-tensor products are well-defined.The result follows from the corresponding matrix STP associativity property.

4. Tensor singular value decomposition via semi-tensor product

This section develops STP-SVD from a rearrangement-based matrix formulation, then extends it to multi-term and tensor decompositions. The multi-term framework improves approximation fidelity while supporting truncated variants and tensor-slice computation.

  • 4.1. Single-term STP-SVD of matrices: STP-SVD rearranges a block matrix into R(A), whose singular vectors produce matrix factors B and C for an STP-based approximation.The construction uses block matrices A_i,j and an optimal Kronecker product approximation through the rearrangement operator.
  • 4.2. Multi-term STP-SVD of matrices: The single-term formulation is inherently limited by one Kronecker component, motivating additional components to capture more information from the original matrix.The multi-term scheme targets this bottleneck by summing multiple orthogonal STP factorization components.
  • 4.2. Multi-term STP-SVD of matrices: A truncated multi-term variant retains the leading r singular components of each factor, with error arising from both global and per-factor truncation.The two error sources correspond to rank-k truncation of R(A) and truncated SVD of each matrix B_i.
  • 4.3. Multi-term STP-SVD of tensors: The matrix construction generalizes to tensors under an invertible transform by applying MSTP-SVD to each frontal slice, producing the tensor MSTP-SVD.The resulting tensor formulation preserves the structurally consistent factorization form and supports truncated ranks organized in a rank matrix.
  • 4.3. Multi-term STP-SVD of tensors: Under a scaled-unitary transform condition, the truncated tensor approximation has a Frobenius-norm upper bound combining transform-domain truncation and per-matrix SVD errors.The rank matrix R specifies the retained singular rank for each matrix associated with each frontal slice.

5. Fast randomized tensor singular value decomposition via semi-tensor product

The paper accelerates multi-term semi-tensor-product SVD by replacing costly exact SVD computations with randomized subspace extraction and power iteration. The resulting method reduces complexity while maintaining bounded approximation error and negligible accuracy loss.

  • Randomized subspace extraction replaces costly exact SVD in MSTP-SVD, yielding notable speedup with negligible accuracy loss.The method uses random projection and power iteration before performing SVD in a lower-dimensional subspace.
  • Direct full SVD on each large-scale transform-domain frontal slice is computationally prohibitive, motivating randomized acceleration.
  • The algorithm forms an orthonormal subspace, projects the rearranged matrix into a compact matrix, computes a cheaper SVD, and maps truncated factors back to the original space.
  • The error analysis identifies a trade-off among truncation k, oversampling s, and power iterations q: larger k reduces residual energy but increases sampling bias.Larger s mitigates sampling error, while additional q helps when singular values decay slowly, at added computational cost.

6. Numerical experiments

Experiments evaluate the proposed methods on image and video compression and completion using PSNR, SSIM, runtime, and visual comparisons. Multi-term methods improve reconstruction quality, while randomized variants preserve comparable quality with lower computational cost.

  • Image compression: In image compression, MSTP-SVD and MRSTP-SVD recover finer local details, whereas baseline methods produce over-smoothed outputs and lose subtle image content.The visual comparison covers representative Lake and Road images, with Night and Fruit results supplied separately.
  • Video compression: Across video frames, multi-term schemes consistently outperform baselines as k increases, while randomized methods retain comparable accuracy with substantial acceleration.The reported frame-wise comparisons use the first 40 frames of four benchmark videos.
  • Video compression: Over four high-resolution videos, MRSTP-SVD gains over 5 dB PSNR on Market, nearly 4 dB on Aerial, and reduces runtime by over 5 s versus baselines.TMRSTP-SVD provides further speedup with only minor acceptable accuracy loss.
  • Image completion: For image completion, proposed methods achieve higher PSNR, richer textures, and fewer artifacts, while randomized substitution greatly reduces computational burden.The evaluation covers twenty test images and reports competitive reconstruction quality for the randomized scheme.
  • Video completion: For video completion, randomized TMRSTP-SVD maintains comparable PSNR and SSIM with negligible quality loss and reduces total runtime by around 25%.Visual results show finer textures in missing regions while baselines leave noticeable artifacts.

7. Conclusion

The paper introduces a flexible tensor semi-tensor product, a multi-term MSTP-SVD model, and a randomized MRSTP-SVD variant for accurate and efficient visual-data processing. Experiments validate the methods for image/video compression and tensor completion, while future work includes acceleration, parameter tuning, and higher-order extensions.

  • 7. Conclusion: The proposed tensor semi-tensor product supports third-order tensors under arbitrary invertible linear transforms while preserving the closed-form T-SVD structure.The construction also accommodates any unitary transform, providing flexibility beyond fixed-transform alternatives.
  • 7. Conclusion: MSTP-SVD combines multiple orthogonal components and improves low-rank approximation accuracy over single-term schemes.This multi-term design addresses the limitations of single-term factorization.
  • 7. Conclusion: MRSTP-SVD combines randomized projection and power iteration to balance reconstruction fidelity with computational efficiency for large-scale applications.The randomized variant targets the computational bottleneck of deterministic multi-term modeling.
  • 7. Conclusion: Image/video compression and tensor completion experiments validate the proposed methods, with randomized processing providing substantial acceleration at negligible accuracy cost.The experiments include both compression and completion tasks.
  • 7. Conclusion: The paper identifies algorithmic acceleration, adaptive parameter tuning, and extensions to higher-order tensors and broader algebraic structures as future directions.These directions are presented as avenues for further development.

CRediT authorship contribution statement

The CRediT statement assigns authorship contributions across writing, visualization, methodology, software, validation, supervision, analysis, investigation, data curation, and project administration.

  • CRediT authorship contribution statement: Xingchen Xiao contributed to the original draft, visualization, methodology, software, validation, and conceptualization.
  • CRediT authorship contribution statement: Feng Zhang contributed to review and editing, supervision, resources, funding acquisition, and conceptualization.
  • CRediT authorship contribution statement: Wenjin Qin contributed to review and editing, formal analysis, investigation, and data curation.
  • CRediT authorship contribution statement: Jianjun Wang contributed to review and editing, supervision, and project administration.

Declaration of competing interest

The authors declare no known competing financial interests or personal relationships that could have influenced the reported work.

  • Declaration of competing interest: The authors declare no known competing financial interests or personal relationships related to the reported work.

Data availability

The datasets used in the study are publicly available from the sources cited in the numerical experiments section.

  • Data availability: The study datasets are publicly available through the sources cited in the numerical experiments section.

Supplementary Material of Semi-Tensor Product-Based

The supplementary material supplies mathematical preliminaries, theoretical proofs, algorithm pseudocodes, and additional validation for the proposed STP-SVD framework. It develops multi-term tensor decompositions and explains how randomized projection and power iteration approximate the deterministic method.

  • Overview: The supplement provides preliminaries, full proofs, pseudocodes, and additional experiments while leaving the main paper’s core contributions unchanged.These materials support the theoretical and algorithmic developments presented in the main work.
  • Theoretical results: Theoretical results establish multi-term STP-SVD for matrices, extend it to tensors with orthogonal factors and closed-form error bounds, and derive an expected error bound for MRSTP-SVD.The randomized bound separates deterministic truncation error from randomized subspace-approximation error.
  • Transform assumption: The framework assumes an invertible transform matrix satisfying L^H L = L L^H = ρI_l and L^-1 = L^H/ρ.This transform condition is used in the tensor error analysis.
  • Randomized algorithm: MRSTP-SVD replaces full SVDs of rearranged frontal slices with randomized projection and power iteration to reduce computational cost.Its total reconstruction error is decomposed into deterministic multi-term truncation and randomized approximation components.
  • Algorithms: The pseudocodes cover truncated STP-SVD, multi-term matrix and tensor variants, MSTP-SVD, and randomized MRSTP-SVD.The tensor procedures transform the input, reorganize frontal-slice blocks, compute truncated decompositions, and form the factors.

Appendix D. Supplementary experimental results

Supplementary experiments evaluate transform choices and proposed deterministic and randomized methods on additional image compression, video reconstruction, and video completion tasks. Across these settings, multi-term methods improve reconstruction quality, while randomized variants substantially reduce runtime with small quality losses.

  • Transform comparison: DFT, DCT, and ROT provide comparable reconstruction quality, while DFT has the lowest computational overhead across the tested images.These observations support using DFT as the default transform in subsequent experiments.
  • Image compression: MSTP-SVD improves PSNR over single-term STP-SVD by 7.9 dB and 3.1 dB, and exceeds TT-SVD by 5.8–7.3 dB on two additional images.MRSTP-SVD has less than 0.08 dB PSNR loss while reducing runtime by approximately 22%.
  • Video reconstruction: Across the additional video samples, proposed methods recover richer textures and finer details than baseline approaches.The comparisons include original, truncated, and randomized variants under the main-text experimental settings.
  • Video completion: Under 70% randomly missing pixels, the proposed completion methods outperform baselines in reconstruction accuracy and produce fewer visible artifacts in missing regions.Randomized TMRSTP-SVD substantially reduces completion runtime relative to deterministic TMSTP-SVD with nearly negligible quality loss.
Loading 2609.11168v1…