The Multi-Symplectic Lanczos Algorithm and Its Applications to Color Image Processing

Zhigang Jia, Xuan Liu, Meixiang ZhaoarXiv 2020 · DOI · arXiv

Abstract

Low-rank approximations are essential for modern mathematical models in data science, yet a persistent challenge remains: ensuring these approximations inherit the original structural properties of the data. This paper introduces a novel multi-symplectic method based on Lanczos bidiagonalization designed to compute partial singular triplets of JRS-symmetric matrices. By preserving intrinsic multi-symmetry, this algorithm reconstructs optimal low-rank approximations for color images and videos. Utilizing augmented Ritz and harmonic Ritz vectors for implicit restarting, the method efficiently calculates both the largest and smallest singular triplets. Experimental results in color face recognition and video reconstruction demonstrate that this approach significantly outperforms state-of-the-art algorithms in both speed and accuracy.

Introduction

In the era of big data, low-rank approximations serve as a cornerstone for data compression, noise reduction, and feature extraction. By simplifying massive datasets into their most essential components, researchers can process information more efficiently. However, when dealing with color images, standard approximation techniques often falter. Traditional methods typically treat Red, Green, and Blue (RGB) channels as independent layers or flatten them into a single matrix, a process that ignores the vital cross-channel correlations inherent in color data.

To address this, researchers have turned to quaternions—four-dimensional numbers—to represent pixels, effectively linking the color channels. While quaternion-based Singular Value Decomposition (SVD) is mathematically superior for this task, it is computationally expensive for large-scale data. Iterative methods like the Lanczos algorithm offer a faster alternative, but they often suffer from "structural drift," where the iterative process gradually loses the underlying algebraic symmetry of the quaternion data. This paper presents the Multi-Symplectic Lanczos (MSL) algorithm, a structure-preserving approach that maintains the integrity of color data throughout the computation.

Methodology: Multi-Symplectic Lanczos Bidiagonalization

The core innovation of this research is the Multi-Symplectic Lanczos (MSL) Bidiagonalization method. This algorithm operates on JRS-symmetric matrices, which are the real-number counterparts of quaternion matrices. By working within this real representation, the algorithm avoids the heavy computational overhead of complex quaternion arithmetic while retaining all its structural benefits.

Key Technical Components

  • Multi-Symplectic Transformations: The algorithm employs specialized mathematical rotations that ensure JRS-symmetry is preserved at every iteration. This prevents the numerical drift that plagues standard Lanczos implementations.
  • Implicit Restarting: To manage memory constraints and improve convergence, the authors implement an implicit restarting mechanism. This allows the algorithm to focus on the most relevant data without storing the entire history of the iteration.
  • Ritz Vector Optimization: The method utilizes augmented Ritz vectors to identify the $k$ largest singular values (representing the primary structure of an image) and harmonic Ritz vectors to find the $k$ smallest singular values (often associated with high-frequency details or noise).

Experimental Evaluation

The MSL algorithm was evaluated against several state-of-the-art tools, including irlba and lansvdQ, across diverse datasets:

  1. Sparse and Synthetic Matrices: Testing on Matrix Market sparse matrices (e.g., bcspwr10, af23560) and synthetic dense matrices proved the algorithm's robustness in handling large-scale JRS-symmetric structures.
  2. Color Face Recognition: Using the Georgia Tech Face Database, the MSL method was integrated into Color Principal Component Analysis (CPCA). It achieved high recognition accuracy while requiring significantly less computational time than existing models.
  3. Video Compression and Reconstruction: The algorithm was applied to color videos (yunlonglake.mp4 and children.mov). In these tests, the MSL variants (specifically irlbaMS) reconstructed frames with higher fidelity and lower residuals than standard methods.

Key Insights

  • Stability through Symmetry: Forcing the algorithm to respect JRS-symmetry does more than preserve mathematical purity; it enhances numerical stability. Because the algorithm is constrained to the correct algebraic space, it converges on solutions in fewer iterations.
  • Precision in the Small-Scale: Unlike many algorithms that struggle to identify the smallest singular values, the MSL method provides a reliable path to these values. This is particularly useful for denoising applications where the "noise" is embedded in the smallest singular triplets.
  • Efficiency of Real Representations: The research demonstrates that high-level quaternion results can be achieved using optimized real-number linear algebra libraries, making the method highly practical for real-world deployment.

Conclusion

The Multi-Symplectic Lanczos algorithm represents a significant advancement in structured numerical linear algebra. By bridging the gap between the theoretical elegance of quaternions and the practical necessity of high-speed computation, the authors have provided a powerful tool for color image and video processing. Future research may extend this multi-symplectic framework to other structured matrices, potentially benefiting fields such as hyperspectral imaging and complex signal processing.

Summary updated

Abstract

Low-rank approximations of original samples are playing more and more an important role in many recently proposed mathematical models from data science. A natural and initial requirement is that these representations inherit original structures or properties. With this aim, we propose a new multi-symplectic method based on the Lanzcos bidiagonalization to compute the partial singular triplets of JRS-symmetric matrices. These singular triplets can be used to reconstruct optimal low-rank approximations while preserving the intrinsic multi-symmetry. The augmented Ritz and harmonic Ritz vectors are used to perform implicit restarting to obtain a satisfactory bidiagonal matrix for calculating the $k$ largest or smallest singular triplets, respectively. We also apply the new multi-symplectic Lanczos algorithms to color face recognition and color video compressing and reconstruction. Numerical experiments indicate their superiority over the state-of-the-art algorithms.
BibTeX
@misc{jia2020multi,
  author = {Zhigang Jia and Xuan Liu and Meixiang Zhao},
  title = {{The Multi-Symplectic Lanczos Algorithm and Its Applications to Color Image Processing}},
  year = {2020},
  eprint = {2005.01299},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.01299},
}
Figure