1 Introduction

As a special case of matrix recovery, matrix completion addresses to complete the incomplete matrix according to the existing information, which has been widely applied in image restoration [1,2,3,4], video denoising [5], and recommendation system [6, 7]. A typical example is Netflix prize problem [8], which can infer the user’s favorite degree for other films according to the user’s evaluation of some films, and then the movie recommendation is made for other users.

Assuming that \(M\in {\mathbf {R}}^{m \times n}\) is a given low rank or approximate low rank matrix and \(X\in {\mathbf {R}}^{m \times n}\) is a low rank matrix to be recovered, then the completion problem of X can be represented as the following optimization problem:

$$\begin{aligned} \min _{X} ~\text {rank}(X) ~~ \text {s. t.} ~~X_{ij}=M_{ij},(i,j)\in \Omega , \end{aligned}$$
(1.1)

where \(\text {rank}{(\cdot )}\) denotes the rank of matrix, \(\Omega \subset \{1,\ldots ,m\}\times \{1,\ldots ,n\}\) is a set of location coordinates for known data. If the sampling operator, \(P_{\Omega }(X)\),

$$\begin{aligned}{}[P_{\Omega }(X)]_{ij}=\left\{ \begin{array}{rcl} X_{ij}, &{} {(i,j)\in \Omega };\\ 0, &{} \text {otherwise}, \end{array}\right. \end{aligned}$$
(1.2)

is introduced, then the problem (1.1) can be denoted as

$$\begin{aligned} \min _{X} ~\text {rank}(X) ~~~ \text {s. t.} ~~P_{\Omega }(X)=P_{\Omega }(M). \end{aligned}$$
(1.3)

Another important problem of matrix recovery is low rank sparse decomposition, also known as robust principal component analysis (RPCA), which has been widely applied in medical image processing [9, 10], video surveillance [11, 12], pattern recognition [13,14,15], and so on. The main purpose of RPCA is to decompose M into the sum of a low rank matrix X and a sparse matrix E, that is, \(M=X+E\), where X and E are unknown matrices. In other words, the optimization problem

$$\begin{aligned} \min _{X,E} ~\text {rank}(X) +\lambda \Vert E\Vert _0 ~~~ \text {s. t.} ~~M=X+E \end{aligned}$$
(1.4)

needs to be solved, where \(\Vert \cdot \Vert _{0}\) denotes the \(\ell _{0}\) norm of matrix, and \(\lambda \) (\(>0\)) is regularization parameter.

Since the rank function is non-convex and discontinuous, the optimization problems (1.3) and (1.4) are both NP hard problems, which cannot be solved directly by the commonly used optimization algorithms. Fazel [16] proposed a method to replace the rank function in the optimization problems (1.3) and (1.4) by using the nuclear norm (NN) \(\Vert \cdot \Vert _{ *}\), and the \(\ell _{1}\) norm instead of the \(\ell _{0}\) norm. Therefore, Eqs. (1.3) and (1.4) are converted to

$$\begin{aligned} \min _{X} ~\Vert X\Vert _{*} ~~~\text {s. t.} ~~P_{\Omega }(X)=P_{\Omega }(M), \end{aligned}$$
(1.5)

and

$$\begin{aligned} \min _{X,E} ~\Vert X\Vert _{*} +\lambda \Vert E\Vert _1 ~~ \text {s. t.} ~~M=X+E, \end{aligned}$$
(1.6)

respectively. Here \(\Vert X\Vert _{*}=\sum _{i=1}^{\min {(m,n)}}\sigma _{i}(X)\) (\(\sigma _1(X)\ge \sigma _2(X)\ge \cdots \ge \sigma _{\min {(m,n)}}(X)\)) is NN of matrix X, that is, the sum of all singular values of matrix X, and \(\Vert E\Vert _{1}=\sum _{i=1}^{m}\sum _{j=1}^{n}|e_{ij}|\) is the \(\ell _1\) norm of matrix E, that is, the sum of all the absolute values of elements of matrix E.

Up to now, a series of studies [16,17,18,19] have shown that NN can be used as an approximate substitute for rank function. At the same time, some algorithms for solving convex optimization with NN [20,21,22,23] have been proposed one after another. This is because in the rank function, all the non-zero singular values have the same effect, and NN adds all the non-zero singular values and minimizes them at the same time, so that the different singular values have different contributions as much as possible. However, NN is not the best approximate substitute for rank function. Although the algorithms based on NN have strong theoretical guarantee, these algorithms can only get the suboptimal solution in practical application.

In 2012, a non-convex minimum optimal substitution for NN is proposed, which is named as Schatten p-norm [6], and defined by \(\Vert X\Vert _{p}= \left( \sum _{i=1}^{\min {(m,n)}}\sigma _{i}^{p}(X) \right) ^{1/p}\) (\(0<p\le 1\)). Obviously, when \(p=1\), it is equivalent to the NN. And when p approaches 0, the Schatten p-norm approximates the rank function. In 2013, Hu et al. [1] proposed a new norm called as truncated nuclear norm (TNN): \(\Vert X\Vert _{r}=\sum _{i=r+1}^{\min {(m,n)}}\sigma _{i}(X)\). Its main idea is to remove the larger singular values of r and add the remaining singular values of \((\min (m, n)-r)\) to reduce the influence of large singular values on low rank. Recently, Gu et al. [24] proposed to replace NN with the weighted nuclear norm (WNN) defined by \(\Vert X\Vert _{\omega ,*}=\sum _{i=1}^{\min {(m,n)}}\omega _{i}\sigma _{i}(X)\) in order to change the influence of singular value on rank function with different weights, and showed that the proposed WNN has a good approximate effect. In [25] and [26], a truncated Schatten p-norm (TSPN) is proposed, which sums only the p power of singular values of \((\min (m,n)-r)\), that is, \(\Vert X\Vert _{r}^{p}=\sum _{i=r+1}^{\min {(m,n)}}\sigma _{i}^{p}(X)\). In [25], a compression sensing model based on truncated Schatten p-norm is proposed, and the alternating direction multiple method (ADMM) was used to solve the model. The proposed method in [25] has a good performance in image restoration. In [26], Chen et al. used truncated Schatten p-norm and proposed an optimization model of human motion recovery, and further showed that the truncated Schatten p-norm has a better effect of approximate rank function than other norms by using a series of experiments.

The motivations of the paper are as follows.

  • In the rank function, all the non-zero singular values have the same effect. However, the different singular values should have different contributions as much as possible. So NN is not the best approximate substitute for rank function.

  • The main idea of TNN is to remove the larger singular values of r and add the remaining singular values of \((\min (m, n)-r)\) to reduce the influence of large singular values on low rank. It was shown that TNN has better approximate effect than NN.

  • When \(0<p<1\), Schatten p-norm is a non-convex minimum optimal substitution for NN, and when \(p=1\), it is equivalent to the nuclear norm. Specially, when p approximates 0, the Schatten p-norm approximates the rank function.

  • Truncated Schatten p-norm sums only the p power of singular values of \((\min (m,n)-r)\), which combines TNN and Schatten p-norm advantages. It has been shown in [25, 26] that Schatten p-norm has a good performance in image restoration and a better effect of approximate rank function than other norms by using a series of experiments.

The main contributions of this paper can be summarized as follows.

  • The truncated Schatten p-norm based non-convex regularization models, which are directed against matrix completion and RPCA problems, respectively, are proposed;

  • The function expansion method is used to transform the non-convex optimization model into the convex optimization model, and the two-step iterative algorithm of ADMM [27] is utilized to solve the model;

  • The convergence of the proposed algorithm is proved mathematically;

  • The advantages of the proposed methods are further illustrated by synthetic data, actual image restoration, and background separation experiments.

The contents of this paper are arranged as follows. In Sect. 2, we establish regularization models of matrix completion based on truncated Schatten p-norm, corresponding algorithms, and convergence theorem. The corresponding RPCA regularization model and solution method based on truncated Schatten p-norm are described in Sect. 3. Section 4 describes and analyses the experimental results, and through the comparison of experimental results, the advantages of the proposed method are further explained. Section 5 makes a summarization and reduces the conclusion of the whole article. Finally, the details of the proof of the convergence theorem are attached in “Appendix”.

2 Regularization of matrix completion based on truncated Schatten p-norm (TSPN-MC)

2.1 TSPN-MC model

From [25] and [26], it follows that truncated Schatten p-norm can be written as

$$\begin{aligned} \Vert X\Vert _{r}^{p}&=\sum _{i=r+1}^{\min (m,n)}(\sigma _{i}(X))^{p} \nonumber \\&=\min _{A,B}\sum _{i=1}^{\min (m,n)}(1-\sigma _{i}(B^{\top }A)) (\sigma _{i}(X))^{p},~~ 0<p\le 1, \end{aligned}$$
(2.1)

where \(A\in {\mathbf {R}}^{r\times m}\), and \(B\in {\mathbf {R}}^{r\times n}\). Further, we need the following lemma.

Lemma 2.1

( see[25]) Suppose that the rank of matrix \(X\in {\mathbf {R}}^{m\times n}\) is \(r (r\le \min (m,n))\), and its singular value decomposition is \(X=U\Delta V^{\top }\), where \(U=(\mu _{1}, \ldots , \mu _{m})\in {\mathbf {R}}^{m\times m}\), \(\Delta \in {\mathbf {R}}^{m \times n}\), \(V=(\nu _{1}, \ldots , \nu _{n})\in {\mathbf {R}}^{n\times n}\). Then when \(A=(\mu _{1}, \ldots , \mu _{r})^{\top }\in {\mathbf {R}}^{r\times m}\), \(B=(\nu _{1}, \ldots , \nu _{r})^{\top }\in {\mathbf {R}}^{r\times n}\), and \(0<p\le 1\), the optimization problem:

$$\begin{aligned} \Vert X\Vert _{r}^{p}= & {} \min _{A,B}\sum _{i=1}^{\min (m,n)}(1-\sigma _{i}(B^{\top }A))(\sigma _{i}(X))^{p} ~~ \text {s. t.} ~~AA^{\top } \nonumber \\= & {} I_{r\times r}, BB^{\top }=I_{r\times r} \end{aligned}$$
(2.2)

has optimal solution.

From Eq. (2.1) and Lemma 2.1, we improve the model of matrix completion (1.3) and obtain the new model based on the truncated Schatten p-norm:

$$\begin{aligned} \min _{X} ~\sum _{i=1}^{\min (m,n)}(1-\sigma _{i}(B^{\top }A)) (\sigma _{i}(X))^{p} ~~\text {s. t.} ~~P_{\Omega }(X)=P_{\Omega }(M), \end{aligned}$$
(2.3)

where \(A\in {\mathbf {R}}^{r\times m}\), \(B\in {\mathbf {R}}^{r\times n}\), \(AA^{\top }=I_{r\times r}\), \(BB^{\top }=I_{r\times r}\), and \(0<p\le 1\).

2.2 Solving TSPN-MC

Since (2.3) is a non-convex optimization problem, it cannot be solved directly by the usual method. To this end, we first put our hand to transform the model (2.3).

Let \(F(\sigma (X))=\sum _{i=1}^{\min (m,n)}(1-\sigma _{i}(B^{\top }A))(\sigma _{i}(X))^{p}\), then its derivative with respect to \(\sigma (X)\) is

$$\begin{aligned} \nabla F(\sigma (X))=\sum _{i=1}^{\min (m,n)}p(1-\sigma _{i} (B^{\top }A))(\sigma _{i}(X))^{p-1}. \end{aligned}$$
(2.4)

Therefore, we can obtain that the first-order Taylor expansion of \(F(\sigma (X))\):

$$\begin{aligned} \begin{aligned} F(\sigma (X))&=F(\sigma (X_{k}))+\langle \nabla F(\sigma (X_{k})), \sigma (X)-\sigma (X_{k})\rangle \\&=\nabla F(\sigma (X_{k}))\cdot \sigma (X) \\&=\sum _{i=1}^{\min (m,n)}p(1-\sigma _{i}(B^{\top }A))(\sigma _{i}(X_{k}))^{p-1}\cdot \sigma _{i}(X). \end{aligned} \end{aligned}$$
(2.5)

Let \(\omega _{i}=p(1-\sigma _{i}(B^{\top }A))(\sigma _{i}(X_{k}))^{p-1}\), then \(F(\sigma (X))=\sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i}(X)\), where \(W:=\{\omega _{i}\}_{i=1}^{\min (m,n)}\) is a no decreasing weight sequence. As a result, the model (2.3) becomes a model based on weighted nuclear norm:

