# Tensor Completion Based on Triple Tubal Nuclear Norm
## 1 Introduction  
In recent decades, the rapid progress in multi-linear algebra [1] has provided a firm theoretical foundation for many applications in computer vision [2], data mining [3], machine learning [4], signal processing [5], and many other areas. Benefiting from its multi-way nature, the tensor has power against the vector and matrix in exploiting multi-way information in multi-modal data, like color images [6], videos [7], hyper-spectral images [8], functional magnetic resonance imaging [9], traffic volume data [10], etc. In many computer vision tasks, the data, like color images or videos, may be moderately redundant, then it can be interpreted by fewer latent factors [11]. The low-rank tensor provides a suitable model for such data [12]. The two most well-known low-rank tensor models are the low-CP-rank model [13], which tries to interpret a tensor in the fewest rank-one tensors [14], and the low-Tucker-rank model [15], which seeks a tensor proxy that is simultaneously low-rank along each mode. In many computer vision applications, like image or video inpainting, one has to tackle the missing values in the observed data tensor due to many circumstances [2; 16], including failure of sensors, errors or loss in communication, occlusions or noise in the environment, etc. However, it isobviously unable to fill in the missing entries perfectly since they can take arbitrary values without other priors taken into consideration. The most adopted prior is the low-rank prior assuming the underlying data tensor has low rank. Low-rank tensor completion [2; 17] seeks a low-rank tensor to fit the underlying data tensor. It has been a hot research topic due its wide use [18]. In low-rank tensor recovery, the rank minimization problem (RMP) is often formulated [2]. However, the general rank minimization problem and most tensor problems are NP-hard [19; 20]. To obtain polynomial-time algorithms, many different tensor rank surrogates have been proposed [2; 7; 17; 21; 22; 23; 24] to substitute the rank functions in RMP. Surrogates of the tensor CP rank and Tucker rank have been broadly studied [7; 17; 23; 25; 26; 27; 28; 29]. Recently, a novel low-rank tensor model called the low-tubal-rank model was proposed [22; 30]. The core of it is to model the 3D data as a tensor that has low tubal-rank [31], which is defined through a new tensor singular value decomposition (t-SVD) [1; 32]. It has been successfully used in modeling multi-way real-world data, such as color images [6], videos [33], seismic data [34], WiFi fingerprint [35], MRI imaging [22], traffic volume data [36], etc. As pointed out in [37], compared with other tensor models, the low-tubal-rank tensor model is superior in capturing a \"spatial-shifting\" correlation, which is ubiquitous in real-world data arrays. This paper focuses on low-tubal-rank models for tensor completion. The recently-proposed tensor tubal nuclear norm (TNN) [30] based on t-SVD has shown superiority in imputing missing values in 3D visual data, like color images and videos. Its power lies in exploiting tube (often carrying temporal/channel information) redundancy in a circulant way while preserving the row and column (often carrying spatial information) relationship. A simple and successful variant of TNN, dubbed the twist tubal nuclear norm (t-TNN) [16], instead exploits row redundancy in a circulant way while keeping the tube relationship. However, both of them only exploit one kind of redundancy in a circulant way. In this paper, a new tensor norm dubbed the tensor triple tubal nuclear norm (TriTNN) is proposed to simultaneously exploit the row, column and tube redundancy while preserving the relative tube, row and column relationship. Based on the proposed TriTNN, a tensor completion model is studied and optimized by alternating direction multiplier methods (ADMM) [38]. Experimental results on color images, videos and LiDAR datasets demonstrate that the proposed TriTNN has better performances than other state-of-the-art nuclear norm-based tensor norms. The paper is organized as follows.