# Tensor Completion Based on Triple Tubal Nuclear Norm
## 4 TriTNN-Based Tensor Completion
### An ADMM Solver to Problem (21)  
The alternative direction multiplier method (ADMM) [38] has been extensively used in solving composite convex problems like Problem (21). We will solve Problem (21) by using ADMM in this subsection. Considering the definition of TriTNN, we introduce auxiliary variables \(\mathbf{\mathcal{U}},\mathbf{\mathcal{V}},\mathbf{\mathcal{W}}\in\mathbb{R}^{n_{1}\times n _{2}\times n_{3}}\) and obtain the following constrained problem:  
\[ \begin{array}{rl}\min_{\mathbf{\mathcal{L}},\mathbf{\mathcal{U}},\mathbf{ \mathcal{V}},\mathbf{\mathcal{W}}}&\frac{1}{2}\|\mathbf{\mathcal{O}}\odot(\mathbf{ \mathcal{T}}-\mathbf{\mathcal{L}})\|_{\text{F}}^{2}+\tau\lambda_{1}\|\mathbf{\mathcal{ U}}\|_{\star}+\tau\lambda_{2}\|\mathbf{\mathcal{V}}\|_{\star}+\tau\lambda_{3}\|\mathbf{ \mathcal{W}}\|_{\star}\\ \text{s.t.}&\mathbf{\mathcal{U}}=\mathbf{\mathcal{L}},\ \ \mathbf{\mathcal{V}}=\mathbf{ \mathcal{\overrightarrow{\mathcal{L}}}},\ \ \mathbf{\mathcal{W}}=\mathbf{ \mathcal{\underline{\mathcal{L}}}}.\end{array}  \tag{22}\]  
First, the augmented Lagrangian of Problem (22) is:  
\[ \begin{array}{rl}L_{\rho}(\mathbf{\mathcal{L}},\mathbf{\mathcal{U}},\mathbf{\mathcal{V}},\mathbf{\mathcal{W}},\mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2},\mathbf{\mathcal{Y}} _{3})\\ =\frac{1}{2}\|\mathbf{\mathcal{O}}\odot(\mathbf{\mathcal{T}}-\mathbf{\mathcal{L}})\|_{ \text{F}}^{2}+\tau\lambda_{1}\|\mathbf{\mathcal{U}}\|_{\star}+\tau\lambda_{2}\|\bm {\mathcal{V}}\|_{\star}+\tau\lambda_{3}\|\mathbf{\mathcal{W}}\|_{\star}+\langle\mathbf{ \mathcal{Y}}_{1},\mathbf{\mathcal{U}}-\mathbf{\mathcal{L}}\rangle+\frac{\rho}{2}\|\mathbf{ \mathcal{U}}-\mathbf{\mathcal{L}}\|_{\text{F}}^{2}\\ \qquad\quad+\Big{\langle}\mathbf{\mathcal{Y}}_{2},\mathbf{\mathcal{V}}-\mathbf{ \overrightarrow{\mathcal{L}}}\Big{\rangle}+\frac{\rho}{2}\|\mathbf{\mathcal{V}}- \mathbf{\overrightarrow{\mathcal{L}}}\|_{\text{F}}^{2}+\Big{\langle}\mathbf{\mathcal{ Y}}_{3},\mathbf{\mathcal{W}}-\mathbf{\underline{\mathcal{L}}}\Big{\rangle}+\frac{\rho}{2}\|\mathbf{ \mathcal{W}}-\mathbf{\underline{\mathcal{L}}}\|_{\text{F}}^{2},\end{array}  \tag{23}\]  
where \(\mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2}\) and \(\mathbf{\mathcal{Y}}_{3}\) are Lagrangian multipliers and \(\rho>0\) is the penalty parameter. Using the framework of ADMM, we update the variables alternatively by fixing others at the \(k+1\)-th iteration in the following way. Update \(\mathbf{\mathcal{L}}\). We update \(\mathbf{\mathcal{L}}\) by fixing the other variables as follows:  
\[ \begin{split}\mathbf{\mathcal{L}}^{k+1}&=\operatorname*{ argmin}_{\mathbf{\mathcal{L}}}\,L_{\rho}(\mathbf{\mathcal{L}},\mathbf{\mathcal{U}}^{k},\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{L}}}\,\,\,\,\,\frac{1}{2} \|\mathbf{\mathcal{O}}\odot(\mathbf{\mathcal{T}}-\mathbf{\mathcal{L}})\|_{\mathrm{F}}^{2} \,+\left<\mathbf{\mathcal{Y}}^{k}_{1},\mathbf{\mathcal{U}}^{k}-\mathbf{\mathcal{L}}\right> +\frac{\rho}{2}\|\mathbf{\mathcal{U}}^{k}-\mathbf{\mathcal{L}}\|_{\mathrm{F}}^{2}\\ &\qquad\qquad\qquad+\left<\mathbf{\mathcal{Y}}^{k}_{2},\mathbf{\mathcal{ V}}^{k}-\overrightarrow{\mathbf{\mathcal{L}}}\right>+\frac{\rho}{2}\|\mathbf{\mathcal{V}}^{k}- \overrightarrow{\mathbf{\mathcal{L}}}\|_{\mathrm{F}}^{2}+\left<\mathbf{\mathcal{Y}}^{ k}_{3},\mathbf{\mathcal{W}}^{k}-\overleftarrow{\mathbf{\mathcal{L}}}\right>+\frac{ \rho}{2}\|\mathbf{\mathcal{W}}^{k}-\overleftarrow{\mathbf{\mathcal{L}}}\|_{\mathrm{F}} ^{2}\\ &=(\rho\mathbf{\mathcal{U}}^{k}+\rho\overleftarrow{\mathbf{\mathcal{V}}^{ k}}+\rho\overrightarrow{\mathbf{\mathcal{W}}^{k}}+\mathbf{\mathcal{Y}}^{k}_{1}+ \overleftarrow{\mathbf{\mathcal{Y}}^{k}_{2}}+\overrightarrow{\mathbf{\mathcal{Y}}^{ k}_{3}}+\mathbf{\mathcal{O}}\odot\mathbf{\mathcal{T}})\odot(\mathbf{\mathcal{O}}+\rho \mathbb{I}),\end{split}  \tag{24}\]  
where \(\odot\) denotes element-wise division and \(\mathbb{I}\) denotes the tensor of all ones.