# Linear Total Variation Approximate Regularized Nuclear Norm Optimization for Matrix Completion

Authors: Xu Han; Jiasong Wu; Lu Wang; Yang Chen; Lotfi Senhadji; Huazhong Shu
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Matrix completion that estimates missing values in visual data is an important topic in computer vision. Most of the recent studies focused on the low rank matrix approximation via the nuclear norm. However, the visual data, such as images, is rich in texture which may not be well approximated by low rank constraint. In this paper, we propose a novel matrix completion method, which combines the nuclear norm with the local geometric regularizer to solve the problem of matrix completion for redundant texture images. And in this paper we mainly consider one of the most commonly graph regularized parameters: the total variation norm which is a widely used measure for enforcing intensity continuity and recovering a piecewise smooth image. The experimental results show that the encouraging results can be obtained by the proposed method on real texture images compared to the state-of-the-art methods.


---

## Body

## 1. Introduction

The problem of matrix completion, which can be seen as the extension of recently developed compressed sensing (CS) theory [1–3], plays an important role in the field of signal and image processing [4–11]. This problem occurs in many real applications in computer vision and pattern recognition, such as image inpainting [12, 13], video denoising [14], and recommender systems [15, 16]. Reconstruction algorithms for matrix completion have received much attention. Cai et al. [17] proposed an algorithm, namely, the singular value thresholding (SVT) algorithm for matrix completion and related nuclear norm minimization problems. In [18], a simple and fast singular value projection (SVP) algorithm for rank minimization with affine constraints is exploited. Keshavan et al. [19] dealt with the matrix completion based on singular value decomposition followed by local manifold optimization. In order to achieve a better approximation of the rank of matrix, Hu et al. [11] presented an approach based on the truncated nuclear norm regularization (TNNR), which is defined by the difference between the nuclear norm and the sum of the largest few singular values. Since most of the existing matrix completion models aim to solve the low rank optimization via nuclear norm, we recall here this model. For an incomplete matrix M∈Rm×n of rank r, the model can be described as follows:
(1)min⁡Xrank⁡(X)s.t.XΩ=MΩ,
where X∈Rm×n and MΩ=Mij,(i,j)∈Ω, and Ω is the set of locations corresponding to the observed entries.Unfortunately, the rank minimization problem in (1) is an NP-hard one, so the following convex relaxation is widely used:
(2)min⁡X∥X∥*s.t.XΩ=MΩ,
where ∥·∥* is the nuclear norm given by
(3)∥X∥*=∑k=1min⁡(m,n)σk,
where σk denotes the kth largest singular value of X.In this paper, our objective is to exploit the intrinsic geometry of the data distribution and incorporate it as an additional regularization term to deal with the images which are rich in texture. The total variation (TV) norm has demonstrated its usefulness as a graph regularizer in the field of image processing, so we propose here a method that combines the nuclear norm with the linear TV approximate norm to solve the problem of matrix completion. We call it the linear total variation approximate regularized nuclear norm (LTVNN) minimization problem. This combination optimization problem will be solved by simple and efficient optimization scheme based on the alternating direction method of multipliers (ADMM) model [20, 21].The paper is organized as follows. In the next section, we introduce the proposed LTVNN model and we describe the optimization schemes. In Section3, we establish the convergence results for the iterations given in Section 2. Experimental results on a set of images are provided in Section 4. Finally, we draw some conclusions in Section 5.


## 2. Proposed Method

### 2.1. Some Preliminaries

