A fast matrix completion method based on truncated ${\mathit{L}}_{2, 1}$ norm minimization

1.   Introduction

Low rank matrix completion, which is a method of estimating the missing values in a matrix, is becoming more and more important for the research areas that includes image processing ^[1,2], machine learning ^[3,4], information theory ^[5,6], wireless communications ^[7,8], radar target localization ^[9,10], etc. Since most real-world data matrices may have low-rank structures, the unobserved values in a matrix $M(M\in {\mathbb{R}}^{m\times n}$, $0 < m\le n)$ can be recovered accurately by optimizing the following rank minimization problem,

where ${X\in R}^{m\times n}$ is a low rank matrix whose rank is $r$ and $0 < r\ll \mathrm{m}\mathrm{i}\mathrm{n}(m, n)$. $\mathrm{\Omega }$ is the collection of positions of observations in $M$ and $X$. ${M}_{\mathrm{\Omega }}$ is a matrix whose values of unobserved entries are initialized to zeros. Since the matrix rank is discrete and not convex, the problem in Eq (1) is difficult to optimize ^[11]. The most widely used matrix completion methods include nuclear norm minimization methods, fast methods based on matrix factorization, and weighted nuclear norm minimization methods, where the nuclear norm of a matrix is the summation of its singular values ^[12].

The nuclear norm minimization methods include singular value thresholding (SVT) ^[13], fixed point continuation with approximating singular value decomposition (FPCA) ^[14], approximated proximal gradient (APG) ^[15], and feature matrix based nuclear norm minimization (FNNM) ^[34], etc. Since the nuclear norm is the tightest convex relaxation of matrix rank, these nuclear norm minimization methods can converge accurately on synthetic data-sets that have strict low rank structures with a theoretical guarantee ^[16]. However, it has been reported that these nuclear norm minimization methods are very slow on large scale matrices, because of the full SVD iterations in their updating steps. Another disadvantage of these methods is that they are not accurate when dealing with matrices of complex structures in some real-world applications ^[17].

The fast matrix completion methods proposed in recent years include matrix bi-factorization (MBF) ^[18], fast tri-factorization (FTF) ^[19], and low rank matrix fitting (LMaFit) ^[20], whose common purpose is to reduce the computational costs of traditional methods using SVD. These fast methods suppose that the incomplete matrix containing missing values can be decomposed into the multiplication of two or three small scale sub-matrices at first. Then, they recover the missing values in an incomplete matrix using QR decomposition to calculate the variables for reducing their computational costs. Sufficient experimental results show that these fast methods based on matrix factorization are faster than the nuclear norm optimization methods, i.e., SVT ^[13], FPCA ^[14], APG ^[15], and so on. However, these fast methods have been reported to be not accurate especially on test matrices with full rank structures in some real applications ^[17].

The weighted nuclear norm minimization methods include weighted nuclear norm minimization (WNNM) ^[21], truncated Schatten-p norm minimization ^[22], Schatten capped p norm minimization (SCPN) ^[23], truncated nuclear norm regularization (TNNR) ^[17], truncated quadratic norm minimization ^[44], and so on. In the WNNM method ^[21], different singular values are assigned with different weights by a decreasing function, i.e., a large singular value can be assigned with a small weight. The main reason is that the useful information of a matrix can be reconstructed by the large singular values and singular vectors. It has been reported that WNNM can generate more accurate results than the nuclear norm minimization methods can. The truncated Schatten-p norm minimization method and SCPN method proposed two improved weighted functions for singular values and can optimize their non-convex minimization model efficiently by an alternating direction method of multipliers. They can converge much faster than the WNNM method.

