1 Introduction

Quaternion [1] as a mathematical concept was originally introduced by Hamilton in 1843. As an extension of complex numbers, a quaternion number consists of one real part and three imaginary parts. A quaternion matrix is a generalization of a complex matrix in quaternion algebra. By now, quaternions and quaternion matrices have widely used in signal processing [2, 3], machine learning [4, 5], color image processing [6, 7], and other fields [8, 9]. By encoding the red, green, and blue channel pixel values of a color image on the three imaginary parts of quaternion matrix, this method perfectly fits the color image structure and effectively preserves the inter-relationship between the color channels [10].

As an emerging mathematical tool, low-rank quaternion matrix approximation (LRQA) has attracted much attention in the field of color image processing, such as color face recognition [11], color image inpainting [12,13,14,15], and color image denoising [16, 17]. For instance, Chen et al. [18] proposed the quaternion nuclear norm-based LRQA for color image denoising and inpainting. This method fully utilizes the high correlation among RGB channels by extending low-rank matrix approximation into the quaternion domain. Yu et al. [19] further extended the weighted nuclear norm minimization (WNNM) into the quaternion domain and proposed the quaternion-based WNNM method for color image restoration. Notably, the work [20] proposed the robust quaternion matrix completion to minimize the nuclear norm and \(l_1\)-norm. This approach provides an exact recovery guarantee under certain conditions and shows superior performance for color image recovery. Moreover, Jia et al. [21] introduced the patch group-based nonlocal self-similarity (NSS) prior scheme to learn explicit NSS models, and subsequently offered the NSS-based quaternion matrix completion (QMC) algorithm to reconstruct color images, leading to a promising result. Furthermore, they extended this approach to tensor NSS-based QMC for color videos inpainting. Additionally, in [22], the authors employed quaternion logarithmic norm to achieve a more accurate low-rank approximation. However, a key limitation of these methods for generating low-rank quaternion matrix approximation is that they need to compute the quaternion singular value decomposition (QSVD) in each iteration and suffer from computational deficiency, especially for large-scale data.

In addition to rank minimization, recent studies have utilized quaternion matrix decomposition and randomized techniques to improve the performance of LRQA [13, 23]. For instance, Miao et al. [24] suggested the matrix factorization for the target quaternion matrix, followed by three quaternion-based bilinear factor matrix norm factorization methods for low-rank quaternion matrix completion, which can avoid expensive calculations. Liu et al. [25] presented a randomized QSVD algorithm for low-rank matrix approximation. The randomized QSVD algorithm reduces the computational cost compared to traditional QSVD for large-scale data. Is there any method with lower computational cost for low-rank approximation of a quaternion matrix?

In recent years, the matrix CUR (MCUR) method [26,27,28] for fast low-rank approximation of real matrices has been actively investigated because of its ability to efficiently handle large-scale problems. The MCUR method approximates a low-rank matrix by directly sampling a subset of columns and rows from the original matrix and representing it as a product of three small-scale matrices. Owing to the random column/row selection strategy, the MCUR decomposition shows great potential for reducing the computational costs and preserving the properties of the original data matrix compared with other methods [29, 30].

To further enhance the approximation performance and boost the computational efficiency of LRQA, we consider the efficient quaternion matrix CUR (QMCUR) method for low-rank approximation. Precisely, the QMCUR approximation of a quaternion matrix is obtained by utilizing the actual rows and columns of the original quaternion matrix. Additionally, we employ two different sampling strategies to sample the above-selected columns and rows. In summary, the introduction of the QMCUR approximation and the utilization of sampling strategies offer promising avenues for achieving low-rank approximation. The main contributions of this paper are twofold:

  • We consider the QMCUR method for low-rank approximation of a quaternion matrix. This approach helps to reduce computational costs and improve the precision of low-rank approximation.

  • The perturbation error bound of the proposed approximation method is studied and demonstrated under the spectral norm. We also employ the QMCUR method to color image recovery problem and develop an algorithm to solve it.

  • Experimental results for synthetic data and color images demonstrate that the proposed QMCUR approximation method achieves a substantial speed-up while maintaining accuracy compared with other methods.

The rest of the paper is organized as follows. The main notation and preliminary for quaternions are presented in Section 2. Section 3 gives the details of the proposed quaternion CUR approximation method and perturbation error bound, and presents the QMCUR method for color image recovery. We provide numerical experiments in Section 4. Finally, some concluding remarks will be given in Section 5.

2 Preliminaries

2.1 Notation

Throughout this paper, \(\mathbb {R}\), \(\mathbb {C}\), and \(\mathbb {Q}\) respectively denote the set of real numbers, the set of complex numbers, and the set of quaternions. The set of all positive integers is denoted by \(\mathbb {N}\), and the symbol [n] represents the set of integers \(\{1, \dots , n\}\) for any \(n\in \mathbb {N}\). A scalar, a vector, and a matrix are written as x, \(\textbf{x}\), and \(\textbf{X}\), respectively. A dot (above the variable) is used to denote a quaternion variable \(\mathbb {Q}\) (e.g., \(\dot{x}\), \(\dot{\textbf{x}}\), and \(\dot{\textbf{X}}\) respectively represent a quaternion scalar, a quaternion vector, and a quaternion matrix). We use \(\dot{\textbf{X}}(I,:)\) and \(\dot{\textbf{X}}(:,J)\) to denote the row and column submatrices with indices I and J, respectively. Here, \((\cdot )^*, (\cdot )^\top , (\cdot )^H,\) and \((\cdot )^{\dagger }\) represent the conjugate, transpose, conjugate transpose, and Moore-Penrose inverse, respectively.

2.2 Quaternion and quaternion matrices

The set of quaternions \(\mathbb {Q}\) is a linear space over \(\mathbb {R}\), with an ordered basis of 1, \(\varvec{i}\), \(\varvec{j}\), and \(\varvec{k}\). Here, \(\varvec{i}\), \(\varvec{j}\), and \(\varvec{k}\) are three imaginary units with the multiplication laws: \(\varvec{i}^2 = \varvec{j}^2 = \varvec{k}^2 = \varvec{ijk} = -1\), \(\varvec{ij} = -\varvec{ji} = \varvec{k}\), \(\varvec{jk} = -\varvec{kj} = \varvec{i}\), \(\varvec{ki} = -\varvec{ik} = \varvec{j}\). An quaternion number \(\dot{x}\in \mathbb {Q}\) is of the form \(\dot{x} = {x}_0 + x_1\varvec{i} + x_2\varvec{j} + x_3\varvec{k}\) \(\in \) \(\mathbb {Q}\) with \(x_0, x_1, x_2, x_3 \in \mathbb {R}\). In particular, \(\dot{x}\) is called a pure quaternion if the real component \(x_0\) equals 0. The conjugate and modulus of \(x\) are defined as \(\dot{x}^* = x_0 - x_1\varvec{i} - x_2\varvec{j} -x_3\varvec{k}\) and \(|\dot{x}| = \sqrt{x_0^2 + x_1^2 + x_2^2 + x_3^2}\), respectively.

