# An Efficient Tensor Completion Method Combining Matrix Factorization and Smoothness

Authors: Leiming Tang; Xunjie Cao; Weiyang Chen; Changbo Ye
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In this paper, the low-complexity tensor completion (LTC) scheme is proposed to improve the efficiency of tensor completion. On one hand, the matrix factorization model is established for complexity reduction, which adopts the matrix factorization into the model of low-rank tensor completion. On the other hand, we introduce the smoothness by total variation regularization and framelet regularization to guarantee the completion performance. Accordingly, given the proposed smooth matrix factorization (SMF) model, an alternating direction method of multiple- (ADMM-) based solution is further proposed to realize the efficient and effective tensor completion. Additionally, we employ a novel tensor initialization approach to accelerate convergence speed. Finally, simulation results are presented to confirm the system gain of the proposed LTC scheme in both efficiency and effectiveness.


---

## Body

## 1. Introduction

As a high-order generalization of vector and matrix, tensor can show complicated structures of high-order data more clearly. With the tensor form, we can understand the internal connection of data from a higher level perspective. Thus, tensor is widely applied in several fields like signal reconstruction [1], signal processing [2–5], image recovery [6], and video inpainting [7].The purpose of low-rank tensor completion (LRTC) is to estimate missing entries and recover the incomplete tensor data, which takes advantage of the low rank prior to estimate the missing data. Optimization problem LRTC can be ordinarily formulated as follows:(1)minXrankX,s.t.XΩ=TΩ.Here, X is the target tensor, and T is the available data; Ω is observed entries index. The constraint XΩ=TΩ is to keep the entries of X in Ω consistent with T.It is obvious that minimizing the tensor rank is the fundamental problem of LRTC. However, there is no uniform definition of the tensor rank. CP-rank [8] and Tucker-rank [9] are two commonly used definitions, which lie in the corresponding decompositions, CP decomposition [10], and Tucker decomposition [11]. Moreover, the problem of calculating CP-rank is NP-hard, and it has no relevant relaxation.Although minimizing Tucker-rank is still NP-hard, it can be relaxed by sum of nuclear norm (SNN) since it is the tightest surrogate of matrix rank. Based on this property of Tucker-rank, Liu et al. [12] developed a theoretical framework for LRTC, and the definition of the nuclear norm for tensors is formed as follows:(2)X∗=∑i=1NωiXi∗.Here, Xi is the mode-i unfolding matrix of X, X∗ presents the nuclear norm of Xi, and ωi≥0 (∑i=1Nωi=1, i=1,2,⋯,N) denotes the corresponding weight value of Xi. Then, the LRTC model can be written as(3)minX∑i=1NωiXi∗,s.t.XΩ=TΩ.As shown in (3), the LRTC problem is divided into a series of matrix nuclear norm minimization. Through unfolding the target tensor, the matrices are formed to be optimized. In order to resolve (3), SiLRTC, HaLRTC, and FaLRTC were proposed by Liu as the solution for LRTC [12]. Unfortunately, all these algorithms require to compute singular value decomposition (SVD) iteratively, which is complexity exhausted. Considering this difficulty, Liu and Shang [13] applied matrix factorization to the SNN model to reduce the scale of matrices requiring SVD (see details in Section 2).(4)minLi,RiX∑i=1NωiRi∗,i=1,⋯,N,s.t.Xi=LiRi,XΩ=TΩ,where Li∈StIi,si, Ri∈ℝsi×∏j≠iIj, and StIi,si denote the Stiefel manifold, and si>ri is a given upper bound of rank. In this paper, we use SNN combined with matrix factorization to utilize the low-rankness feature of tensors and improve the efficiency of LRTC.Additionally, only considering low-rankness factor is not adequate for LRTC, which results in inevitable performance degradation with the decrement of the sampling rate [14, 15]. Apart from the low rankness of tensor, smoothness is also a significant attribute in real world data. For instance, spectral signals [16] and natural pictures and videos [17] generally have this property. Total variation (TV) [18] is commonly applied as constraints to ensure smoothness. The application of TV in image processing has been proved that it can effectively encourage the smooth prior [4, 19, 20].For the purpose of improving the quality of tensor completion, Yokota and Hontani [21] proposed LRTV-PDS to minimize SNN and TV simultaneously as:(5)minXρX∗+1−ρXTV,s.t.vmin≤X≤vmax,XΩ−TΩF2≤δ,where ρ is the trade-off connecting the SNN and TV term and δ is the noise threshold parameter. The first constraint restricts the recovered data in a range, vmin,vmax. The second constraint means that the output tensor and original tensor are usually the same at observed entries. Considering the effect of noise, some deviation within a certain range is allowed.As another commonly used definition of tensor rank, CP-rank is also widely utilized in LRTC. On the basis of CP decomposition, Yokota et al. [22] considered TV as the smoothness constraint along with the CP-rank and proposed the smooth PARAFAC tensor completion (SPC) method to achieve better result of tensor completion when the sampling rate is exceedingly low.However, the TV regularization usually leads to staircase effect [23], which may cause the possible loss of information and geometric features in practice. For this reason, the framelet regularization can be further applied to avoid the possible performance degradation. More precisely, as a generation of the orthogonal basis, framelet effectively relaxes the restriction of the orthogonality and linear independence so that the valuable information and geometric features can be well preserved by the introduced redundancy [24]. In this paper, the framelet is applied to exploit the smoothness and preserve more details.Considering SNN, matrix factorization, framelet, and TV simultaneously, we propose a novel model for tensor completion, which is named smooth matrix factorization (SMF). The SMF model is formulated as(6)minX∑i=1NωiRi∗+λ1WX3T1,1+λ2DSX31,1,s.t.XΩ=TΩ,Xi=LiRi,Li∈StIi,si,i=1,⋯,N.Here, λ1 and λ2 are adjustable parameters to balance SNN, framelet, and TV. Besides W indicates framelet transformation, DS denotes the difference matrix, and l1,1-norm is the sum of absolute values of the matrix elements.In addition, we notice that how to initialize the observed tensor can affect the efficiency and effectiveness of tensor completion. Most of these existing works only focus on optimizing the model and ignore initializing the tensor before iteration algorithm. There are two commonly used initialization methods: one is to set the unknown values as zero; the other is to set them as the average of all observed values. Different from the existing simple methods, our proposed initialization method considers the location of the known data and expands the known data around until the entire tensor is completed. Through the rough estimation of unknown data, we get a more accurate initial tensor, which can accelerate the convergence speed of solution.In summary, the low-complexity tensor completion (LTC) scheme is proposed to improve the efficiency of LRTC. The proposed LTC mainly consists of two parts—the SMF model and the alternating direction method of multiple- (ADMM-) based solution. Specifically, the matrix factorization is introduced into the SNN to exploit the low rankness of the entire tensor. By factorizing matrices, the computational complexity in calculating SVD can be significantly reduced, which leads to efficiency improvement. Then, to guarantee the effectiveness of tensor completion, the TV is used to exploit the smoothness globally. After that, the framelet is further applied to further ensure the smoothness and preserve the information due to its redundancy. With respect to the proposed SMF model, we also give an effective ADMM-based algorithm to solve it. Additionally, we propose a novel initialization approach to accelerate convergence speed. On the basis of natural data, such as color image and grayscale video, the experimental results show our LTC scheme can achieve a better trade-off between performance and complexity for LRTC.Compared with the existing works, the contributions of this paper are mainly three folds:(i)
By concurrently utilizing the low-rank and smooth properties, we propose an advanced model for low-rank tensor completion. Besides, matrix factorization is introduced to this model to save calculation cost(ii)
We propose an effective tensor initialization approach, which can get a better start point for tensor completion to accelerate the convergence speed(iii)
An ADMM-based algorithm is developed to resolve the new SMF model. As shown in the result of numerical experiments, our method can clearly improve the effectiveness of LRTCThe rest of this paper is structured as follows: Firstly, we present some notations that this work needs in Section2. Then, we propose the LTC scheme which consists of the SMF model and the corresponding ADMM-based solution in Section 3. Afterwards, the performance of LTC is evaluated and compared with other competing methods in Section 4. Finally, the conclusions are given in Section 5.