The TNNR method ^[17] proposed a novel truncated nuclear norm, which is the summation of the smallest $r-t$ singular values, where $t$ is the number of subtracted singular values and $r$ is the rank of incomplete matrix. In the TNNR method, the largest $t$ singular values are not optimized, which leads to a fact that the main useful information of tested matrix is retained. Hence, TNNR is much more accurate than the SVT, APG, WNNM, SCPN, FTF, and MBF methods. However, it has been reported that the TNNR method converges more slowly than the SVT method does. In order to reduce the number of iterations of TNNR, a modified TNNR method based on weighted residual error (TNNR-WRE) ^[24] has been proposed. In the TNNR-WRE method, the rows with less missing values are recovered prior to the rest ones by optimizing a weighted residual error matrix. Sufficient experimental results show that the modified TNNR-WRE method is much faster than the TNNR method, because the number of SVD iterations of the former is much smaller than that of the latter. However, the TNNR-WRE method uses SVD decomposition to calculate the singular values of matrices, which leads to a fact that the computation cost of TNNR-WRE is as large as that of TNNR. Consequently, the TNNR-WRE method may become slow when dealing with real world images. In the truncated quadratic norm minimization method ^[44], a truncated quadratic norm has been proposed as a better relaxation function of matrix rank than nuclear norm. Experimental results show that this method performs well in terms of convergence accuracy. However, it is much slower than the fast methods using QR, such as LMaFit and FTF.

In recent years, the robustness of matrix completion methods and the balance between speed and convergence accuracy have received increasing attention. On one side, some robust matrix completion methods have been proposed, such as the robust matrix completion methods based on ${l}_{p}$ norm minimization ^[25,26], the robust M-estimation based matrix completion method ^[27], the robust matrix completion based on half-quadratic optimization ^[28], and some robust methods based on ${l}_{0}$ norm ^[29] or ${l}_{1}$ norm ^[30], or ${l}_{2}$ norm ^[31]. Compared with the traditional matrix completion methods, this class of methods have better performances on parameter robustness and resistance to non-Gauss noises. On the other side, some fast and accurate matrix completion methods based on matrix factorization and ${L}_{\mathrm{2, 1}}$ norm minimization (the sum of Frobenius norms of rows in $X$) have been investigated, such as an iteratively reweighted ${L}_{\mathrm{2, 1}}$ norm minimization method (IRLNM) ^[32], a modified fast matrix bi-factorization (FMBF) ^[33] method, and so on. Since the IRLNM method replaces the SVD decomposition with a less computationally intensive QR decomposition to calculate the eigenvectors, it is faster than the methods requiring SVD. The recently proposed FMBF method is faster than the IRLNM method, because the former just performing one time of QR decomposition in its each iteration, while the latter performs two times of QR decompositions.

For further improving the speed and convergence accuracy of TNNR, a truncated ${L}_{\mathrm{2, 1}}$ norm minimization method is proposed, which can be abbreviated as TLNM. The major contributions of our proposed TLNM can be concluded as follows,

● A novel truncated ${L}_{\mathrm{2, 1}}$ Norm is designed for low rank matrix recovery. Since the truncated ${L}_{\mathrm{2, 1}}$ Norm is a better relaxation of rank function than the truncated nuclear norm, the proposed TLNM method is much more accurate than the TNNR method and other state-of-arts methods.

● The proposed truncated ${L}_{\mathrm{2, 1}}$ Norm minimization model for matrix completion can be solved extremely fast by QR decomposition, which indicates that the proposed TLNM method should be much faster than the TNNR method.

The proposed truncated ${L}_{\mathrm{2, 1}}$ norm and the optimization model in this paper will have a significant impact on relevant research areas, such as low rank matrix representation ^[42], background modeling ^[43], sparse signal recovery ^[45], and so on.

2.   Related works

TNNR is a widely used matrix completion method, which has received widespread attention in many research fields, such as signal processing ^[35,36,37], image processing ^[38,39], neural networks ^[40,41], and so on. However, it seems to become slow in some real applications. Hence, a modified TNNR method based on truncated ${L}_{\mathrm{2, 1}}$ norm is investigated to increase the speed of TNNR. Before introducing our proposed TLNM method, the optimization model of TNNR, and some related works should be introduced in section.

2.1.   The TNNR method ^[17]

Suppose $X(X\in {\mathbb{R}}^{m\times n})$ is a low rank matrix corresponding to a partially observed matrix and its SVD decomposition is that $X = US{V}^{T}$, where $U(U\in {\mathbb{R}}^{m\times m})$ and $V(V\in {\mathbb{R}}^{n\times n})$ are orthogonal matrices, $S(S\in {\mathbb{R}}^{m\times n})$ is a diagonal matrix whose diagonal entries are the singular values of $X$. The truncated nuclear norm of $X$ is defined as follows,

