Low Tubal Rank Tensor Completion With Non-uniform Sampling

With the rapid development and popularization of computer technology in recent decades,and the improvement of computing capacity,massive data are sensed,stored,analyzed and calculated.Tensors are higher-order generalizations of vectors and matrices.Extensive real world data can be naturally represented as tensors.Therefore,tensor analysis algorithms have a very rapid development and wide applications.Tensor completion is an important issue in the field of tensor analysis.It aims to recovery the underlying tensor from some observed elements.Tensor completion is obviously an ill-posed problem,because the missing elements can be arbitrary values,which makes tensor completion face enormous challenges.Fortunately,real world data always have some intrinsic structure,such as sparse and low rank.In recent years,many low tubal rank tensor completion algorithms have been proposed.Nearly all the existing theoretical analyses of low tubal rank tensor completion algorithms assume that the sampling process is uniform.That is to say,every element in the underlying tensor has the same probability to be sampled.In this paper,we study the low tubal rank tensor completion with non-uniform sampling.The main contributions of this paper are as follows:1.The condition of low tubal rank tensor completion,applying the tensor nuclear norm minimization algorithm,with non-uniform sampling is theoretically studied.And the underlying tensor is not necessary incoherent.A theorem is proposed to give the condition,and proved by the dual certification.Low tubal rank tensor completion method with non-uniform sampling is proposed.Compared with the previous uniform sampling tensor completion method,it requires fewer samples to achieve the same precision.2.To overcome the fact that the tensor leverage score is often unknown in real world application,we propose a two phase tensor completion algorithm without the prior of the tensor leverage score,when the sample procedure is under control.The algorithm estimate the tensor leverage score by a portion of budget of the number of observed elements,and then sample the rest budget of elements according to the estimated tensor leverage score.Finally,the underlying tensor is completed by all the elements sampled from both two steps.3.Extensive experiments are conducted in this paper to verify our results on both 3-order tensors generated randomly and real data sets.And different methods are compared with each other on the image and video data.It can be seen that the non-uniform sample method with tensor leverage score performs better than the tensor two-phase procedure,while the two phase procedure performs better than the traditional uniform sample procedure.