## 2. Preliminary

In this section, several basic notations and relevant definitions this work needs are shown [25].


### 2.1. Tensor Basics

Here, we use different fonts to distinguish data formats. For instance, we write vectors asx, matrices as X, and tensors as X. The i1,i2,⋯,iN−th component of X∈ℝI1×I2×⋯×IN is denoted as xi1,i2,⋯,iN.The inner product of two tensorsA and B is formulated as(7)A,B=∑i1i2⋯iNai1i2⋯iNbi1i2⋯iN.As the corresponding norm to the inner product, the definition of Frobenius norm of tensorA is then given as(8)AF=A,A=∑i1i2⋯iNai1i2⋯iN2.The fiber of the tensorX is a vector obtained by fixing each index except one. The mode-n fiber is denoted as Xi1,⋯,in−1,:,in+1,⋯,iN. The mode-n unfolding of tensor X∈ℝI1×I2×⋯×IN is represented as Xn∈ℝIn×∏i≠nIi. Additionally, we denote the inverse operator of unfolding as “fold.” For example, the operation of fold a matrix into a tensor is written as X=foldnXn.


### 2.2. Matrix Factorization

Given a low-rank tensorX∈ℝI1×I2×⋯×IN with rank r1,r2,⋯,rN, the mode-i unfolding Xi∈ℝIi×∏j≠iIj can be factorized into the form X=LiRi,i=1,⋯,N, where Li∈StIi,si, Ri∈ℝsi×∏j≠iIj, and StIi,si=B∈ℝIi×si:BTB=I represent the Stiefel manifold, the collection of all orthonormal Ii×si matrices, and si>ri is a designated constraint of rank, i=1,⋯,N. By introducing matrix factorization, we have the following property of tensor nuclear norm:(9)Xi∗=LiRi∗=Ri∗,i=1,⋯,N.Thus, the SNN minimization problem (3) can be rewritten with smaller scale matrices as follows to reduce computational complexity:(10)minLi,RiX∑i=1NωiRi∗,s.t.Xi=LiRi,Li∈StIi,si,XΩ=TΩ,i=1,⋯,N.


### 2.3. Framelet

In the discrete setting, the framelet transform is denoted as a linear operatorW∈ℝk×mn. For instance, Wf means that the framelet transform operator W is applied to the image data, which rearranged as a vector f∈ℝmn. On the basis of the unitary extension principle, W denotes the framelet transform matrix satisfying WTW=I. In this paper, the piecewise linear B-spline framelets constructed by [26] is applied to exploit the smoothness and preserve details in tensor completion.


## 2.1. Tensor Basics

Here, we use different fonts to distinguish data formats. For instance, we write vectors asx, matrices as X, and tensors as X. The i1,i2,⋯,iN−th component of X∈ℝI1×I2×⋯×IN is denoted as xi1,i2,⋯,iN.The inner product of two tensorsA and B is formulated as(7)A,B=∑i1i2⋯iNai1i2⋯iNbi1i2⋯iN.As the corresponding norm to the inner product, the definition of Frobenius norm of tensorA is then given as(8)AF=A,A=∑i1i2⋯iNai1i2⋯iN2.The fiber of the tensorX is a vector obtained by fixing each index except one. The mode-n fiber is denoted as Xi1,⋯,in−1,:,in+1,⋯,iN. The mode-n unfolding of tensor X∈ℝI1×I2×⋯×IN is represented as Xn∈ℝIn×∏i≠nIi. Additionally, we denote the inverse operator of unfolding as “fold.” For example, the operation of fold a matrix into a tensor is written as X=foldnXn.


## 2.2. Matrix Factorization

