TL;DR
This paper introduces a novel block-diagonalization technique for quaternion circulant matrices using a permuted discrete quaternion Fourier transform. This method allows for efficient computation of quaternion circulant matrix inverses and forms the basis for a new quaternion tensor singular value decomposition (QT-SVD), which shows promise in applications like color video reconstruction.
What Problem Does This Paper Address?
Quaternion circulant matrices, while analogous to complex circulant matrices, pose a challenge because they cannot be directly diagonalized by a standard discrete quaternion Fourier transform due to the non-commutative nature of quaternions. This limitation hinders efficient computation of their inverses and related matrix operations. Furthermore, extending tensor decomposition techniques like T-SVD to the quaternion domain is crucial for processing quaternion-valued data, such as color images and videos, which are naturally represented by quaternion tensors.
Methods
The core contribution is the block-diagonalization of quaternion circulant matrices. Instead of full diagonalization, the authors show that these matrices can be transformed into a block-diagonal form consisting of 1x1 and 2x2 blocks. This is achieved by using a permuted discrete quaternion Fourier transform matrix and leveraging a three-axis system representation of quaternions (μ, α, β). This block-diagonal structure is then used to derive an efficient algorithm for computing the inverse of quaternion circulant matrices in O(n log n) operations.
Building on this, the paper extends these concepts to quaternion tensor singular value decomposition (QT-SVD). The authors adapt the t-product framework for quaternion tensors and propose a QT-SVD that leverages the block-diagonalization of quaternion circulant matrices. This allows for efficient computation of the QT-SVD by applying quaternion Fourier transforms along the "tubes" of the tensor.
Datasets
The paper uses synthetic data for testing quaternion circulant matrix inverse computations and linear prediction of quaternion signals. For the application in color image reconstruction, the authors use a "Mobile" YUV sequences video dataset, which contains 300 frames, each being a 144x176 RGB image represented as a pure quaternion tensor.
Key Insights and Ideas
- Quaternion circulant matrices are not fully diagonalizable by standard QFTs: This is a fundamental difference from complex circulant matrices and necessitates new approaches.
- Block-diagonalization is the key: Transforming quaternion circulant matrices into a block-diagonal form (1x1 and 2x2 blocks) unlocks efficient computational methods.
- Permuted QFT is crucial: The use of a permuted discrete quaternion Fourier transform is essential for achieving this block-diagonal structure.
- QT-SVD offers advantages for quaternion data: The proposed QT-SVD method demonstrates superior performance in capturing spatial-shift correlations and reconstructing color video data compared to existing methods.
- Efficiency gains: The block-diagonalization leads to O(n log n) complexity for quaternion circulant matrix inversion, significantly outperforming standard methods.
Key Results
- An efficient algorithm for computing the inverse of quaternion circulant matrices with O(n log n) complexity is presented. This method is shown to be faster and more accurate than standard MATLAB inverse functions.
- The proposed Quaternion Tensor Singular Value Decomposition (QT-SVD) is applied to color video reconstruction. Experimental results show that QT-SVD achieves higher PSNR and SSIM values compared to FT-QTF, t-QSVD, and standard T-SVD, particularly for higher rank approximations.
- The QT-SVD method demonstrates better reconstruction quality, capturing finer details and more accurate colors in the reconstructed video frames.
Limitations and Future Work
- Octonion limitations: The paper briefly mentions an alternative approach using octonions for diagonalizing quaternion circulant matrices but notes that the non-associative nature of octonions leads to computational issues.
- Computational cost of QT-SVD: While QT-SVD shows superior reconstruction quality, it requires more computational time than FT-QTF and t-QSVD, which is attributed to the slower quaternion SVD used in its implementation. The authors suggest exploring faster quaternion SVD methods to improve efficiency.
- Future work: The authors suggest applying the developed block-diagonalization results to quaternion Toeplitz systems and further exploring the QT-SVD for various image and signal processing tasks. They also mention the potential for designing parallel quaternion SVD algorithms.
Summary updated