where ${\sigma }_{i} = {S}_{i, i}$ and the singular values are arranged in decreasing order, i.e., ${\sigma }_{i}\ge {\sigma }_{j}(0 < i < j\le m)$. The parameter $t(0\le t < m)$ stands for the number of subtracted singular values.

In the TNNR method, the truncated nuclear norm is rewritten as follows,

where ${‖X‖}_{\mathrm{*}}$ is the nuclear norm of $X$, i.e., ${‖X‖}_{\mathrm{*}} = \sum _{i = 1}^{m}{\sigma }_{i}$. According to the Von Neumann's trace inequality, it is not difficult to see that

where$A(A\in {\mathbb{R}}^{t\times m})$ and $B(B\in {\mathbb{R}}^{t\times n})$ are row orthogonal matrices. $Tr\left(X\right)$ stands for the trace function of matrix $X$, i.e., the summation of diagonal entries of $X$.

According to Eq (4), the optimization model of TNNR can be formulated as follows,

The variables in Eq (5) can be optimized alternatively using an alternating direction method of multipliers. The readers are suggested to see more details about the optimization process in ^[17].

Sufficient experimental results show that the TNNR method converges more accurately than the SVT, APG, MBF and FTF methods do. However, it has been reported that the TNNR method is not fast on images with full rank structures, because of its large number of singular value decomposition updating iterations.

2.2.   The MBF method ^[18]

In order to improve the speed of matrix completion, a fast matrix completion method based on MBF has been proposed recently by Liu ^[18]. In the MBF method, the underlying matrix $X$that needs recovering is decomposed as follows,

where the variable $C\in {\mathbb{R}}^{m\times r}$ is a column orthogonal matrix, $D\in {\mathbb{R}}^{r\times n}$ is a real matrix. $r$is a positive integer and $r\in (0, m]$.

Then, a nuclear norm minimization problem is formulated for fast matrix completion as follows,

The nuclear norm minimization problem in Eq (7) can be solved using an alternation direction method efficiently. Since the size of variable $D$ is $r\times n$ and $r\ll n$, the computation cost of SVD on $D$ is much smaller than that of SVD on $X$. Hence, the speed of MBF is faster than TNNR, SCPN, FNNM, SVT, etc.

However, the accuracy of the MBF method is not as large as the recently proposed methods, such as TNNR, SCPN, and FNNM. The explanation is that the variable $D$ should be updated by a singular value thresholding operator ^[13], which results in a convergence accuracy of MBF that is almost equal to those of SVT and APG. Moreover, the MBF method may become not fast when it deals with matrices of full rank. It may be because that the parameter $r$, i.e., the row number of sub-matrix $D$, should be arranged with a large value and the computation cost of SVD decomposition on matrix $D$ will become large obviously in such case.

3.   Our proposed method

In an attempt to increase the speed and convergence accuracy of TNNR, a truncated ${L}_{\mathrm{2, 1}}$norm minimization method using QR decomposition for fast and accurate matrix completion is proposed in this section.

3.1.   The truncated ${\boldsymbol{L}}_\bf{2, 1}$ norm

Suppose that the optimal matrix $X$ for incomplete matrix $M$ is decomposed as that

where the definitions of $C$ and $D$ are the same as those of $C$ and $D$ in Eq (6), respectively. $E$ is a noise matrix in size of $m\times n$. Then, the ${L}_{\mathrm{2, 1}}$ norm of $D$ is formulated as follows,

where ${D}_{i\cdot }$ stands for the ${i}^{th}$ row of $D$ and ${‖{D}_{i\cdot }‖}_{F}$ is the Frobenius norm of ${D}_{i\cdot }$, i.e.,

In fact, the ${L}_{\mathrm{2, 1}}$ norm of $D$ shown in Eq (9) can be reformulated as follows,

where${H}^{+}$ is the Moore-Penrose pseudo inverse of $H$ and $H(H\in {\mathbb{R}}^{m\times n})$ is a row normalized matrix, i.e.,

where the variable $G$ is a diagonal matrix in size of $r\times r$, ${G}_{i, i}$ and ${H}_{i\cdot }$ are respectively defined as follows,