$$\begin{aligned} \begin{aligned} \min _{X} ~\sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i} ~~ \text {s. t.} ~~P_{\Omega }(X)=P_{\Omega }(M). \end{aligned} \end{aligned}$$
(2.6)

Consequently, we can use ADMM and divide into two steps to solve the convex optimization model (2.6):

  • Step 1: Initialize \(X_{1}=M\), and calculate \(X_{s} = U_{s} \Delta _{s}V_{s}^{\top }\) in the \((s+1)\)-th iteration. Then, \(A_{s}\) and \(B_{s}\) are calculated from \(U_{s}\) and \(V_{s}\);

  • Step 2: Fix \(A_{s}\) and \(B_{s}\), and calculate the weight \(W=\{\omega _{i}\}_{i=1}^{r}\) of K-th iteration. Then, the ADMM algorithm is used to solve (2.6).

We sort out the specific solution process, and obtain the following Algorithm 1.

figure a

The process of using ADMM to solve (2.6) is described in detail below. We first introduce the variable N and rewrite the model (2.6) as

$$\begin{aligned} \min _{X} ~\sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i} ~~\text {s. t.} ~~X+N=M,P_{\Omega }(N)=0. \end{aligned}$$
(2.7)

Then, we construct augmented Lagrangian function of (2.7) as

