# Tensor Completion Based on Triple Tubal Nuclear Norm
## 4 TriTNN-Based Tensor Completion
### An ADMM Solver to Problem (21)
### Convergence of Algorithm 1

As Problem (21) has more than two variables, the convergence property of Algorithm 1 cannot be directly obtained from existing results on the convergence of ADMM [38]. Thus, we prove its convergence in terms of the objective function in the following theorem. **Theorem 1** (Convergence of Algorithm 1). : _For any \(\rho>0\), if the unaugmented Lagrangian \(L_{0}(\mathbf{\mathcal{L}},\mathbf{\mathcal{U}},\mathbf{\mathcal{V}},\mathbf{\mathcal{W}}, \mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2},\mathbf{\mathcal{Y}}_{3})\) has a saddle point, then the iterations \((\mathbf{\mathcal{L}}^{k},\mathbf{\mathcal{U}}^{k},\mathbf{\mathcal{V}}^{k},\mathbf{\mathcal{ W}}^{k},\mathbf{\mathcal{Y}}_{1}^{k},\mathbf{\mathcal{Y}}_{2}^{k},\mathbf{\mathcal{Y}}_{3}^{k})\) in Algorithm 1 satisfy the residual convergence, objective convergence and dual variable convergence of Problem (21)._

Proof. : The key idea of the proof is to rewrite Problem (9) into a two-block ADMM problem. Since the _RowTwist_ and _ColTwist_ operations are linear, there exist two matrices \(P_{1},P_{2}\in\mathbb{R}^{n_{1}n_{2}n_{3}\times n_{1}n_{2}n_{3}}\), such that the constraints \(\mathbf{\mathcal{V}}=\text{ColTwist}(\mathbf{\mathcal{L}})\) and \(\mathbf{\mathcal{W}}=\text{RowTwist}(\mathbf{\mathcal{L}})\) are equivalent to the vectorization expressions:

\[\text{vec}(\mathbf{\mathcal{V}})=P_{1}\text{vec}(\mathbf{\mathcal{L}}),\text{ and }\quad\text{vec}(\mathbf{\mathcal{W}})=P_{2}\text{vec}(\mathbf{\mathcal{L}}),\]

where \(\text{vec}(\cdot)\) denotes the operation of tensor vectorization (see [14]). For notational simplicity, let:

\[\mathbf{x}=\text{vec}(\mathbf{\mathcal{L}}),\quad\mathbf{y}= \begin{bmatrix}\text{vec}( \mathbf{\mathcal{Y}}_{1})\\ \text{vec}(\mathbf{\mathcal{Y}}_{2})\\ \text{vec}(\mathbf{\mathcal{Y}}_{3})\end{bmatrix} ,\quad\mathbf{z}= \begin{bmatrix} \text{vec}(\mathbf{\mathcal{U}})\\ \text{vec}(\mathbf{\mathcal{V}})\\ \text{vec}(\mathbf{\mathcal{W}})\end{bmatrix} ,\quad\mathbf{A}= \begin{bmatrix}I\\ P_{1}\\ P_{2}\end{bmatrix} ,\]

and:

\[f(\mathbf{x})=\frac{1}{2}\|\mathbf{\mathcal{O}}\odot(\mathbf{\mathcal{L}}-\mathbf{\mathcal{T}} )\|_{\text{F}}^{2},\quad g(\mathbf{z})=\tau(\lambda_{1}\|\mathbf{\mathcal{U}}\|_{\star }+\lambda_{2}\|\mathbf{\mathcal{V}}\|_{\star}+\lambda_{3}\|\mathbf{\mathcal{W}}\|_{ \star}).\]

It is obvious that \(f(\cdot)\) and \(g(\cdot)\) are closed, proper and convex. Then, Problem (21) can be re-written as follows:

\[\min_{\mathbf{x},\mathbf{z}} f(\mathbf{x})+g(\mathbf{z})\] s.t. \[\mathbf{Ax}-\mathbf{z}=\mathbf{0}.\]According to the convergence analysis in [38], we have: objective convergence: \[\lim_{k\to\infty}f(\mathbf{x}^{k})+g(\mathbf{z}^{k})=f^{*}+g^{*},\] dual variable convergence: \[\lim_{k\to\infty}\mathbf{y}^{k}=\mathbf{y}^{*},\] constraint convergence: \[\lim_{k\to\infty}\mathbf{A}\mathbf{x}^{k}-\mathbf{z}^{k}=\mathbf{0},\]

where \(f^{*},g^{*}\) are the optimal values of \(f(\mathbf{x})\), \(g(\mathbf{z})\), respectively. Variable \(\mathbf{y}^{*}\) is a dual optimal point defined as:

\[\mathbf{y}^{*}= \begin{bmatrix}\mathrm{vec}(\mathbf{\mathcal{Y}}_{1}^{*})\\ \mathrm{vec}(\mathbf{\mathcal{Y}}_{2}^{*})\\ \mathrm{vec}(\mathbf{\mathcal{Y}}_{3}^{*})\end{bmatrix} ,\]

where \((\mathbf{\mathcal{Y}}_{1}^{*},\mathbf{\mathcal{Y}}_{2}^{*},\mathbf{\mathcal{Y}}_{3}^{*})\) is the dual component of a saddle point \((\mathbf{\mathcal{L}}^{*},\mathbf{\mathcal{U}}^{*},\mathbf{\mathcal{Y}}^{*},\mathbf{\mathcal{ W}}^{*},\mathbf{\mathcal{Y}}_{1}^{*},\mathbf{\mathcal{Y}}_{2}^{*},\mathbf{\mathcal{Y}}_{3}^{*})\) of the unaugmented Lagrangian \(L_{0}(\mathbf{\mathcal{L}},\mathbf{\mathcal{U}},\mathbf{\mathcal{V}},\mathbf{\mathcal{W}}, \mathbf{\mathcal{Y}}_{1},\mathbf{\mathcal{Y}}_{2},\mathbf{\mathcal{Y}}_{3})\). ### Differences from Prior Work

First, we show the difference between the proposed model TriTNN and two mostly related models TNN [30] and t-TNN [16].