Analogously, a quaternion matrix \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) can be written as \(\dot{\textbf{X}}= \textbf{X}_0 + \textbf{X}_1\varvec{i} + \textbf{X}_2\varvec{j} + \textbf{X}_3\varvec{k}\) with \(\textbf{X}_0, \textbf{X}_1, \textbf{X}_2, \textbf{X}_3\in \mathbb {R}^{m\times n}\). For given \(\dot{\textbf{X}}=(\dot{x}_{st})\in \mathbb {Q}^{m\times n}\), the conjugate of \(\dot{\textbf{X}}\) is denoted by \(\dot{\textbf{X}}^*= (\dot{x}^*_{st})\in \mathbb {Q}^{m\times n}\), the transpose of \(\dot{\textbf{X}}\) is denoted by \(\dot{\textbf{X}}^\top = (\dot{x}_{ts})\in \mathbb {Q}^{n\times m}\), and the conjugate transpose of \(\dot{\textbf{X}}\) is denoted by \(\dot{\textbf{X}}^H= (\dot{x}^*_{ts})\in \mathbb {Q}^{n\times m}\). Moreover, the Frobenius norm of \(\dot{\textbf{X}}\) is defined as \(\Vert \dot{\textbf{X}}\Vert _F = \sqrt{\text {Tr}(\dot{\textbf{X}}^H\dot{\textbf{X}})}= \sqrt{\sum _{s=1}^m\sum _{t=1}^n|\dot{x}_{st}|^2}\), where \(\text {Tr}(\cdot )\) is the trace operator, and the spectral norm \(\Vert \dot{\textbf{X}}\Vert _2\) is defined as \(\Vert \dot{\textbf{X}}\Vert _2=\max _{\varvec{\dot{a}}\in \mathbb {Q}^n,\Vert \varvec{\dot{a}}\Vert _2 = 1}\Vert \dot{\textbf{X}}\varvec{\dot{a}}\Vert _2\). The following gives some definitions and properties of quaternion matrices.

Definition 1

(The rank of quaternion matrix[31]) The maximum number of right (left) linearly independent columns (rows) of a quaternion matrix \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) is called the rank of \(\dot{\textbf{X}}.\)

Definition 2

(Quaternion singular value decomposition (QSVD)[31]) Let \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) be of rank k. There exist unitary quaternion matrices \(\dot{\textbf{W}}\in \mathbb {Q}^{m\times m}\) and \(\dot{\textbf{V}}\in \mathbb {Q}^{n\times n}\) such that \( \dot{\textbf{X}}=\dot{\textbf{W}}\mathbf {\Sigma }\dot{\textbf{V}}^{H},\) where \(\mathbf {\Sigma }=\left( \begin{aligned}&\textbf{D}_k&\textbf{0}\\&\textbf{0}&\textbf{0} \end{aligned}\right) \in \mathbb {R}^{m\times n}\), and \(\textbf{D}_k\) = diag(\(\sigma _1,\dots ,\sigma _k\)) \(\in \mathbb {R}^{k\times k}\) is a real diagonal matrix and has k positive entries \(\sigma _k\) (\(i = 1,\dots , k\)) on its diagonal (i.e., positive singular values of \(\dot{\textbf{X}}). \) The truncated QSVD of \(\textbf{A}\) with rank k is denoted by \(\textbf{A}_k=\dot{\textbf{W}}_k\mathbf {\Sigma }_k\dot{\textbf{V}}_k^{H}\), where \(\dot{\textbf{W}}_k= \dot{\textbf{W}} (:, 1:k)\in \mathbb {Q}^{m\times k}\), \(\dot{\textbf{V}}_k= \dot{\textbf{V}}(:, 1:k)\in \mathbb {Q}^{n\times k}\), and \(\mathbf {\Sigma }_k\) is a \(k \times k\) matrix containing the largest k singular values.

Definition 3

(Cayley-Dickson form[32]and Complex adjoint form [31]) Let \(\dot{\textbf{X}}= \textbf{X}_0 + \textbf{X}_1\varvec{i} + \textbf{X}_2\varvec{j} + \textbf{X}_3\varvec{k},\) \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\), \(\textbf{X}_0,\textbf{X}_1,\textbf{X}_2,\textbf{X}_3\in \mathbb {R}^{m\times n}.\) Then the Cayley-Dickson form of \(\dot{\textbf{X}}\) is expressed by \(\dot{\textbf{X}} = \textbf{X}_a+\textbf{X}_b\varvec{j}\in \mathbb {Q}^{m\times n},\) where \(\textbf{X}_a=\textbf{X}_0+\textbf{X}_1\varvec{i},\textbf{X}_b =\textbf{X}_2+\textbf{X}_3\varvec{j},\) and \(\textbf{X}_a,\textbf{X}_b\in \mathbb {C}^{m\times n}.\) The complex adjoint form of \(\textbf{X}\) is formulated as

$$\begin{aligned} \textbf{P}_{\dot{\textbf{X}}}= \left[ \begin{aligned}\textbf{X}_a\ \ &\ \ \textbf{X}_b\\ -\textbf{X}_b^*\ \&\ \ \textbf{X}_a^* \end{aligned} \right] \in \mathbb {C}^{2m\times 2n}, \end{aligned}$$
(1)