Given a low-rank tensorX∈ℝI1×I2×⋯×IN with rank r1,r2,⋯,rN, the mode-i unfolding Xi∈ℝIi×∏j≠iIj can be factorized into the form X=LiRi,i=1,⋯,N, where Li∈StIi,si, Ri∈ℝsi×∏j≠iIj, and StIi,si=B∈ℝIi×si:BTB=I represent the Stiefel manifold, the collection of all orthonormal Ii×si matrices, and si>ri is a designated constraint of rank, i=1,⋯,N. By introducing matrix factorization, we have the following property of tensor nuclear norm:(9)Xi∗=LiRi∗=Ri∗,i=1,⋯,N.Thus, the SNN minimization problem (3) can be rewritten with smaller scale matrices as follows to reduce computational complexity:(10)minLi,RiX∑i=1NωiRi∗,s.t.Xi=LiRi,Li∈StIi,si,XΩ=TΩ,i=1,⋯,N.


## 2.3. Framelet

In the discrete setting, the framelet transform is denoted as a linear operatorW∈ℝk×mn. For instance, Wf means that the framelet transform operator W is applied to the image data, which rearranged as a vector f∈ℝmn. On the basis of the unitary extension principle, W denotes the framelet transform matrix satisfying WTW=I. In this paper, the piecewise linear B-spline framelets constructed by [26] is applied to exploit the smoothness and preserve details in tensor completion.


## 3. The Proposed LTC Scheme

In this section, the LTC scheme is proposed, which consists of the SMF model, the tensor initialization method, and the ADMM-based algorithm.


### 3.1. The Proposed SMF Model

Considering a 3rd-order tensorX∈ℝn1×n2×n3, the proposed SMF model is as follows:(11)minX∑i=13ωiRi∗+λ1WX3T1,1+λ2DSX31,1,s.t.XΩ=TΩ,Xi=LiRi,Li∈StIi,si,i=1,2,3.Here,λ1 and λ2 are regularization parameters, X is the object tensor, and TΩ is the incomplete input tensor, and Ω is the set of indices of available data in T.Typically, the SMF model contains two main terms—SNN with matrix factorization and smoothness constraints.The first term, SNN with matrix factorization, can exploit the low-rank property. The goal of introducing SNN is to exploit the globally multidimensional structure, which is the basic of LRTC. Based on the introduced SNN, matrix factorization is further applied to save calculation cost. The purpose of introducing matrix factorization in SNN is to improve the efficiency. Given a low-rank tensorX∈ℝI1×I2×⋯×IN with rank r1,r2,⋯,rN, the mode-i unfolding Xi∈ℝIi×∏j≠iIj can be factorized into the form X=LiRi,i=1,⋯,N. Then, the SNN problem can be rewritten with smaller scale matrices to reduce computational complexity. For example, the computational complexity of SVD of X (X∈ℝm×n, rankX=r) is Om2n+mn2. By introducing matrix factorization, the cost of computing SVD can be reduced to Om2s+ms2,r<s≪n [13].The second term, smoothness constraints, contains the total variation regularization and the framelet regularization, which are used for a better performance of tensor completion.The total variation regularizationDSX31,1 is used to exploit piecewise smoothness along the mode-3 unfolding of X, where Ds is the difference matrix(12)Ds=−11⋯000−1⋯00⋮⋮⋱⋮⋮00⋯−1110⋯0−1.The TV regularization is used to make the third dimension of the recovered tensor smooth to improve the efficiency of tensor completion.The framelet regularizationWX3T1,1 retains details in spatial domain. Here, W denotes the framelet transform matrix satisfying WTW=I. The framelet regularization can further ensure the output tensor smooth and preserve the details due to its redundancy.In summary, SMF exploits the global low-rank property and the smoothness prior along both the spatial and third mode. As shown in experiments, SNN with matrix factorization term, total variation regularization, and framelet regularization, the three parts of SMF take advantage of these two properties to improve the efficiency and effectiveness of tensor completion.


### 3.2. The Tensor Initialization Method

In order to improve the efficiency of tensor completion, we initialize the incomplete tensor to get a better start point for subsequent data processing. Considering the location of known data, the main idea of our tensor initialization method is expanding the known data around until the entire tensor is completed.Here, we use a specific example to illustrate our tensor initialization method. Considering an incomplete color image which is denoted asX∈ℝn1×n2×n3, we make a rough estimate of missing data by assigning the value of each known pixel to the unknown pixels around it. In other words, by averaging the known values adjacent each unknown pixel, the value of the pixel is initialized. For example, if xi,j,k is unknown and two adjacent pixels, xi−1,j,k and xi,j+1,k, are observed, we can set xi,j,k as 0.5xi−1,j,k+xi,j+1,k. All unknown pixels observed with adjacent pixels can be initialized in this way.Here, we introduce the operatorH=PX, which means(13)Hi,j,k=1,ifXi,j,k≠0,0,ifXi,j,k=0,which is used to project the original tensor to the binarized tensor.In this step, we have completed an expansion of the known pixels, and the pixels initialized this time will be considered as known in next expansion. Then, we repeat this expansion process until the entire tensor is filled. The proposed tensor initialization method is detailed in Algorithm1.


### 3.3. The Proposed ADMM-Based Algorithm

