The t-Product of Reduced Biquaternion Tensors

Introduction

The t-product is a product of third-order tensors that keeps the order at three. It contracts the second mode of the first tensor against the first mode of the second, as the matrix product does, and couples the third mode by a circular convolution. This article defines the product by its block circulant matrix, gives its equivalent form under the discrete Fourier transform along the third mode, proves the algebraic laws, identifies the identity and the inverse, and fixes the conjugate transpose that makes the product an adjoint operation.

The entries are reduced biquaternions, and the tensor space is Reduced Biquaternion Tensors as a Vector Space. The product is not the Einstein product of The Einstein Product of Reduced Biquaternion Tensors: the Einstein product contracts all trailing modes against all leading modes and generally raises the order, while the t-product keeps the order at three and requires equal third modes. The letter t names this transformed product; it is not the tensor product $\otimes$ of Tensor Products of Algebras and Tensor Products of Sesqualgebras.

The source of the product over reduced biquaternions is Cui-E Yu, Xin Liu, Hui Luo and Yang Zhang, "Reduced biquaternion tensors and applications in color video processing", where it is called the Ht-product. The complex and real t-products it extends are those of Misha E. Kilmer and Carla D. Martin.

The Block Circulant Reading

Let $A\in{\mathbb{B}_{\mathrm{red}}}^{n_1\times n_2\times n_3}$ and $B\in{\mathbb{B}_{\mathrm{red}}}^{n_2\times n_4\times n_3}$. The block circulant matrix generated by the frontal slices of $A$ is the $n_1n_3\times n_2n_3$ block matrix