The relation between the QSVD of quaternion matrix \(\dot{\textbf{X}}\) and the SVD of its equivalent complex matrix \(\textbf{P}_{\dot{\textbf{X}}}\in \mathbb {C}^{2m\times 2n}\) (\(\textbf{P}_{\dot{\textbf{X}}} = \textbf{W}\mathbf {\Sigma '}\textbf{V}^H\)) is defined as follows [3, 33, 34]

$$\begin{aligned} \mathbf {\Sigma }&\ \ =\ \ \text {row}(\text {col}_{odd}(\mathbf {\Sigma '})) \in \mathbb {R}^{m\times n},\\ \dot{\textbf{W}}&\ \ =\ \ \text {col}_{odd}(\mathbf {W_1}) + \text {col}_{odd}(-\mathbf {W_2^*})\varvec{j} \in \mathbb {Q}^{m\times m}, \\ \dot{\textbf{V}}&\ \ =\ \ \text {col}_{odd}(\mathbf {V_1}) + \text {col}_{odd}(-\mathbf {V_2^*})\varvec{j}\in \mathbb {Q}^{n\times n}, \end{aligned}$$
(2)

such that \(\dot{\textbf{X}} = \dot{\textbf{W}}\mathbf {\Sigma }\dot{\textbf{V}}^H,\) where

$$\begin{aligned} \textbf{W} = \left[ \begin{aligned} [\mathbf {W_1}]_{m\times 2m}\\ [\mathbf {W_2}]_{m\times 2m} \end{aligned} \right] \in \mathbb {C}^{2m\times 2m}, \ \ \ \ \textbf{V} = \left[ \begin{aligned} [\mathbf {V_1}]_{n\times 2n}\\ [\mathbf {V_2}]_{n\times 2n} \end{aligned} \right] \in \mathbb {C}^{2n\times 2n}, \end{aligned}$$
(3)

and \(\text {row}_{odd}(\textbf{M})\), \(\text {col}_{odd}(\textbf{M})\) extracts the odd rows and odd columns of matrix \(\textbf{M}\), respectively. Consequently, we obtain the QSVD of quaternion matrix \(\dot{\textbf{X}}\) as \(\dot{\textbf{X}} = \dot{\textbf{W}}\mathbf {\Sigma }\dot{\textbf{V}}^H.\)

Based on QSVD \(\dot{\textbf{X}} = \dot{\textbf{W}}\mathbf {\Sigma }\dot{\textbf{V}}^H\) we can further obtain the Moore-Penrose inverses [35, 36] of quaternion matrix as

$$\begin{aligned} \dot{\textbf{X}}^{\dagger } =\dot{\textbf{V}}\mathbf {\Sigma }^{\dagger }\dot{\textbf{W}}^H = \dot{\textbf{V}}\left( \begin{aligned}&\textbf{D}_r^{-1}&\textbf{0}\\&\textbf{0}&\textbf{0} \end{aligned}\right) \dot{\textbf{W}}^H\dot{\textbf{X}}\in \mathbb {Q}^{n\times m}.\end{aligned}$$
(4)

More information about quaternion matrices can be found in [3, 31, 35].

3 Proposed approach

In this section, we first present the QMCUR method, which is designed to efficiently compute a low-rank approximation of a large-scale quaternion matrix with low computational costs and comparable accuracy. Then we provide the perturbation estimates for the QMCUR approximation of the noisy version of low-rank matrices. Furthermore, We employ the QMCUR method to color image recovery problem and develop an algorithm to solve it.

3.1 QMCUR-based low-rank approximation method

We now present the QMCUR approximation method. Let \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) be a low-rank quaternion matrix with a predefined rank k. Consider row indices \(I\subseteq [m]\) and column indices \(J\subseteq [n]\) satisfying \(|I|, |J|\ge k\). Denote a column submatrix \(\dot{\textbf{C}} = \dot{\textbf{X}}(:, J)\) whose columns span the column space of \(\dot{\textbf{X}}\) and a row submatrix \(\dot{\textbf{R}} = \dot{\textbf{X}}(I,:)\) whose rows span the row space of \(\dot{\textbf{X}}\). Then the QMCUR approximation of \(\dot{\textbf{X}}\) is a product of the form

$$\begin{aligned} \dot{\textbf{X}} \approx \dot{\textbf{C}}\dot{\textbf{U}}\dot{\textbf{R}},\end{aligned}$$
(5)

where \(\dot{\textbf{C}}\in \mathbb {Q}^{m\times |J|}\) with |J| columns from the quaternion matrix \(\dot{\textbf{X}}\) and \(\dot{\textbf{R}}\in \mathbb {Q}^{|I|\times n}\) with |I| rows from the quaternion matrix \(\dot{\textbf{X}}\). It’s obvious that the core quaternion matrix \(\dot{\textbf{U}}\in \mathbb {Q}^{|J|\times |I|}\) should be computed to yield the smallest error. The optimal choice for the core quaternion matrix \(\dot{\textbf{U}}\) in the least-squares sense is \(\dot{\textbf{U}}=\dot{\textbf{C}}^{\dagger }\dot{\textbf{X}}\dot{\textbf{R}}^{\dagger }\) [37] because

$$\begin{aligned} \dot{\textbf{C}}^{\dagger }\dot{\textbf{X}}\dot{\textbf{R}}^{\dagger } = \mathop {\arg \min }_{\dot{\textbf{U}}\in \mathbb {Q}^{|J|\times |I|}}\Vert \dot{\textbf{X}}-\textbf{CUR}\Vert _F^2. \end{aligned}$$
(6)

Note that one may replace \(\dot{\textbf{C}}^{\dagger }\) in (5) by \(\dot{\textbf{C}}^{\dagger }\dot{\textbf{X}}\dot{\textbf{R}}^{\dagger }\) to improve the approximation, resulting in the QMCUR approximation \(\dot{\textbf{C}}\dot{\textbf{C}}^{\dagger }\dot{\textbf{X}}\dot{\textbf{R}}^{\dagger }\dot{\textbf{R}}\). Algorithm 1 summarizes the overall process of the QMCUR approximation.

Algorithm 1
figure a

Main steps of QMCUR approximation

Full size image

In Algorithm 1, the matrix \(\dot{\textbf{U}}\in \mathbb {Q}^{|J|\times |I|}\) is computed by \(\dot{\textbf{U}}=\dot{\textbf{C}}^{\dagger }\dot{\textbf{X}}\dot{\textbf{R}}^{\dagger }.\) Here, the computation of \(\dot{\textbf{C}}^{\dagger }\) relies on its QSVD (see (4) for more details) [35, 36]. If the QSVD of \(\dot{\textbf{C}}\in \mathbb {Q}^{m\times |J|}\) is \( \dot{\textbf{C}}=\dot{\textbf{W}}\mathbf {\Sigma }\dot{\textbf{V}}^{H},\) then the Moore-Penrose inverse of \(\dot{\textbf{C}}\) is given by

$$\begin{aligned} \dot{\textbf{C}}^{\dagger } =\dot{\textbf{V}}\mathbf {\Sigma }^{\dagger }\dot{\textbf{W}}^H \in \mathbb {Q}^{|J|\times m}. \end{aligned}$$
(7)

And the calculation of \(\dot{\textbf{R}}^{\dagger }\in \mathbb {Q}^{n\times |I|}\) is similar to that of \(\dot{\textbf{C}}^{\dagger }\). Additionally, we set the size of \(\dot{\textbf{C}}\) to be \(m \times k\log k\) and \(\dot{\textbf{R}}\) to be \(k\log k \times n\) for the QMCUR approximation method. The indices used to determine \(\dot{\textbf{C}}\) and \(\dot{\textbf{R}}\) are sampled using two different strategies [38, 39]. In the first strategy, the sampling probabilities \(p_j^{\text {col}}\) and \(q_i^{\text {row}}\) for each column j and row i of the quaternion matrix \(\dot{\textbf{X}}\) are based on the Euclidean norm of the columns and rows, which are respectively defined as

$$\begin{aligned} p_j^{\text {col}}:=\frac{\Vert \dot{\textbf{X}}(:,j)\Vert _2^2}{\Vert \dot{\textbf{X}}\Vert _F^2}, \ \ j = 1,2,\dots ,n\ \ \text {and} \ \ q_i^{\text {row}}:=\frac{\Vert \dot{\textbf{X}}(i,:)\Vert _2^2}{\Vert \dot{\textbf{X}}\Vert _F^2}, \ \ i = 1,2,\dots ,m. \end{aligned}$$
(8)

This strategy is referred to as QMCUR_length. In the second strategy, the sampling probabilities \( p_j^{\text {unif}} \) and \( q_i^{\text {unif}} \) are respectively defined as

$$\begin{aligned} p_j^{\text {unif}} := \frac{1}{n}, \ \ j = 1,2,\dots ,n\ \ \text {and} \ \ q_i^{\text {unif}} := \frac{1}{m}, \ \ i = 1,2,\dots ,m. \end{aligned}$$
(9)

This approach is referred to as QMCUR_uniform.

3.2 Computational complexity

Now, we discuss the computational complexity of the proposed algorithm. Let \(\dot{\textbf{X}}\in \mathbb {H}^{m\times n}\) be a given quaternion matrix. According to (2), the computation of the QSVD for a \(m\times n\) quaternion matrix is equivalent to the computation of the SVD of a \(2m\times 2n\) complex matrix (its complex adjoint). Thus, the computational complexity of QSVD for a \(m\times n\) quaternion matrix is \(\mathcal {O}(\text {min}(8mn^2, 8nm^2))\). Then, computing \(\dot{\textbf{C}}^{\dagger }\) requires performing QSVD on matrices with size of \(m\times |J|\) and multiplication, which cost \(\mathcal {O}((9|J|^2m+|J|m^2).\) Similarly, computing \(\dot{\textbf{R}}^{\dagger }\) requires performing QSVD on matrices with size of \(|I|\times n\) and multiplication, which cost \(\mathcal {O}(9|I|^2n+|I|n^2).\) Computing \(\dot{\textbf{U}}\) and \(\dot{\textbf{X}}\) only involves multiplication costing \(\mathcal {O}((|I|+|J|)mn+|I||J|(m+n))\). In summary, the computational cost of the developed algorithm is \(\mathcal {O}((8|J|^2m+8|I|^2n+|J|m^2+|I|n^2+(|J|+|I|)mn).\)

3.3 Perturbation estimates for CUR approximation

In practical applications, quaternion matrix data is often perturbed, such as noise in pictures, which may cause huge errors. In this section, we present the perturbation analysis suggested by the QMCUR approximation described above. Our main task will be to consider matrices in the form of

$$\begin{aligned} {\tilde{\dot{\textbf{X}}}} = \dot{\textbf{X}} + \dot{\textbf{E}},\end{aligned}$$
(10)

where \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) with rank k, and \(\dot{\textbf{E}}\in \mathbb {Q}^{m\times n}\) is an arbitrary noise quaternion matrix drawn from a certain distribution.

Before analyzing the perturbation, we will first introduce some notations. If \({\tilde{\dot{\textbf{X}}}} = \dot{\textbf{X}} + \dot{\textbf{E}}\), and we consider \({\tilde{\dot{\textbf{C}}}} = {\tilde{\dot{\textbf{X}}}}(:,J)\in \mathbb {Q}^{m\times |J|}\), \({\tilde{\dot{\textbf{R}}}} = {\tilde{\dot{\textbf{X}}}}(I,:)\in \mathbb {Q}^{|I|\times n}\), and \({\tilde{\dot{\textbf{U}}}} = {\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^{\dagger }\in \mathbb {Q}^{|J|\times |I|}\) for selected index sets I and J. Then we write

$$\begin{aligned} \left\{ \begin{aligned}&{\tilde{\dot{\textbf{C}}}} = \dot{\textbf{X}}(:,J)+ \dot{\textbf{E}}(:,J) =\dot{\textbf{C}}+ \dot{\textbf{E}}(:,J),\\ &{\tilde{\dot{\textbf{R}}}} = \dot{\textbf{X}}(I,:)+ \dot{\textbf{E}}(I,:)=\dot{\textbf{R}}+ \dot{\textbf{E}}(I,:),\end{aligned} \right. \end{aligned}$$
(11)

where \({\dot{\textbf{C}}} ={\dot{\textbf{X}}}(:,J)\in \mathbb {Q}^{m\times |J|}\), \({\dot{\textbf{R}}}= {\dot{\textbf{X}}}(I,:)\in \mathbb {Q}^{|I|\times n}\), and \({\dot{\textbf{U}}} ={\dot{\textbf{C}}}^{\dagger }{\dot{\textbf{X}}}{\dot{\textbf{R}}}^{\dagger }\in \mathbb {Q}^{|J|\times |I|}.\) For ease of notation, we will use the conventions that \({\dot{\textbf{E}}_J}=\dot{\textbf{E}}(:, J)\in \mathbb {Q}^{m\times |J|}\) and \({\dot{\textbf{E}}_I}= {\dot{\textbf{E}}}(I,:)\in \mathbb {Q}^{|I|\times n}\). The following theorem provides a perturbation estimate for the QMCUR approximation.

Theorem 1

Let \({\tilde{\dot{\textbf{X}}}} = \dot{\textbf{X}} + \dot{\textbf{E}}\) for a fixed but arbitrary \(\dot{\textbf{E}}\in \mathbb {Q}^{m\times n}\). Using the notation in (11), then the following holds:

$$\begin{aligned} \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} \Vert \le \Vert \dot{\textbf{E}}_I\Vert \Vert {\dot{\textbf{X}}}{\dot{\textbf{R}}}^{\dagger }\Vert + \Vert \dot{\textbf{E}}_J\Vert \Vert {\dot{\textbf{C}}}^{\dagger }{\dot{\textbf{X}}}\Vert + 3\Vert \dot{\textbf{E}}\Vert . \end{aligned}$$
(12)

Furthermore, suppose that \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) has rank k and its truncated QSVD is \(\dot{\textbf{X}}=\dot{\textbf{W}}_k \mathbf {\Sigma }_k\dot{\textbf{V}}_k^{H}\), where \(\dot{\textbf{W}}_k\in \mathbb {Q}^{m\times k}\), \(\mathbf {\Sigma }_k\in \mathbb {R}^{k\times k}\), and \(\dot{\textbf{V}}_k\in \mathbb {Q}^{n\times k}.\) Then we have

$$\begin{aligned} \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}} {\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} \Vert \le \Vert \dot{\textbf{E}}\Vert (\Vert \dot{\textbf{W}}_{k,I}^{\dagger }\Vert + \Vert \dot{\textbf{V}}_{k,J}^{\dagger }\Vert +3), \end{aligned}$$
(13)

where \(\dot{\textbf{W}}_{k,I} = \dot{\textbf{W}}_{k}(I,:)\in \mathbb {Q}^{|I|\times k}\) and \(\dot{\textbf{V}}_{k,J} = \dot{\textbf{V}}_{k}(J,:)\in \mathbb {Q}^{|J|\times k}\) for index sets I, J.

In a word, Theorem 1 shows that the error estimation in the QMCUR method is controlled by the pseudoinverses of the submatrices of the orthogonal singular vectors and is linear in the norm of the noise \(\dot{\textbf{E}}\). To establish Theorem 1, we will introduce the following lemmas.

Lemma 1

Suppose that \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\) has rank k with the QMCUR approximation: \(\dot{\textbf{X}}\approx \textbf{CUR}\), where \(\dot{\textbf{C}} = \dot{\textbf{X}}(:,J)\) with selected column indices J, \(\dot{\textbf{R}} = \dot{\textbf{X}}(I,:)\) with selected row indices I, and \(\dot{\textbf{U}} = \dot{\textbf{C}}^\dagger \dot{\textbf{X}}\dot{\textbf{R}}^\dagger \). Then we have

$$\begin{aligned} \text {rank}(\dot{\textbf{C}}) = \text {rank}(\dot{\textbf{R}}) = \text {rank}(\dot{\textbf{X}}). \end{aligned}$$
(14)

Proof

Recall that \(\dot{\textbf{C}} = \dot{\textbf{X}}(:,J)\). Thus, span(\(\dot{\textbf{C}}\)) \(\subset \) span(\(\dot{\textbf{X}}\)). On account of the fact that \(\dot{\textbf{X}}=\dot{\textbf{C}}\dot{\textbf{C}}^{\dagger }\dot{\textbf{X}}\dot{\textbf{R}}^{\dagger }\dot{\textbf{R}}\), we have span(\(\dot{\textbf{X}}\)) \(\subset \) span(\(\dot{\textbf{C}}\)). A similar argument shows that span(\(\dot{\textbf{R}}^H\)) \(\subset \) span(\(\dot{\textbf{X}}^H\)). The conclusion follows. \(\square \)

Lemma 2

The following hold:

$$\begin{aligned} \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger {\tilde{\dot{\textbf{X}}}} \Vert \le \Vert \dot{\textbf{E}}_J\Vert \Vert \dot{\textbf{C}}^\dagger \dot{\textbf{X}}\Vert + \Vert \dot{\textbf{E}}\Vert , \ \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^\dagger {\tilde{\dot{\textbf{R}}}} \Vert \le \Vert \dot{\textbf{E}}_I\Vert \Vert \dot{\textbf{X}}\dot{\textbf{R}}^\dagger \Vert + \Vert \dot{\textbf{E}}\Vert . \end{aligned}$$
(15)

Proof

Note that

$$\begin{aligned} \Vert (\textbf{I}-{\tilde{\dot{\textbf{C}}}} {\tilde{\dot{\textbf{C}}}} ^\dagger ){\dot{\textbf{C}}}\Vert&= \Vert (\textbf{I}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger ){\tilde{\dot{\textbf{C}}}} - (\textbf{I}-{\tilde{\dot{\textbf{C}}}} {\tilde{\dot{\textbf{C}}}} ^\dagger ){\dot{\textbf{E}}_J}\Vert \\ &\le \Vert (\textbf{I}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger ){\tilde{\dot{\textbf{C}}}} \Vert + \Vert (\textbf{I}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger ){\dot{\textbf{E}}_J}\Vert \\ &\le \Vert \dot{\textbf{E}}_J\Vert . \end{aligned}$$
(16)

The final inequality holds because the first norm term is 0 by identity of the Moore-Penrose pseudoinverse and \(\Vert \textbf{I}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger \Vert _2\le 1\) as this is an orthogonal projection operator. Since \(\text {rank}(\dot{\textbf{C}}) = \text {rank}(\dot{\textbf{X}})\), we have \(\dot{\textbf{X}} = \dot{\textbf{C}}\dot{\textbf{C}}^\dagger \dot{\textbf{X}}\). Then

$$\begin{aligned} \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger {\tilde{\dot{\textbf{X}}}} \Vert&\le \Vert (\textbf{I}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger ){\dot{\textbf{X}}}\Vert + \Vert \dot{\textbf{E}}\Vert \\ &= \Vert (\textbf{I}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^\dagger ){\dot{\textbf{C}}}\dot{\textbf{C}}^\dagger \dot{\textbf{X}}\Vert + \Vert \dot{\textbf{E}}\Vert \\ &\le \Vert \dot{\textbf{E}}_J\Vert \Vert \dot{\textbf{C}}^\dagger \dot{\textbf{X}}\Vert + \Vert \dot{\textbf{E}}\Vert . \ \end{aligned}$$
(17)

The second inequality is derived by mimicking the above argument. The conclusion follows. \(\square \)

Lemma 3

Suppose \(\dot{\textbf{X}}, \dot{\textbf{C}}, \dot{\textbf{U}}, \) and \(\dot{\textbf{R}}\) are as in (5) such that \( \dot{\textbf{X}}= \dot{\textbf{C}}\dot{\textbf{U}}\dot{\textbf{R}}\), and suppose that rank\((\dot{\textbf{X}})\) = k. Let \(\dot{\textbf{X}}={\dot{\textbf{W}}}_k \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H}\) be the truncated QSVD of \(\dot{\textbf{X}}\). Then the following hold:

$$\begin{aligned} \Vert {\dot{\textbf{X}}}{\dot{\textbf{R}}}^{\dagger }\Vert = \Vert \dot{\textbf{W}}_{k,I}^{\dagger }\Vert , \ \Vert {\dot{\textbf{C}}}^{\dagger }{\dot{\textbf{X}}}\Vert = \Vert (\dot{\textbf{V}}_{k,J}^H)^{\dagger }\Vert , \end{aligned}$$
(18)

where \(\dot{\textbf{W}}_{k,I} = \dot{\textbf{W}}_{k}(I,:)\in \mathbb {Q}^{|I|\times k}\) and \(\dot{\textbf{V}}_{k,J} = \dot{\textbf{V}}_{k}(J,:)\in \mathbb {Q}^{|J|\times k}\) for selected index sets I, J.

Proof

Begin with the fact that \(\dot{\textbf{R}}={\dot{\textbf{W}}}_k(I,:) \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H}={\dot{\textbf{W}}}_{k,I} \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H}. \) Then we have