Here, we design an effective ADMM-based algorithm to resolve the convex problem. In particular, we introduce two additional variablesM, N, and the model (11) can be equivalently transformed to the following formulation:(14)minLi,Ri,X∑i=13ωiRi∗+λ1M1,1+λ2N1,1,s.t.Xi=LiRi,Li∈StIi,si,i=1,2,3,M=WX3T,N=DSX3,XΩ=TΩ,where M∈ℝn1n2×n3 and N∈ℝn3×n1n2. By introducing matrices M and N, we separate blocks of variables and the augmented Lagrangian function of (14) becomes:(15)LLi,Ri,X,M,N=∑i=13ωiRi∗+β12Xi−LiRiF2+λ1M1,1+WX3T−M,Ψ+β22WX3T−MF2+λ2N1,1+DSX3−N,Θ+β32DSX3−NF2,s.t.Li∈StIi,si,i=1,2,3,XΩ=TΩ,whereΨ and Θ are the Lagrange multipliers and β1, β2, and β3 are the penalty parameters. Based on ADMM, we can divide the problem (15) into subproblems which are easier to deal with in smaller sizes.Algorithm 1: The Proposed Tensor Initialization Method.
Input: The observed tensor T∈ℝn1×n2×n3.Output: The initialized tensor X.1:X=T,Xnext=X2:while 0 exists in Xdo3:H=PX4:fork=1ton3do5:fori=1ton1do6:forj=1ton2do7:ifXi,j,k=0then8:αsum=Hi−1,j,k+Hi,j+1,k+Hi+1,j,k+Hi,j−1,k9:ifαsum≠0then10:Xnexti,j,k=hi−1,j,k/αsumXi−1,j,k+hi,j+1,k/αsumXi,j+1,k+hi+1,j,k/αsumXi+1,j,k+hi,j−1,k/αsumXi,j−1,k11:end if12:end if13:end for14:end for15:end for16:X=Xnext17:end while18:returnXFor the purpose of facilitating the analysis of time complexity in the proposed ADMM-based algorithm, we assume thats=maxs1,s2,s3, X∈ℝn1×n2×n3, and n1≥n2≥n3.The first subproblem optimizes the variableLi, which is presented as:(16)Lik+1=argminLiXik−LiRikF2,s.t.Li∈StIi,si.Through solving this subproblem with the orthogonality constraint, the optimalLi is calculated. Following [27, 28], the optimal solution is given by:(17)Lik+1=QRXikRikT.The cost of computingL is Os2n1.The second subproblem optimizing the variableRi can be calculated as follows:(18)Rik+1=argminRiωiRi∗+β12Xik−Lik+1RiF2.Then,Rik+1 is the optimal solution to the subproblem (18) if and only if(19)0∈ωi∂Rik+1∗+β1Lik+1TLik+1Rik+1−Xik,where ∂⋅∗ is the subdifferential of ⋅∗. Considering the property of Lik+1, Lik+1TLik+1=Is, the formula can be transformed as(20)0∈ωi∂Rik+1∗+β1Rik+1−Lik+1TXik.Obviously, the formula (20) also needs to be satisfied by the optimal solution Ri for the following convex problem:(21)argminRiωiRi∗+β12Ri−Lik+1TXikF2.Therefore,Rik+1 is also the solution to the subproblem (21), which has an explicit solution.(22)Rik+1=SVTωi/β1Lik+1TXik.Algorithm 2: The Proposed ADMM-based Algorithm for Solving the SMF Model in (11).
Input: The initialized tensor T, index set Ω, parameters λ1,λ2,β1,β2,andβ3.Output: The completed tensor X.1:initialize:X0=T,Li0=eyeIi,si,Ri0=randsi,Πi≠jIj,i=1,2,3,M0,N0,ψ0andΘ0initializedto0,k=0,kmax=300.2:while not converged and k<kmaxdo3:fori=1 to 3 do4:Lik+1 via (17)5:Rik+1 via (22)6:  end for7:Mk+1 via (24)8:Nk+1 via (27)9:Xk+1 via (29)10:ψk+1,Θk+1 via (30)11:end while12:returnXk+1Here,SVTτ⋅ is a singular value thresholding operator defined by SVTτX=Udiagmaxσ−τ,0VT, the SVD of X is given by Q=Udiagσi1≤i≤rVT. The complexity of computing R is Osn12n22.The third subproblem aboutM related to framelet regularization can be written as:(23)Mk+1=argminMλ1M1,1+WX3kT−M,Ψ+β22WX3kT−MF2=argminMλ1M1,1+β22WX3kT−M+Ψβ2F2.This problem has an explicit optimal solution(24)Mk+1=Sλ1/β2WX3kT+Ψβ2,where Sμ⋅ is a soft-thresholding operator written as:(25)Sμx=0,if∣x∣≤μ,signx∣x∣−μ,if∣x∣>μ.The cost of calculatingWX3T is Ola2n1n2n3. Here, l denotes the framelet level and a denotes filter number, then the cost of calculating M is Olm2n1n2n3.The fourth subproblem aboutN concerning total variation regularization can be calculated as follows:(26)Nk+1=argminNλ2N1,1+DSX3k−N,Θ+β32DSX3k−NF2=argminNλ2N1,1+β32DSX3k−N+Θβ3F2,which has an explicit solution(27)Nk+1=Sλ2/β3DSX3k+Θβ3.The cost of computingN is On1n2n32.The final subproblem optimizingX can be formulated as:(28)XΩck+1=argminX∑i=13β12Xi−LiRiF2+β22WX3kT−M+Ψβ2F2+β32DSX3k−N+Θβ3F2.We can updateX as follows:(29)XΩck+1=∑ifoldiinvβ1I+β2I+β3DsTDs∗β1Lik+1Rik+1+β2WTM−Ψβ2T+β3DsTN−Θ/β3NΩc,XΩk+1=TΩ.The cost of calculatingX is Osn1n2n3+lm2n1n2n3+n1n2n32+n13.According to ADMM, the multipliersΨ and Θ are updated as(30)Ψk+1=Ψk+β2WX3k+1T−Mk+1,Θk+1=Θk+β3DSX3k+1−Nk+1.To summarize, the proposed iterative ADMM-based algorithm for solving the SMF model in (11) is outlined in Algorithm 2. The computing complexity of L, R, M, N, and X at each iteration is Osn12n22+lm2n1n2n3+n13.


## 3.1. The Proposed SMF Model

