# Accelerated Tensor Robust Principal Component Analysis via Factorized Tensor Norm Minimization
## 4 Proposed Algorithm
### Solution Algorithm  
The solution to the optimization problem in (17) can be obtained efficiently using an alternating direction method of multiplier (ADMM)-based algorithm.  
1. Computation of \(\mathcal{A}\). Finding the optimal \(\mathcal{A}_{k}\) at iteration \(k\), while keeping the other variables fixed, involves solving the following sub-problem derived from (17) such that \[\mathcal{A}_{k+1}=\arg\min\mathcal{A}_{k}\frac{1}{2n_{3}}\|\mathcal{A}_{k}\|_ {F}^{2}+\mu\|\mathcal{A}_{k}*\mathcal{B}_{k}^{T}-\mathcal{Q}\|_{F}^{2},\] (19) where \(\mathcal{Q}=\mathcal{X}-\mathcal{S}_{k}-\mu^{-1}\mathcal{P}_{k}\). By taking the derivative of (19) with respect to \(\mathcal{A}_{k}\), and rearranging terms, we obtain the closed-form solution for \(\mathcal{A}_{k+1}\) as follows: \[\mathcal{A}_{k+1}=\mathcal{Q}*\mathcal{B}_{k}*(\frac{1}{n_{3}}\mathcal{I}+ \mu\mathcal{B}_{k}^{T}*\mathcal{B}_{k})^{-1},\] (20) where \(\mathcal{I}\in\mathbb{R}^{r\times r\times n_{3}}\) denotes the identity tensor.
2. Computation of \(\mathcal{B}\). Similar to (19), we fix \(\mathcal{A}_{k+1},\mathcal{S}_{k}\) and \(\mathcal{P}_{k}\), and then formulate the sub-problem for updating \(\mathcal{B}_{k+1}\) such that \[\mathcal{B}_{k+1}=\arg\min_{\mathcal{B}_{k}}\frac{1}{2n_{3}}\|\mathcal{B}\|_ {F}^{2}+\mu\|\mathcal{A}_{k+1}*\mathcal{B}_{k}^{T}-\mathcal{Q}\|_{F}^{2}.\] (21) By taking the derivative of (21) with respect to \(\mathcal{B}_{k}\), and rearranging terms, we obtain the closed-form solution for \(\mathcal{B}_{k+1}\) such that \[\mathcal{B}_{k+1}=\mathcal{Q}*\mathcal{A}_{k+1}*(\frac{1}{n_{3}}\mathcal{I}+ \mu\mathcal{A}_{k+1}^{T}*\mathcal{A}_{k+1})^{-1}.\] (22)
3. Computation of \(\mathcal{S}\). The optimal sub-problem for updating \(\mathcal{S}_{k}\), while keeping the other terms in (17) fixed, is defined as follows: \[\mathcal{S}_{k+1}=\arg\min_{\mathcal{S}_{k}}\frac{\lambda}{\mu}||\mathcal{S}|| _{1}+\|\mathcal{S}_{k}-\mathcal{H}\|_{F}^{2},\] (23) where \(\mathcal{H}=\mathcal{X}-\mathcal{A}_{k+1}*\mathcal{B}_{k+1}^{T}-\mu^{-1} \mathcal{P}_{k}\). Since the second term in (23) is convex and differentiable, the closed-form solution of (23) can be obtained using the soft-thresholding operator \(D_{\tau}(x)\) defined as [24] \[D_{\tau}(\mathcal{X}_{i_{1},i_{2},i_{3}})=\begin{cases}\text{ sign}(\mathcal{X}_{i_{1},i_{2},i_{3}})(|\mathcal{X}_{i_{1},i_{2},i_{3}}|-\tau)&\text{if }|\mathcal{X}_{i_{1},i_{2},i_{3}}|>\tau,\\ 0&\text{if }|\mathcal{X}_{i_{1},i_{2},i_{3}}|\leq\tau,\end{cases}\] (24) where \(\mathcal{X}_{i_{1},i_{2},i_{3}}\) denotes the \((i_{1},i_{2},i_{3})-\)th element of \(\mathcal{X}\). Thus, the update for \(\mathcal{S}_{k+1}\) is obtained by applying soft-thresholding as \(\mathcal{S}_{k+1}=D_{\lambda/\mu}(\mathcal{H})\).  
The procedure for finding \(\mathcal{A}_{k},\mathcal{B}_{k}\) and \(\mathcal{S}_{k}\) is summarized in Algorithm 1. Before computing \(\mathcal{A}_{1},\mathcal{B}_{1}\), we initialize the factor tensors \(\mathcal{A}_{0}\) and \(\mathcal{B}_{0}\) by performing T-SVD of \(\mathcal{X}\) with truncation level \(r\), such that \(\mathcal{X}\approx\mathcal{A}_{0}*\mathcal{B}_{0}^{T}\).  
```
1:\(\mathcal{P}_{0}=0\)
2:\(\mathcal{A}_{0}=\mathcal{U}_{0}*\sqrt{\mathcal{C}_{0}}\) and \(\mathcal{B}_{0}=\mathcal{V}_{0}*\sqrt{\mathcal{C}_{0}}\), where \([\mathcal{U}_{0},\mathcal{C}_{0},\mathcal{V}_{0}]=\text{TT-SVD}(\mathcal{X},r)\)
3:for k = 1,2,...,do
4: Update \(\mathcal{A}_{k+1}\) via (20)
5: Update \(\mathcal{B}_{k+1}\) via (22)
6: Update \(\mathcal{S}_{k+1}\) via (23)
7:\(\mathcal{L}_{k+1}=\mathcal{A}_{k+1}*\mathcal{B}_{k+1}^{T}\)
8:\(\mathcal{P}_{k+1}=\mathcal{P}_{k}+\mu(\mathcal{L}_{k+1}+\mathcal{S}_{k+1}- \mathcal{X})\)
9:if\(\frac{\|\mathcal{L}_{k+1}-\mathcal{C}_{k}\|_{F}}{\|\mathcal{L}_{k}\|_{F}}\leq\epsilon\)then
10: break
11:endif
12:endfor
13:return\(\mathcal{L}_{k+1}\)
```  
**Algorithm 1**\(X_{k+1}=\mathbf{TRPCAAL}(\mathcal{X},r,\lambda,\mu,\epsilon)\)