$$\begin{aligned} \dot{\textbf{X}}\dot{\textbf{R}}^\dagger = {\dot{\textbf{W}}}_{k} \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H}({\dot{\textbf{W}}}_{k,I} \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H})^\dagger . \end{aligned}$$
(19)

Notice that \(\dot{\textbf{W}}_{k,I}\) has full column rank, \(\mathbf {\Sigma }_k\) is a \(k\times k\) matrix with full rank, and \(\dot{\textbf{V}}_k^{H}\) has orthogonal rows (i.e., \((\dot{\textbf{V}}_k^{H})^\dagger = \dot{\textbf{V}}_k\)). In this case,

$$\begin{aligned} (\dot{\textbf{W}}_{k,I} \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H})^\dagger = ({\dot{\textbf{V}}}_k^{H})^\dagger \mathbf {\Sigma }_k^{-1}\dot{\textbf{W}}_{k,I}^\dagger = \dot{\textbf{V}}_k \mathbf {\Sigma }_k^{-1}\dot{\textbf{W}}_{k,I}^\dagger . \end{aligned}$$
(20)

Consequently, the following holds:

$$\begin{aligned} \Vert {\dot{\textbf{X}}}{\dot{\textbf{R}}}^{\dagger }\Vert&= \Vert {\dot{\textbf{W}}}_{k} \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H} \dot{\textbf{V}}_k \mathbf {\Sigma }_k^{-1}\dot{\textbf{W}}_{k,I}^\dagger \Vert \\ &=\Vert \mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H} \dot{\textbf{V}}_k \mathbf {\Sigma }_k^{-1}\dot{\textbf{W}}_{k,I}^\dagger \Vert \\ &=\Vert \mathbf {\Sigma }_k\mathbf {\Sigma }_k^{-1}\dot{\textbf{W}}_{k,I}^\dagger \Vert \\ &=\Vert \dot{\textbf{W}}_{k,I}^\dagger \Vert . \end{aligned}$$
(21)