and

where ${D}_{i\cdot }$ stands for the ${i}^{th}$ row of $D$ and ${H}_{i\cdot }$ stands for the ${i}^{th}$ row of $H$. According to Eq (3), the truncated ${L}_{\mathrm{2, 1}}$ norm of matrix $D$ is defined as follows,

where the parameter $t(0\le t < r)$ stands for the number of subtracted Frobenius norms of rows in $D$. In view of Eqs (9) and (11), it is not difficult to see that ${‖D‖}_{t\left(\mathrm{2, 1}\right)}$ is equal to

where $\widehat{C} = ({\widehat{\mathrm{c}}}_{1}, {\widehat{\mathrm{c}}}_{2}, \dots, {\widehat{\mathrm{c}}}_{r})$ is a real matrix and its rows are defined as follows,

where ${c}_{i}$ stands for the ${i}^{th}$ column of $C$. Since the variable $H$ in Eq (12) is not an orthogonal matrix, it is easy to see that the truncated ${L}_{\mathrm{2, 1}}$ norm in Eq (16) can be solved very fast by QR decomposition.

3.2.   The proposed truncated ${\boldsymbol{L}}_\bf{2, 1}$ norm minimization based matrix completion method (TLNM)

Suppose the underlying matrix $X$ has been decomposed as in Eq (8). The optimization problem of TLNM is given as follows,

where $W$ is a diagonal matrix with positive randomized diagonal entries. The remained variables, such as $X$, $C$, $D$, and $E$, have been defined in Eqs (8) and (12). The parameter $\mu$ is a positive real number.

Since ${\left|\right|D\left|\right|}_{t\left(\mathrm{2, 1}\right)}$is equal to $Tr\left({C}^{T}X{H}^{+}\right)$, the constrained optimization model in Eq (18) can be relaxed as the following model,

By letting ${X}_{1} = {X}_{M}$, the variables i.e., $X$, $C$, $D$, and $E$ in Eq (19), are updated alternatively one by one.

First, the variable ${C}_{k+1}$ is updated by solving the following sub-problem,

According to the work by Wen ^[20], the optimization problem in Eq (20) can be rewritten as the following problem

where

Because the variable $C$ is an orthonormal matrix, it can be optimized with the help of QR. Suppose the QR decomposition of $T$ is

where $Q = \left({q}_{1}, {q}_{2}, \dots, {q}_{m}\right)$ is an orthonormal matrix, $P(P\in {\mathbb{R}}^{m\times r})$ is an upper triangular matrix. Then, ${C}_{k+1}$ can be updated as follows,

where ${q}_{i}(i\in \left[1, r\right])$ is a column vector whose length is equal to $m$. According to Eq (17), the variable ${\widehat{C}}_{k+1}$ can be updated as follows,

where ${\widehat{\mathrm{c}}}_{i}$ stands for the ${i}^{th}$row of ${\widehat{C}}_{k+1}$ and $i\in [1, t]$.

Second, the variable ${D}_{k+1}$ is updated by solving the following problem,

Since ${C}_{k+1}$ is a column orthogonal matrix, it is not difficult to see that

Third, according to the problem in Eq (19), the matrix ${X}_{k+1}$ can be updated by solving the following minimization problem,

Let $\frac{\nabla F}{\nabla X} = 0$, we have,

In order to reduce the computation cost for solving Eq (31), the matrix ${\widehat{C}}_{k}^{}{{{H}_{k}}^{+}}^{T}$ is replaced with ${\widehat{C}}_{k}^{}{H}_{k}$, because the matrices ${{H}^{+}}^{T}$ and $H$ have the same singular vectors. Consequently, we have,

and

Fourth, the variable ${E}_{k+1}$is updated by solving the following problem,

The problem in Eq (35) can be solved via a gradient descent search, and

where $\lambda (0 < \lambda < 1)$ is a positive parameter that regulates the step size of gradient descent search.

Finally, the parameter ${\mu }_{k+1}$, which regulates the step size shown in Eq (33), is updated as follows,

where $\rho (\rho > 1)$ and ${\mu }_{0} > 0$.