$$\begin{aligned} \Gamma (X,N,Y,\mu )= & {} \sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i}+\langle Y,M-X-N\rangle \nonumber \\&+\frac{\mu }{2}\Vert M-X-N\Vert _{F}^{2}, \end{aligned}$$
(2.8)

where Y is a Lagrangian multiplier, and \(\mu > 0\) is a penalty factor.

Fixing X, and updating N follows

$$\begin{aligned} N_{k+1}=\arg \min _{N}\frac{\mu _{k}}{2}\left\| N- \left( M-X_{k}+\frac{1}{\mu _{k}}Y_{k}\right) \right\| _{F}^{2} ~~~\text {s. t.} ~~\Vert P_{\Omega }(N)\Vert _{F}^{2}=0, \end{aligned}$$
(2.9)

and

$$\begin{aligned} N_{k+1}=M-X_{k}+\frac{1}{\mu _{k}}Y_{k}. \end{aligned}$$
(2.10)

Then, fixing N and updating X follows

$$\begin{aligned} X_{k+1}= & {} \arg \min _{X}\frac{1}{\mu _{k}} \sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i} \nonumber \\&+\frac{1}{2} \left\| X- \left( M-N_{k+1} +\frac{1}{\mu _{k}}Y_{k}\right) \right\| _{F}^{2}. \end{aligned}$$
(2.11)

