Enhancing Matrix Completion Using a Modified Second-Order Total Variation

Abstract

In this paper, we propose a new method to deal with the matrix completion problem. Different from most existing matrix completion methods that only pursue the low rank of underlying matrices, the proposed method simultaneously optimizes their low rank and smoothness such that they mutually help each other and hence yield a better performance. In particular, the proposed method becomes very competitive with the introduction of a modified second-order total variation, even when it is compared with some recently emerged matrix completion methods that also combine the low rank and smoothness priors of matrices together. An efficient algorithm is developed to solve the induced optimization problem. The extensive experiments further confirm the superior performance of the proposed method over many state-of-the-art methods.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Matrix Completion (MC) refers to the problem of filling in missing entries of an unknown matrix from a limited sampling of its entries. This problem has received widespread attentions of researchers in many real applications; see, e.g., [1–3]. Generally, it is impossible to exactly recover arbitrary matrices from such a problem without some additional information since the problem is extraordinarily ill-posed [4] and hence has infinitely many solutions. However, in many realistic scenarios, very often the matrix we wish to recover is low-rank or can be approximated by a low-rank matrix, as illustrated in Figure 1. Therefore, an immediate idea to model MC is to pursue the low rank of matrices by solving the following optimization problem:$$\begin{array}{c}\text{(1)}& \underset{X}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left(X\right)\mathrm{s}.\mathrm{t}.\hspace{1em}{X}_{\Omega }=M_{\Omega },\end{array}$$where $X,M\in {\mathbb{R}}^{m\times n}$ and the entries of $M$ in location set $\Omega \subset [m]\times [n]$ ($[k]\triangleq \{\mathrm{1,2},\dots ,k\}$) are given while the remaining entries are missing.

[figures omitted; refer to PDF]

Unfortunately, problem (1) is of little practical use since it is NP-hard in general. To circumvent this issue, a nuclear norm minimization method was suggested in [4, 5], which solves$$\begin{array}{c}\text{(2)}& \underset{X}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{‖X‖}_{\ast }\mathrm{s}.\mathrm{t}.\hspace{1em}{X}_{\Omega }=M_{\Omega },\end{array}$$where ${‖X‖}_{\ast }\triangleq {\sum }_{i=\mathrm{1}}^{\mathrm{m}\mathrm{i}\mathrm{n}\{m,n\}}{\sigma }_i(X)$ and ${\sigma }_i(X)$ denotes the $i$th largest singular value of $X$. Especially in [4], Candès and Recht have proved theoretically that any low-rank matrices can be exactly recovered by solving problem (2) under some necessary assumptions. Recently, some new and deep results on the above problem (2) have been obtained to tackle the theoretical defects in [4]; see, e.g., [6, 7]. Many algorithms have also been proposed to solve problem (2) and its variants, including the Accelerated Proximal Gradient (APG) algorithms [8, 9], the Iterative Reweighted Least Squares (IRLS) algorithm [10], and the Singular Value Thresholding (SVT) algorithms [11, 12].

Nuclear norm is the tightest convex approximation of rank function, but it is far from the closest one [13]. The relationship between nuclear norm and the rank function of matrices is similar to that between ${\mathcal{l}}_{\mathrm{1}}$ norm and ${\mathcal{l}}_{\mathrm{0}}$ norm of vectors [4, 14]. To get a much closer approximation to the rank function, many nonconvex functions used to approximate the ${\mathcal{l}}_{\mathrm{0}}$ norm, see, e.g., [15–19], have been successfully extended to replace the nuclear norm [20–22]. Two representative ones are the Schatten-$q$ quasi-norm [20, 23, 24] and the truncated nuclear norm [21, 25] which is also called the partial sum of singular values [26]. The induced methods based on the above two approximate functions have been well investigated to deal with the MC problem [20, 21] and obtained much better performance than previous nuclear norm minimization method. Besides the above, there still exist many other methods used to tackle the MC problem; see, e.g., [27, 28] for the matrix factorization based methods and [29, 30] for the greedy methods.

Overall, almost all the existing MC methods are designed to approach the rank function and thus to induce the low rank. To some degree, low rank only characterizes the global prior of a matrix. In some instances, however, besides the low rank the matrices often have some additional structural priors. We still take the matrix (grey image) shown in Figure 1(a) for example. It is rich in smoothness features (priors). In other words, an entry and its neighboring entries in such a matrix often have small difference in their values. When dealing with such matrices, most existing MC methods in fact can not well capture their smoothness priors and hence may result in a poor performance. On the other hand, when the entries of a matrix reach an incredibly high missing ratio or the high-quality recovered matrices are in urgent need, one has no choice but to take their additional priors into consideration since it will become very difficult to exactly/robustly recover any matrices only by using their low rank prior. Therefore, how to mine more available priors of underlying matrices and integrate them into MC becomes a very crucial problem.

In this paper, we propose a new method that combines the low rank and smoothness priors of underlying matrices together to deal with the MC problem. Our method is not the first work on this topic, but by using a modified second-order total variation of matrices it becomes very competitive. In summary, the contributions of this paper are stated as follows:

(i)

A modified second-order total variation and nuclear norm of matrix are combined to characterize the smoothness and low-rank priors of underling matrices, respectively, which makes our method much more competitive for MC problem.

(ii)

An efficient algorithm is developed to deal with the optimization problem and the extensive experiments testify to the effectiveness of the proposed method over many state-of-the-art MC methods.

The remainder of this paper is organized as follows. In Section 2, we review some MC methods that simultaneously optimize both the low rank and smoothness priors of underlying matrices. Since matrices can be considered as the second-order tensors, this indicates that most tensor based completion methods can also be applied to the MC problem. Two related tensor completion methods are also included and introduced in this section. In Section 3, we present the proposed method and design an efficient algorithm to solve the induced optimization problem. Experimental results are presented in Section 4. Finally, the conclusion and future work are given in Section 5.

2. A Review on MC with Smoothness Priors

