Efficient Deterministic Algorithms for Approximating Tensor–Tensor Multiplication

ABSTRACT This article investigates the efficient computation of the tensor–tensor multiplication, that is, t‐product, in streaming settings with limited memory and computational resources. We propose two deterministic sketching algorithms, FD‐ATP and COOD‐ATP. For both methods, we rigorously establish spectral norm error bounds and prove that they achieve a ‐approximation up to a multiplicative factor with respect to the best low‐tubal‐rank approximation of the t‐product. Extensive numerical experiments demonstrate the effectiveness and efficiency of the proposed methods.