Let \(Q_{X}=M-N_{k+1}+\frac{1}{\mu _{k}}Y_{k}\), then (2.11) can be solved by the following Lemma 2.2.

Lemma 2.2

(see [24]) Suppose that the rank of matrix Q is r, and its singular value decomposition is \(Q=U\Delta V^{\top }\), \(\Delta =\text {Diag}(\sigma _{i}(Q))\), \(1\le i\le r\), then for any \(\tau >0\), the optimization problem

$$\begin{aligned} X^{*}=\arg \min _{X}\tau \sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i}+\frac{1}{2}\Vert X-Q\Vert _{F}^{2}, \end{aligned}$$
(2.12)

has optimum solution:

$$\begin{aligned} X^{*}=S_{\omega ,\tau }(Q):=U(\Delta -\tau \mathrm {diag}(W))_{+}V^{\top }, \end{aligned}$$

where \(S_{\omega ,\tau }(\cdot )\) is weighted singular value shrink operator, \((\cdot )_{+}:=\max (\cdot ,0)\), and \(W=\{\omega _{i}\}_{i=1}^{r}\).

Therefore, from Lemma 2.2 it follows the solution of (2.11):

$$\begin{aligned} X_{k+1}=S_{\omega ,\frac{1}{\mu _{k}}}(Q_{X}). \end{aligned}$$
(2.13)

