# Image Completion with Hybrid Interpolation in Tensor Representation
## 3 Proposed Algorithm
```
Input :\(\mathcal{M}\in\mathbb{R}^{I_{1}\times\ldots\times I_{N}}\) - input tensor, \(\Omega=[\omega_{i_{1},\ldots,i_{N}}]\in\mathbb{R}^{I_{1}\times\ldots\times I_{ N}}\) - a binary tensor of indicators for the missing entries, \(d(\cdot,\cdot)\) - distance metrics, \(\tau\) - scaling factor, \(R=\{R_{1},\ldots,R_{N}\}\) - degrees of the interpolation polynomials, \(\{S_{1},\ldots,S_{N}\}\) - partitioning rates, \(\{\theta_{1},\ldots,\theta_{N}\}\) - rates of overlapping (in percentage). Output :\(\mathcal{Y}\in\mathbb{R}^{I_{1}\times\ldots\times I_{N}}\) - completed tensor
1 for\(n=1,\ldots,N\)do
2 Compute factor matrices \(\mathbf{F}^{(n)}\) using metrics \(d\), and \(\mathbf{P}^{(n)}\) using set \(R\). 3\(\mathbf{F}=\mathbf{F}^{(N)}\otimes\ldots\otimes\mathbf{F}^{(1)}\), \(\mathbf{P}=\mathbf{P}^{(N)}\otimes\ldots\otimes\mathbf{P}^{(1)}\),
4 foreach\((s_{1},\ldots,s_{N})\)do
5 Create \(\hat{\mathcal{Y}}\) from \(\mathcal{M}\) using (1), and select \(\hat{\mathcal{Y}}^{(s_{1},\ldots,s_{N})}=\left[y_{\Gamma(s_{1}),\ldots,\Gamma( s_{N})}\right]\in\mathbb{R}^{L_{1}\times\ldots\times L_{N}}\) from \(\hat{\mathcal{Y}}\) and \(\Omega^{(s_{1},\ldots,s_{N})}=\left[\omega_{\Gamma(s_{1}),\ldots,\Gamma(s_{N} )}\right]\in\mathbb{R}^{L_{1}\times\ldots\times L_{N}}\) from \(\Omega\), using rule (22),
6 Compute \(\mathbf{\omega}^{(s_{1},\ldots,s_{N})}=\operatorname{vec}(\Omega^{(s_{1},\ldots,s _{N})})\) and \(\mathbf{\omega}^{(s_{1},\ldots,s_{N})}=1-\mathbf{\omega}^{(s_{1},\ldots,s_{N})}\), and \(\mathbf{y}(\mathbf{\omega}^{(s_{1},\ldots,s_{N})})=\operatorname{vec}(\hat{\mathcal{Y }}^{(s_{1},\ldots,s_{N})})\),
7 Select \(\mathbf{F}(\mathbf{\omega}^{(s_{1},\ldots,s_{N})},\mathbf{\omega}^{(s_{1},\ldots,s_{N})}) \in\mathbb{R}^{\left[\Omega^{(s_{1},\ldots,s_{N})}\right]\times\left[\Omega^ {(s_{1},\ldots,s_{N})}\right]\) and \(\mathbf{F}(\mathbf{\omega}^{(s_{1},\ldots,s_{N})},\mathbf{\omega}^{(s_{1},\ldots,s_{N})}) \in\mathbb{R}^{\left[\Omega^{(s_{1},\ldots,s_{N})}\right]\times\left[\Omega^ {(s_{1},\ldots,s_{N})}\right]}\) from \(\mathbf{F}\), \(\mathbf{P}(\mathbf{\omega}^{(s_{1},\ldots,s_{N})}. )\in\mathbb{R}^{\left[\Omega^{(s_{1}, \ldots,s_{N})}\right]\times\prod_{n=1}^{N}R_{n}}\) from \(\mathbf{P}\),
8 Compute \(\mathbf{w}(\mathbf{\omega}^{(s_{1},\ldots,s_{N})})\) and \(\mathbf{c}\) solving system (19),
9 Given \(\mathbf{w}(\mathbf{\omega}^{(s_{1},\ldots,s_{N})})\) and \(\mathbf{c}\), compute \(\hat{\mathbf{y}}^{(s_{1},\ldots,s_{N})}\) from (20), and construct \(\mathcal{Y}^{(s_{1},\ldots,s_{N})}\) using (21). 10\(\mathcal{Y}=\left[\mathcal{Y}^{(s_{1},\ldots,s_{N})}\right]\in\mathbb{R}^{I_{1 }\times\ldots\times I_{N}}\). ```  
**Algorithm 1**Tensorial Interpolation for Image Completion (TI-IC)  
**Remark 2**. : _The computational complexity for calculating matrices \(\mathbf{F}\) and \(\mathbf{P}\) in Algorithm 1 amounts to \(\mathcal{O}\left(\prod_{n=1}^{N}I_{n}(I_{n}+R_{n})\right)\). Assuming Gaussian elimination is used for solving system (19), we have \(\mathcal{O}\left(S_{Y}(\left|\Omega^{(s_{1},\ldots,s_{N})}\right|+\prod_{n=1}^{ N}R_{n})^{3}\right)\) for \(S_{Y}\) subtensors, and \(\mathcal{O}(S_{Y}(\left|\tilde{\Omega}^{(s_{1},\ldots,s_{N})}\right|+\prod_{n=1} ^{N}R_{n})(\left|\Omega^{(s_{1},\ldots,s_{N})}\right|+\prod_{n=1}^{N}R_{n}))\) for computing \(\hat{\mathbf{y}}^{(s_{1},\ldots,s_{N})}\) from (20). Let \(\left|\Omega\right|=\xi\prod_{n=1}^{N}I_{n}\) and \(\forall(s_{1},\ldots,s_{N}):\left|\Omega^{(s_{1},\ldots,s_{N})}\right|=\xi \prod_{n=1}^{N}L_{n}\), where \(0\leq\xi\leq 1\). Neglecting matrix \(\mathbf{P}\) in (19) because it is much smaller than \(\mathbf{F}\), the computational complexity for solving system (19) can be roughly estimated as \(\mathcal{O}\left(S_{Y}(\left|\Omega^{(s_{1},\ldots,s_{N})}\right|)^{3}\right)= \mathcal{O}\left(S_{Y}\xi^{3}(\prod_{n=1}^{N}L_{n})^{3}\right)\approx\mathcal{O }\left(\xi^{3}\prod_{n=1}^{N}\frac{l_{n}^{3}}{S_{n}^{3}}\right)\).