The second equality above follows from the unitary invariance of the norm [40]. Similarly, we have

$$\begin{aligned} \Vert {\dot{\textbf{C}}}^{\dagger }{\dot{\textbf{X}}}\Vert = \Vert (\dot{\textbf{V}}_{k,J}^H)^{\dagger }\Vert ,\end{aligned}$$
(22)

whereupon the conclusion follows from the fact that \( \Vert (\dot{\textbf{V}}_{k,J}^H)^{\dagger } = (\dot{\textbf{V}}_{k,J}^\dagger )^H\) which has the same norm as \(\dot{\textbf{V}}_{k,J}^\dagger \). The conclusion follows. \(\square \)

Proof of Theorem 1

First note that

$$\begin{aligned} \Vert \dot{\textbf{X}} -{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} \Vert&=\Vert \dot{\textbf{X}} -{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}} +{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger } {\tilde{\dot{\textbf{X}}}}( \textbf{I}-\dot{\textbf{R}}^{\dagger }\dot{\textbf{R}})\Vert \\ &\le \Vert {\dot{\textbf{X}}} - {\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}\Vert + \Vert {\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }\Vert \Vert {\tilde{\dot{\textbf{X}}}}( \textbf{I}-\dot{\textbf{R}}^{\dagger }\dot{\textbf{R}})\Vert \\ &\le \Vert \dot{\textbf{X}} - {\tilde{\dot{\textbf{C}}}} {\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}\Vert + \Vert {\tilde{\dot{\textbf{X}}}}(\textbf{I}-\dot{\textbf{R}}^{\dagger }\dot{\textbf{R}})\Vert . \end{aligned}$$
(23)