In general, the proposed truncated ${L}_{\mathrm{2, 1}}$norm minimization method that is abbreviated as TLNM is obviously faster than the TNNR method and other methods proposed in recent years. In order to facilitate the implementation of our proposed TLNM method for the readers, the updating steps of TLNM are summarized in Algorithm 1.

3.3.   Complexity analysis of our proposed TLNM method

In this section, the computation complexities of TLNM, TNNR and other popular methods are summarized in Table 1.

In Table 1, $m$ is the row number of $M$, $n$ is the column number of $M$ and $r(0 < r\ll m)$ is the estimated rank of $M$. Since the most CPU time of TLNM is spent on executing QR for calculating the orthogonal matrix $C$, the complexity of TLNM is equal to that of QR, i.e., $O(m\cdot {r}^{2})$. The most CPU time of TNNR is spent on using SVD to compute the singular values at its each iteration. Consequently, the complexity of TNNR is equal to that of SVD, i.e., $O(m\cdot {n}^{2})$. Because the LMaFit method is also fast method based on QR, its complexity is equal to that of TLNM. FNNM and SCPN are two kinds of methods based on weighted nuclear norm minimization, in which the SVD decomposition is an essential tool for computing the singular values. Thus, the computation complexities of FNNM and SCPN are all equal to that of SVD. Since the MBF method uses both QR decomposition and SVD decomposition at its each iteration, its computation complexity is $O(m\cdot {r}^{2}+{r}^{3})$.

According to the complexities shown in Table 1, it is clear that the computation complexity of TLNM is much smaller than those of TNNR, FNNM and SCPN.

4.   Experimental results

In the experiments, TLNM is tested on a number of real-world color images and its convergence accuracy and speed are compared with the results of other popular methods including LMaFit ^[20], TNNR ^[17], MBF ^[18], SCPN ^[23], and FNNM ^[34].

In the experiments for TLNM, the parameter $\lambda$ is set to $0.001$, ${\mu }_{0}$ is set to $\frac{100}{{‖M‖}_{F}}$ and $t$ is selected from 1~25. The value of parameter $\rho$ should be adjusted according to the tested data. The maximum iteration numbers for TLNM, TNNR, MBF, FNNM, SCPN, and MBF are set to 300,300,300,500,500, and 500, respectively. The parameters for TNNR, SCPN, FNNM, LMaFit, and MBF are adjusted optimally.

All the experiments are conducted on a laptop computer equipped with i7-1195G7 CPU and 32 GB of RAM memory.

4.1.   Images containing random missing values

For evaluating our proposed TLNM method, 16 colorful images are tested. These images shown in Figure 1 are also widely used by some popular matrix completion methods proposed in recent years, such as the TNNR ^[17] method, a low-rank quaternion matrix completion method ^[1], and a non-local robust quaternion method ^[2]. In our proposed TLNM, the channels of these images are recovered separately.

In our experimental, 50% entries of the images (A~P) in Figure 1 are randomly selected as missing entries, i.e., their values are initialized to zero, to generate incomplete images (${A}_{\mathrm{\Omega }}~{P}_{\mathrm{\Omega }}$) at first. Then, the TLNM method is tested using these images and its performance is compared with those of other five methods. The peak signal-to-noise ratio (PSNR) is chosen as the standard for evaluating convergence accuracy and is given as that

where ${X}_{opt}$ is an output of a matrix completion method, $I$ is matrix without missing values.

Let $r = 300$ and $\rho = 1.02$, the TLNM method is tested on the 16 incomplete images, i.e., ${A}_{\mathrm{\Omega }}~{P}_{\mathrm{\Omega }}$. The PSNR values of TLNM, TNNR, MBF, LMaFit, SCPN, and FNNM are listed in Table 2.

The PSNR values listed in Table 2 show that our proposed TLNM is much more accurate than the compared methods. The MBF method is not as accurate as the SCPN and TNNR methods, because the former cannot adaptively regulate the thresholds for the singular values of tested images. The LMaFit method is less accurate than the MBF method, because it cannot obtain the singular values of incomplete images via its updating steps. The PSNR values of TNNR on the 16 incomplete images are much better than those of MBF and LMaFit, because the truncated nuclear norm is a much better approximation of rank function than the nuclear norm. The SCPN method is a bit more accurate than the FNNM method on most tested incomplete images. The main reason is that the Schatten capped $p$ norm used in SCPN can be seen as a special case of weighted nuclear norm that assigns different weights for different singular values, while FNNM is a nuclear norm minimization method. The PSNR values of TLNM on the tested images are much more accurate than the TNNR method and the recently proposed FNNM and SCPN. Hence, the proposed truncated ${L}_{\mathrm{2, 1}}$ norm should be a better relaxation of rank function than truncated nuclear norm.