The total variation along the vertical and horizontal directions can be described as(4)Dj,kv(X)={Xj,k-Xj+1,k,1≤j<m0,j=m,(5)Dj,kh(X)={Xj,k-Xj,k+1,1≤k<n0,k=n.
So the total variation ofX is the summation for the magnitude of the gradient of each pixel [22]:
(6)∥X∥TV=∑j,k(Dj,kvX)2+(Dj,khX)2.
And the equvalent total variation formula as follows:
(7)∥X∥TV=∑j,k(|Dj,kvX|+|Dj,khX|).
Here, we use the linear total variation approximate of (7) to approximate the second kind of total variation; that is,
(8)∥X∥LTVA=∑j,k((Dj,kvX)2+(Dj,khX)2).


### 2.2. Proposed Model

As mentioned above, the key point of the proposed approach is the combination of the nuclear norm and the linear total variation approximate norm; therefore, the optimization problem is described as(9)min⁡X(1-γ)∥X∥*+γ∥X∥LTVAs.t.XΩ=MΩ,
where 0≤γ≤1 is a penalty parameter, ∥X∥* is the nuclear norm defined in (3), and ∥X∥LTVA is linear total variation norm approximate defined in (8), which can be reformulated as
(10)∥X∥LTVA=Tr⁡[(X-Xϕ1)(X-Xϕ1)T]+Tr⁡[(X-ϕ2X)(X-ϕ2X)T]=∥(X-Xϕ1)∥F2+∥(X-ϕ2X)∥F2,
where “Tr⁡” means the trace of the matrix, ∥·∥F denotes the Frobenius norm of the matrix, and ϕ1 and ϕ2 are, respectively, the column and row transform matrix given by
(11)ϕ1=[000⋯010⋯00100⋮⋮⋱⋮00⋯1︸(n-1)×(n-1)00⋮1]n×n,ϕ2=[(m-1)×(m-1)010⋯0︷001000⋮⋮⋱⋮⋮00⋯1000⋯1]m×m.So, the problem in (9) can be rewritten as
(12)min⁡X(1-γ)∥X∥*+γ∥(X-Xϕ1)∥F2+γ∥(X-ϕ2X)∥F2s.t.XΩ=MΩ.


### 2.3. The Optimization Scheme

The alternating direction method of multipliers-ADMM [20, 21] is an efficient and scalable optimization model which exploits the structure of the optimization problem. In this section, we use ADMM to deal with the problem in (12), which can be reformulated as
(13)min⁡X,W(1-γ)∥X∥*+γ∥(W-Wϕ1)∥F2+γ∥(W-ϕ2W)∥F2s.t.X=W,WΩ=MΩ,
where ∥(W-Wϕ1)∥F2 and ∥(W-ϕ2W)∥F2 are the indicator functions. The augmented Lagrange function of (13) is
(14)L(X,Y,W,λ)=(1-γ)∥X∥*+γ∥(W-Wϕ1)∥F2+γ∥(W-ϕ2W)∥F2+λ2∥W-X∥F2+Tr⁡(YT(W-X)),
where λ>0 is the penalty parameter and Y is the multiplier. The solution can be obtained by incorporating the solutions of each regularization problem separately which are defined as follows.Row TV is as follows:(15)LR(XR,YR,WR,λ)=(1-γ)∥XR∥*+γ∥(WR-ϕ2WR)∥F2+λ2∥WR-XR∥F2+Tr⁡(YRT(WR-XR)),whereXR denotes the optimization result along the vertical direction of the total variation defined in (4).Column TV is as follows:(16)LC(XC,YC,WC,λ)=(1-γ)∥XC∥*+γ∥(WC-WCϕ1)∥F2+λ2∥WC-XC∥F2+Tr⁡(YCT(WC-XC)),whereXC denotes the optimization result along the horizontal direction of the total variation defined in (5).We deal with column linear TV optimization problem in (16) by the following steps in each iteration.Step 1 (initial setting).
X
C
1
=
M
Ω, WC1=XC1, YC1=XC1, with the tolerance ε.Step 2 (computingXCk+1).
FixWCk and YCk, and minimize (16) for obtaining XCk+1 as
(17)XCk+1=argmin⁡X(1-γ)∥XC∥*+γ∥(WCk-WCkϕ1)∥F2+λ2∥WC-XCk∥F2+Tr⁡(YCkT(WC-XCk)).
Ignoring the constant terms, (17) can be rewritten as
(18)XCk+1=argmin⁡X(1-γ)∥XC∥*+λ2∥XC-(WCk+1λYCk)∥F2.
To solve (18), Cai et al. [17] introduce the soft-thresholding operator Dτ which is defined as follows:
(19)Dτ(X):=UDτ(Σ)VT,Dτ(Σ)=diag⁡{max⁡(σi-τ)+},
where t+=max⁡(0,t).
Using the operatorDτ in (19), the solution of (18) can be obtained as
(20)XCk+1=D(1-γ)/λ(WCk+1λYCk).Step 3 (computingWCk+1).
FixXCk+1 and YCk and calculate WCk+1 as follows:
(21)WCk+1=argmin⁡WL(XCk+1,YCk,WC,λ)
which is a quadratic function of WC and can be easily solved by setting the derivation of L(XCk+1,YCk,WC,λ) to zeros, and then we get
(22)WCk+1=(λXCk+1-YCk)×[2γ(I-ϕ1-ϕ1T+ϕ1Tϕ1)+λIn×n]-1.
Then we fix the values at the observed entries:
(23)WCk+1=(WCk+1)Ωm+MΩ,
where Ωm denotes the set of the missing entries.Step 4 (computingYCk+1).
FixXCk+1 and WCk+1 and calculate YCk+1 as follows:
(24)YCk+1=YCk+λ(WCk+1-XCk+1).
Until the stop condition:∥XCk+1-XCk∥F≤ε.Row TV problem defined by (15) can be solved in a similar way to that of column TV problem. The only difference is the WRk+1 in the second step, which is given by
(25)WRk+1=[2γ(I-ϕ2-ϕ2T+ϕ2Tϕ2)+λIm×m]-1×(λXRk+1-YRk).
And the stop condition is ∥XRk+1-XRk∥F≤ε.Finally, we obtainedXk+1 as the average of XCk+1 and XRk+1; that is,
(26)Xk+1=XCk+1+XRk+12.


## 2.1. Some Preliminaries

The total variation along the vertical and horizontal directions can be described as(4)Dj,kv(X)={Xj,k-Xj+1,k,1≤j<m0,j=m,(5)Dj,kh(X)={Xj,k-Xj,k+1,1≤k<n0,k=n.
So the total variation ofX is the summation for the magnitude of the gradient of each pixel [22]:
(6)∥X∥TV=∑j,k(Dj,kvX)2+(Dj,khX)2.
And the equvalent total variation formula as follows:
(7)∥X∥TV=∑j,k(|Dj,kvX|+|Dj,khX|).
Here, we use the linear total variation approximate of (7) to approximate the second kind of total variation; that is,
(8)∥X∥LTVA=∑j,k((Dj,kvX)2+(Dj,khX)2).


## 2.2. Proposed Model

As mentioned above, the key point of the proposed approach is the combination of the nuclear norm and the linear total variation approximate norm; therefore, the optimization problem is described as(9)min⁡X(1-γ)∥X∥*+γ∥X∥LTVAs.t.XΩ=MΩ,
where 0≤γ≤1 is a penalty parameter, ∥X∥* is the nuclear norm defined in (3), and ∥X∥LTVA is linear total variation norm approximate defined in (8), which can be reformulated as
(10)∥X∥LTVA=Tr⁡[(X-Xϕ1)(X-Xϕ1)T]+Tr⁡[(X-ϕ2X)(X-ϕ2X)T]=∥(X-Xϕ1)∥F2+∥(X-ϕ2X)∥F2,
where “Tr⁡” means the trace of the matrix, ∥·∥F denotes the Frobenius norm of the matrix, and ϕ1 and ϕ2 are, respectively, the column and row transform matrix given by
(11)ϕ1=[000⋯010⋯00100⋮⋮⋱⋮00⋯1︸(n-1)×(n-1)00⋮1]n×n,ϕ2=[(m-1)×(m-1)010⋯0︷001000⋮⋮⋱⋮⋮00⋯1000⋯1]m×m.So, the problem in (9) can be rewritten as
(12)min⁡X(1-γ)∥X∥*+γ∥(X-Xϕ1)∥F2+γ∥(X-ϕ2X)∥F2s.t.XΩ=MΩ.


## 2.3. The Optimization Scheme

The alternating direction method of multipliers-ADMM [20, 21] is an efficient and scalable optimization model which exploits the structure of the optimization problem. In this section, we use ADMM to deal with the problem in (12), which can be reformulated as
(13)min⁡X,W(1-γ)∥X∥*+γ∥(W-Wϕ1)∥F2+γ∥(W-ϕ2W)∥F2s.t.X=W,WΩ=MΩ,
where ∥(W-Wϕ1)∥F2 and ∥(W-ϕ2W)∥F2 are the indicator functions. The augmented Lagrange function of (13) is
(14)L(X,Y,W,λ)=(1-γ)∥X∥*+γ∥(W-Wϕ1)∥F2+γ∥(W-ϕ2W)∥F2+λ2∥W-X∥F2+Tr⁡(YT(W-X)),
where λ>0 is the penalty parameter and Y is the multiplier. The solution can be obtained by incorporating the solutions of each regularization problem separately which are defined as follows.Row TV is as follows:(15)LR(XR,YR,WR,λ)=(1-γ)∥XR∥*+γ∥(WR-ϕ2WR)∥F2+λ2∥WR-XR∥F2+Tr⁡(YRT(WR-XR)),whereXR denotes the optimization result along the vertical direction of the total variation defined in (4).Column TV is as follows:(16)LC(XC,YC,WC,λ)=(1-γ)∥XC∥*+γ∥(WC-WCϕ1)∥F2+λ2∥WC-XC∥F2+Tr⁡(YCT(WC-XC)),whereXC denotes the optimization result along the horizontal direction of the total variation defined in (5).We deal with column linear TV optimization problem in (16) by the following steps in each iteration.Step 1 (initial setting).
X
C
1
=
M
Ω, WC1=XC1, YC1=XC1, with the tolerance ε.Step 2 (computingXCk+1).
FixWCk and YCk, and minimize (16) for obtaining XCk+1 as
(17)XCk+1=argmin⁡X(1-γ)∥XC∥*+γ∥(WCk-WCkϕ1)∥F2+λ2∥WC-XCk∥F2+Tr⁡(YCkT(WC-XCk)).
Ignoring the constant terms, (17) can be rewritten as
(18)XCk+1=argmin⁡X(1-γ)∥XC∥*+λ2∥XC-(WCk+1λYCk)∥F2.
To solve (18), Cai et al. [17] introduce the soft-thresholding operator Dτ which is defined as follows:
(19)Dτ(X):=UDτ(Σ)VT,Dτ(Σ)=diag⁡{max⁡(σi-τ)+},
where t+=max⁡(0,t).
Using the operatorDτ in (19), the solution of (18) can be obtained as
(20)XCk+1=D(1-γ)/λ(WCk+1λYCk).Step 3 (computingWCk+1).
FixXCk+1 and YCk and calculate WCk+1 as follows:
(21)WCk+1=argmin⁡WL(XCk+1,YCk,WC,λ)
which is a quadratic function of WC and can be easily solved by setting the derivation of L(XCk+1,YCk,WC,λ) to zeros, and then we get
(22)WCk+1=(λXCk+1-YCk)×[2γ(I-ϕ1-ϕ1T+ϕ1Tϕ1)+λIn×n]-1.
Then we fix the values at the observed entries:
(23)WCk+1=(WCk+1)Ωm+MΩ,
where Ωm denotes the set of the missing entries.Step 4 (computingYCk+1).
FixXCk+1 and WCk+1 and calculate YCk+1 as follows:
(24)YCk+1=YCk+λ(WCk+1-XCk+1).
Until the stop condition:∥XCk+1-XCk∥F≤ε.Row TV problem defined by (15) can be solved in a similar way to that of column TV problem. The only difference is the WRk+1 in the second step, which is given by
(25)WRk+1=[2γ(I-ϕ2-ϕ2T+ϕ2Tϕ2)+λIm×m]-1×(λXRk+1-YRk).
And the stop condition is ∥XRk+1-XRk∥F≤ε.Finally, we obtainedXk+1 as the average of XCk+1 and XRk+1; that is,
(26)Xk+1=XCk+1+XRk+12.


## 3. Convergence Analysis

In this section, we give the proof of the convergence of column total variation (16) and the convergence of row total variation is similar to the column total variation. Here, the objection function (16) about column variation is as follows:
(27)min⁡Xfτ(X)s.t.XΩ=MΩfτ(X)=τ∥X∥*+12Tr⁡[(X-Xϕ1)(X-Xϕ1)T],τ=1-γ2γ.Lemma 1.
LetZ∈∂fτ(X) and Z′∈∂fτ(X′). Then
(28)〈Z-Z′,X-X′〉≥∥X-X′∥F2.
The details of the proof can be found in [17].Theorem 2.
Assuming that the sequence of step size obeys0<inf⁡λk<sup⁡λk<(2α/β), α=〈(Xk-X*)(I-ϕ1-ϕ1T+ϕ1ϕ1T),Xk-X*〉 and β=∥Xk-X*∥F2. Here, X* denotes the optimization result and Xk denotes the kth iteration object variable; then by the iteration procedure defined in Section 2.3, we can obtain the unique optimization result, that is, X*. And the details of the proof can be found in the Appendix.


## 4. Experiments

In this section, we test the proposed method on a set of images. The algorithm was implemented with MATLAB programming language on a PC machine, which sets up Microsoft Windows 7 operating system and has an Intel Core I5 CPU with speed of 2.79 GHz and 2 GB RAM.We deal with three channels (r,g,b) of color images separately and combine the results together to get the final outcome. We use peak signal-to-noise ratio (PSNR) values to evaluate the performance:
(29)PSNR=10×log10(2552MSE),
where MSE denotes mean squared error,
(30)MSE=13mn[error2(r)+error2(g)+error2(b)].In the experiments, we consider two situations: random mask sample and word mask sample. Figure1 describes the recovered results with 60% random mask and word mask for γ=0,0.5 and 1 by LTVNN. Figure 2 shows the recovered PSNR for Pepper under different random sample ratios and word mask sample for γ from 0 to 1 with step of 0.1 by LTVNN. It can be observed from these two figures that the best result is obtained for the value of γ near to 0.5, which corresponds to the case where the two norms (nuclear and LTV) are equivalently used in (9). For the two extreme cases: γ=0 (only the nuclear norm is taken into consideration) and γ=1 (only the linear total variation approximate norm is considered), the algorithm loses its efficiency.The recovered results with 60% random mask and word mask forγ=0, 0.5 and 1 by LTVNN.
(a)
Original image (256 × 256)
(b)
Random masked image
(c)
γ
=
0, PSNR: 8.934
(d)
γ
=
0.5, PSNR: 29.183
(e)
γ
=
1, PSNR: 8.593
(f)
Word masked image
(g)
γ
=
0, PSNR: 14.706
(h)
γ
=
0.5, PSNR: 33.421
(i)
γ
=
1, PSNR: 14.759Figure 2
The recovered PSNR for Pepper under different random sample ratio and word mask sample withγ from 0 0 to 1 by LTVNN.We also compare our method (LTVNN) with other matrix completion methods including TNNR [10, 11], SVT [12], SVP [13], and OptSpace [14]. Figure 3 plots the recovered PSNR for Pepper for γ=0.5 with different random sample ratios (from 40% to 90%) by LTVNN and other four methods (TNNR, SVT, SVP, and OptSpace). It can be seen from Figure 3 that the proposed LTVNN method achieves much higher PSNR than the other methods. Figure 4 shows the comparison of PSNR of recovered methods for Lena under word mask with γ=0.5 by LTVNN and the other methods. Table 1 lists the PSNR results under word mask sample with γ=0.5 for different images by LTVNN and the other methods. From Figure 4 and Table 1, we can see that the proposed method outperforms the other matrix completion methods under word mask for different images.Table 1
PSNR results under word mask sample withγ=0.5 for different images by LTVNN, TNNR, SVT, SVP, and OptSpace.
LTVNN
TNNR [10, 11]
SVT [12]
SVP [13]
OptSpace [14]
Mandrill (256×256)
29.495
27.845
27.736
18.881
26.264
Pepper (256×256)
33.421
31.019
30.188
23.648
27.141
Barbara (240×192)
31.170
29.261
29.352
22.901
23.427
Barbara (512×512)
32.680
30.682
28.855
22.113
26.872
Girl (256×256)
36.797
34.298
33.848
27.128
30.977
Couple (256×256)
36.916
35.176
35.241
29.649
32.815
Airplane (512×512)
31.883
30.083
25.506
19.573
26.222
House (256×256)
34.340
33.288
32.646
22.374
27.505
Sailboat (512×512)
30.858
29.103
27.079
26.778
20.891Figure 3
Recovered PSNR for Pepper underγ=0.5 with different random sample ratio by LTVNN, TNNR, SVT, SVP, and OptSpace.Comparison of PSNR of recovered methods for Lena under word mask withγ=0.5 by LTVNN, TNNR, SVT, SVP, and OptSpace.
(a)
Original image (256 × 256)
(b)
Word masked image
(c)
LTVNN (PSNR: 32.920)
(d)
TNNR (PSNR: 30.189)
(e)
SVT (PSNR: 30.760)
(f)
SVP (PSNR: 22.159)
(g)
OptSpace (PSNR: 26.492)


## 5. Conclusion

In this paper, we have proposed a new model that combines the nuclear norm and total variation norm for the matrix completion problem, which was then solved by ADMM model. Experimental results demonstrate the effectiveness of the proposed algorithm compared to other methods.



---

*Source: 765782-2014-05-28.xml*