# Tensor Completion Based on Triple Tubal Nuclear Norm
## 3 The Triple Tubal Nuclear Norm
### Tubal Nuclear Norm  
Based on the preliminaries introduced in Section 2, the tubal nuclear norm is defined as follows:  
Figure 1: Illustration of tensor (t)-SVD.  
**Definition 7** (Tubal nuclear norm [31]).: _The tubal nuclear norm (TNN) \(\|\mathbf{\mathcal{T}}\|_{*}\) of a 3D tensor \(\mathbf{\mathcal{T}}\) is defined as the nuclear norm of the block diagonal matrix of \(\widetilde{\mathbf{\mathcal{T}}}\) (the Fourier domain version of \(\mathbf{\mathcal{T}}\)), i.e.,_  
\[\|\mathbf{\mathcal{T}}\|_{*}:=\|\text{\rm{bdiag}}(\widetilde{\mathbf{\mathcal{T}}})\|_{ *}=\sum_{k=1}^{n_{3}}\|\widetilde{\mathbf{\mathcal{T}}}^{(k)}\|_{*}. \tag{6}\]  
From Definition 7, we can compute the TNN of a tensor efficiently through first conducting FFT along the tube direction and summing the nuclear norms of each frontal slice. Given a tensor \(\mathbf{\mathcal{T}}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}\), the computation cost of \(\|\mathbf{\mathcal{T}}\|_{*}\) is \(O(n_{1}n_{2}n_{3}(n_{3}+\log n_{3}))\). Since a block circulant matrix can be block diagonalized through the Fourier transform [1], we obtain:  
\[\|\mathbf{\mathcal{T}}\|_{*}=\|\text{\rm{bdiag}}(\widetilde{\mathbf{\mathcal{T}}})\|_ {*}=\|(F_{n_{3}}\otimes\mathbf{I}_{n_{1}})\text{\rm{bcirc}}(\mathbf{\mathcal{T}})(F_ {n_{3}}^{-1}\otimes\mathbf{I}_{n_{2}})\|_{*}=\|\text{\rm{bcirc}}(\mathbf{\mathcal{T}}) \|_{*}, \tag{7}\]  
where \(\otimes\) denotes the Kronecker product [14], \(\mathbf{F}_{n}\) is the \(n\times n\) discrete Fourier transform matrix and \(\mathbf{I}_{n}\) is an \(n\times n\) identity matrix. Note that \((\mathbf{F}_{n_{3}}\otimes\mathbf{I}_{n_{1}})/\sqrt{n_{3}}\) is a unitary matrix.  
The tubal nuclear norm has been used as a convex relaxation of the tensor tubal-rank for tensor completion, tensor robust principle component analysis (TRPCA) and outlier robust tensor principle component analysis (OR-TPCA) [6; 30; 36; 39]. In optimization over TNN, one often needs to compute the proximal operator [40] of TNN defined as:  
\[\mathfrak{S}_{\tau}(\mathbf{\mathcal{T}}_{0}):=\underset{\mathbf{\mathcal{T}}}{\text{ argmin}}\ \frac{1}{2}\|\mathbf{\mathcal{T}}_{0}-\mathbf{\mathcal{T}}\|_{\text{F}}^{2}+\tau\|\mathbf{ \mathcal{T}}\|_{*}. \tag{8}\]  
In [3], a closed-form expression of \(\mathfrak{S}_{\tau}(\cdot)\) is given as follows:  
**Definition 8** ([3]).: _For a 3D tensor \(\mathbf{\mathcal{T}}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}\) with reduced t-SVD \(\mathbf{\mathcal{T}}=\mathbf{\mathcal{U}}*\mathbf{\mathcal{S}}*\mathbf{\mathcal{V}}^{\top}\), where \(\mathbf{\mathcal{U}}\in\mathbb{R}^{n_{1}\times r\times n_{3}}\) and \(\mathbf{\mathcal{V}}\in\mathbb{R}^{n_{2}\times r\times n_{3}}\) are orthogonal tensors and \(\mathbf{\mathcal{S}}\in\mathbb{R}^{r\times r\times n_{3}}\) is the f-diagonal tensor of singular tubes, the proximal operator \(\mathfrak{S}_{\tau}(\cdot)\) at \(\mathbf{\mathcal{T}}_{0}\) can be computed through the following equation:_  
\[\mathfrak{S}_{\tau}(\mathbf{\mathcal{T}}):=\mathbf{\mathcal{U}}*\text{\rm{idft3}}( \max(\text{\rm{dft3}}(\mathbf{\mathcal{S}})-n_{3}\tau,0))*\mathbf{\mathcal{V}}^{\top}. \tag{9}\]