After the comparison of convergence accuracy, it is necessary to compare the speed of TLNM with those of TNNR, SCPN, FNNM, MBF, and LMaFit. The CPU times for these six methods to reach the PSNR values shown in Table 2 are plotted in Figure 2.

The CPU time curves plotted in Figure 2 show that TLNM is obviously faster than the TNNR, SCPN, FNNM, and MBF methods, because TLNM can recover the incomplete images by QR and the computation cost of QR is 7 percent of that of SVD ^[32]. FNNM is the slowest one among the six tested methods, because its CPU time is much larger than those of other methods. More exactly, it takes about 110~180 seconds to search for the optimal solutions, while other methods take less than 80 seconds. The TNNR method takes about 40~71 seconds to converge on the 16 tested images, which indicates that it converges faster than the FNNM method does. Compared with FNNM and TNNR, the CPU time of SCPN is much smaller, which leads to a fact that the SCPN method can converge with fewer number of iterations. The main reason is that these three methods are almost equal in terms of computational cost. The MBF method is a bit faster than the SCPN method, because it can improve its speed by performing SVD decomposition on a small size matrix. The CPU time of LMaFit is almost equal to TLNM, because neither of these two methods require the usage of SVD.

In view of the PSNR values in Table 2 and the CPU time curves plotted in Figure 2, it is easy to see that TLNM outperforms its competing methods, i.e., TNNR, SCPN, FNNM, LMaFit, and MBF, in both convergence accuracy and CPU time.

To intuitively show the details of output of TLNM and other state-of-art methods, some of their outputs are shown in Figure 3.

From Figure 3, it is easy to see that the recovered images shown in (A4) and (B4) given by LMaFit are respectively not as clear as the results shown in (A8) and (B8) given by TLNM, because there're many noises remained in the former. The recovery results of MBF shown in (A3) and (B3) are much better than the results given by LMaFit, however they contain a small bit of noisy pixels. The SCPN method performs better on the incomplete image shown in (B2) than on the image shown in (A2), because its output shown in (B5) is much better than the result shown in (A5). The recovered images given by TLNM, FNNM and TNNR, which are almost as clear as the original images shown in (A1) and (B1), are much better than the results given by LMaFit, MBF, and SCPN.

4.2.   Experimental results on images with structured missing values

Eliminating structural missing textures that occur in an image is a more difficult work than restoring the images containing random missing values, because the pixels covered by texts are distributed continuously.

In this section, the 16 color images shown in Figure 1 are arranged with some textures to generate the incomplete images for testing our proposed TLNM method. In Figure 4, an example of incomplete image with texture missing entries is plotted for show.

All the 16 color images shown in Figure 1 will be masked by the same textures as in Figure 4 for generating the incomplete images in this section. The final PSNR values and CPU times of TLNM on the 16 incomplete images with textures are compared with those of other state-of-art methods.

First, the PSNR values of TLNM and other five methods are listed for comparation in Table 3. Although removing the textures is a more difficult task than that in Section 4. 1, our proposed TLNM method has a much better performance in such case than the performances of LmaFit, MBF, SCPN, FNNM, and TNNR methods. The PSNR values of LMaFit on the 16 tested images are much smaller than those of MBF. Hence, the MBF method is more capable of handling the matrix completion tasks with structured missing values. Compared with the MBF method, the recently proposed SCPN method is much more accurate, because the latter can regulate the weights for singular values adaptively. Since the FNNM method is a nuclear norm minimization method, its convergence accuracies are smaller than those of SCPN on the tested images. The proposed TLNM method is much more accurate than the TNNR method on most tested images, because the PSNR values of TLNM are better than those of TNNR. In view of the PSNR values in Tables 2 and 3, it is easy to see that TLNM can recover the incomplete images with random missing entries and textured missing entries much more accurately than the five compared methods on most tested images.