Considering a 3rd-order tensorX∈ℝn1×n2×n3, the proposed SMF model is as follows:(11)minX∑i=13ωiRi∗+λ1WX3T1,1+λ2DSX31,1,s.t.XΩ=TΩ,Xi=LiRi,Li∈StIi,si,i=1,2,3.Here,λ1 and λ2 are regularization parameters, X is the object tensor, and TΩ is the incomplete input tensor, and Ω is the set of indices of available data in T.Typically, the SMF model contains two main terms—SNN with matrix factorization and smoothness constraints.The first term, SNN with matrix factorization, can exploit the low-rank property. The goal of introducing SNN is to exploit the globally multidimensional structure, which is the basic of LRTC. Based on the introduced SNN, matrix factorization is further applied to save calculation cost. The purpose of introducing matrix factorization in SNN is to improve the efficiency. Given a low-rank tensorX∈ℝI1×I2×⋯×IN with rank r1,r2,⋯,rN, the mode-i unfolding Xi∈ℝIi×∏j≠iIj can be factorized into the form X=LiRi,i=1,⋯,N. Then, the SNN problem can be rewritten with smaller scale matrices to reduce computational complexity. For example, the computational complexity of SVD of X (X∈ℝm×n, rankX=r) is Om2n+mn2. By introducing matrix factorization, the cost of computing SVD can be reduced to Om2s+ms2,r<s≪n [13].The second term, smoothness constraints, contains the total variation regularization and the framelet regularization, which are used for a better performance of tensor completion.The total variation regularizationDSX31,1 is used to exploit piecewise smoothness along the mode-3 unfolding of X, where Ds is the difference matrix(12)Ds=−11⋯000−1⋯00⋮⋮⋱⋮⋮00⋯−1110⋯0−1.The TV regularization is used to make the third dimension of the recovered tensor smooth to improve the efficiency of tensor completion.The framelet regularizationWX3T1,1 retains details in spatial domain. Here, W denotes the framelet transform matrix satisfying WTW=I. The framelet regularization can further ensure the output tensor smooth and preserve the details due to its redundancy.In summary, SMF exploits the global low-rank property and the smoothness prior along both the spatial and third mode. As shown in experiments, SNN with matrix factorization term, total variation regularization, and framelet regularization, the three parts of SMF take advantage of these two properties to improve the efficiency and effectiveness of tensor completion.


## 3.2. The Tensor Initialization Method

In order to improve the efficiency of tensor completion, we initialize the incomplete tensor to get a better start point for subsequent data processing. Considering the location of known data, the main idea of our tensor initialization method is expanding the known data around until the entire tensor is completed.Here, we use a specific example to illustrate our tensor initialization method. Considering an incomplete color image which is denoted asX∈ℝn1×n2×n3, we make a rough estimate of missing data by assigning the value of each known pixel to the unknown pixels around it. In other words, by averaging the known values adjacent each unknown pixel, the value of the pixel is initialized. For example, if xi,j,k is unknown and two adjacent pixels, xi−1,j,k and xi,j+1,k, are observed, we can set xi,j,k as 0.5xi−1,j,k+xi,j+1,k. All unknown pixels observed with adjacent pixels can be initialized in this way.Here, we introduce the operatorH=PX, which means(13)Hi,j,k=1,ifXi,j,k≠0,0,ifXi,j,k=0,which is used to project the original tensor to the binarized tensor.In this step, we have completed an expansion of the known pixels, and the pixels initialized this time will be considered as known in next expansion. Then, we repeat this expansion process until the entire tensor is filled. The proposed tensor initialization method is detailed in Algorithm1.


## 3.3. The Proposed ADMM-Based Algorithm

