Efficient quaternion CUR method for low-rank approximation to quaternion matrix

Peng-Ling Wu, Kit Ian Kou, Hongmin Cai, Zhaoyuan Yu

Abstract

Low-rank quaternion matrix approximation is a critical tool for color image processing, yet traditional approaches are often limited by the high computational cost of Quaternion Singular Value Decomposition (QSVD). This paper introduces QMCUR, an efficient alternative that approximates quaternion matrices by sampling actual rows and columns. By avoiding full decomposition, QMCUR achieves significant speedups while maintaining accuracy comparable to, or even exceeding, traditional methods in tasks such as image compression and completion.

Introduction

In signal and image processing, color images are naturally represented as quaternion matrices. Unlike standard real-valued matrices, quaternions consist of one real part and three imaginary parts ($i, j, k$), which map directly to the Red, Green, and Blue (RGB) channels. This representation is powerful because it preserves the inherent inter-relationships between color channels during processing.

However, the standard tool for low-rank approximation, QSVD, is a major computational bottleneck. It is slow to compute for large-scale data and becomes impractical in iterative algorithms where it must be recalculated frequently. This research addresses the need for a faster "sketching" method that provides high-quality approximations without the overhead of full decomposition.

The QMCUR Method

The proposed Quaternion Matrix CUR (QMCUR) method approximates a quaternion matrix $\mathbf{X}$ as the product of three smaller matrices: $\mathbf{C}$ (selected columns), $\mathbf{R}$ (selected rows), and a small "link" matrix $\mathbf{U}$ calculated to minimize approximation error.

Two primary sampling strategies were evaluated:

  1. QMCUR_length: Rows and columns are selected with a probability proportional to their Euclidean norm, prioritizing the most significant data points.
  2. QMCUR_uniform: Rows and columns are selected at random with equal probability.

Beyond the algorithm itself, the authors provided a rigorous perturbation analysis to prove that the approximation remains stable even when the input data is corrupted by noise. This theoretical foundation ensures reliability in real-world applications where data is rarely perfect.

Figure 2: Comparison of relative error and running time between QMCUR variants and QSVD across different noise levels (sigma) and matrix dimensions.

Experimental Results

The researchers tested QMCUR using synthetic data, the Set27 dataset for compression, and the Kodak PhotoCD dataset for image recovery.

Speed and Scalability

As shown in the performance plots, QMCUR is significantly faster than QSVD. While QSVD's computational cost grows sharply with matrix dimension $m$, the running time for QMCUR variants remains relatively flat. This efficiency makes it ideal for large-scale applications.

Accuracy and Noise Stability

Despite being a randomized approximation, QMCUR maintains high accuracy. In many scenarios, particularly under noisy conditions, the QMCUR_uniform strategy performed surprisingly well, sometimes outperforming the more complex length-based sampling. The method's stability is further confirmed by comparing actual error against the theoretical error bound as noise levels increase.

Figure 3: Error of the QMCUR approximation compared to the theoretical error bound as the spectrum norm of noise increases.

Image Recovery and Compression

In practical tests on the Kodak dataset, QMCUR achieved higher Peak Signal-to-Noise Ratio (PSNR) and Structural Similarity Index (SSIM) scores than several state-of-the-art methods. For image compression, it provided lower relative error than QSVD when the target rank was appropriately selected, proving that it is not just a faster method, but a high-fidelity one.

Conclusion

The QMCUR method offers a robust and efficient framework for quaternion matrix approximation. By leveraging data-driven sampling rather than abstract basis vectors, it preserves the structure of color images while drastically reducing computational time. Future work may focus on adaptive rank estimation and applying this framework to other quaternion-based domains like 3D motion tracking and seismic data analysis.

Summary updated

BibTeX
@inproceedings{wu2024efficient,
  author = {Peng-Ling Wu and Kit Ian Kou and Hongmin Cai and Zhaoyuan Yu},
  title = {{Efficient quaternion CUR method for low-rank approximation to quaternion matrix}},
  booktitle = {Numer. Algorithms},
  year = {2024},
  url = {https://openreview.net/forum?id=cKsKAbywoB},
}
Figure