Second, the CPU times of TLNM on images containing textures are plotted in Figure 5.

The curves in Figure 5 show that the speed of TLNM is equal to that of LMaFit and is much smaller than those of TNNR, SCPN and FNNM. The TLNM method takes about 10 seconds to recover the textured missing entries for each image, while the TNNR method takes about 65~130 seconds. The SCPN methods should have a smaller number of iterations than TNNR and FNNM, its CPU times on the 16 images are much smaller than those of the latter. The FNNM method is the slowest one among the six tested matrix completion methods, because it takes about 120~150 seconds to converge.

By comparing the CPU times shown in Figure 5, we see that TLNM should be 5 times as fast as SCPN, 10 times as fast as TNNR and 13 times as fast as FNNM, respectively.

Third, some outputs given by TLNM and other methods are displayed in Figure 6.

Figure 6 indicates that the result given by LMaFit is not clear, because the recovered image in (D) has many noisy pixels. The result given by MBF shown in (C) is much better than that given by LMaFit. However, there are very noticeable text traces appeared in (C). The result of SCPN shown in (E) is much clearer than those of FNNM, MBF, and LMaFit. Hence, this result reaffirms a fact that the weighted nuclear norm minimization method should have a better convergence accuracy than a method based on nuclear norm minimization in most cases. The TNNR method can recover the images masked by textures successfully, because its PSNR value is much better than those of the SCPN, FNNM, LMaFit, and MBF methods. Moreover, the result given by TNNR is much better than the results given by SCPN and FNNM. However, there are some inconspicuous traces of texture remained in the recovered image given by TNNR. The TLNM method is much more accurate than the compared methods, because its PSNR, i.e., 27.02, is much better than those of the latter. The recovery result given by TLNM shown in (H) is clearer than the results of other methods, because there is almost no noises distributed in image (H).

Finally, the detailed convergence processes of TLNM and other five compared methods, i.e., the PSNR curves, are plotted in Figure 7.

From Figure 7, it is easy to see that the FNNM takes about 400 iterations to converge, which is the slowest method among the six tested methods. The SCPN and TNNR take about 100 and 180 iterations to converge, respectively. The iteration number of MBF, TLNM, and LMaFit are almost equal to 200. Although the gap in the number of iterations between the TLNM and TNNR methods is not large, their CPU times vary greatly. The main reason is that the computation cost of TLNM is smaller than that of TNNR. In view of the CPU times shown in Fig. 5 and the PSNR curves in Figure 7, it is not difficult to see that the CPU time of each iteration for TLNM is about ten percent of that of TNNR, which means that the main computation costs of TNNR and TLNM are main consumed by QR decomposition and SVD decomposition, respectively. Hence, the methods based on QR, i.e., TLNM, LmaFit, and MBF, are faster than the TNNR, SCPN, and FNNM methods using SVD.

5.   Conclusions

In this paper, a truncated ${L}_{\mathrm{2, 1}}$ norm minimization method, which is abbreviated as TLNM, is proposed for improving the speed and convergence accuracy of TNNR. On one side, for improving the convergence accuracy of TNNR, a novel truncated ${L}_{\mathrm{2, 1}}$ norm is designed as a better relaxation of rank function than the truncated nuclear norm in the proposed TLNM. Second, for improving the speed of TNNR, the optimization problem of TLNM is solved using QR decomposition to update the key variables. Experimental results using color images show that TLNM is more accurate than the fast methods based on matrix factorization and other state-of-art methods, such as LmaFit, MBF, SCPN, FNNM, and TNNR. Since the speed of QR is about 7 times as fast as that of SVD, the proposed TLNM method is faster than the compared state-of-art methods using SVD, i.e., SCPN, TNNR, and FNNM.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 62102002, in part by the Natural Science Foundation of Anhui Province of China under Grant 2008085QF291, by the Research Start-up Fund of West Anhui University, No. WGKQ2021053, in part by the transverse project of designing and processing of gas gun driven by high pressure air mixed with Gas (0045021079).

Conflict of interest

The authors declare that there are no conflicts of interest.