The low rank and smoothness priors of underlying matrices have been well studied in MC and visual data processing communities [31, 32], respectively. However, their combined work for MC is rarely reported. To the best of our knowledge, Han et al. [33] gave the first such work for MC and proposed a Linear Total Variation approximation regularized Nuclear Norm (LTVNN) minimization method, which takes the form$$\begin{array}{c}\text{(3)}& \underset{X}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\gamma {‖X‖}_{\ast }+\left(\mathrm{1}-\gamma \right){‖X‖}_{\mathrm{L}\mathrm{T}\mathrm{V}\mathrm{A}}\mathrm{s}.\mathrm{t}.\hspace{1em}{X}_{\Omega }=M_{\Omega },\end{array}$$where $\mathrm{0}\le \gamma \le \mathrm{1}$ is a penalty parameter. In LTVNN method, the smoothness priors of underlying matrices are constrained by a Linear Total Variation Approximation (LTVA), which is defined as$$\begin{array}{}\text{(4)}& {‖X‖}_{\mathrm{L}\mathrm{T}\mathrm{V}\mathrm{A}}\triangleq {\displaystyle \sum }_{i=\mathrm{1}}^m\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^{\mathrm{n}}\left({\left(D_{i,j}^v\left(X\right)\right)}^{\mathrm{2}}+{\left(D_{i,j}^h\left(X\right)\right)}^{\mathrm{2}}\right),\end{array}$$where $$\begin{array}{c}\text{(5)}& D_{i,j}^v\left(X\right)=\left\{\begin{array}{cc}{X}_{i,j}-X_{i+\mathrm{1},j},\hfill & \mathrm{1}\le i<m\hfill \\ \mathrm{0},\hfill & i=m,\hfill \end{array}\right.D_{i,j}^h\left(X\right)=\left\{\begin{array}{cc}{X}_{i,j}-X_{i,j+\mathrm{1}},\hfill & \mathrm{1}\le j<n\hfill \\ \mathrm{0},\hfill & j=n.\hfill \end{array}\right.\end{array}$$It has been shown in [33] that this LTVNN method is superior to many state-of-the-art MC methods, such as previous SVT method [11] and TNNR method [21], that only pursue the low rank. However, LTVNN method may result in staircase effect due to the use of linear total variation. On the other hand, the induced LTVNN algorithm does not solve problem (3) directly, but solves it by dividing problem (3) into two subproblems firstly, then solving these two subproblems independently and outputting the final results based on the solutions to these two subproblems lastly. Obviously, such an algorithm strategy is not consistent with their proposed optimization problem (3).

Recently, such consideration has been extended to deal with the tensor completion (TC) problem. From the perspective of tensor, vectors and matrices can be considered as the first- and second-order tensors, respectively. Therefore, most existing TC methods can still be used to deal with the MC problem. In 2014, Chen et al. [34] proposed a Tucker decomposition based Simultaneous Tensor Decomposition and Completion (STDC) method for TC. This STDC method solves the following optimization problem:$$\begin{array}{c}\text{(6)}& \underset{\mathcal{G},U^{\left(\mathrm{1}\right)},\dots ,U^{\left(N\right)}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{\displaystyle \sum }_{i=\mathrm{1}}^N{\alpha }_i{‖U^{\left(i\right)}‖}_{\ast }+\delta \mathrm{T}\mathrm{r}\left(\Phi L{\Phi }^T\right)+\gamma {‖\mathcal{G}‖}_F^{\mathrm{2}}\mathrm{s}.\mathrm{t}.\hspace{1em}\mathcal{X}=\mathcal{G}\times {\left\{U^{\left(i\right)}\right\}}_{i=\mathrm{1}}^N,\\ \hspace{1em}{\mathcal{X}}_{\Omega }={\mathcal{M}}_{\Omega },\end{array}$$where $\mathcal{X},\mathcal{M}\in {\mathbb{R}}^{I_{\mathrm{1}}\times I_{\mathrm{2}}\cdots \times I_N}$, $\mathcal{X}\triangleq \mathcal{G}\times \{U^{(i)}{\}}_{i=\mathrm{1}}^N$ is the Tucker decomposition of tensor $\mathcal{X}$, $\Phi \triangleq (U^{(\mathrm{1})}\otimes U^{(\mathrm{2})}\otimes \cdots \otimes U^{(N)})$ is a unified factor matrix that contains all factor matrices, $\otimes$ is the Kronecker product, and $L$ is a preset matrix designed by some priors. Similar to the matrix case, the elements of tensor $\mathcal{M}$ in location set $\Omega$ ($\subset [I_{\mathrm{1}}]\times [I_{\mathrm{2}}]\times \cdots \times [I_N])$ are given while the rest are missing. In problem (6), ${\sum }_{i=\mathrm{1}}^N{\alpha }_i{‖U^{(i)}‖}_{\ast }$, i.e., the first term of the objective function, characterizes the low rank of tensor $\mathcal{X}$, and its second term enforces the similarity between individual components, which provides some smoothed results for $\mathcal{X}$. Thus, STDC can be considered as a tensor extension of low-rank and smooth matrix completion. Later, based on another PARAFAC decomposition of tensors, Yokota et al. [35] proposed a Smooth PARAFAC tensor Completion (SPC) method that integrates low rank and smoothness priors of tensor by solving$$\begin{array}{c}\text{(7)}& \underset{\mathcal{G},U^{\left(\mathrm{1}\right)},\dots ,U^{\left(N\right)}}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\frac{\mathrm{1}}{\mathrm{2}}{‖\mathcal{X}-\mathcal{Z}‖}_F^{\mathrm{2}}+{\displaystyle \sum }_{r=\mathrm{1}}^R\frac{g_r^{\mathrm{2}}}{\mathrm{2}}{\displaystyle \sum }_{i=\mathrm{1}}^N{\rho }^{\left(i\right)}{‖L^{\left(i\right)}{\mathbf{u}}_r^{\left(i\right)}‖}_p^p\mathrm{s}.\mathrm{t}.\hspace{1em}\mathcal{Z}={\displaystyle \sum }_{r=\mathrm{1}}^R{g}_r·{\mathbf{u}}_r^{\left(\mathrm{1}\right)}\odot {\mathbf{u}}_r^{\left(\mathrm{2}\right)}\odot \cdots \odot {\mathbf{u}}_r^{\left(N\right)},\\ \hspace{1em}{\mathcal{X}}_{\Omega }={\mathcal{M}}_{\Omega },\\ \hspace{1em}{\mathcal{X}}_{{\Omega }^c}={\mathcal{Z}}_{{\Omega }^c},\\ \hspace{1em}{‖{\mathbf{u}}_r^{\left(i\right)}‖}_{\mathrm{2}}=\mathrm{1},\\ \hspace{1em}\forall r\in \left[R\right],\hspace{0.17em}\hspace{0.17em}\forall i\in \left[N\right],\end{array}$$where $\mathcal{Z}\triangleq {\sum }_{r=\mathrm{1}}^R{g}_r·{\mathbf{u}}_r^{(\mathrm{1})}\odot {\mathbf{u}}_r^{(\mathrm{2})}\odot \cdots \odot {\mathbf{u}}_r^{(N)}$ is the PARAFAC decomposition of tensor $\mathcal{Z}$, $\odot$ is the outer product, ${\Omega }^c$ stands for the complement set of $\Omega$, ${‖·‖}_p$ is the classical ${\mathcal{l}}_p$ norm on vectors, and the matrix $L^{(i)}\in {\mathbb{R}}^{(I_i-\mathrm{1})\times I_i}$ is a smoothness constraint matrix, defined as $$\begin{array}{}\text{(8)}& L^{\left(i\right)}\triangleq \left[\begin{array}{ccccc}\mathrm{1}& -\mathrm{1}& & & \\ & \mathrm{1}& -\mathrm{1}& & \\ & & \ddots & \ddots & \\ & & & \mathrm{1}& -\mathrm{1}\end{array}\right].\end{array}$$SPC method integrates low rank and smoothness priors into a single term (i.e., the second term of the objective function in problem (7)), and it is totally different from the STDC method. Besides, it has been proved numerically in [35] that SPC method performs much better than the SDTC method. More discussion on tensor and TC problems is beyond the scope of this paper, we refer interested readers to [35, 36] and the references within.

3. Proposed New Method

In this section, we propose a new method that combines the low rank and smoothness priors of underlying matrices to deal with the MC problem. In our method, the nuclear norm is used to characterize the low rank of underlying matrices while their smoothness priors are characterized by a modified second-order total variation (MSTV), which is defined as$$\begin{array}{}\text{(9)}& {‖X‖}_{\mathrm{M}\mathrm{S}\mathrm{T}\mathrm{V}}\triangleq {\displaystyle \sum }_{i=\mathrm{1}}^m\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^n\left({\left(R_{i,j}^v\left(X\right)\right)}^{\mathrm{2}}+{\left(R_{i,j}^h\left(X\right)\right)}^{\mathrm{2}}\right),\end{array}$$where $$\begin{array}{}\text{(10)}& R_{i,j}^v\left(X\right)=\left\{\begin{array}{cc}{X}_{i+\mathrm{1},j}-X_{i,j},\hfill & i=\mathrm{1},\hfill \\ X_{i-\mathrm{1},j}+X_{i+\mathrm{1},j}-\mathrm{2}{X}_{i,j},\hfill & \mathrm{1}<i<m,\hfill \\ X_{i-\mathrm{1},j}-X_{i,j},\hfill & i=m,\hfill \end{array}\right.\end{array}$$and $$\begin{array}{}\text{(11)}& R_{i,j}^h\left(X\right)=\left\{\begin{array}{cc}{X}_{i,j+\mathrm{1}}-X_{i,j},\hfill & j=\mathrm{1},\hfill \\ X_{i,j-\mathrm{1}}+X_{i,j+\mathrm{1}}-\mathrm{2}{X}_{i,j},\hfill & \mathrm{1}<j<n,\hfill \\ X_{i,j-\mathrm{1}}-X_{i,j},\hfill & j=n.\hfill \end{array}\right.\end{array}$$Obviously, such a modified second-order total variation is a new metric for smoothness priors of matrices, which is not different from the classical second-order total variation [37], or from previous linear total variation approximation. However, from a functional perspective, it not only inherits the geometrical structure of second-order total variation which avoids the staircase effect caused by linear total variation approximation, but also yields a smooth function that allows more efficient numerical algorithms. Figure 2 shows the geometrical differences between the linear total variation approximation and our modified second-order total variation. Besides, equation (9) can be further written in matrix form as$$\begin{array}{}\text{(12)}& {‖X‖}_{\mathrm{M}\mathrm{S}\mathrm{T}\mathrm{V}}={‖X^T{R}_m‖}_F^{\mathrm{2}}+{‖X{R}_n‖}_F^{\mathrm{2}},\end{array}$$where for $v=m,n$$$\begin{array}{}\text{(13)}& R_v\triangleq \left[\begin{array}{cccccc}-\mathrm{1}& \mathrm{1}& & & & \\ \mathrm{1}& -\mathrm{2}& \mathrm{1}& & & \\ & \mathrm{1}& -\mathrm{2}& \ddots & & \\ & & \mathrm{1}& \ddots & \mathrm{1}& \\ & & & \ddots & -\mathrm{2}& \mathrm{1}\\ & & & & \mathrm{1}& -\mathrm{1}\end{array}\right]\in {\mathbb{R}}^{v\times v}.\end{array}$$

[figures omitted; refer to PDF]

Now, the proposed methods that are based on nuclear norm and a modified second-order total variation can be modeled as the following optimization problem:$$\begin{array}{c}\text{(14)}& \underset{X}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{‖X‖}_{\ast }+\lambda \left({‖X^T{R}_m‖}_F^{\mathrm{2}}+{‖X{R}_n‖}_F^{\mathrm{2}}\right)\mathrm{s}.\mathrm{t}.\hspace{1em}{X}_{\Omega }=M_{\Omega },\end{array}$$where $\lambda >\mathrm{0}$ is a penalty parameter. Although in problem (14) nuclear norm is used to characterize the low rank of matrices, it can be replaced by some other approximate functions of rank function, such as Schatten-$q$ quasi-norm and truncated nuclear norm. On the other hand, both problem (14) and the aforementioned problem (3) share some similarities, but one will see later in the experimental part that the induced algorithm by proposed problem (14) performs much better than that of problem (3).

To solve problem (14), we adopt the Alternating Direction Method of Multipliers (ADMM) [38], which has been widely used to solve many application problems. To use ADMM, we first rewrite problem (14) as$$\begin{array}{c}\text{(15)}& \underset{X}{\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{‖X‖}_{\ast }+\lambda \left({‖Y^T{R}_m‖}_F^{\mathrm{2}}+{‖Y{R}_n‖}_F^{\mathrm{2}}\right)\mathrm{s}.\mathrm{t}.\hspace{1em}X-Y=\mathrm{0},\\ \hspace{1em}{Y}_{\Omega }=M_{\Omega }.\end{array}$$

Then the corresponding augmented Lagrangian function of (15) is presented as $$\begin{array}{}\text{(16)}& {\mathcal{L}}_{\rho }\left(X,Y,Z\right)={‖X‖}_{\ast }+\lambda \left({‖Y^T{R}_m‖}_F^{\mathrm{2}}+{‖Y{R}_n‖}_F^{\mathrm{2}}\right)+\mathrm{tr}\left(Z^T\left(X-Y\right)\right)+\frac{\rho }{\mathrm{2}}{‖X-Y‖}_F^{\mathrm{2}},\end{array}$$where $Z\in {\mathbb{R}}^{m\times n}$ is the dual variable and $\rho >\mathrm{0}$ is a penalty parameter associated with the augmentation. According to ADMM, the iterative procedure can be described as follows:

(1)

Fixing $Y^{(k)}$ and $Z^{(k)}$, solve for $X^{(k+\mathrm{1})}$ by $$\begin{array}{}\text{(17)}& X^{\left(k+\mathrm{1}\right)}=\underset{X}{\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{\mathcal{L}}_{\rho }\left(X,Y^{\left(k\right)},Z^{\left(k\right)}\right),\end{array}$$

 

which is equivalent to$$\begin{array}{}\text{(18)}& X^{\left(k+\mathrm{1}\right)}=\underset{X}{\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{‖X‖}_{\ast }+\frac{\rho }{\mathrm{2}}{‖X-G‖}_F^{\mathrm{2}},\end{array}$$

 

where $G=Y^{(k)}-Z^{(k)}/\rho$. According to [11], problem (18) has a closed-form solution, which can be obtained by the singular value thresholding operator ${\mathcal{D}}_{\rho }(·)$, i.e.,$$\begin{array}{}\text{(19)}& X^{\left(k+\mathrm{1}\right)}={\mathcal{D}}_{\rho }\left(G\right)\triangleq S_G\hspace{0.17em}\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}\left(\mathrm{m}\mathrm{a}\mathrm{x}{\left\{{\sigma }_i\left(G\right)-\frac{\mathrm{1}}{\rho },\mathrm{0}\right\}}_{\mathrm{1}\le i\le m}\right)D_G^T,\end{array}$$

 

where $G\triangleq S_G·\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}(\{{\sigma }_i(G){\}}_{\mathrm{1}\le i\le m})·D_G^T$ is the singular value decomposition of $G$.

(2)

Fixing $X^{(k+\mathrm{1})}$ and $Z^{(k)}$, solve for $Y^{(k+\mathrm{1})}$ by $$\begin{array}{c}\text{(20)}& Y^{\left(k+\mathrm{1}\right)}=\underset{Y}{\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}{\mathcal{L}}_{\rho }\left(X^{\left(k+\mathrm{1}\right)},Y,Z^{\left(k\right)}\right),\mathrm{s}.\mathrm{t}.\hspace{1em}{Y}_{\Omega }=M_{\Omega },\end{array}$$

 

which is equivalent to $$\begin{array}{c}\text{(21)}& Y^{\left(k+\mathrm{1}\right)}=\underset{Y}{\mathrm{a}\mathrm{r}\mathrm{g}\hspace{0.17em}\mathrm{m}\mathrm{i}\mathrm{n}}\hspace{1em}\mathcal{J}\left(Y\right)\triangleq \lambda \left({‖Y^T{R}_m‖}_F^{\mathrm{2}}+{‖Y{R}_n‖}_F^{\mathrm{2}}\right)+\frac{\rho }{\mathrm{2}}{‖Y-H‖}_F^{\mathrm{2}},\mathrm{s}.\mathrm{t}.\hspace{1em}{Y}_{\Omega }=M_{\Omega },\end{array}$$

 

where $H\triangleq X^{(k+\mathrm{1})}+Z^{(k)}/\rho$. By setting the derivative of $\mathcal{J}(Y)$ with respect to $Y$ to zero, we have$$\begin{array}{}\text{(22)}& \mathrm{2}\lambda R_m{R}_m^{T}Y+Y\left(\mathrm{2}\lambda R_n{R}_n^T+\rho I_n\right)=\rho H,\end{array}$$

 

where $I_n$ is an $n\times n$ identity matrix. Equation (22) is the well known Sylvester equation [39]. In this paper, we resort to the Matlab command $lyap$ to solve it; i.e.,$$\begin{array}{}\text{(23)}& \widehat{Y}=lyap\left(\mathrm{2}\lambda R_m{R}_m^T,\mathrm{2}\lambda R_n{R}_n^T+\rho I_n,-\rho H\right).\end{array}$$

 

After we obtain $\widehat{Y}$, i.e., the solution to (22), we can hence approximately obtain $Y^{(k+\mathrm{1})}$ by$$\begin{array}{}\text{(24)}& Y^{\left(k+\mathrm{1}\right)}=M_{\Omega }+{\widehat{Y}}_{{\Omega }^c}.\end{array}$$

(3)

Update $Z^{(k+\mathrm{1})}$ by$$\begin{array}{}\text{(25)}& Z^{\left(k+\mathrm{1}\right)}=Z^{\left(k\right)}+\rho \left(X^{\left(k+\mathrm{1}\right)}-Y^{\left(k+\mathrm{1}\right)}\right).\end{array}$$

We summarize the iterative procedure in Algorithm 1. Note that we do not use a fixed $\rho$ but adopt an adaptive updating strategy for $\rho$ (see the 7th step in Algorithm 1). Such a setting is mainly inspired by the recent studies on ADMM [21, 26, 40]. In fact, both the theoretical and applied results have shown that such a setting can help achieve quick convergence for ADMM based algorithms and hence avoid high computation cost. Without loss of generality, we simply set $t=\mathrm{1.05}$ and ${\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{1}{\mathrm{0}}^{\mathrm{3}}$ for Algorithm 1. It should also be noted that the performance of the proposed algorithm can be further improved if one can optimize these two parameters.

Algorithm 1: Solving problem (14) via ADMM.

Input: $\lambda$ , $\Omega$, $M_{\Omega }$, $X^{(0)}$ = $Y^{(0)}$ = $M_{\Omega }$, $Z^{(0)}$ = 0, $\rho$, $R_m$, and $R_n$

Output: $X^{♯}$

 1:   Initialize $k\leftarrow 1$

 2:   repeat

 3:  Update $X^{\left(k+1\right)}$ by (19);

 4:  Update $\widehat{Y}$ by (23);

 5:  Update $Y^{(k+1)}$ by (24);

 6:  Update $Z^{(k+1)}$ by (25);

 7:  Update $\rho \leftarrow \min \{t\rho ,{\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}\}$;

 8:  Update $k\leftarrow k+1$.

 9:   until a certain stopping criterion is satisfied.

 10: return $X^{♯}\leftarrow M_{\Omega }+X_{{\Omega }^c}^{(k)}$.

4. Numerical Experiments

In this section, some experiments are conducted to evaluate the performance of the proposed method. They mainly involve solving the randomly masked image completion problem and the text masked image reconstruction problem. The former problem aims to complete the incomplete images generated by masking their entries randomly, and the latter one aims to reconstruct the images with text. In our experiments, the Lenna image shown in Figure 1(a) and 20 widely used test images shown in Figure 3 are used to generate the desired test matrices. To evaluate the quality of the reconstructed images, Structural SIMilarity (SSIM) and Peak Signal-to-Noise Ratio (PSNR) indices are adopted. We refer readers to [41] for SSIM index. As to PSNR index, suppose Mean Squared Error (MSE) is defined as ${‖(M-X^{♯}{)}_{{\Omega }^c}‖}_F^2/\left|{\Omega }^c\right|$, where $\left|{\Omega }^c\right|$ counts the number of elements in ${\Omega }^c$ and $M$ and $X^{♯}$ are the original image and the reconstructed image, respectively; then we can calculate the PSNR value by $\mathrm{10}\hspace{0.17em}{\mathrm{l}\mathrm{o}\mathrm{g}}_{\mathrm{10}}(\mathrm{25}{\mathrm{5}}^{\mathrm{2}}/\mathrm{M}\mathrm{S}\mathrm{E})$. The missing ratio of an incomplete image is always defined as $\left|{\Omega }^c\right|/(m·n)$. All the experiments are implemented in Matlab and the codes can be downloaded from https://github.com/DongSylan/LIMC.

[figure omitted; refer to PDF]

4.1. Convergence Behavior

In this part, we conduct some experiments to examine the convergence behavior of our Algorithm 1. The desired test matrices are generated by masking the entries in Lenna image randomly with a 60% missing ratio. Before the convergence analysis, we have to determine a proper penalty parameter $\lambda$ since it plays a vital role in our Algorithm 1. Figure 4 plots the relationship between $\lambda$ and the PSNR and SSIM results obtained by our Algorithm 1. It is easy to see that $\lambda =\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ is the best selection. In above experiments, we initialize $\rho =\mathrm{1}{\mathrm{0}}^{-\mathrm{2}}$ and set the stopping criterion as$$\begin{array}{c}\text{(26)}& n\left(k\right)\triangleq \frac{{‖X^{\left(k+\mathrm{1}\right)}-X^{\left(k\right)}‖}_F}{\max \left\{{‖X^{\left(k\right)}‖}_F,\mathrm{1}\right\}}<\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}\mathrm{o}\mathrm{r}\hspace{0.17em}\hspace{0.17em}k>\mathrm{500},\end{array}$$where, here and throughout, $n(k)$ is called the Relative Neighboring Iteration Error (RNIE). Similar to RNIE, we define Relative True Iteration Error (RTIE) as $t(k)\triangleq {‖X^{(k+\mathrm{1})}-M‖}_F/{‖M‖}_F$. In what follows, we always set $\lambda =\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$ and $\rho =\mathrm{1}{\mathrm{0}}^{-\mathrm{2}}$ for our Algorithm 1.

[figures omitted; refer to PDF]

Figure 5 plots the convergence results of our Algorithm 1. One can easily see that both the RNIE and RTIE decrease rapidly and consistently. Specifically, in terms of RNIE, when $k$ exceeds 200 it tends to be smaller than $\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$. However, under the same condition, RTIE tends to be a constant. These observations to some degree indicate that the stopping criterion (26) is reasonable for our Algorithm 1.

[figures omitted; refer to PDF]

4.2. Randomly Masked Image Completion

To illustrate the effectiveness of our method, we compare our Algorithm 1 with 5 other state-of-the-art algorithms. They are IRLS algorithm [24], PSSV algorithm [26], LTVNN algorithm [33], and the SPC algorithms [35] with TV and QV smoothing, i.e., the SPC-TV and SPC-QV algorithms. In our experiments, we set $q=\mathrm{0.5}$, $\lambda =\mathrm{1}{\mathrm{0}}^{-\mathrm{4}}$, and $K=\mathrm{20}$ for IRLS algorithm, $\gamma =\mathrm{1}{\mathrm{0}}^{-\mathrm{3}}$ for PSSV algorithm, $\gamma =\mathrm{0.5}$ and $\lambda =\mathrm{1}$ for LTVNN algorithm, $\rho =[\mathrm{0.01,0.01}]$ for SPC-TV algorithm, and $\rho =[\mathrm{0.5,0.5}]$ for SPC-QV algorithm. We also uniformly set their maximum iterations to 500.

We start with completing the Lenna image masked randomly with several different missing ratios $\in \{\mathrm{70,65,60,55,50}\%\}$. The obtained PSNR and SSIM results are presented in Table 1, where the highest PSNR and SSIM values are underlined and marked in bold, while their second highest values are underlined only. One can directly see that, when the missing ratio decreases or in other words the known information increases, all the algorithms tend to perform better. However, our Algorithm 1 performs better than the rest of the algorithms in both PSNR and SSIM perspectives whenever the missing ratio ranges. Specifically, when compared to the IRLS and PSSV algorithms that only pursue the low rank of underlying matrices, our Algorithm 1 improves their PSNR and SSIM performance by more than 5dB and 0.2, respectively. Figure 6 shows the reconstructed images obtained by these algorithms. It is easy to find that our Algorithm 1 not only avoids the staircase effect resulting from LTVNN algorithm, but also leads to a better smoothness performance than SPC-TV and SPC-QV algorithms.

Table 1

PSNR$|$SSIM results on Lenna image with different missing ratios by different algorithms.

	70%	65%	60%	55%	50%
IRLS	21.89$|$0.595	22.49$|$0.661	22.91$|$0.707	23.13$|$0.747	23.34$|$0.774
PSSV	21.80$|$0.585	22.60$|$0.646	23.21$|$0.696	23.90$|$0.744	24.61$|$0.791
LTVNN	23.89$|$0.793	24.42$|$0.824	24.91$|$0.853	25.41$|$0.881	25.90$|$0.900
SPC-TV	24.29$|$0.743	24.88$|$0.776	25.24$|$0.801	25.72$|$0.829	26.06$|$0.852
SPC-QV	26.66 $|$ 0.864	27.15 $|$ 0.883	27.50 $|$ 0.898	27.89 $|$ 0.912	28.18 $|$ 0.925
Ours	27.87 $|$ 0.906	28.46 $|$ 0.921	28.96 $|$ 0.936	29.54 $|$ 0.948	29.89 $|$ 0.957

[figures omitted; refer to PDF]

To further confirm the effectiveness of our method, we apply our Algorithm 1, together with other 5 algorithms, to 20 widely used test images (Figure 3). The obtained results are presented in Table 2. An overall impression observed from Table 2 is that our Algorithm 1 achieves the highest SSIM in all cases and the highest PSNR in almost all cases. Although in terms of PSNR our Algorithm 1 performs weaker than SPC-QV algorithm in some cases, but these cases only occupy a small proportion (13/80) of all the cases, and the PSNR difference in these cases is also very small (less than 0.8dB).

Table 2

PSNR$|$SSIM results on 20 test images with different missing ratios by different algorithms.

	Missing ratio=70%						Missing ratio=60%
	IRLS	PSSV	LTVNN	SPC-TV	SPC-QV	Ours	IRLS	PSSV	LTVNN	SPC-TV	SPC-QV	Ours
1	27.58$|$0.802	27.88$|$0.821	29.32$|$0.902	29.14$|$0.864	30.59 $|$ 0.910	31.96 $|$ 0.936	29.11$|$0.869	29.35$|$0.882	30.41$|$0.935	29.84$|$0.888	30.94 $|$ 0.924	33.55 $|$ 0.965
2	21.34$|$0.586	21.43$|$0.593	23.37$|$0.768	23.50$|$0.715	25.29 $|$ 0.819	25.25 $|$ 0.838	22.61$|$0.712	22.67$|$0.700	24.22$|$0.833	24.34$|$0.784	26.10 $|$ 0.868	26.23 $|$ 0.888
3	22.03$|$0.596	22.12$|$0.606	24.29$|$0.804	24.70$|$0.761	27.37 $|$ 0.879	28.73 $|$ 0.922	23.12$|$0.709	23.80$|$0.730	25.44$|$0.868	25.78$|$0.825	28.27 $|$ 0.911	29.96 $|$ 0.949
4	19.87$|$0.470	20.19$|$0.487	21.95$|$0.645	21.55$|$0.592	22.64 $|$ 0.692	22.60 $|$ 0.728	20.90$|$0.610	20.79$|$0.596	22.49$|$0.736	22.01$|$0.681	23.19 $|$ 0.768	23.21 $|$ 0.800
5	22.77$|$0.630	23.25$|$0.644	24.67$|$0.755	24.71$|$0.735	26.15 $|$ 0.816	26.04 $|$ 0.829	23.98$|$0.735	24.22$|$0.742	25.44$|$0.824	25.41$|$0.803	26.80 $|$ 0.864	27.00 $|$ 0.882
6	22.72$|$0.623	22.56$|$0.609	24.55$|$0.766	24.86$|$0.742	26.94 $|$ 0.838	27.13 $|$ 0.861	23.69$|$0.721	23.94$|$0.716	25.53$|$0.833	25.69$|$0.802	27.61 $|$ 0.875	27.85 $|$ 0.895
7	20.76$|$0.582	20.91$|$0.592	22.64$|$0.804	23.11$|$0.734	24.94 $|$ 0.852	25.24 $|$ 0.887	21.98$|$0.704	22.21$|$0.702	23.57$|$0.865	24.04$|$0.797	25.79 $|$ 0.890	26.45 $|$ 0.929
8	24.26$|$0.683	24.14$|$0.689	25.48$|$0.839	26.86$|$0.808	28.62 $|$ 0.879	27.85 $|$ 0.882	25.56$|$0.782	26.21$|$0.788	26.68$|$0.886	28.11$|$0.852	29.81 $|$ 0.906	29.14 $|$ 0.917
9	20.40$|$0.558	20.33$|$0.557	22.01$|$0.687	22.14$|$0.667	23.78 $|$ 0.762	23.68 $|$ 0.784	21.37$|$0.674	21.28$|$0.665	22.73$|$0.769	22.85$|$0.748	24.45 $|$ 0.824	24.55 $|$ 0.846
10	23.39$|$0.621	23.25$|$0.614	25.09$|$0.730	25.34$|$0.731	27.25 $|$ 0.816	27.54 $|$ 0.838	24.26$|$0.717	24.48$|$0.725	25.96$|$0.805	26.19$|$0.801	28.08 $|$ 0.867	28.61 $|$ 0.888
11	19.19$|$0.539	19.60$|$0.571	21.69$|$0.798	21.53$|$0.690	23.23 $|$ 0.810	23.29 $|$ 0.850	20.69$|$0.669	20.68$|$0.662	22.52$|$0.856	22.36$|$0.753	23.96 $|$ 0.853	24.07 $|$ 0.894
12	17.87$|$0.525	17.92$|$0.528	19.80$|$0.696	19.95$|$0.658	22.04 $|$ 0.780	22.41 $|$ 0.800	18.89$|$0.642	19.12$|$0.654	20.66$|$0.784	20.89$|$0.746	23.07 $|$ 0.845	23.57 $|$ 0.865
13	24.69$|$0.619	24.64$|$0.616	27.07$|$0.783	26.83$|$0.742	28.70 $|$ 0.833	29.22 $|$ 0.864	25.69$|$0.731	25.73$|$0.719	27.81$|$0.843	27.51$|$0.805	29.26 $|$ 0.875	30.11 $|$ 0.906
14	24.00$|$0.668	23.89$|$0.666	25.53$|$0.777	25.94$|$0.766	27.96 $|$ 0.847	27.92 $|$ 0.861	25.12$|$0.760	25.25$|$0.765	26.49$|$0.842	26.96$|$0.830	28.83 $|$ 0.889	29.03 $|$ 0.905
15	23.44$|$0.595	23.71$|$0.605	25.64$|$0.735	25.38$|$0.707	26.92 $|$ 0.791	27.11 $|$ 0.814	24.48$|$0.704	24.49$|$0.700	26.22$|$0.800	25.93$|$0.773	27.50 $|$ 0.842	28.04 $|$ 0.870
16	19.73$|$0.545	19.72$|$0.546	21.43$|$0.750	21.92$|$0.690	24.06 $|$ 0.825	24.54 $|$ 0.868	20.85$|$0.666	21.04$|$0.658	22.41$|$0.826	22.81$|$0.764	24.93 $|$ 0.872	25.67 $|$ 0.913
17	19.76$|$0.514	19.59$|$0.504	21.94$|$0.704	21.96$|$0.653	24.10 $|$ 0.787	24.74 $|$ 0.835	20.76$|$0.634	20.94$|$0.630	22.86$|$0.789	22.89$|$0.738	24.96 $|$ 0.844	25.75 $|$ 0.885
18	20.12$|$0.555	19.96$|$0.543	22.11$|$0.748	22.67$|$0.708	25.71 $|$ 0.846	27.10 $|$ 0.898	20.98$|$0.659	21.76$|$0.675	23.39$|$0.827	23.84$|$0.783	26.75 $|$ 0.889	28.43 $|$ 0.932
19	21.83$|$0.604	21.72$|$0.599	23.63$|$0.809	24.35$|$0.758	26.93 $|$ 0.889	27.76 $|$ 0.927	22.78$|$0.715	23.64$|$0.721	24.95$|$0.877	25.59$|$0.822	28.02 $|$ 0.920	29.13 $|$ 0.953
20	20.27$|$0.577	20.38$|$0.584	22.01$|$0.748	22.21$|$0.703	23.84 $|$ 0.806	23.20 $|$ 0.812	21.41$|$0.695	21.63$|$0.693	22.89$|$0.823	23.19$|$0.779	24.85 $|$ 0.861	24.22 $|$ 0.868
	Missing ratio=55%						Missing ratio=50%
	IRLS	PSSV	LTVNN	SPC-TV	SPC-QV	Ours	IRLS	PSSV	LTVNN	SPC-TV	SPC-QV	Ours
1	29.45$|$0.887	29.98$|$0.905	30.87$|$0.946	30.06$|$0.899	31.04 $|$ 0.930	34.03 $|$ 0.973	29.90$|$0.901	30.74$|$0.923	31.47$|$0.957	30.46$|$0.910	31.45 $|$ 0.937	34.76 $|$ 0.978
2	22.91$|$0.750	23.21$|$0.745	24.53$|$0.859	24.75$|$0.815	26.44 $|$ 0.887	26.65 $|$ 0.906	23.15$|$0.782	23.80$|$0.787	24.88$|$0.881	25.15$|$0.842	26.84 $|$ 0.905	27.10 $|$ 0.922
3	23.36$|$0.743	24.58$|$0.780	25.88$|$0.890	26.20$|$0.850	28.66 $|$ 0.924	30.47 $|$ 0.958	23.59$|$0.772	25.42$|$0.824	26.35$|$0.910	26.69$|$0.873	29.04 $|$ 0.936	30.94 $|$ 0.965
4	21.15$|$0.658	21.03$|$0.643	22.65$|$0.769	22.18$|$0.718	23.34 $|$ 0.796	23.44 $|$ 0.826	21.28$|$0.696	21.26$|$0.687	22.82$|$0.800	22.36$|$0.753	23.56 $|$ 0.823	23.68 $|$ 0.851
5	24.17$|$0.766	24.61$|$0.783	25.71$|$0.851	25.68$|$0.830	27.06 $|$ 0.883	27.30 $|$ 0.902	24.36$|$0.793	25.02$|$0.819	25.95$|$0.873	25.93$|$0.854	27.31 $|$ 0.900	27.61 $|$ 0.918
6	23.95$|$0.758	24.54$|$0.763	25.94$|$0.859	26.05$|$0.829	27.90 $|$ 0.892	28.12 $|$ 0.909	24.08$|$0.783	25.01$|$0.799	26.26$|$0.880	26.37$|$0.852	28.12 $|$ 0.905	28.33 $|$ 0.920
7	22.31$|$0.743	22.98$|$0.752	24.04$|$0.889	24.55$|$0.824	26.21 $|$ 0.905	27.00 $|$ 0.944	22.37$|$0.772	23.48$|$0.790	24.28$|$0.906	24.78$|$0.848	26.40 $|$ 0.917	27.36 $|$ 0.954
8	25.81$|$0.810	27.13$|$0.830	27.11$|$0.906	28.58$|$0.875	30.04 $|$ 0.918	29.39 $|$ 0.931	26.04$|$0.831	28.08$|$0.861	27.62$|$0.922	29.14$|$0.892	30.49 $|$ 0.927	29.80 $|$ 0.942
9	21.67$|$0.715	21.77$|$0.714	23.05$|$0.803	23.20$|$0.783	24.77 $|$ 0.849	24.93 $|$ 0.871	21.84$|$0.749	22.19$|$0.757	23.36$|$0.833	23.55$|$0.815	25.09 $|$ 0.872	25.25 $|$ 0.890
10	24.47$|$0.750	25.07$|$0.772	26.38$|$0.836	26.62$|$0.832	28.45 $|$ 0.888	29.01 $|$ 0.906	24.62$|$0.778	25.66$|$0.812	26.71$|$0.860	27.02$|$0.858	28.81 $|$ 0.905	29.45 $|$ 0.922
11	21.00$|$0.710	21.15$|$0.702	22.89$|$0.878	22.72$|$0.781	24.29 $|$ 0.872	24.42 $|$ 0.911	21.17$|$0.743	21.60$|$0.742	23.09$|$0.896	22.92$|$0.806	24.46 $|$ 0.887	24.65 $|$ 0.923
12	19.09$|$0.683	19.66$|$0.705	20.97$|$0.814	21.27$|$0.782	23.44 $|$ 0.868	23.97 $|$ 0.887	19.31$|$0.721	20.38$|$0.758	21.39$|$0.846	21.82$|$0.818	23.99 $|$ 0.892	24.56 $|$ 0.909
13	25.94$|$0.764	26.25$|$0.760	28.17$|$0.865	27.83$|$0.830	29.58 $|$ 0.891	30.55 $|$ 0.920	26.11$|$0.792	26.70$|$0.796	28.40$|$0.884	28.08$|$0.851	29.80 $|$ 0.906	30.82 $|$ 0.932
14	25.35$|$0.790	25.92$|$0.807	26.93$|$0.868	27.41$|$0.857	29.19 $|$ 0.906	29.52 $|$ 0.922	25.52$|$0.813	26.65$|$0.843	27.26$|$0.887	27.73$|$0.876	29.49 $|$ 0.919	29.90 $|$ 0.934
15	24.75$|$0.744	24.91$|$0.746	26.54$|$0.831	26.24$|$0.806	27.85 $|$ 0.867	28.52 $|$ 0.893	24.94$|$0.773	25.25$|$0.781	26.77$|$0.855	26.52$|$0.832	28.12 $|$ 0.887	28.86 $|$ 0.911
16	21.12$|$0.706	21.64$|$0.707	22.77$|$0.853	23.24$|$0.795	25.29 $|$ 0.891	26.10 $|$ 0.928	21.28$|$0.738	22.22$|$0.752	23.16$|$0.878	23.66$|$0.825	25.69 $|$ 0.908	26.56 $|$ 0.941
17	20.94$|$0.670	21.51$|$0.684	23.20$|$0.821	23.19$|$0.770	25.20 $|$ 0.865	26.08 $|$ 0.903	21.09$|$0.706	22.00$|$0.732	23.52$|$0.848	23.55$|$0.804	25.51 $|$ 0.885	26.44 $|$ 0.918
18	21.24$|$0.696	22.64$|$0.733	23.96$|$0.856	24.39$|$0.816	27.18 $|$ 0.905	28.91 $|$ 0.943	21.36$|$0.727	23.50$|$0.783	24.40$|$0.880	24.88$|$0.844	27.60 $|$ 0.920	29.49 $|$ 0.953
19	23.00$|$0.750	24.39$|$0.770	25.43$|$0.898	26.09$|$0.848	28.44 $|$ 0.931	29.61 $|$ 0.962	23.19$|$0.777	25.20$|$0.815	25.88$|$0.917	26.53$|$0.871	28.67 $|$ 0.941	29.94 $|$ 0.968
20	21.64$|$0.734	22.13$|$0.740	23.20$|$0.848	23.60$|$0.813	25.23 $|$ 0.883	24.58 $|$ 0.890	21.77$|$0.764	22.67$|$0.783	23.49$|$0.872	23.93$|$0.840	25.58 $|$ 0.900	25.00 $|$ 0.909

4.3. Text Masked Image Reconstruction

Compared to the randomly masked image completion problem, text masked image reconstruction is a relatively hard task since the entries masked by the text are not randomly distributed in the matrix and the text may mask some important texture information. However, this problem can still be transformed into an MC problem by checking the position of the text first and regarding the corresponding entries as missing values.

Figure 7 shows the visual results obtained by above-mentioned algorithms on reconstruction of the Lenna image with text. In terms of PSNR and SSIM values, our Algorithm 1 and the SPC-QV algorithm rank first and second, respectively, followed by the rest of the algorithms. In terms of visual quality, the proposed Algorithm 1 well reconstructs the original image and its local feature structure is also well kept without seeing any text traces. In contrast, the images reconstructed by IRLS and PSSV algorithms are covered with the obvious text traces. The LTVNN algorithm suffers from staircase effect again. The image reconstructed by the SPC-QV algorithm is better than that by SPC-TV algorithm, but still has some faint text traces. Based on previous 20 test images, we generate another 20 desired images with text (Figure 8) to compare our Algorithm 1 with 5 other algorithms in dealing with the text masked image reconstruction problem. The obtained PSNR and SSIM results are reported in Table 3, which confirms again the excellent performance of our Algorithm 1.

Table 3

PSNR$|$SSIM results on reconstruction of 20 test images with text by different algorithms.

	IRLS	PSSV	LTVNN	SPC-TV	SPC-QV	Ours
1	28.56$|$0.956	30.47$|$0.975	30.91 $|$ 0.981	29.78$|$0.965	30.74$|$0.973	34.17 $|$ 0.992
2	22.13$|$0.911	23.96$|$0.930	24.43$|$0.955	24.62$|$0.939	26.13 $|$ 0.962	26.65 $|$ 0.972
3	22.27$|$0.895	25.45$|$0.944	25.41$|$0.963	25.78$|$0.948	27.70 $|$ 0.971	30.19 $|$ 0.987
4	21.14$|$0.897	21.68$|$0.904	22.69$|$0.933	22.50$|$0.920	23.43 $|$ 0.939	23.58 $|$ 0.950
5	23.60$|$0.919	25.18$|$0.943	25.33$|$0.951	25.40$|$0.945	26.62 $|$ 0.960	26.96 $|$ 0.969
6	22.85$|$0.902	24.94$|$0.932	25.74$|$0.956	25.56$|$0.941	27.30 $|$ 0.964	27.98 $|$ 0.973
7	21.14$|$0.906	23.30$|$0.933	23.20$|$0.959	23.70$|$0.937	25.00 $|$ 0.963	26.48 $|$ 0.983
8	24.93$|$0.926	29.08$|$0.962	27.33$|$0.969	28.72$|$0.956	30.12 $|$ 0.971	31.02 $|$ 0.979
9	21.12$|$0.905	22.70$|$0.926	22.94$|$0.940	23.38$|$0.935	24.66 $|$ 0.953	25.07 $|$ 0.962
10	23.84$|$0.912	26.49$|$0.948	26.04$|$0.949	26.76$|$0.950	28.19 $|$ 0.964	29.34 $|$ 0.974
11	20.20$|$0.895	21.32$|$0.911	22.21$|$0.958	22.07$|$0.924	23.41 $|$ 0.951	23.72 $|$ 0.971
12	18.12$|$0.892	20.51$|$0.926	20.64$|$0.943	20.97$|$0.933	22.62 $|$ 0.956	23.61 $|$ 0.967
13	25.32$|$0.920	27.09$|$0.938	27.95$|$0.959	27.72$|$0.947	29.28 $|$ 0.965	30.72 $|$ 0.977
14	24.31$|$0.920	26.74$|$0.951	26.67$|$0.958	27.18$|$0.953	28.58 $|$ 0.968	29.21 $|$ 0.977
15	24.30$|$0.913	25.41$|$0.929	26.37$|$0.948	26.06$|$0.938	27.42 $|$ 0.955	28.50 $|$ 0.968
16	20.19$|$0.890	22.56$|$0.920	22.41$|$0.949	22.97$|$0.931	24.80 $|$ 0.961	26.33 $|$ 0.977
17	19.76$|$0.874	21.80$|$0.908	22.77$|$0.942	22.61$|$0.925	24.27 $|$ 0.953	25.57 $|$ 0.969
18	19.77$|$0.872	23.90$|$0.933	23.72$|$0.953	23.97$|$0.937	26.48 $|$ 0.966	29.24 $|$ 0.984
19	21.43$|$0.895	24.76$|$0.931	25.19$|$0.967	25.12$|$0.943	27.25 $|$ 0.971	29.55 $|$ 0.988
20	20.69$|$0.902	22.71$|$0.934	22.80$|$0.951	23.02$|$0.941	24.44 $|$ 0.961	24.18 $|$ 0.967

[figures omitted; refer to PDF]

[figure omitted; refer to PDF]

5. Conclusion and Future Work

This paper proposed a new method that combines the low rank and smoothness priors of matrices to tackle the matrix completion problem. Different from previous LTVNN method, our proposed method characterizes the smoothness of matrices by using a modified second-order total variation, which not only avoids the staircase effect caused by LTVNN method, but also leads to a better performance. Even compared to the recently emerged smooth PARAFAC tensor completion method, our method is still highly competitive in both PSNR and SSIM perspectives. The extensive experiments further confirm the excellent performance of our proposed method. Potential future work includes replacing the nuclear norm used in our method with other (nonconvex) low-rank promoting functions, integrating more available priors of matrices to enhance the performance of existing matrix completion methods, and applying our modified second-order total variation to the tensor completion problems.

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.

Acknowledgments

This work was supported by the Natural Science Foundation of China under Grants Nos. 61273020 and 61673015.

References

[1] N. Komodakis, "Image Completion Using Global Optimization," Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06), pp. 442-452, DOI: 10.1109/CVPR.2006.141, .

[2] Y. Koren, R. Bell, C. Volinsky, "Matrix factorization techniques for recommender systems," The Computer Journal, vol. 42 no. 8, pp. 30-37, DOI: 10.1109/mc.2009.263, 2009.

[3] H. Ji, C. Liu, Z. Shen, Y. Xu, "Robust video denoising using low rank matrix completion," Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR '10), pp. 1791-1798, DOI: 10.1109/CVPR.2010.5539849, .

[4] E. J. Candès, B. Recht, "Exact matrix completion via convex optimization," Foundations of Computational Mathematics, vol. 9 no. 6, pp. 717-772, DOI: 10.1007/s10208-009-9045-5, 2009.

[5] B. Recht, M. Fazel, P. A. Parrilo, "Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization," SIAM Review, vol. 52 no. 3, pp. 471-501, DOI: 10.1137/070697835, 2010.

[6] Y. Chen, "Incoherence-optimal matrix completion," Institute of Electrical and Electronics Engineers Transactions on Information Theory, vol. 61 no. 5, pp. 2909-2923, DOI: 10.1109/TIT.2015.2415195, 2015.

[7] G. Liu, P. Li, "Low-rank matrix completion in the presence of high coherence," IEEE Transactions on Signal Processing, vol. 64 no. 21, pp. 5623-5633, DOI: 10.1109/TSP.2016.2586753, 2016.

[8] S. W. Ji, J. P. Ye, "An accelerated gradient method for trace norm minimization," pp. 457-464, DOI: 10.1145/1553374.1553434, .

[9] K.-C. Toh, S. Yun, "An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems," Pacific Journal of Optimization, vol. 6 no. 3, pp. 615-640, 2010.

[10] M. Fornasier, H. Rauhut, R. Ward, "Low-rank matrix recovery via iteratively reweighted least squares minimization," SIAM Journal on Optimization, vol. 21 no. 4, pp. 1614-1640, DOI: 10.1137/100811404, 2011.

[11] J. Cai, E. J. Candès, Z. Shen, "A singular value thresholding algorithm for matrix completion," SIAM Journal on Optimization, vol. 20 no. 4, pp. 1956-1982, DOI: 10.1137/080738970, 2010.

[12] J.-F. Cai, S. Osher, "Fast singular value thresholding without singular value decomposition," Methods and Applications of Analysis, vol. 20 no. 4, pp. 335-351, DOI: 10.4310/MAA.2013.v20.n4.a2, 2013.

[13] C. Xu, Z. C. Lin, H. B. Zha, "A unified convex surrogate for the Schatten-p norm," Proceedings of the AAAI Conference on Artificial Intelligence, pp. 926-932, .

[14] S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing,DOI: 10.1007/978-0-8176-4948-7, 2013.

[15] R. Chartrand, "Exact reconstruction of sparse signals via nonconvex minimization," IEEE Signal Processing Letters, vol. 14 no. 10, pp. 707-710, DOI: 10.1109/LSP.2007.898300, 2007.

[16] J. Wen, D. Li, F. Zhu, "Stable recovery of sparse signals via L p -minimization," Applied and Computational Harmonic Analysis, vol. 38 no. 1, pp. 161-176, DOI: 10.1016/j.acha.2014.06.003, 2015.

[17] Y. Wang, W. Yin, "Sparse signal reconstruction via iterative support detection," SIAM Journal on Imaging Sciences, vol. 3 no. 3, pp. 462-491, DOI: 10.1137/090772447, 2010.

[18] P. Yin, Y. Lou, Q. He, J. Xin, "Minimization of l 1-2 for compressed sensing," SIAM Journal on Scientific Computing, vol. 37 no. 1, pp. A536-A563, DOI: 10.1137/140952363, 2015.

[19] W. Wang, J. Wang, Z. Zhang, "Robust Signal Recovery with Highly Coherent Measurement Matrices," IEEE Signal Processing Letters, vol. 24 no. 3, pp. 304-308, DOI: 10.1109/LSP.2016.2626308, 2017.

[20] G. Marjanovic, V. Solo, "On l q optimization and matrix completion," IEEE Transactions on Signal Processing, vol. 60 no. 11, pp. 5714-5724, DOI: 10.1109/TSP.2012.2212015, 2012.

[21] Y. Hu, D. Zhang, J. Ye, X. Li, X. He, "Fast and accurate matrix completion via truncated nuclear norm regularization," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35 no. 9, pp. 2117-2130, DOI: 10.1109/TPAMI.2012.271, 2013.

[22] T.-H. Ma, Y. Lou, T.-Z. Huang, "Truncated L 1-2 models for sparse recovery and rank minimization," SIAM Journal on Imaging Sciences, vol. 10 no. 3, pp. 1346-1380, DOI: 10.1137/16M1098929, 2017.

[23] F. P. Nie, H. Huang, C. Ding, "Low-rank matrix recovery via efficient Schatten p-norm minimization," Proceedings of the 26th AAAI Conference on Artificial Intelligence, pp. 655-661, .

[24] M. J. Lai, Y. Y. Xu, W. T. Yin, "Improved iteratively reweighted least squares for unconstrained smoothed l q minimization," SIAM Journal on Numerical Analysis, vol. 51 no. 2, pp. 927-957, DOI: 10.1137/110840364, 2013.

[25] F. Cao, J. Chen, H. Ye, J. Zhao, Z. Zhou, "Recovering low-rank and sparse matrix based on the truncated nuclear norm," Neural Networks, vol. 85, pp. 10-20, DOI: 10.1016/j.neunet.2016.09.005, 2017.

[26] T.-H. Oh, Y.-W. Tai, J.-C. Bazin, H. Kim, I. S. Kweon, "Partial sum minimization of singular values in robust PCA: Algorithm and applications," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38 no. 4, pp. 744-758, DOI: 10.1109/TPAMI.2015.2465956, 2016.

[27] R. H. Keshavan, A. Montanari, S. Oh, "Matrix completion from a few entries," IEEE Transactions on Information Theory, vol. 56 no. 6, pp. 2980-2998, DOI: 10.1109/TIT.2010.2046205, 2010.

[28] Z. Wen, W. Yin, Y. Zhang, "Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm," Mathematical Programming Computation, vol. 4 no. 4, pp. 333-361, DOI: 10.1007/s12532-012-0044-1, 2012.

[29] K. Lee, Y. Bresler, "ADMiRA: atomic decomposition for minimum rank approximation," IEEE Transactions on Information Theory, vol. 56 no. 9, pp. 4402-4416, DOI: 10.1109/tit.2010.2054251, 2010.

[30] Z. Wang, M.-J. Lai, Z. Lu, W. Fan, H. Davulcu, J. Ye, "Orthogonal rank-one matrix pursuit for low rank matrix completion," SIAM Journal on Scientific Computing, vol. 37 no. 1, pp. A488-A514, DOI: 10.1137/130934271, 2015.

[31] M. A. Davenport, J. Romberg, "An overview of low-rank matrix recovery from incomplete observations," IEEE Journal of Selected Topics in Signal Processing, vol. 10 no. 4, pp. 608-622, DOI: 10.1109/JSTSP.2016.2539100, 2016.

[32] P. Rodriguez, "Total variation regularization algorithms for images corrupted with different noise models: a review," Journal of Electrical and Computer Engineering, vol. 2013,DOI: 10.1155/2013/217021, 2013.

[33] Xu Han, Jiasong Wu, Lu Wang, Yang Chen, Lotf Senhadji, Huazhong Shu, "Linear total variation approximate regularized nuclear norm optimization for matrix completion," Abstract and Applied Analysis, vol. 2014,DOI: 10.1155/2014/765782, 2014.

[34] Y.-L. Chen, C.-T. Hsu, H.-Y. M. Liao, "Simultaneous tensor decomposition and completion using factor priors," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 36 no. 3, pp. 577-591, DOI: 10.1109/TPAMI.2013.164, 2014.

[35] T. Yokota, Q. Zhao, A. Cichocki, "Smooth PARAFAC decomposition for tensor completion," IEEE Transactions on Signal Processing, vol. 64 no. 20, pp. 5423-5436, DOI: 10.1109/TSP.2016.2586759, 2016.

[36] T. G. Kolda, B. W. Bader, "Tensor decompositions and applications," SIAM Review, vol. 51 no. 3, pp. 455-500, DOI: 10.1137/07070111X, 2009.

[37] K. Papafitsoros, C. B. Schoenlieb, B. Sengul, "Combined first and second order total variation inpainting using split Bregman," Image Processing On Line, vol. 3, pp. 112-136, DOI: 10.5201/ipol.2013.40, 2013.

[38] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, "Distributed optimization and statistical learning via the alternating direction method of multipliers," Foundations and Trends in Machine Learning, vol. 3 no. 1,DOI: 10.1561/2200000016, 2011.

[39] P. Benner, R.-C. Li, N. Truhar, "On the ADI method for Sylvester equations," Journal of Computational and Applied Mathematics, vol. 233 no. 4, pp. 1035-1045, DOI: 10.1016/j.cam.2009.08.108, 2009.

[40] Z. C. Lin, R. S. Liu, Z. X. Su, "Linearized alternating direction method with adaptive penalty for low-rank representation," Proceedings of the 25th Annual Conference on Neural Information Processing Systems, .

[41] Z. Wang, A. C. Bovik, H. R. Sheikh, E. P. Simoncelli, "Image quality assessment: from error visibility to structural similarity," IEEE Transactions on Image Processing, vol. 13 no. 4, pp. 600-612, DOI: 10.1109/TIP.2003.819861, 2004.