# Tensor Completion Based on Triple Tubal Nuclear Norm
## 4 TriTNN-Based Tensor Completion
### An ADMM Solver to Problem (21)
Update \(\mathbf{\mathcal{U}}\),\(\mathbf{\mathcal{V}}\) and \(\mathbf{\mathcal{W}}\). Tensor \(\mathbf{\mathcal{U}}\) is updated as follows:  
\[ \begin{split}\mathbf{\mathcal{U}}^{k+1}&= \operatorname*{argmin}_{\mathbf{\mathcal{U}}}\,L_{\rho}(\mathbf{\mathcal{L}}^{k+1}, \mathbf{\mathcal{U}},\mathbf{\mathcal{V}}^{k},\mathbf{\mathcal{W}}^{k},\mathbf{\mathcal{Y}}^{ k}_{1},\mathbf{\mathcal{Y}}^{k}_{2},\mathbf{\mathcal{Y}}^{k}_{3})\\ &=\operatorname*{argmin}_{\mathbf{\mathcal{U}}}\,\,\tau\lambda_{1}\| \mathbf{\mathcal{U}}\|_{\mathbf{\mathcal{U}}}\,\,+\left<\mathbf{\mathcal{Y}}^{k}_{1},\mathbf{ \mathcal{U}}-\mathbf{\mathcal{L}}^{k+1}\right>+\frac{\rho}{2}\|\mathbf{\mathcal{U}}- \mathbf{\mathcal{L}}^{k+1}\|_{\mathrm{F}}^{2}\\ &=\mathfrak{S}_{\tau\lambda_{1}/\rho}(\mathbf{\mathcal{L}}^{k+1}- \frac{\mathbf{\mathcal{Y}}^{k}_{1}}{\rho}),\end{split}  \tag{25}\]  
where \(\mathfrak{S}_{\cdot}(\cdot)\) is the proximal operator of TNN at point \(\mathbf{\mathcal{L}}^{k+1}-\mathbf{\mathcal{Y}}^{k}_{1}/\rho\) with parameter \(\tau\lambda_{1}/\rho\) (see Equation (8)). Tensors \(\mathbf{\mathcal{V}}\) and \(\mathbf{\mathcal{W}}\) are updated similarly to \(\mathbf{\mathcal{U}}\),  
\[ \begin{split}\mathbf{\mathcal{V}}^{k+1}&= \operatorname*{argmin}_{\mathbf{\mathcal{V}}}\,L_{\rho}(\mathbf{\mathcal{L}}^{k+1},\mathbf{ \mathcal{U}}^{k+1},\mathbf{\mathcal{V}},\mathbf{\mathcal{W}}^{k},\mathbf{\mathcal{Y}}^{k}_{ 1},\mathbf{\mathcal{Y}}^{k}_{2},\mathbf{\mathcal{Y}}^{k}_{3})\\ &=\text{ColSqueeze}(\mathfrak{S}_{\tau\lambda_{2}/\rho}( \overrightarrow{\mathbf{\mathcal{L}}^{k+1}}-\frac{\mathbf{\mathcal{Y}}^{k}_{2}}{\rho} )),\end{split}  \tag{26}\]  
and:  
\[ \begin{split}\mathbf{\mathcal{W}}^{k+1}&= \operatorname*{argmin}_{\mathbf{\mathcal{W}}}\,L_{\rho}(\mathbf{\mathcal{L}}^{k+1},\mathbf{ \mathcal{U}}^{k+1},\mathbf{\mathcal{V}}^{k+1},\mathbf{\mathcal{W}},\mathbf{\mathcal{Y}}^{ k}_{1},\mathbf{\mathcal{Y}}^{k}_{2},\mathbf{\mathcal{Y}}^{k}_{3})\\ &=\text{RowSqueeze}(\mathfrak{S}_{\tau\lambda_{3}/\rho}( \overrightarrow{\mathbf{\mathcal{L}}^{k+1}}-\frac{\mathbf{\mathcal{Y}}^{k}_{3}}{\rho} )).\end{split}  \tag{27}\]  
Update \(\mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2}\) and \(\mathbf{\mathcal{Y}}_{3}\). Using dual ascending, we update \(\mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2}\) and \(\mathbf{\mathcal{Y}}_{3}\) as follows:  
\[ \begin{split}\mathbf{\mathcal{Y}}^{k+1}_{1}&= \mathbf{\mathcal{Y}}^{k}_{1}+\rho(\mathbf{\mathcal{U}}^{k+1}-\mathbf{\mathcal{L}}^{k+1}),\\ \mathbf{\mathcal{Y}}^{k+1}_{2}&=\mathbf{\mathcal{Y}}^{k}_{2}+ \rho(\mathbf{\mathcal{V}}^{k+1}-\overrightarrow{\mathbf{\mathcal{L}}^{k+1}}),\\ \mathbf{\mathcal{Y}}^{k+1}_{3}&=\mathbf{\mathcal{Y}}^{k}_{3}+ \rho(\mathbf{\mathcal{W}}^{k+1}-\overrightarrow{\mathbf{\mathcal{L}}^{k+1}}).\end{split}  \tag{28}\]  
We summarize the algorithm in Algorithm 1 and analyze the computational complexity as follows. Complexity analysis: The main computational cost in each iteration rests in the singular tube thresholding operator, requiring the computation of FFT, IFFT and SVDs. Therefore, the time complexity in each iteration is:  
\[O\big{(}n_{1}n_{2}n_{3}(n_{1}+n_{2}+n_{3}+\log(n_{1}n_{2}n_{3}))\big{)}, \tag{29}\]```
1:The observed tensor \(\mathbf{\mathcal{T}}\), the parameters \(\tau,\lambda_{1},\lambda_{2},\lambda_{3},\rho\). 2:while not converged do
3: Update \(\mathbf{\mathcal{L}}\) using Equation (24);
4: Update \(\mathbf{\mathcal{U}},\mathbf{\mathcal{V}}\) and \(\mathbf{\mathcal{W}}\) using Equations (25), (26) and (27), respectively;
5: Update \(\mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2}\) and \(\mathbf{\mathcal{Y}}_{3}\) using Equations (28);
6: Check the convergence conditions: \[\|\mathbf{\mathcal{L}}^{k+1}-\mathbf{\mathcal{L}}^{k}\|_{\infty}\leq\delta, \|\mathbf{\mathcal{U}}^{k+1}-\mathbf{\mathcal{U}}^{k}\|_{\infty}\leq\delta,\] \[\|\mathbf{\mathcal{V}}^{k+1}-\mathbf{\mathcal{V}}^{k}\|_{\infty}\leq\delta, \|\mathbf{\mathcal{W}}^{k+1}-\mathbf{\mathcal{W}}^{k}\|_{\infty}\leq\delta.\]
7:endwhile
8:\(\mathbf{\mathcal{L}}\). ```

**Algorithm 1** Solving Problem (21) using ADMM.