The second inequality follows from the fact that \(\Vert \dot{\textbf{C}}\dot{\textbf{C}}^{\dagger }\Vert _F = 1\). Next, using the formula \( {\tilde{\dot{\textbf{X}}}} = \dot{\textbf{X}} + \dot{\textbf{E}}\), we have \(\Vert {\tilde{\dot{\textbf{X}}}}(\textbf{I}-{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} )\Vert \le \Vert \dot{\textbf{X}}(\textbf{I}-{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} )\Vert +\Vert \dot{\textbf{E}}\Vert \) since \(\Vert \textbf{I}-{\tilde{\dot{\textbf{R}}}} ^\dagger {\tilde{\dot{\textbf{R}}}} \Vert _2\le 1\). Then applying Lemma 2, we obtain

$$\begin{aligned} \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} \Vert&\le \Vert \dot{\textbf{X}} - {\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}\Vert + \Vert \dot{\textbf{X}}(\textbf{I}-{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} )\Vert + \Vert \dot{\textbf{E}}\Vert \\ &\le \Vert \dot{\textbf{E}}_I\Vert \Vert {\dot{\textbf{X}}}{\dot{\textbf{R}}}^{\dagger }\Vert + \Vert \dot{\textbf{E}}_J\Vert \Vert {\dot{\textbf{C}}}^{\dagger }{\dot{\textbf{X}}}\Vert + 3\Vert \dot{\textbf{E}}\Vert . \end{aligned}$$
(24)

Moreover, from Lemma 3, it follows that

$$\begin{aligned} \Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{C}}}} ^{\dagger }{\tilde{\dot{\textbf{X}}}}{\tilde{\dot{\textbf{R}}}} ^{\dagger }{\tilde{\dot{\textbf{R}}}} \Vert \le \Vert \dot{\textbf{E}}\Vert (\Vert \dot{\textbf{W}}_{k,I}^{\dagger }\Vert + \Vert \dot{\textbf{V}}_{k,J}^{\dagger }\Vert +3). \end{aligned}$$
(25)

