# Low Tensor Rank Constrained Image Inpainting Using a Novel Arrangement Scheme
## 3 Methods
### Method 3: The Low TT Rank-Based Method  
TT decomposition works better on higher-order tensors than Tucker decomposition. To fulfill TT decomposition efficiently, the third flexible QA scheme is exploited to permute the 3-order image into a higher-order tensor. Based on the basic QA scheme, high-order tensors can be obtained flexibly. The third flexible QA scheme is shown below. Take a \(16\times 16\) matrix as an example, as shown in Figure 4a. First, a 2-order matrix is turned into a 3D tensor via the basic QA scheme, and the basic QA is repeated to obtain the final 4D tensor with the size of \(4\times 4\times 4\times 4\). The entry comes from the ith smaller matrix of the first basic QA scheme, and the jth smaller matrix of the second basic QA scheme is labeled as the MATLAB notation \((.;.,i,j)\). By analogy, the third flexible QA scheme can permute a matrix with the size of \(4^{P}\times 4^{Q}\) to order-min\(\{P,Q\}\) tensor with the size of \(\underbrace{4\times 4\times\cdots\times 4}_{\min\{P,Q\}}\). An RGB image with the size of \(4^{P}\times 4^{Q}\times 3\) can be permuted into an order-min\(\{P,Q\}+1\) tensor with the size of \(\underbrace{4\times 4\times\cdots\times 4\times 3}_{1+\min\{P,Q\}}\). The third flexible QA scheme should ensure that the designed tensor has a higher order. Figure 4: (**a**) Examples of the third flexible QA scheme. Using the third flexible QA, the matrix size of \(16\times 16\) can be permuted into an order-4 tensor size of \(4\times 4\times 4\times 4\). (**b**) Singular values of TT matrices. We permute the order-3 Lena RGB image size of \(256\times 256\times 3\) into an 8-order tensor with the size of \(4\times 4\times 4\times 4\times 4\times 4\times 4\times 4\times 3\) by the third flexible QA scheme. Then, eight different TT matrices are obtained from this higher-order tensor. We labeled those TT matrices as k = 1, 2, \(\ldots\), 8. We permute the Lena image into a high-order tensor via the third flexible QA scheme, and then obtain the TT matrices of the augmented tensor. We name these TT matrices as QA-TT matrices, and their singular values are shown in Figure 4b, which demonstrates the low TT rankness of the rearranged tensor. Then, we enforce the low TT rankness to improve the inpainting accuracy. The third model is as follows:  
\[\min_{X}\sum_{n=1}^{N}\alpha_{n}\|\mathcal{T}_{n}\Phi_{3}X\|_{*}\;\text{{ subject to}}\;\;X(i,\,j)=Y(i,\,j),\;\forall(i,\,j)\in\Omega \tag{14}\]  
where \(\Phi_{3}\) stands for the third flexible QA used to permute image \(X\) into a high-dimensional tensor. We name the tensor obtained by the third flexible QA scheme as a QA tensor. \(\mathcal{T}_{n}\) is the operator that converts a tensor into the \(n^{th}\) TT matrix, \(n=1,\,2,\,\cdots,\,N\). The order of QA tensor is \(N\). The inverse operators corresponding to \(\Phi\) and \(\mathcal{T}_{n}\) are \(\Phi^{-1}\) and \(\mathcal{T}_{n}^{-1}\), respectively. The weight \(\alpha_{n}\) is as follows:  
\[\alpha_{n}=\frac{\theta_{n}}{\sum_{n=1}^{N-1}\theta_{n}}\text{with }\theta_{n}=\min(\prod_{l=1}^{n}l_{l},\prod_{l=k+1}^{N}l_{l}) \tag{15}\]  
where \(I_{1}\times I_{2}\times\cdots\times I_{N}\) is the size of the QA tensor. Combining the low TT rank and sparsity constraints, we introduce auxiliary variables \(Z=DX\) and \(U_{n}V_{n}^{H}=\mathcal{T}_{n}\Phi_{3}X\) and rewrite (14) as the following unconstrained convex optimization problem for all \(n=1,\,\,\cdots,N-1\):  
\[ \begin{array}{l}\min_{U_{n}V_{n}\Delta_{n}L,Z,X}\tau_{\Omega}(X)+\frac{1}{2} \sum\limits_{n=1}^{N-1}\alpha_{n}\left(\|U_{n}\|_{F}^{2}+\|V_{n}\|_{F}^{2} \right)+\frac{\beta}{2}\|Z\|_{1}\\ +\frac{\rho_{1}}{2}\sum\limits_{n=1}^{N-1}\alpha_{n}\left\|\mathcal{T}_{n} \Phi_{3}X-U_{n}V_{n}^{H}+\Lambda_{n}\right\|_{F}^{2}\big{)}+\frac{\beta\rho_{ 2}}{2}\|DX-Z+L\|_{F}^{2}\end{array}  \tag{16}\]  
By applying ADMM, each sub-problem is performed at each iteration \(t\). Lastly, we obtain \(X\) by \(X^{*}=\sum_{n=1}^{N-1}\alpha_{n}X_{n}^{*}\), where \(X_{n}^{*}\) represents the optimal solution of the nth sub-problem.