Here, we design an effective ADMM-based algorithm to resolve the convex problem. In particular, we introduce two additional variablesM, N, and the model (11) can be equivalently transformed to the following formulation:(14)minLi,Ri,X∑i=13ωiRi∗+λ1M1,1+λ2N1,1,s.t.Xi=LiRi,Li∈StIi,si,i=1,2,3,M=WX3T,N=DSX3,XΩ=TΩ,where M∈ℝn1n2×n3 and N∈ℝn3×n1n2. By introducing matrices M and N, we separate blocks of variables and the augmented Lagrangian function of (14) becomes:(15)LLi,Ri,X,M,N=∑i=13ωiRi∗+β12Xi−LiRiF2+λ1M1,1+WX3T−M,Ψ+β22WX3T−MF2+λ2N1,1+DSX3−N,Θ+β32DSX3−NF2,s.t.Li∈StIi,si,i=1,2,3,XΩ=TΩ,whereΨ and Θ are the Lagrange multipliers and β1, β2, and β3 are the penalty parameters. Based on ADMM, we can divide the problem (15) into subproblems which are easier to deal with in smaller sizes.Algorithm 1: The Proposed Tensor Initialization Method.
Input: The observed tensor T∈ℝn1×n2×n3.Output: The initialized tensor X.1:X=T,Xnext=X2:while 0 exists in Xdo3:H=PX4:fork=1ton3do5:fori=1ton1do6:forj=1ton2do7:ifXi,j,k=0then8:αsum=Hi−1,j,k+Hi,j+1,k+Hi+1,j,k+Hi,j−1,k9:ifαsum≠0then10:Xnexti,j,k=hi−1,j,k/αsumXi−1,j,k+hi,j+1,k/αsumXi,j+1,k+hi+1,j,k/αsumXi+1,j,k+hi,j−1,k/αsumXi,j−1,k11:end if12:end if13:end for14:end for15:end for16:X=Xnext17:end while18:returnXFor the purpose of facilitating the analysis of time complexity in the proposed ADMM-based algorithm, we assume thats=maxs1,s2,s3, X∈ℝn1×n2×n3, and n1≥n2≥n3.The first subproblem optimizes the variableLi, which is presented as:(16)Lik+1=argminLiXik−LiRikF2,s.t.Li∈StIi,si.Through solving this subproblem with the orthogonality constraint, the optimalLi is calculated. Following [27, 28], the optimal solution is given by:(17)Lik+1=QRXikRikT.The cost of computingL is Os2n1.The second subproblem optimizing the variableRi can be calculated as follows:(18)Rik+1=argminRiωiRi∗+β12Xik−Lik+1RiF2.Then,Rik+1 is the optimal solution to the subproblem (18) if and only if(19)0∈ωi∂Rik+1∗+β1Lik+1TLik+1Rik+1−Xik,where ∂⋅∗ is the subdifferential of ⋅∗. Considering the property of Lik+1, Lik+1TLik+1=Is, the formula can be transformed as(20)0∈ωi∂Rik+1∗+β1Rik+1−Lik+1TXik.Obviously, the formula (20) also needs to be satisfied by the optimal solution Ri for the following convex problem:(21)argminRiωiRi∗+β12Ri−Lik+1TXikF2.Therefore,Rik+1 is also the solution to the subproblem (21), which has an explicit solution.(22)Rik+1=SVTωi/β1Lik+1TXik.Algorithm 2: The Proposed ADMM-based Algorithm for Solving the SMF Model in (11).
Input: The initialized tensor T, index set Ω, parameters λ1,λ2,β1,β2,andβ3.Output: The completed tensor X.1:initialize:X0=T,Li0=eyeIi,si,Ri0=randsi,Πi≠jIj,i=1,2,3,M0,N0,ψ0andΘ0initializedto0,k=0,kmax=300.2:while not converged and k<kmaxdo3:fori=1 to 3 do4:Lik+1 via (17)5:Rik+1 via (22)6:  end for7:Mk+1 via (24)8:Nk+1 via (27)9:Xk+1 via (29)10:ψk+1,Θk+1 via (30)11:end while12:returnXk+1Here,SVTτ⋅ is a singular value thresholding operator defined by SVTτX=Udiagmaxσ−τ,0VT, the SVD of X is given by Q=Udiagσi1≤i≤rVT. The complexity of computing R is Osn12n22.The third subproblem aboutM related to framelet regularization can be written as:(23)Mk+1=argminMλ1M1,1+WX3kT−M,Ψ+β22WX3kT−MF2=argminMλ1M1,1+β22WX3kT−M+Ψβ2F2.This problem has an explicit optimal solution(24)Mk+1=Sλ1/β2WX3kT+Ψβ2,where Sμ⋅ is a soft-thresholding operator written as:(25)Sμx=0,if∣x∣≤μ,signx∣x∣−μ,if∣x∣>μ.The cost of calculatingWX3T is Ola2n1n2n3. Here, l denotes the framelet level and a denotes filter number, then the cost of calculating M is Olm2n1n2n3.The fourth subproblem aboutN concerning total variation regularization can be calculated as follows:(26)Nk+1=argminNλ2N1,1+DSX3k−N,Θ+β32DSX3k−NF2=argminNλ2N1,1+β32DSX3k−N+Θβ3F2,which has an explicit solution(27)Nk+1=Sλ2/β3DSX3k+Θβ3.The cost of computingN is On1n2n32.The final subproblem optimizingX can be formulated as:(28)XΩck+1=argminX∑i=13β12Xi−LiRiF2+β22WX3kT−M+Ψβ2F2+β32DSX3k−N+Θβ3F2.We can updateX as follows:(29)XΩck+1=∑ifoldiinvβ1I+β2I+β3DsTDs∗β1Lik+1Rik+1+β2WTM−Ψβ2T+β3DsTN−Θ/β3NΩc,XΩk+1=TΩ.The cost of calculatingX is Osn1n2n3+lm2n1n2n3+n1n2n32+n13.According to ADMM, the multipliersΨ and Θ are updated as(30)Ψk+1=Ψk+β2WX3k+1T−Mk+1,Θk+1=Θk+β3DSX3k+1−Nk+1.To summarize, the proposed iterative ADMM-based algorithm for solving the SMF model in (11) is outlined in Algorithm 2. The computing complexity of L, R, M, N, and X at each iteration is Osn12n22+lm2n1n2n3+n13.


## 4. Numerical Experiments

In this part, several experiments are conducted on one synthetic and some visual data to demonstrate the performance of our proposed LTC scheme. We also compare it with another four state-of-the-art algorithms: MFTC [13], HaLRTC [12], LRTV-PDS [21], and SPC [22]. Here, we notice that MFTC and HaLRTC only use Tucker-rank to exploit the low-rank prior, while LRTV-PDS and SPC use Tucker-rank and CP-rank, respectively. Besides, both of them are expected to achieve better results on visual data for considering TV term as the smoothness constraint. To measure the estimated accuracy of completed tensor data, peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) are employed as quality metrics. The PSNR is defined as 10log10MAX2/MSE. Here, MAX is the max of whole data, and MSE is formulated as X^−X0F2/N. The SSIM estimates the resemblance of images in luminance, contrast, and structure. The relative change is defined as RelCha=Xk+1−XkF/XF, which is set as stopping criterion of all five algorithms. In the following experiments, if the relative change is smaller than the tolerance 10−5 during the iteration, we terminate the iterative process and output Xk as the recovered tensor.


### 4.1. Synthetic Data Completion

Here, we apply our LTC scheme and MFTC on synthetic data.Figure1 displays a visualization of a synthetic tensor and the corresponding results of tensor completion achieved by MFTC and LTC. We use four Gaussian functions to get the synthetic 3rd-order tensor. By randomly removing 80% of the voxels, we get the incomplete tensor. Compared to the results of MFTC and LTC, it is obvious that only low-rank assumption is not enough for highly missing data, and smoothness constraints can effectively improve the performance of tensor completion.Figure 1
Isosurface of synthetic data and completed results of MFTC and LTC.


### 4.2. Color Images Completion