So updating Y and \(\mu \) achieves

$$\begin{aligned} Y_{k+1}= & {} Y_{k}+\mu _{k}(M-X_{k+1}-N_{k+1}), \end{aligned}$$
(2.14)
$$\begin{aligned} \mu _{k+1}= & {} \min (\rho \mu _{k}, \mu _{\text {max}}), \end{aligned}$$
(2.15)

where \(\rho (>1)\) is a constant.

Sorting out the above details obtains the following matrix completion regularization (TSPN-MC) algorithm based on truncated Schatten p-norm 2.

figure b

As the end of this section, we give the convergence theorem of Algorithm 2. The details of its proof will be given in “Appendix”.

Theorem 2.1

\(\{X_{k}\}\) obtained by Algorithm 2 is convergent.

3 Low rank sparse decomposition based on truncated Schatten p-norm (TSPN-RPCA)

In the previous section, we introduced the TSPN-MC model and presented solution algorithms. In this section, we build a matrix low-rank sparse decomposition model based on truncated Schatten p-norm and its solution algorithm.

We can rewrite the model (1.4) as

$$\begin{aligned} \begin{aligned}&\min _{X,E} ~\sum _{i=1}^{\min (m,n)}(1-\sigma _{i}(B^{\top }A))(\sigma _{i}(X))^{p} \\&\quad +\lambda \Vert E\Vert _1 ~~~ \text {s. t.} ~~M =X+E. \end{aligned} \end{aligned}$$
(3.1)

Similarly, the TSPN-RPCA model can be solved by two-steps iterative method. Because the first step solution process is the same as the first step solution process of model TSPN-MC, we here only introduces the second step solving process with ADMM. Clearly, the Lagrangian functions of (3.1) can be represented as

$$\begin{aligned} \begin{aligned} \Gamma (X, E, Y, \mu )&=\sum _{i=1}^{\min (m,n)}(1-\sigma _{i}(B^{\top }A))(\sigma _{i}(X))^{p}+\lambda \Vert E\Vert _{1}\\&\quad +\langle {Y, M-X-E}\rangle +\frac{\mu }{2}\Vert M-X-E\Vert _{F}^{2}. \end{aligned} \end{aligned}$$
(3.2)

Applying ADMM obtains