$$ \operatorname{circ}(A)= \begin{pmatrix} A^{(1)} & A^{(n_3)} & A^{(n_3-1)} & \cdots & A^{(2)}\\ A^{(2)} & A^{(1)} & A^{(n_3)} & \cdots & A^{(3)}\\ A^{(3)} & A^{(2)} & A^{(1)} & \cdots & A^{(4)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ A^{(n_3)} & A^{(n_3-1)} & A^{(n_3-2)} & \cdots & A^{(1)} \end{pmatrix}, $$

whose block in position $(i,j)$, with $1\le i,j\le n_3$, is $A^{(1+((i-j)\bmod n_3))}$. The vectorisation and its inverse are

$$ \operatorname{Vec}(B)= \begin{pmatrix} B^{(1)}\\ B^{(2)}\\ \vdots\\ B^{(n_3)} \end{pmatrix}, \qquad \operatorname{Fold}\bigl(\operatorname{Vec}(B)\bigr)=B, $$

so that $\operatorname{Vec}(B)$ is an $n_2n_3\times n_4$ block column. The t-product is

$$ A\ast B=\operatorname{Fold}\bigl(\operatorname{circ}(A)\operatorname{Vec}(B)\bigr)\in{\mathbb{B}_{\mathrm{red}}}^{n_1\times n_4\times n_3}. $$

The definition is the one of the source, written there with the two complex parts,

$$ A\ast B=\operatorname{Fold}\bigl((\operatorname{circ}(A_{1,i})+j\operatorname{circ}(A_{j,k}))\operatorname{Vec}(B)\bigr), $$

and the two forms agree because $\operatorname{circ}(A)=\operatorname{circ}(A_{1,i})+j\operatorname{circ}(A_{j,k})$. The product is $\mathbb{B}_{\mathrm{red}}$-bilinear: it is linear in each slot over the commutative algebra.

Remark (the product is not commutative). The algebra of the entries is commutative, but the block circulant matrix is a matrix over that algebra, and matrix multiplication over a commutative ring need not commute. Let $n_1=n_2=n_4=2$, $n_3=2$, and let $A$ and $B$ have only the first frontal slice nonzero:

$$ A^{(1)}=\begin{pmatrix}1&0\\0&0\end{pmatrix},\quad A^{(2)}=0, \qquad B^{(1)}=\begin{pmatrix}0&0\\1&0\end{pmatrix},\quad B^{(2)}=0. $$

Then the first frontal slice of $A\ast B$ is $A^{(1)}B^{(1)}=0$ and its second slice is zero, so $A\ast B=0$; while the first frontal slice of $B\ast A$ is $B^{(1)}A^{(1)}=\begin{pmatrix}0&0\\1&0\end{pmatrix}\neq0$. The t-product is not commutative, even though every entry commutes with every other. The commutativity of the algebra is used in the idempotent reduction below, not in the commutativity of the product.

Remark (the product is not the Einstein product). The Einstein product of two third-order tensors is a tensor of order four, and it is written by juxtaposition. The t-product of two third-order tensors is a tensor of order three, and it is written $\ast$. At order two the two products coincide with the matrix product; at order three they do not.

The Fourier Reading

Let $\omega=e^{-2\pi i/n_3}$ and let $\widehat A=\mathcal F_3(A)$ be the discrete Fourier transform of $A$ along the third mode,

$$ \widehat A^{(k)}=\sum_{t=1}^{n_3}\omega^{(k-1)(t-1)}A^{(t)},\qquad 1\le k\le n_3. $$

Write $\mathcal F_3$ for the transform and $\mathcal F_3^{-1}$ for its inverse.

The inverse is

$$ A^{(t)}=\frac1{n_3}\sum_{k=1}^{n_3}\omega^{-(t-1)(k-1)}\widehat A^{(k)}. $$

The transform is applied entrywise; it is $\mathbb{B}_{\mathrm{red}}$-linear and it commutes with the algebra multiplication because the coefficients $\omega^{r}$ are complex numbers and therefore central.

Theorem (the transform carries the product to the slicewise product). For compatible $A,B$,

$$ \boxed{\; \widehat{A\ast B}^{(k)}=\widehat A^{(k)}\widehat B^{(k)},\qquad 1\le k\le n_3 \;}, $$

and equivalently

$$ \operatorname{diag}(\widehat{A\ast B})=\operatorname{diag}(\widehat A)\operatorname{diag}(\widehat B), $$

where $\operatorname{diag}(\widehat A)$ is the block diagonal matrix with blocks $\widehat A^{(1)},\dots,\widehat A^{(n_3)}$.

Proof. Let $F$ be the $n_3\times n_3$ matrix $F_{st}=\omega^{(s-1)(t-1)}$, so that $F^{-1}=\frac1{n_3}\overline F$ and $\operatorname{Vec}(\widehat A)=(F\otimes I_{n_1})\operatorname{Vec}(A)$. The block circulant is diagonalised by $F$:

$$ (F\otimes I_{n_1})\operatorname{circ}(A)(F^{-1}\otimes I_{n_2})=\operatorname{diag}(\widehat A). $$

Then

$$ \operatorname{Vec}(\widehat{A\ast B}) =(F\otimes I_{n_1})\operatorname{Vec}(A\ast B) =(F\otimes I_{n_1})\operatorname{circ}(A)\operatorname{Vec}(B) =\operatorname{diag}(\widehat A)(F\otimes I_{n_2})\operatorname{Vec}(B) =\operatorname{diag}(\widehat A)\operatorname{Vec}(\widehat B). $$

The block column on the right is the stack of the products $\widehat A^{(k)}\widehat B^{(k)}$, which is the transform of $A\ast B$.

The inverse form of the product is useful in the algorithms:

$$ A\ast B=\operatorname{Fold}\Bigl(\frac1{n_3}(\overline F\otimes I_{n_1})\operatorname{diag}(\widehat A)\operatorname{diag}(\widehat B)(\mathbf 1\otimes I_{n_4})\Bigr), $$

where $\mathbf 1$ is the $n_3\times1$ column of ones. The identity is the transform of the block circulant definition; the factor $1/n_3$ is the inverse transform, not a normalisation of the product.

Remark (the normalisation). The source uses the $*$-unitary Fourier matrix with entries $n_3^{-1/2}\omega^{(s-1)(t-1)}$ and carries the factors $\sqrt{n_3}$ in the transform. The product is the same; only the normalisation of the intermediate arrays differs. The convention here is the unnormalised transform, so that $\widehat{A\ast B}^{(k)}=\widehat A^{(k)}\widehat B^{(k)}$ without a scalar factor.

The Idempotent Reduction

Write $A=A_{(1)}\Pi_++A_{(2)}\Pi_-$ and $B=B_{(1)}\Pi_++B_{(2)}\Pi_-$, with $\Pi_\pm=\frac12(1\pm j)$ and $\Pi_+\Pi_-=0$, $\Pi_\pm^2=\Pi_\pm$. Since the t-product is $\mathbb{B}_{\mathrm{red}}$-bilinear and the idempotents are orthogonal,

$$ A\ast B=(A_{(1)}\ast B_{(1)})\Pi_++(A_{(2)}\ast B_{(2)})\Pi_-, $$

where the two products on the right are the complex t-products, taken with the same block circulant or Fourier definition over $\mathbb{C}$. Conversely, a complex t-product is the case in which the second idempotent coordinate is zero. The map

$$ A\longmapsto (A_{(1)},A_{(2)}) $$

is therefore, for square tensors, an isomorphism of algebras from $({\mathbb{B}_{\mathrm{red}}}^{n\times n\times n_3},\ast)$ onto the direct product of two copies of $(\mathbb{C}^{n\times n\times n_3},\ast)$; for rectangular tensors it is a bijection that carries every compatible product to the pair of complex products.

Remark (what the commutativity gives). The reduction is componentwise because the algebra is commutative and the idempotents are central. The product is not made commutative by this reduction: each complex t-product is a product of matrices in the transform, and the two matrix products need not commute. The reduction separates the two idempotent coordinates; it does not symmetrise the product.

The Algebraic Laws

Proposition (associativity). For compatible tensors,

$$ \boxed{\; (A\ast B)\ast C=A\ast(B\ast C) \;}. $$

Proof. In the transform, the three factors become $\widehat A^{(k)},\widehat B^{(k)},\widehat C^{(k)}$, and the matrix product is associative. The transform is invertible, so the identity holds in the original variables.

Proposition (distributivity). For compatible tensors,

$$ A\ast(B+C)=A\ast B+A\ast C,\qquad (B+C)\ast D=B\ast D+C\ast D. $$

Proof. The transform is linear and the matrix product is distributive over the algebra.

The product is also associative with the scalar multiplication: $(cA)\ast B=A\ast(cB)=c(A\ast B)$ for $c\in\mathbb{B}_{\mathrm{red}}$.

The identity tensor. Let $\mathrm I\in{\mathbb{B}_{\mathrm{red}}}^{n\times n\times n_3}$ be the tensor whose first frontal slice is the identity matrix $I_n$ and whose other frontal slices are zero:

$$ \mathrm I^{(1)}=I_n,\qquad \mathrm I^{(k)}=0\quad(2\le k\le n_3). $$

Then $\widehat{\mathrm I}^{(k)}=I_n$ for every $k$, and therefore

$$ A\ast\mathrm I=\mathrm I\ast A=A $$

for every $A\in{\mathbb{B}_{\mathrm{red}}}^{n\times n\times n_3}$. The tensor all of whose frontal slices are $I_n$ is not the identity for $n_3\ge2$: its transform has $n_3I_n$ in the first slice and zero in the others.

The inverse. A tensor $A\in{\mathbb{B}_{\mathrm{red}}}^{n\times n\times n_3}$ is invertible if there is $B$ with $A\ast B=B\ast A=\mathrm I$. The inverse is unique: if $B$ and $C$ are inverses, then

$$ B=B\ast\mathrm I=B\ast(A\ast C)=(B\ast A)\ast C=\mathrm I\ast C=C. $$

It is written $A^{-1}$.

Theorem (the invertibility criterion). A square tensor $A\in{\mathbb{B}_{\mathrm{red}}}^{n\times n\times n_3}$ is invertible if and only if every frontal slice $\widehat A^{(k)}$ of its transform is an invertible matrix over $\mathbb{B}_{\mathrm{red}}$, equivalently if and only if both complex matrices $(\widehat A_{(1)})^{(k)}$ and $(\widehat A_{(2)})^{(k)}$ are nonsingular for every $k$. In that case

$$ \widehat{A^{-1}}^{(k)}=(\widehat A^{(k)})^{-1}, $$

that is, the inverse is the inverse transform of the slicewise inverses.

Proof. If $A\ast B=\mathrm I$, then $\widehat A^{(k)}\widehat B^{(k)}=I_n$ for every $k$, so each $\widehat A^{(k)}$ is invertible. Conversely, if each $\widehat A^{(k)}$ is invertible, define $B$ by the inverse transform of the slicewise inverses; then $\widehat{A\ast B}^{(k)}=\widehat A^{(k)}(\widehat A^{(k)})^{-1}=I_n$ for every $k$, so $A\ast B=\mathrm I$, and the same computation on the other side gives $B\ast A=\mathrm I$. Over $\mathbb{B}_{\mathrm{red}}\cong\mathbb{C}\oplus\mathbb{C}$, a matrix is invertible if and only if both of its complex coordinate matrices are invertible.

The inverse is not the entrywise inverse. The set of invertible tensors of a fixed square shape is a group under $\ast$, with identity $\mathrm I$ and inverse $A^{-1}$.

The Conjugate Transpose

The conjugate transpose $A^{\mathsf H}$ is defined in Reduced Biquaternion Tensors as a Vector Space: conjugate the entries, transpose the first two modes, and reverse the order of the frontal slices $2,\dots,n_3$. It is the bar-transpose, not the star of the algebra.

Proposition (the adjoint identity). For compatible $A,B$,

$$ \boxed{\; (A\ast B)^{\mathsf H}=B^{\mathsf H}\ast A^{\mathsf H} \;}. $$

Proof. In the transform, the reversal is exactly what makes the transform of $A^{\mathsf H}$ equal to the slicewise bar-transpose $(\widehat A^{(k)})^{\mathsf H}$. Then

$$ \widehat{(A\ast B)^{\mathsf H}}^{(k)} =\bigl(\widehat A^{(k)}\widehat B^{(k)}\bigr)^{\mathsf H} =(\widehat B^{(k)})^{\mathsf H}(\widehat A^{(k)})^{\mathsf H}, $$

which is the transform of $B^{\mathsf H}\ast A^{\mathsf H}$.

Without the reversal the identity fails for $n_3\ge3$: the conjugate of $\omega$ is $\omega^{-1}$, and the slice order must be reversed to compensate. For $n_3\le2$ the reversal is trivial and the frontal conjugate transpose is the adjoint.

$*$-Unitary and Hermitian tensors. A tensor $U\in{\mathbb{B}_{\mathrm{red}}}^{n\times n\times n_3}$ is $*$-unitary if

$$ U^{\mathsf H}\ast U=U\ast U^{\mathsf H}=\mathrm I, $$

and a tensor $A$ is Hermitian if $A^{\mathsf H}=A$. By the transform criterion, $U$ is $*$-unitary if and only if every $\widehat U^{(k)}$ is a $*$-unitary matrix over $\mathbb{B}_{\mathrm{red}}$, and $A$ is Hermitian if and only if every $\widehat A^{(k)}$ is Hermitian. The two statements follow from the algebra isomorphism of the transform and the preservation of the conjugate transpose.

The Cost

The block circulant definition costs $O(n_3^2n_1n_2n_4)$ operations: the block circulant has $n_3^2$ blocks, and the block product has $n_3^2$ matrix products of size $n_1\times n_2$ by $n_2\times n_4$. The Fourier definition costs

$$ O\bigl(n_1n_2n_3\log n_3+n_2n_4n_3\log n_3+n_3n_1n_2n_4\bigr), $$

the two transforms, the $n_3$ slicewise matrix products, and the inverse transform. For $n_3$ large the Fourier form is the faster one, and it is the form used by the algorithms of the branch. For square $n\times n\times n_3$ tensors the slicewise term is $O(n^3n_3)$ and the transforms are $O(n^2n_3\log n_3)$.

Verification

The identities of this article were recomputed on random tensors of sizes $3\times2\times4$, $2\times3\times4$ and $3\times3\times4$, with at most $36$ entries. The block circulant definition and the Fourier definition agreed to $3.6\times10^{-15}$; the transform identity agreed to $1.3\times10^{-15}$; associativity agreed to $1.4\times10^{-14}$; the distributive law agreed to $5.6\times10^{-15}$; the identity tensor reproduced its argument to $3.0\times10^{-16}$; the two-sided inverse reproduced the identity to $2.8\times10^{-16}$; the adjoint identity held exactly; the idempotent reduction held exactly; and the noncommutativity witness gave $\langle A\ast B\rangle_*^{1/2}=0$ with $\langle B\ast A\rangle_*^{1/2}=1$.

Summary

The t-product of $A\in{\mathbb{B}_{\mathrm{red}}}^{n_1\times n_2\times n_3}$ and $B\in{\mathbb{B}_{\mathrm{red}}}^{n_2\times n_4\times n_3}$ is $A\ast B=\operatorname{Fold}(\operatorname{circ}(A)\operatorname{Vec}(B))$, a tensor of shape $n_1\times n_4\times n_3$. Under the Fourier transform along the third mode it becomes the slicewise matrix product, $\widehat{A\ast B}^{(k)}=\widehat A^{(k)}\widehat B^{(k)}$. The product is associative, distributive and $\mathbb{B}_{\mathrm{red}}$-bilinear, and it is not commutative: the algebra of the entries is commutative, but the block circulant is a matrix over that algebra. The identity has $I_n$ in its first frontal slice and zeros elsewhere; a square tensor is invertible exactly when every transform slice is an invertible matrix over $\mathbb{B}_{\mathrm{red}}$, equivalently when both complex coordinate slices are nonsingular. The conjugate transpose, with the reversal of the slices $2,\dots,n_3$, satisfies $(A\ast B)^{\mathsf H}=B^{\mathsf H}\ast A^{\mathsf H}$; the reversal is what makes the adjoint identity hold. In the two idempotent coordinates the product is the pair of the two complex t-products. The t-product is the matrix product read slice by slice in the Fourier domain, with the third mode coupled by a circular convolution.

Summary of Notation

Symbol Meaning
$A\ast B$ The t-product of $A$ and $B$
$\operatorname{circ}(A)$ The block circulant matrix of the frontal slices of $A$
$\operatorname{Vec}(B)$, $\operatorname{Fold}$ The block column of the frontal slices and its inverse
$\widehat A$ The Fourier transform of $A$ along the third mode
$\widehat A^{(k)}$ The $k$-th frontal slice of the transform
$\omega$ $e^{-2\pi i/n_3}$
$\mathrm I$ The identity tensor, $I_n$ in the first slice and zero elsewhere
$A^{-1}$ The inverse of a square tensor under $\ast$
$A^{\mathsf H}$ The conjugate transpose, with the slices $2,\dots,n_3$ reversed
$A_{(1)},A_{(2)}$ The idempotent coordinates of $A$

Further Reading

  • Cui-E Yu, Xin Liu, Hui Luo and Yang Zhang, "Reduced biquaternion tensors and applications in color video processing", arXiv:2403.01690 (2024). The Ht-product, its transform form and its use in color video processing.
  • Misha E. Kilmer and Carla D. Martin, "Factorization strategies for third-order tensors", Linear Algebra and its Applications 435 (2011) 641–658. The t-product over the reals, the block circulant definition and the Fourier diagonalisation.
  • Z. Qin, Z. Ming and L. Zhang, "Singular value decomposition of third order quaternion tensors", Applied Mathematics Letters 123 (2022) 107597. The quaternion t-product and the slicewise transform.
  • Tamara G. Kolda and Brett W. Bader, "Tensor decompositions and applications", SIAM Review 51 (2009) 455–500. The general tensor operations and the distinction between the tensor product and the transformed products.