In this part, we compare the performance of MFTC, HaLRTC, PDS, SPC, and the proposed LTC on four color images “Lena,” “Giant,” “Pepper,” and “Airplane.” The incomplete images are generated by randomly deleting elements. In color image data completion, the missing ratios (MRs) are set as 70%, 80%, and 90%. The quality metrics of recovered images completed by five methods are listed in Table1. From Table 1, it is obvious that LTC achieves high quality metrics values and performs better than other LRTC algorithms except SPC.Table 1
The PSNR and SSIM values of five LRTC algorithms on image data.
ImageMRPSNRSSIMLTCMFTCHaLRTCPDSSPCLTCMFTCHaLRTCPDSSPCLena70%28.3622.4624.9628.1128.830.87840.67380.75230.86560.888080%26.8220.1721.5126.0627.460.82740.56030.58340.80950.847390%24.2116.9017.5423.1125.440.73290.40430.38750.70830.7744Giant70%24.1620.5920.3623.0925.260.81450.69490.71230.77620.847680%22.5918.4817.3021.3123.550.73590.56120.57800.68100.778190%20.4115.2613.9119.2221.520.59340.35780.37220.53400.6580Pepper70%29.2624.7324.4730.8730.380.94260.86330.84400.96820.952180%27.6422.0519.8028.7429.080.91090.77090.67210.94450.933890%25.0918.1015.8525.3227.000.84200.58070.48110.87650.8944Airplane70%27.5525.0326.1627.5328.100.92760.86300.90100.94760.927880%25.9922.7122.6125.7027.100.88570.77870.79380.90640.904290%23.5919.5119.1123.0725.490.80590.62560.62610.80690.8584Figure2 presents the results of color image “Lena” recovered by MFTC, HaLRTC, PDS, SPC, and LTC with different missing ratios. The MRs are set as 70%, 80%, and 90%. From Figure 2, it can be observed that the quality of the completed images by MFTC and HaLRTC becomes worse as the missing ratio increases, while the results obtained by PDS, SPC, and LTC still contain most information of the original image.Figure 2
The recovered color image by five tensor completion methods withMR=70%, 80%, 90%.Figure3 presents the recovered color images “Lena,” “Giant,” “Pepper,” and “Airplane” completed by MFTC, HaLRTC, PDS, SPC, and LTC with MR=80%. Obviously, we can see that methods with smoothness constraints (PDS, SPC, and LTC) perform better than those only considering low-rank prior (MFTC, HALRTC) for different color images.Figure 3
The different recovered color images by five tensor completion methods withMR=80%.Figure4 shows performance comparison of color image “Lena” by MFTC, HaLRTC, PDS, SPC, and LTC in PSNR, SSIM, and running time. The MRs are set as 50%, 60%, 70%, 80%, and 90%, respectively. We can see that PDS, SPC, and LTC are superior to MFTC and HaLRTC in terms of PSNR and SSIM. With MR increasing, the advantage of methods with smoothness constraints becomes more prominent. While ensuring the performance, LTC achieves about 80% running time reduction compared to PDS and SPC, which implies that introducing matrix factorization indeed improves the efficiency of tensor completion.Figure 4
Comparison of performances by five LRTC methods on the color image. (a) Comparison of PSNR, (b) comparison of SSIM, and (c) comparison of running time.
(a)(b)(c)In order to analyze the effect of parametersλ1 and λ2, we evaluate the performance of the recovered color image “Lena” by LTC with MR=70%. Figure 5 shows the change of the PSNR values for different values of λ1 and λ2. It is observed that both λ1 and λ2 evidently effect the tensor completed results of our proposed LTC scheme. Additionally, the LTC achieves higher PSNR values when λ1=10, λ2=10.Figure 5
The PSNR values with different values of parametersλ1 and λ2.To compare the convergence behavior of LTC with or without tensor initialization, we display the relative change (RelCha) values of the recovered color image “Lena” withMR=90% in Figure 6. It is observed that the RelCha value of LTC with tensor initialization decreases faster than LTC without tensor initialization, which proves the effectiveness of our proposed tensor initialization method to accelerate the convergence speed.Figure 6
The convergence behavior of LTC with or without tensor initialization to show the effect of smoothness constraints in tensor completion.


### 4.3. Video Completion

Here, two videos: “suzie” and “hall” are tested, and only the first 30 frames of each video are used for tensor completion. The size of videos for LRTC is144×176×30.Figure7 shows the 10th frame in two videos recovered by five tensor completion methods with MRs=70% and 80%, which presents the visual results of recovered videos. Obviously, the videos recovered by PDS, SPC, and LTC are visually superior to MFTC and HaLRTC. Definitely, SPC and LTC has a better performance to complete the video for preserving details well, while some parts of recovered video by PDS are still blurry.Figure 7
The single frame of recovered videos by five tensor completion methods withMR=70%, 80%.Figure8 presents the PSNR and SSIM values of each frame of completed video “suzie” by five algorithms with MRs=60%, 70% and 80%, which shows the performance comparison more straightforward. From curves in Figure 8, we can conclude that SPC and LTC are better than other algorithms in both stability and effectiveness.Figure 8
The PSNR and SSIM values by five tensor completion methods withMR=60%, 70%, 80%.Figure9 shows performance comparison of tensor completion for video “suzie” by our proposed LTC and the comparing four algorithms in PSNR, SSIM, and running time. The MRs are set as 40%, 50%, 60%, 70%, and 80%, respectively. Apparently, PDS, SPC, and LTC perform better than MFTC and HaLRTC when the MR is high. While ensuring the performance, LTC achieves about 90% and 50% running time reduction compared to SPC and PDS, respectively. It means that introducing matrix factorization can effectively reduce the running time of recovering incomplete videos.Figure 9
Comparison of performances by five LRTC methods on the video. (a) Comparison of PSNR, (b) comparison of SSIM, and (c) comparison of running time.
(a)(b)(c)


## 4.1. Synthetic Data Completion

Here, we apply our LTC scheme and MFTC on synthetic data.Figure1 displays a visualization of a synthetic tensor and the corresponding results of tensor completion achieved by MFTC and LTC. We use four Gaussian functions to get the synthetic 3rd-order tensor. By randomly removing 80% of the voxels, we get the incomplete tensor. Compared to the results of MFTC and LTC, it is obvious that only low-rank assumption is not enough for highly missing data, and smoothness constraints can effectively improve the performance of tensor completion.Figure 1
Isosurface of synthetic data and completed results of MFTC and LTC.


## 4.2. Color Images Completion