3.4 QMCUR approximation for color image recovery

In this section, we apply the QMCUR approximation method to recover color images. The problem of recovering color images can be formulated as a quaternion matrix completion problem, aiming to find its missing entries through the following optimization. The mathematical model is

$$\begin{aligned} \min \limits _{{\dot{\textbf{X}}}} \ \text {rank}{({\dot{\textbf{X}}})}\ \ \text{ s.t. }\ \ P_{\Omega }({\dot{\textbf{X}}})=P_{\Omega }(\dot{\textbf{Y}}), \end{aligned}$$
(26)

where rank(\(\cdot \)) denotes the rank function, \({\dot{\textbf{X}}}\in \mathbb {Q}^{m\times n}\) and \(\dot{\textbf{Y}}\in \mathbb {Q}^{m\times n}\) represent the recovered and observed quaternion matrices, respectively. \(\Omega \) represents the set of observed elements, and \(P_{\Omega }(\dot{\textbf{X}})\) is the projection operator that keeps entries in \(\Omega \) and zeros out others. However, directly solving the problem (26) is difficult as the rank minimization problem is known as NP-hard [41].

The quaternion nuclear norm minimization (QNNM) [18] is a popular convex surrogate of non-convex rank function, and its minimization method is as following

$$\begin{aligned} \min \limits _{{\dot{\textbf{X}}}} \ \Vert {\dot{\textbf{X}}}\Vert _* \ \ \text{ s.t. }\ \ P_{\Omega }({\dot{\textbf{X}}})=P_{\Omega }(\dot{\textbf{Y}}), \end{aligned}$$
(27)

However, the computational of QNNM can be quite expensive for large-scale data, due to calculating the QSVD of quaternion matrices. Therefore, if the rank of the matrix \(\dot{\textbf{X}}\) is known [42,43,44], the QNNM method can be more effectively replaced by the concept of quaternion decomposition. In this case, the problem (26) is presented as follows

$$\begin{aligned} \min \limits _{{\dot{\textbf{X}}}} \ \Vert P_{\Omega }({\dot{\textbf{X}}}) - P_{\Omega }(\dot{\textbf{Y}})\Vert _F^2 \ \ \ \text{ s.t. } \ \ \text {rank}{({\dot{\textbf{X}}})} = k, \end{aligned}$$
(28)

Intuitively, this problem seeks the matrix \(\dot{\textbf{X}}\) of rank k that best fits the given data \(\dot{\textbf{Y}}\).

Similar to the Algorithm framework in [43], the optimization problem (28) can be expressed as follows

$$\begin{aligned} \min \limits _{{\dot{\textbf{X}}}} \ \Vert \dot{\textbf{X}} - \dot{\textbf{M}}\Vert _F^2 \ \ \ \text{ s.t. } \ \ \text {rank}{({\dot{\textbf{X}}})} = k, \ \ P_{\Omega }({\dot{\textbf{X}}}) = P_{\Omega }(\dot{\textbf{Y}}). \end{aligned}$$
(29)

where \(\dot{\textbf{M}}\in \mathbb {Q}^{m\times n}\) is the auxiliary tensor variable. Therefore, we can solve the optimization problem (28) alternatively over the variables \(\dot{\textbf{X}}\) and \(\dot{\textbf{M}}\). The solution to the minimization problem (28) can be approximated using the following iterative procedures:

$$\begin{aligned} \dot{\textbf{M}}^{t+1}\leftarrow \mathcal {L}(\dot{\textbf{X}}^t), \end{aligned}$$
(30)
$$\begin{aligned} \dot{\textbf{X}}^{t+1}\leftarrow \Omega \circledast \dot{\textbf{Y}} + (\textbf{1}-\Omega ) \circledast \dot{\textbf{M}}^{t+1}, \end{aligned}$$
(31)

where t represents the iteration number, \(\mathcal {L}\) is the an operator used to calculate a low-rank quaternion matrix approximation of the quaternion matrix \(\dot{\textbf{X}}\), which can be achieved by Algorithm 1, and \(\textbf{1}\) is a matrix in which all components are equal to one. The algorithm mainly consists of two steps: low-rank quaternion matrix approximation (30) and masking computation (31). We summarize the proposed method in Algorithm 2. It starts with the initial incomplete data \(\dot{\textbf{X}}^0\) and iteratively enhances the approximate solution until a stopping criterion is satisfied or the maximum number of iterations is reached.

Algorithm 2
figure b

QMCUR approximation for color image recovery

Full size image

4 Numerical experiments

In this section, we conduct numerical experiments to assess the accuracy and computation time of the proposed QMCUR method for low-rank quaternion matrix approximation.

Example 4.1

In this experiment, we demonstrate the error estimation in Theorem 1 using simulation data. We randomly generate a quaternion matrix \(\dot{\textbf{X}}\) as a product \(\dot{\textbf{X}} = {\dot{\textbf{W}}}_k\mathbf {\Sigma }_k{\dot{\textbf{V}}}_k^{H}\in \mathbb {Q}^{m\times m}\), where \(\dot{\textbf{W}}_k\in \mathbb {Q}^{m\times k}, \dot{\textbf{V}}_k\in \mathbb {Q}^{m\times k}\) are unitary matrices, and \(\mathbf {\Sigma }_k\) is a diagonal \(k \times k\) matrix with positive diagonal elements. In addition, the random noise quaternion matrix is given by \(\dot{\textbf{E}}=\textbf{E}_0+\textbf{E}_1\varvec{i}+\textbf{E}_2\varvec{j}+\textbf{E}_3\varvec{k}\in \mathbb {Q}^{m\times n}\), where the entries of \(\textbf{E}_t (t = 0, 1, 2, 3)\) are i.i.d. Gaussian variables with mean zero and variance \(\sigma \). Then we obtain the perturbed quaternion matrix

$$\begin{aligned} {\tilde{\dot{\textbf{X}}}} = \dot{\textbf{X}}+ \dot{\textbf{E}}. \end{aligned}$$
(32)

In this experiment, we assume that \( m = 500 \) and \( k = 50 \). By applying Algorithm 1 to compute the rank-k approximation of \({\tilde{\dot{\textbf{X}}}}\) with \(\sigma = 10^{-1}, 10^{-2}, \dots , 10^{-6}\), Fig. 1 shows the results. As observed, the error \(\Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{U}}}}{\tilde{\dot{\textbf{R}}}} \Vert _2\) increases linearly as \(\Vert \dot{\textbf{E}}\Vert _2\) increases, which confirms the conclusion of Theorem 1.

