Block Diagonalization of Block Circulant Quaternion Matrices and the Fast Calculation for T-Product of Quaternion Tensors

With quaternion matrices and quaternion tensors being gradually used in the color image and color video processing, the block diagonalization of block circulant quaternion matrices has become a key issue in the establishment of T-product based methods for quaternion tensors. Out of this consideration, we aim at establishing a fast calculation approach for the block diagonalization of block circulant quaternion matrices with the help of the fast Fourier transform (FFT). We first show that the discrete Fourier matrix \(\mathbf {F_p}\) cannot diagonalize \(p\times p\) circulant quaternion matrices, nor can the unitary quaternion matrices \(\mathbf {F_p}\textbf{j}\) and \(\mathbf {F_p}(1+\textbf{j})/\sqrt{2}\) with \(\textbf{j}\) being an imaginary unit of quaternion algebra. Then we prove that the unitary octonion matrix \(\mathbf {F_p}\textbf{p}\) with \(\textbf{p}=\textbf{l},\textbf{il}\) or \((\textbf{l}+\textbf{il})/\sqrt{2}\) (\(\textbf{l}, \textbf{il}\) being imaginary units of octonion algebra) can diagonalize a circulant quaternion matrix of size \(p\times p\), which further means that a block circulant quaternion matrix of size \(mp\times np\) can be block diagonalized at the cost of \(O(mnp\log p)\) via the FFT. As one of applications, we give a fast algorithm to speed up the calculation of the T-product between \(m\times n\times p\) and \(n\times s\times p\) third-order quaternion tensors via FFTs, whose computational magnitude is almost 1/p of the original one. As another application, we propose an effective compression strategy for third-order quaternion tensors with a certain low-rankness. Simulations on the color image and color video compression demonstrate that our compression strategy with no QSVD involved, can achieve higher quality compression in terms of PSNR values at much less time costs, compared with the QSVD-based methods.

We do not analyse or generate any data sets, because our work proceeds within a theoretical and mathematical approach.

1. In [17], the tubal-scalars of \(\mathcal {S}\) are called eigentuples of tensor \(\mathcal {A}\). For more relevant studies on the eigentuples and the corresponding eigenmatrices, the linear combinations with tubal-scalars, tensor polynomials and the computation of tensor eigendecomposition for third-order tensors, based on the T-product algebra and the diagonalization theory of circulant matrices, please see [17] for reference.

2. The Matlab command \(svd(\hat{\mathcal {A}}(:,:,r),k)\) means to compute the first k largest singular values for each matrix \(\hat{\mathcal {A}}(:,:,r)\).

3. It can be seen that when the quaternion tensor truncation problem for tensor \(\mathcal {A}\) degenerates to the real case, the term “\((\mathbf {P_p}\otimes \mathbf {I_m})unfold(\overline{\hat{\mathcal {A}}_k^{(1,\textbf{i})}})\)” in the 5-th line of Algorithm 5.2 becomes “\(unfold({\hat{\mathcal {A}}_k^{(1,\textbf{i})}})\)” as a result of the conjugate symmetry of the fourier transform performing on real numbers (please see the reference [17] by Kilmer, Braman, Hao and Hoover in 2013), which implies that our method provided by Algorithm 5.2 reduces to the classic truncated approximation strategy for third-order real tensors given in reference [18], i.e. Algorithm 2.2.

4. The MATLAB code can be downloaded from https://hkumath.hku.hk/\(\sim \)mng/mng_files/LANQSVDToolbox.zip.

5. It can be seen that in the compression for quaternion tensor \(\overrightarrow{\mathcal {M}}\), there are mainly Fourier transform and vector norm computations involved in Algorithm 5.2. So, we refer our method here to as Fourier transform based quaternion vector norm (FT-QVN) method.

6. It is observed that this way of real tensor construction achieves the best performance for color image processing [22].

7. http://trace.eas.asu.edu/yuv/.

8. It is easy to see that the FT-QSVD method is equivalent to the FT-QTF method given in [26] without theoretical proof. So, the proof in Subsection 5.2 provides theoretical analysis for the FT-QTF method.

The authors would like to thank anonymous referees for their valuable comments and suggestions that helped us to improve the quality of this paper. This work is supported by National Natural Science Foundations of China (Grant No.12371315), the Natural Science Foundation of Hunan Province, China (Grant No.2022JJ40543) and China Postdoctoral Science Foundation (Grant No.2021MD703978).

Authors and Affiliations

1. School of Mathematics, North University of China, Taiyuan, 030051, Shanxi, China

   Meng-Meng Zheng

2. Department of Mathematics, National University of Defense Technology, Changsha, 410073, Hunan, China

   Guyan Ni

Corresponding author

Correspondence to Guyan Ni.

Conflict of interest

The authors declare no conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Here, we provide the proofs of Proposition 4.1, Proposition 4.2, Theorem 5.1 and Theorem 5.3.

A.1. Proof of Proposition 4.1:

Proof. (i) From the octonion multiplication rules in Table 2, it can be seen that if \(u\in \{\textbf{l},\textbf{il},\textbf{jl},\textbf{kl}\}\), then \((p+q\textbf{j})u=u\overline{(p+q\textbf{j})}=u(\bar{p}-q\textbf{j}).\) Thus, it can be deduced

(ii) From the octonion multiplication rules in Table 2, it follows that

Thus, it can be deduced \((p\textbf{l})\cdot q\cdot (r\textbf{l})=-p\bar{q}\bar{r}=[p(\textbf{jl})]\cdot q\cdot [r(\textbf{jl})].\)