In this part, we compare the performance of MFTC, HaLRTC, PDS, SPC, and the proposed LTC on four color images “Lena,” “Giant,” “Pepper,” and “Airplane.” The incomplete images are generated by randomly deleting elements. In color image data completion, the missing ratios (MRs) are set as 70%, 80%, and 90%. The quality metrics of recovered images completed by five methods are listed in Table1. From Table 1, it is obvious that LTC achieves high quality metrics values and performs better than other LRTC algorithms except SPC.Table 1
The PSNR and SSIM values of five LRTC algorithms on image data.
ImageMRPSNRSSIMLTCMFTCHaLRTCPDSSPCLTCMFTCHaLRTCPDSSPCLena70%28.3622.4624.9628.1128.830.87840.67380.75230.86560.888080%26.8220.1721.5126.0627.460.82740.56030.58340.80950.847390%24.2116.9017.5423.1125.440.73290.40430.38750.70830.7744Giant70%24.1620.5920.3623.0925.260.81450.69490.71230.77620.847680%22.5918.4817.3021.3123.550.73590.56120.57800.68100.778190%20.4115.2613.9119.2221.520.59340.35780.37220.53400.6580Pepper70%29.2624.7324.4730.8730.380.94260.86330.84400.96820.952180%27.6422.0519.8028.7429.080.91090.77090.67210.94450.933890%25.0918.1015.8525.3227.000.84200.58070.48110.87650.8944Airplane70%27.5525.0326.1627.5328.100.92760.86300.90100.94760.927880%25.9922.7122.6125.7027.100.88570.77870.79380.90640.904290%23.5919.5119.1123.0725.490.80590.62560.62610.80690.8584Figure2 presents the results of color image “Lena” recovered by MFTC, HaLRTC, PDS, SPC, and LTC with different missing ratios. The MRs are set as 70%, 80%, and 90%. From Figure 2, it can be observed that the quality of the completed images by MFTC and HaLRTC becomes worse as the missing ratio increases, while the results obtained by PDS, SPC, and LTC still contain most information of the original image.Figure 2
The recovered color image by five tensor completion methods withMR=70%, 80%, 90%.Figure3 presents the recovered color images “Lena,” “Giant,” “Pepper,” and “Airplane” completed by MFTC, HaLRTC, PDS, SPC, and LTC with MR=80%. Obviously, we can see that methods with smoothness constraints (PDS, SPC, and LTC) perform better than those only considering low-rank prior (MFTC, HALRTC) for different color images.Figure 3
The different recovered color images by five tensor completion methods withMR=80%.Figure4 shows performance comparison of color image “Lena” by MFTC, HaLRTC, PDS, SPC, and LTC in PSNR, SSIM, and running time. The MRs are set as 50%, 60%, 70%, 80%, and 90%, respectively. We can see that PDS, SPC, and LTC are superior to MFTC and HaLRTC in terms of PSNR and SSIM. With MR increasing, the advantage of methods with smoothness constraints becomes more prominent. While ensuring the performance, LTC achieves about 80% running time reduction compared to PDS and SPC, which implies that introducing matrix factorization indeed improves the efficiency of tensor completion.Figure 4
Comparison of performances by five LRTC methods on the color image. (a) Comparison of PSNR, (b) comparison of SSIM, and (c) comparison of running time.
(a)(b)(c)In order to analyze the effect of parametersλ1 and λ2, we evaluate the performance of the recovered color image “Lena” by LTC with MR=70%. Figure 5 shows the change of the PSNR values for different values of λ1 and λ2. It is observed that both λ1 and λ2 evidently effect the tensor completed results of our proposed LTC scheme. Additionally, the LTC achieves higher PSNR values when λ1=10, λ2=10.Figure 5
The PSNR values with different values of parametersλ1 and λ2.To compare the convergence behavior of LTC with or without tensor initialization, we display the relative change (RelCha) values of the recovered color image “Lena” withMR=90% in Figure 6. It is observed that the RelCha value of LTC with tensor initialization decreases faster than LTC without tensor initialization, which proves the effectiveness of our proposed tensor initialization method to accelerate the convergence speed.Figure 6
The convergence behavior of LTC with or without tensor initialization to show the effect of smoothness constraints in tensor completion.


## 4.3. Video Completion

Here, two videos: “suzie” and “hall” are tested, and only the first 30 frames of each video are used for tensor completion. The size of videos for LRTC is144×176×30.Figure7 shows the 10th frame in two videos recovered by five tensor completion methods with MRs=70% and 80%, which presents the visual results of recovered videos. Obviously, the videos recovered by PDS, SPC, and LTC are visually superior to MFTC and HaLRTC. Definitely, SPC and LTC has a better performance to complete the video for preserving details well, while some parts of recovered video by PDS are still blurry.Figure 7
The single frame of recovered videos by five tensor completion methods withMR=70%, 80%.Figure8 presents the PSNR and SSIM values of each frame of completed video “suzie” by five algorithms with MRs=60%, 70% and 80%, which shows the performance comparison more straightforward. From curves in Figure 8, we can conclude that SPC and LTC are better than other algorithms in both stability and effectiveness.Figure 8
The PSNR and SSIM values by five tensor completion methods withMR=60%, 70%, 80%.Figure9 shows performance comparison of tensor completion for video “suzie” by our proposed LTC and the comparing four algorithms in PSNR, SSIM, and running time. The MRs are set as 40%, 50%, 60%, 70%, and 80%, respectively. Apparently, PDS, SPC, and LTC perform better than MFTC and HaLRTC when the MR is high. While ensuring the performance, LTC achieves about 90% and 50% running time reduction compared to SPC and PDS, respectively. It means that introducing matrix factorization can effectively reduce the running time of recovering incomplete videos.Figure 9
Comparison of performances by five LRTC methods on the video. (a) Comparison of PSNR, (b) comparison of SSIM, and (c) comparison of running time.
(a)(b)(c)


## 5. Conclusion

In this paper, we propose a low-complexity tensor completion scheme. Our model takes advantage of SNN to exploit the low-rankness, TV and framelet to recover details and characterize the smoothness, and matrix factorization to improve the efficiency. Besides, a novel tensor initialization method is proposed to accelerate convergence speed. Moreover, an efficient ADMM-based algorithm is developed to solve the SMF model. The numerical experiments on synthetic and real-world data demonstrate both the efficiency and effectiveness of proposed LTC scheme for tensor completion. Smoothing constraints for higher-dimensional data will be the research direction of tensor completion in the future.



---

*Source: 5515446-2021-05-11.xml*