Source-linked AI summary
A Fast Algorithm for Quaternion Tensor Singular Value Decomposition under the T-product
Daochang Zhang, Yue Zhao, Jingqian Li
TL;DR
An unrestricted quaternion matrix SVD can fail to preserve the paired Fourier-block structure needed for tensor factor recovery. The paper constructs a structure-preserving correction and fast algorithm; experiments report reduced decomposition time with near-machine-precision accuracy.
Problem
An unrestricted quaternion matrix SVD need not preserve the paired Fourier-block structure required to recover quaternion tensor factors.
Source: §1 · p. 2, §3.1 · p. 5Method
The paper complexifies paired quaternion blocks, computes complex SVD factors, and maps them back to quaternion factors that preserve the required structure.
Source: §3.1 · p. 5, §3.2 · p. 8Results
1.48–5.13× speedups were reported for Algorithm 2, which maintained comparable numerical accuracy over tested sizes, with near-machine-precision errors.
Source: §4.3 · p. 11Takeaways & Limitations
The corrected construction yields tensor reconstruction and T-unitarity errors at machine precision, while the unrestricted construction has T-product reconstruction error of order one and fails T-unitarity.
Source: §4.1 · p. 10
Abstract
from arXiv · showhide
Quaternion tensor singular value decomposition (T-SVD) under the T-product provides a framework for analyzing multidimensional quaternion data. However, the T-SVD construction of Pan and Ng (SIAM J. Matrix Anal. Appl., 2024) \cite{PanNg2024} contains a structural gap: an unrestricted quaternion matrix SVD need not preserve the paired Fourier block structure required for tensor factor recovery, potentially leading to loss of T-unitarity and inaccurate reconstruction. To address this issue, we develop a structure-preserving construction that transforms each paired quaternion block into a complex matrix and maps its complex SVD factors back to quaternion factors with the required structure. This construction corrects the proof of \cite[Theorem 4]{PanNg2024} and leads to a corrected version of \cite[Algorithm 2]{PanNg2024}, hereafter referred to as the ``corrected algorithm'', ensuring T-unitary tensor factors and an f-diagonal core for arbitrary third-order quaternion tensors. A numerical counterexample demonstrates the failure of \cite[Algorithm 2]{PanNg2024} and verifies the corrected algorithm at machine precision. Notably, we propose a fast structure-preserving algorithm, Algorithm~\ref{alg:t-fast}, and compare it numerically with the corrected algorithm. The experimental results show that Algorithm~\ref{alg:t-fast} reduces the decomposition time while maintaining near-machine-precision accuracy. Furthermore, its application to color video encryption yields high reconstruction quality, favorable ciphertext statistics, and stability under input perturbations.
1. Introduction
Quaternion tensors represent multichannel and multidimensional data while retaining spatial and temporal structure. The paper identifies a structural gap in an existing quaternion T-SVD construction and develops a structure-preserving correction.
1. Introduction
- Quaternion tensors extend quaternion representations of multichannel data to multidimensional data without unfolding away spatial and temporal structure.The three imaginary quaternion components can jointly encode an image’s RGB channels.Source: §1 · p. 1
- An unrestricted quaternion matrix SVD may break the paired Fourier-block relations needed to recover tensor factors, so valid matrix factors need not yield block-circulant tensor factors.The issue affects the proof and corresponding algorithm in Pan and Ng.Source: §1 · p. 2
- The paper corrects the T-SVD construction and presents numerical examples, a fast algorithm comparison, and an application to color video encryption and recovery.The reported evaluations include reconstruction, T-unitarity, computational time, ciphertext statistics, differential sensitivity, and stability under input perturbations.Source: §1 · p. 2
2. Preliminaries
The preliminaries set out quaternion notation and the tensor and Fourier representations used in the subsequent T-SVD construction.
2. Preliminaries
- A quaternion is decomposed into real and three imaginary components; the preliminaries define its conjugate and modulus and distinguish pure and unit quaternions.Orthogonality of pure quaternions is defined using the Euclidean inner product of their imaginary coefficient vectors.Source: §2 · p. 2
- Using an orthogonal unit-pure-quaternion basis, each quaternion has a unique Cayley–Dickson representation as two complex components.The tensor representation is A = Ad + Acα, with complex tensors Ad and Ac.Source: §2 · pp. 2–3
- The block-circulant matrix bcirc(A) is formed from the tensor’s frontal slices, and its first block column uniquely determines A.The unfold operation stacks the frontal slices; fold is its inverse.Source: §2 · p. 3
- The quaternion discrete Fourier transform supplies a frequency-domain representation of quaternion block-circulant matrices.The text identifies the quaternion Fourier matrix as unitary.Source: §2 · p. 3
3. Quaternion T-SVD and Its Computational Algorithm
The paper characterizes the paired Fourier-block structure required for tensor recovery, then constructs a quaternion T-SVD and an FFT-based algorithm that preserve it.
3.1. Quaternion T-SVD
- The earlier unrestricted quaternion SVD can yield valid matrix factors that violate the paired block structure, preventing their general recovery as tensor factors.In particular, it does not ensure the required complex-field membership of diagonal and off-diagonal blocks.Source: §3.1 · pp. 4–5
- A complexification procedure preserves the paired structure and completes the proof of a T-SVD for every third-order quaternion tensor.The resulting decomposition has T-unitary tensor factors and an f-diagonal core.Source: §3.1 · pp. 5, 7
- For paired frequency indices, the construction takes a complex SVD and maps its factors back to quaternion factors with the required block structure.The paired blocks are handled together, while self-paired indices use a quaternion matrix SVD.Source: §3.1 · pp. 5–6
3.2. Computational Algorithm
- The constructive proof yields a block-circulant implementation and an equivalent FFT-based implementation that reduces computational cost.The FFT route avoids explicitly forming and manipulating the block-circulant matrix while computing the same T-SVD.Source: §3.2 · pp. 7–8
- The FFT algorithm computes paired blocks using small complex matrix SVDs and stores their factors to preserve the paired structure.It recovers the tensor factors by inverse Fourier transforms, without explicitly forming block-circulant matrices or Kronecker products.Source: §3.2 · p. 8
4. Numerical examples
The numerical examples show that preserving paired Fourier-block structure is essential for valid tensor-factor recovery, while the tested fast implementation reduces decomposition time with comparable numerical accuracy. The experiments compare the two implementations on random quaternion tensors and quantify the structural failure and correction.
4.1. Example 1
- The unrestricted SVD factors lacked the paired block structure, so their inverse Fourier transforms could not be identified as block-circulant tensor factors.The corrected construction converted the paired quaternion block to a complex matrix, computed its complex SVD, and mapped the factors back with the required structure.Source: §4.1 · pp. 9–10
- The unrestricted quaternion SVD produced a T-product reconstruction error of 1.2166 and T-unitarity errors of 7.0711 × 10^-1, while the corrected construction’s errors were near machine precision.Both constructions reproduced the matrix factorization to machine precision, showing that matrix-level accuracy alone did not ensure valid tensor recovery.Source: §4.1 · p. 10
4.2.1. Experimental Setup
- The benchmark tested 16 tensor sizes selected as round(linspace(4,512,16)); one tensor per size was shared by both implementations, each run twice in reversed order, with times averaged.Decomposition timing included forward FFTs, matrix SVDs, and inverse FFTs; input generation, reconstruction-error evaluation, and file output were excluded.Source: §4.2.1 · pp. 10–11
4.3. Results and discussion
- Relative reconstruction errors were 3.7430 × 10^-15–3.5974 × 10^-14 for Algorithm 2 versus 2.3296 × 10^-15–6.6910 × 10^-15 for the QTFM-based implementation.At n = 512, the corresponding errors were 2.7778 × 10^-14 and 6.6910 × 10^-15.Source: §4.3 · p. 11
- Algorithm 2 was 1.48–5.13 times faster than the QTFM-based implementation across tested sizes while maintaining comparable numerical accuracy.The reported reconstruction errors were near machine precision for both implementations.Source: Figure 1 · p. 11, §4.3 · p. 11
5. Applications to Color Video Processing
This application evaluates quaternion-tensor encryption and recovery on two DAVIS 2017 videos using reconstruction, ciphertext-statistics, and perturbation-stability measures.
5. Applications to Color Video Processing
- The application uses 50-frame kite-surf and 75-frame boat sequences, resizing each RGB frame to 256 × 256 after conversion to double precision with values in [0, 1].Both sequences are from the DAVIS 2017 TrainVal 480p dataset.Source: §5 · p. 11
5.1. Encryption, Recovery, and Evaluation Metrics
- For each frontal slice, imaginary components of S are min–max scaled and 8-bit quantized, XOR-masked and Arnold-permuted, then decrypted, rescaled, and recombined; quantization makes recovery generally lossy.Components with ranges smaller than machine epsilon are encoded as zero, and their minima and maxima are retained for rescaling.Source: §5.1 · p. 12
5.2. Reconstruction Quality and Ciphertext Statistics
- Relative decomposition errors were below 9 × 10−15; kite-surf and boat reconstruction reached PSNR 62.3858 and 63.8569 dB, and SSIM 0.999738 and 0.999810, respectively.Table 1 reports scores averaged over all frames; the quantized integer arrays were recovered exactly, with component quantization accounting for remaining reconstruction discrepancy.Source: §5.2 · p. 12, Table 1 · p. 12
- Encrypted distributions were approximately uniform, while horizontal R-channel correlations fell from 0.982162/0.975509 to −0.015782/−0.015349 for kite-surf/boat.The histogram comparison is at frame 25; the correlation analysis samples 3000 horizontal pixel pairs at identical locations.Source: §5.2 · p. 13, Figure 3 · p. 14, Figure 4 · p. 14
- NPCR and UACI were close to the 99.6094% and 33.4635% independent-uniform-8-bit references after a single plaintext-value perturbation.The results show that this perturbation propagates throughout the ciphertext under the tested setting.Source: §5.2 · p. 13, Table 2 · p. 13
5.3. Stability under Input Perturbations
- Across all six cases, |∆P| was below 0.006 dB and |Sout − Sin| below 5.1 × 10−4, indicating little added distortion beyond that in perturbed inputs.The experiments test pre-encryption input perturbations, not ciphertext corruption.Source: §5.3 · p. 15, Table 3 · p. 15
Funding
The first author received support from three named funding programs.
Funding
- The first author was supported by NSFC, China Postdoctoral Science Foundation, and Jilin Province research-program funding.The passage lists grant numbers 11901079, 2021M700751, JJKH20190690KJ, JJKH20220091KJ, and JJKH20250851KJ.Source: Funding · p. 15