$$\begin{aligned} \left\{ \begin{array}{l} E_{k+1}=\arg \min _{E}\frac{\lambda }{\mu _{k}}\Vert E\Vert _{1}+\frac{1}{2}\left\| E- \left( M-X_{k}+\frac{1}{\mu _{k}}Y_{k}\right) \right\| _{F}^{2},\\ X_{k+1}=\arg \min _{X}\frac{1}{\mu _{k}}\sum _{i=1}^{\min (m,n)}\omega _{i}\sigma _{i}+\frac{1}{2}\left\| X- \left( M-E_{k+1}+\frac{1}{\mu _{k}}Y_{k}\right) \right\| _{F}^{2},\\ Y_{k+1}=Y_{k}+\mu _{k}(M-X_{k+1}-E_{k+1}),\\ \mu _{k+1}=\min (\rho \mu _{k}, \mu _{\max }),\rho >1.\\ \end{array} \right. \end{aligned}$$
(3.3)

Since the method of solving \(X_{k+1}\), \(Y_{k+1}\), and \(\mu _{k+1}\) is the same as that of TSPN-MC model, it is not introduced here. For \(E_{k 1} \), it can be solved by the following Lemma 3.1.

Lemma 3.1

(see [28]) For a given matrix \(C\in {\mathbf {R}}^{m\times n}\), and any \(\tau >0\), the solution of optimization problem

$$\begin{aligned} \min _{E}\tau \Vert E\Vert _{1}+\frac{1}{2}\Vert E-C\Vert ^{2}_{F} \end{aligned}$$
(3.4)

is \(E^{*}=\Theta _{\tau }[c_{ij}] \), where \(c_{ij}\) are the elements of matrixC, \(\Theta _{\tau }[\cdot ]\) is shrink operator defined by

$$\begin{aligned} \Theta _{\tau }[c_{ij}]:=\text {sgn}(c_{ij})\max {(|c_{ij}|-\tau , 0)}. \end{aligned}$$
(3.5)

Furthermore, the algorithm of TSPN-RPCA solved by ADMM can be summarized in following Algorithm 3.

figure c

4 Experiments

In this section, the effectiveness of the proposed model and algorithm are verified by a series of experiments on synthetic data and actual images. The simulations of all experiments are carried out in a MATLAB R2014a environment running on an Intel(R), Core(TM) i3-4150, CPU @ 3.5GHz with 4 GB main memory.

4.1 Application of TSPN-MC in image restoration

Firstly, the experiments results of the methods NN-MC [17], TNN-MC [1], WNN-MC [29], and TSPN-MC on synthetic data are compared, and the feasibility of the proposed algorithm is illustrated. Then, the effectiveness of the four methods is compared by the experimental results on actual image restoration.

4.1.1 Experimental results on synthetic data

Following the generated method of synthetic data in [29], the generated data obeys the Gaussian distribution \({\mathcal {N}}(0,1)\). We set the matrix size as \(m=n=400\), and take \(ps=0.1\), 0.2, and 0.3, respectively. So the number of missing data in the matrix is \((m\times n\times ps)\). Then, we select the value of \(pr\in [0.05, 0.3]\) for each ps at an interval of 0.05, and calculate the rank \(r=pr\times m\) of the data matrix. In order to illustrate the performance of the model, the matrix recovery error is used as an evaluation index, which is defined by

$$\begin{aligned} \text {Error}=\frac{\Vert X-M\Vert _{F}}{\Vert M\Vert _{F}}. \end{aligned}$$
(4.1)

For the data generated by each group of (ps, pr) values, we conduct 10 tests, and then take the average as the final result for that group. For the parameter p in TSPN-MC, depending on the different synthetic data, its specific value will be indicated in the results of the experiment.

Table 1 Error results of synthetic data recovery (\(ps=0.1\), \(p=0.4\))
Full size table
Table 2 Error results of synthetic data recovery (\(ps=0.2\), \(p=0.4\))
Full size table
Table 3 Error results of synthetic data recovery (\(ps=0.3\), \(p=0.3\))
Full size table
Table 4 Average run time of synthetic data recovery (in seconds/s)
Full size table

From the error results shown in Tables 1, 2, and 3, we can see that TSPN-MC and WNN-MC are better than the other two methods in recovery. However, the recovery error of TSPN-MC is the smallest, and it has better performance than the other three methods. On the other hand, with the increase of missing data and the rank of synthetic data matrix, the error fluctuation of TSPN-MC is small and has certain stability. Table 4 shows the average time of four methods to run on synthetic data. Because the singular value decomposition was used three times in the computation weight W, so the running time of TSPN-MC is longer than the other three methods.

4.1.2 Experimental results on image restoration

We select four images with the size of \(300\times 300\). By comparing the peak signal-to-noise ratio (PSNR), we verify the image restoration effect of TSPN-MC under the condition of missing rate of \(20\%, 40\%, 60\%, 80\%\), and text masking, respectively, to illustrate the performance advantages of TSPN-MC. As usual, the PSNR is defined by

$$\begin{aligned} \text {PSNR}=20 \log \frac{255}{ \sqrt{\frac{1}{mn}\Vert X-M\Vert _{F}^{2}}}, \end{aligned}$$
(4.2)

where \(X\in {\mathbf {R}}^{m \times n}, M\in {\mathbf {R}}^{m \times n}\) represents the original image and the restored image, respectively. Since the parameter settings of different images are different, we will mark the parameter p and truncated rank r of each image in the experimental results. The test images used in this article are shown in Fig. 1.

Fig. 1
figure 1

Experimental images

Full size image
Table 5 PSNR of test Fig. 1 (dB) (\(p=0.7\), \(r=8\))
Full size table
Table 6 PSNR of test Fig. 2 (dB) (\(p=0.8\), \(r=3\))
Full size table
Table 7 PSNR of test Fig. 3 (dB) (\(p=0.9\), \(r=2\))
Full size table
Table 8 PSNR of test Fig. 4 (dB) (\(p=0.7\), \(r=4\))
Full size table
Fig. 2
figure 2

Restoration results of image with \(40\%\) missing

Full size image
Fig. 3
figure 3

Restoration results of image with \(80\%\) missing

Full size image
Fig. 4
figure 4

Restoration results of text masking

Full size image

From PSNR shown in Tables 5, 6, 7 and 8, it can be concluded that the restoration effect of TSPN-MC is better than that of the other three methods, and even with the increase of the missing rate, the PSNR value is still decreasing. On the whole, TSPN-MC’s PSNR is higher than other methods, and the recovery effect is better. In order to further illustrate the advantages of the proposed method, Figs. 2, 3, and 4 show the restoration visual effects under different missing or masking conditions, respectively. From these Figures, we can clearly see that the image restored by TSPN-MC is closer to the original image and clearer than that of other methods. To sum up, TSPN-MC model has better recovery performance.

4.2 Application of TSPN-RPCA in background subtraction

4.2.1 Experimental results on synthetic data

In this section, the recovery effects of TSPN-RPCA and LRSD-TNN [30], IALM [21], ALM [21] and APG [31] are compared by generating synthetic data, and the effectiveness of the proposed algorithm is illustrated. First of all, we are generating a synthetic matrix with rank r and Sparsity degree spr: \(M_{0}=X_{0}+E_{0}\). Here the low rank matrix can be written as \(X_{0}=HG^{\top }\), where \(H\in {\mathbf {R}}^{m\times r}\), and \(G\in {\mathbf {R}}^{n\times r}\) satisfies Gaussian distribution \({\mathcal {N}}(0,1)\). And the sparse matrix \(E_{0}\) is a pulse sparse matrix with uniformly distribution on \([- t, t]\), where \(t=\max {(|X_{0}|)}\), and the number of elements in the matrix is \((spr\times m\times n)\). In the experiment, p is set as 0.2.

In order to illustrate the accuracy of synthetic data recovery, we compare the errors of different methods, including recovery total error Totalerr, low rank matrix error LRerr, and sparse matrix error SPerr. These errors are defined by

$$\begin{aligned} \text {Totalerr}= & {} \frac{\Vert M-M_{0}\Vert _{F}}{\Vert M_{0}\Vert _{F}}, \end{aligned}$$
(4.3)
$$\begin{aligned} \text {LRerr}= & {} \frac{\Vert X-X_{0}\Vert _{F}}{\Vert X_{0}\Vert _{F}}, \end{aligned}$$
(4.4)
$$\begin{aligned} \text {SPerr}= & {} \frac{\Vert E-E_{0}\Vert _{F}}{\Vert E_{0}\Vert _{F}}, \end{aligned}$$
(4.5)

respectively, where M, X, and E are restored matrices.

We first fix the rank of matrix as \(r=0.1n\), sparsity degree as \(spr=0.05\), and three sets of data of \(m=n=100, 500, 900\) are generated respectively. The matrix recovery experiments are then carried out in five methods, and the results are shown in Tables 9,  10, and 11. By analyzing the results in the Tables, we know that the error of TSPN-RPCA is the smallest, the accuracy is higher than the other four methods, and the original matrix can be recovered more accurately, and the rank and sparsity of the restored matrix are the same as those of the initial matrix. Even with the increase of matrix dimension, the recovery error of TSPN-RPCA can be maintained at a stable level. Because TSPN-RPCA involves matrix singular value decomposition many times, the time consumption is larger than other methods, especially when the matrix dimension is larger.

On the other hand, we fix matrix size as \(m=n=500\). When setting \(r=0.1n, spr=0.1\) and \(r=0.05n, spr=0.05\), we respectively illustrate the advantages of the proposed method. The results are shown in Tables 12 and 13. By comparing the results of Tables 10 and 12, we find that the recovery accuracy of TSPN-RPCA decreases when the sparsity of matrix is reduced, but it is still superior to other methods. In addition, when the rank of matrix decreases, comparison Tables 10 and 13 finds that the recovery accuracy of TSPN-RPCA does not fluctuate much, and time and the number of iterations are obviously reduced. In a word, TSPN-RPCA has better recovery effect and better performance than other methods.

Table 9 Error result of synthetic data recovery (\(m=n=100\), \(r=0.1n\), \(spr=0.05\))
Full size table
Table 10 Error result of synthetic data recovery (\(m=n=500\), \(r=0.1n\), \(spr=0.05\))
Full size table
Table 11 Error result of synthetic data recovery (\(m=n=900\), \(r=0.1n\), \(spr=0.05\))
Full size table
Table 12 Error result of synthetic data recovery (\(m=n=500\), \(r=0.1n\), \(spr=0.1\))
Full size table
Table 13 Error result of synthetic data recovery (\(m=n=500\), \(r=0.05n\), \(spr=0.05\))
Full size table

4.2.2 Experimental results on background subtraction

In this subsection, the background subtraction experiment is carried out through the actual video, and the superior performance of the proposed method is further verified by the comparative experiment of LRSD-TNN, IALM, and TSPN-RPCA.

For a given video, each frame can be regarded as a column of elements of the matrix. We chose three different videos [30]: Bootstrap, Hall, and Lobby, respectively. We select 16 frames of each video and convert it into a matrix with \((mn \times 16)\) dimension, where m, n is the dimension size of each video. Due to the limited space of the article, this paper only shows the effect diagram of the separation prospect. It can be seen from the visual diagram Fig. 5 that the moving target in the video can be clearly separated by the proposed method. The separation effect of the other two methods is relatively poor, and the light in the background and the “ghost shadow” formed by the moving target appear. In this experiment, the parameter value of TSPN-RPCA is set as \(p=0.2\), and the truncation rank is taken as \(r=3\).

Fig. 5
figure 5

Different video front and rear scene separation effect diagram (from top to bottom is Bootstrap, Hall, Lobby)

Full size image

5 Conclusion

This paper studied matrix completion (TSPN-MC) and matrix low rank sparse decomposition (TSPNR-PCA) based on truncated Schatten p-norm. Combined with the characteristics and advantages of truncated norm and Schatten p-norm, the flexibility of the model and its effectiveness in practical problems are enhanced by adjusting the value of \(p (0 < p\le 1)\). We first used Taylor expansion to transform the proposed TSPN-MC and TSPN-RPCA non-convex models into convex optimization models. Then, the popular alternating direction multiplier method (ADMM) was used to solve the models. In particular, the convergence of the proposed algorithm is proved. A series of comparative experiments further verified the effectiveness and superiority of the proposed method.

It should be pointed out that in the solution of the models, the singular value of the matrix needs to be decomposed and calculated, which is bound to increase the time cost of the experiment. Therefore, in the future research, we should pay attention to how to find new methods to reduce the time consumption caused by singular value decomposition (SVD). In addition, for the selection of truncated rank, we will consider using adaptive method to determine its value in order to reduce the repetition times of the experiment.