# On the Synergy between Nonconvex Extensions of the Tensor Nuclear Norm for Tensor Recovery
## 2 Low-Rank Tensor Completion  
In what follows, \(\mathbb{N}\), \(\mathbb{R}\), and \(\mathbb{R}_{+}\) denote the set of all nonnegative integers, all real numbers, and all nonnegative real numbers. We use capital calligraphic letters for tensors, capital bold letters for matrices, and lowercase bold letters for column vectors. In this paper, we assume that an observation model of tensor recovery can be described as  
\[\mathcal{Y}=\mathrm{A}_{\Omega}(\mathcal{X}_{\mathrm{org}}+\mathcal{V}), \tag{1}\]  
where \(\mathcal{Y}\in\mathbb{R}^{n_{1}\times\cdots\times n_{N}}\), \(\mathcal{X}_{\mathrm{org}}\in\mathbb{R}^{n_{1}\times\cdots\times n_{N}}\), and \(\mathcal{V}\in\mathbb{R}^{n_{1}\times\cdots\times n_{N}}\) are an \(N\)th order observation tensor, an \(N\)th order low-rank original tensor, and an \(N\)th order random tensor, respectively, whose entries are independent and identically distributed Gaussian variables with zero mean and known variance \(\sigma_{\eta}^{2}\). The degradation operator is defined as  
\[\mathrm{A}_{\Omega}(\mathcal{X})_{i_{1},\cdots,i_{N}}=\left\{ \begin{array}{ll} \mathcal{X}_{i_{1},\cdots,i_{N}}&(i_{1},\cdots,i_{N}\in\Omega)\\ 0&(\text{otherwise})\end{array} \right., \tag{2}\]  
where \(\Omega\) is a set of indicators of observable entries. If we can assume that the original tensor is low rank, it can be estimated by finding a tensor that is close to the observation tensor and also low rank. In particular, assuming that the rank of the original tensor is known and that the variance of the noise is 0, estimating the original tensor is the problem of finding a tensor whose rank is identical to the rank of the original tensor and whose known elements match the observation tensor, i.e., finding a tensor within the following set:  
\[\text{Find }\mathcal{X}\in\mathbb{R}^{n_{1}\times\cdots\times n_{N}}\quad \text{s.t. }\mathrm{A}_{\Omega}(\mathcal{X})=\mathrm{A}_{\Omega}(\mathcal{Y}),\text{ rank}_{m}(\mathcal{X})=\hat{r}_{m} \tag{3}\]  
where \(\text{rank}_{m}(\mathcal{X})=\text{rank}(\text{unfold}_{m}(\mathcal{X}))\) and \(m=1,\cdots,N\). We denote rank as the matrix rank and \(\hat{r}_{m}\) as the matrix rank of an \(m\)th mode unfolded original tensor. However, in general, the set containing the equations for the ranks, as in Equation (3), is hard to determine. Thus, we employ an alternative set with an inequality constraint instead of Equation (3):  
\[\text{Find }\mathcal{X}\in\mathbb{R}^{n_{1}\times\cdots\times n_{N}}\quad \text{s.t. }\mathrm{A}_{\Omega}(\mathcal{X})=\mathrm{A}_{\Omega}(\mathcal{Y}),\text{ rank}_{m}(\mathcal{X})\leq\hat{r}_{m}, \tag{4}\]  
The sets shown in Equations (3) and (4) are used directly for the estimation of the original tensor because they generally contain multiple matrices. Additionally, if the observation process includes noise (\(\sigma_{N}\
eq 0\)), it may yield the empty set. Thus, we employ the L2 norm between the observation tensor, which corresponds to the negative log-likelihood of the Gaussian distribution, and the solution of the following minimization problem, including this norm as the estimated tensor:  
\[\min_{\mathcal{X}\in\mathbb{R}^{n_{1}\times\cdots\times n_{N}}}\|\mathrm{A}_{ \Omega}(\mathcal{X})-\mathcal{Y}\|_{2}^{2}\quad\text{s.t.}\ \text{rank}_{m}(\mathcal{X})\leq\hat{r}_{m}(m=1, \cdots,N), \tag{5}\]  
where \(\|\cdot\|_{2}\) is an \(\ell_{2}\) norm of the tensor that is defined as the square root of the sum of the squares of each element of the tensor. Although this problem is one of nonconvex optimization, we can efficiently solve it by using the alternating direction method of multipliers (ADMM) [21], which is known as an algorithm for solving convex optimization problems and is effective in practice for solving nonconvex optimization problems [22; 23; 24]. A detail of an algorithm to solve Equation (5) explains in Appendix A.  
Equations (3) and (5) include the matrix rank of each unfolded tensor, which is very difficult to handle since it is not only nonconvex but also discontinuous.