Fig. 1
figure 1

\(\Vert \dot{\textbf{X}}-{\tilde{\dot{\textbf{C}}}}{\tilde{\dot{\textbf{U}}}}{\tilde{\dot{\textbf{R}}}} \Vert _2\) vs. \(\Vert \dot{\textbf{E}}\Vert _2\)

Full size image
Fig. 2
figure 2

Comparison of low-rank quaternion matrix approximation methods under different noise levels \(\sigma \). Rank k=10 is used in all tests and m varies from 50 to 500. Top row: relative approximation errors vs. quaternion matrix dimensions. Bottom row: running time vs. quaternion matrix dimension

Full size image

Example 4.2

In this experiment, we test the proposed QMCUR method on simulated quaternion data and compare their performance with that of QSVD [33], qSVD4 [45], lansvdQ [46], and CSP-QM [7]. We still consider the perturbed quaternion matrix \({\tilde{\dot{\textbf{X}}}}\) in Example 4.1. Figure 2 displays the relative error and running time computed by different methods with the varying size m when k =10. This error is measured by

$$\begin{aligned} \frac{\Vert \dot{\textbf{M}}-\dot{\textbf{X}}\Vert _F}{\Vert \dot{\textbf{X}}\Vert _F}, \end{aligned}$$
(33)

where \(\dot{\textbf{X}}\) denotes the quaternion matrix that represents the clean data and \(\dot{\textbf{M}}\) is obtained by all methods.

Fig. 3
figure 3

Numerical simulation results of different methods with different sampling strategies to color images with different rank k. From top to bottom: Image01 and Image02, respectively

Full size image
Fig. 4
figure 4

Low-rank color image reconstruction. From top to bottom: Image01 and Image02, respectively

Full size image

As observed, QMCUR\(\_\)length and QMCUR\(\_\)uniform methods in Algorithm 1 are significantly faster than QSVD when the data size (i.e., m) is sufficiently large. In particular, the errors for QMCUR_uniform are smaller than those obtained by the QSVD algorithm in the noiseless case (i.e., \(\sigma \) = 0). This is mainly because only the QSVD of the smaller sizes \(\dot{\textbf{C}}\) and \(\dot{\textbf{R}}\) need to be computed, not the QSVD of the quaternion matrix \(\dot{\textbf{X}}\). The proposed methods require less computation time and give more accurate approximations than the qSVD4, lansvdQ, and CSP-QM methods. This observation verifies that the proposed QMCUR method enhance computational performance by calculating the QSVD of selected rows and columns. In summary, the proposed methods achieve a substantial speed-up while maintaining accuracy compared to other methods, especially when m is sufficiently large.

Example 4.3

In this example, we evaluate the performance of the proposed QMCUR method for color image compression. The dataset used in this example is the Set27Footnote 1 and two images are shown in Fig. 4. Each image, with a size of 683 \(\times \) 1024 \(\times \) 3, is represented by a pure quaternion matrix \(\dot{\textbf{X}}= \mathbf {{R}}\varvec{i} + \textbf{G}\varvec{j} + \textbf{B}\varvec{k}\in \mathbb {Q}^{683\times 1024}\), where \(\mathbf {{R}}\), \(\textbf{G}\), and \(\textbf{B}\) represent the RGB (red, green, blue) channels of color image. The elements of \(\dot{\textbf{X}}\) are \(\dot{x}_{st} = r_{st}\varvec{i} + g_{st}\varvec{j} + b_{st}\varvec{k}\), where \(r_{st}\), \(g_{st}\), and \(b_{st}\) denote the red, green, and blue pixel values at the position (s, t) of the color image, respectively. Notably, the number of rows and columns is sethui to klogk, where k represents the predefined rank of the quaternion matrix \(\dot{\textbf{X}}\in \mathbb {Q}^{m\times n}\).

Figure 3 illustrates the relative error and running time of all methods for various selected ranks. As observed, the performance of the proposed methods is superior to that of QSVD in terms of relative error when k is set to a suitable size. In terms of running time, the proposed methods are much faster than QSVD. Fig. 4 presents the reconstructed image quality for various target ranks, showing little difference in the visual effect between each original image and the approximate image obtained by the proposed methods and QSVD.

Example 4.4

In this part, we test the Algorithm 2 using four-color images of size 512\(\times \)768\(\times \)3 from the Kodak PhotoCD DatasetFootnote 2 under the random missing scenario. Several low-rank matrix completion methods are compared in this experiment, including LRQA-1 [18], QLNF [22], and Q-DFN [24]. The missing ratio (MR) is defined as the ratio of the number of missing elements to the total number of elements. To provide a numerical evaluation of the recovered results, the peak signal-to-noise rate (PSNR), structural similarity (SSIM), and running time per iteration (in seconds) are employed. The higher PSNR and SSIM value imply better recovered results.

Table 1 PSNR, SSIM, and running time per iteration (in seconds) of results by different methods with different MRs on color images. The best and second best values are respectively highlighted in boldface and underlined
Full size table

In Table 1, we list the PSNR, SSIM, and time values of different methods on color images, and the best values are highlighted in bold. Compared with competing methods, the proposed methods (QMCUR_length and QMCUR_uniform) achieve the best results in terms of all quantitative metrics. Furthermore, the proposed QMCUR_uniform is the fastest, demonstrating its feasibility on large-scale color images. To clearly observe the recovery performance, Fig. 5 presents the recovered images of four color images by all methods with MR = 80\(\%\). As observed, the proposed methods generate better results than the compared methods. These observations demonstrate that our methods can be applicable for large-scale data processing.

Fig. 5
figure 5

Visual comparison of different methods for color image recovery. From top to bottom: Image03, Image04, Image05, and Image06, respectively

Full size image

5 Conclusion

This work presented an efficient quaternion matrix CUR method for computing low-rank approximation of a quaternion matrix. The QMCUR approximation offers a balance between accuracy and computational costs by selecting specific column and row submatrices of a given quaternion matrix. Besides, we conducted a perturbation analysis of the proposed approximation method and concluded that the error in the quaternion spectral norm is correlated with the noise quaternion matrix in the first order. Experimental results illustrated that the QMCUR approximation methods are significantly faster than comparative low-rank quaternion matrix approximation methods, without sacrificing the quality of reconstruction on both synthetic and color image datasets. In the future, we will extend the proposed methods to other high-dimensional data processing, e.g., quaternion tensor completion [47], tensor completion [48, 49] and multi-dimensional image recovery [50].