(iii) Similar to the proof of (ii), from Table 2, we can obtain that

thus, it follows that \((p\textbf{l})\cdot (q\textbf{j})\cdot (r\textbf{l})=pq\bar{r}\textbf{j}=[p(\textbf{jl})]\cdot (q\textbf{j})\cdot [r(\textbf{jl})].\)

(iv) Similarly, from Table 2, we can obtain that

thus, it follows that \((p\textbf{l})\cdot q\cdot [r(\textbf{jl})]=\bar{p}q\bar{r}\textbf{j}=-[p(\textbf{jl})]\cdot q\cdot (r\textbf{l}).\)

(v) Similarly, from Table 2, we can obtain that

thus, it follows that \((p\textbf{l})\cdot (q\textbf{j})\cdot [r(\textbf{jl})]=\bar{p}\bar{q}\bar{r}=-[p(\textbf{jl})]\cdot (q\textbf{j})\cdot (r\textbf{l}).\) \(\square \)

A.2. Proof of Proposition 4.2:

Proof. (i) From Proposition 4.1, it follows that

Noting that \(p,q,r,s\in \mathbb {C}\), thus we have that

(ii) From Proposition 4.1 (i) and (ii), it follows that

By the octonion multiplication rules shown in Table 2, we can obtain that

From Proposition 4.1 (i) and (iii), it follows that

By the octonion multiplication rules shown in Table 2, we can obtain that

Hence, it follows that

In addition, by the octonion multiplication rules shown in Table 2, it is similar to obtain that (iii), (iv), (v) and (vi) hold. \(\square \)

A.3. Proof of Theorem 5.1:

Proof. To show that (5.2) holds, we only need to prove that

From Theorem 4.4 and (5.1), it follows that

Then by Proposition 4.2 (iii), (iv) and (7.2), it follows that

By Proposition 4.2 (iii), (iv) and (7.3), it follows that

By a similar proof as [20, Lemma 2.3], we can obtain that the following property holds for quaternion tensors \(\mathcal {A}\) and \(\mathcal {B}\), that is:

Thereby, from (7.4), (7.5) and (7.6), it is deduced that

By (4.1) and (2.4), it is easy to see \(\mathbf {{P}_{p}}=\mathbf {F_{p}}\mathbf {F_{p}}=\mathbf {F^*_{p}}\mathbf {F^*_{p}} =-(\mathbf {F_{p}}\textbf{l})(\mathbf {F^*_{p}}\textbf{l}) =-(\mathbf {F^*_{p}}\textbf{l})(\mathbf {F_{p}}\textbf{l})\in \mathbb {R}^{p\times p}\) and

Denote \(\hat{\textbf{A}_1}={Diag}(\hat{\mathcal {A}}^{(1,\textbf{i})}),\hat{\textbf{A}_2}={Diag}(\hat{\mathcal {A}}^{(\textbf{j},\textbf{k})}), \hat{\textbf{B}_1}={Diag}(\hat{\mathcal {B}}^{(1,\textbf{i})}),\;\text{ and }\;\hat{\textbf{B}_2}={Diag}(\hat{\mathcal {B}}^{(\textbf{j},\textbf{k})}).\) Then, from Proposition 4.2 (i), (v), (vi) and (7.8), it follows

From Proposition 4.2 (ii), (v), (vi) and (7.8), it follows

From Proposition 4.2 (i), (v), (vi) and (7.8), it follows

From Proposition 4.2 (ii), (v) and (vi), it follows

Thus, by (7.7), (7.9), (7.10), (7.11), (7.12), (7.2) and (7.3), we obtain that

i.e., (7.1) holds. \(\square \)

A.4. Proof of Theorem 5.3:

Proof. From \(\hat{\mathcal {A}}=\textrm{fft}(\overline{\mathcal {A}},[\;],3)\), it follows that

By Lemma 5.2, it follows from (5.10) that \(\hat{\mathcal {A}_k}=\textrm{fft}(\overline{\mathcal {A}_k},[\;],3)\), thus

Furthermore, Since \(\mathbf {F_p}\otimes \mathbf {I_m}\) is unitary, it follows that

Assume that \(\widetilde{\mathcal {A}}\in M\), then there exist \(\mathcal {X}\in \mathbb {Q}^{m\times k\times p}\), \(\mathcal {Y}\in \mathbb {Q}^{k\times n\times p}\) such that

where \(\widetilde{\mathcal {A}}=\widetilde{\mathcal {A}}_1+\widetilde{\mathcal {A}}_2\textbf{j}\) with \(\widetilde{\mathcal {A}}_1\), \(\widetilde{\mathcal {A}}_2\in \mathbb {C}^{m\times n\times p}\). Then similar to (7.13), we can obtain that

For every \(i\in [p]\), denote the QSVD of \(\mathcal {X}(:,:,i) \mathcal {Y}(:,:,i)\) as

then it follows from \(\mathcal {X}\in \mathbb {Q}^{m\times k\times p}\) and \(\mathcal {Y}\in \mathbb {Q}^{k\times n\times p}\) that \(\widetilde{\mathcal {S}}(k+1:m,k+1:n,i)=0\). Hence, it is deduced that

which, together with (7.13), implies that \(\mathcal {A}_k=argmin_{\widetilde{\mathcal {A}}\in M}||\mathcal {A} -\widetilde{\mathcal {A}}||_F\). \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions