Multi-Tensor Network Representation for High-Order Tensor Completion

The TN model represents a high-order tensor as the multilinear operation over a set of latent factors, and the number of factors is equivalent to the order of the tensor without considering the internal vertices. As illustrated in Fig.2, the difference among various TD models lies in the topological structure constructed by the connections among latent factors, e.g., the TR model [43] establishes a connection between the head and tail factors based on TT [42]. For the sake of clarity, we employ $\Psi$ to denote the TN model uniformly. Suppose that an $N$-order tensor $\boldsymbol{\mathcal{X}}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ is decomposed by $\Psi$ and we obtain $N$ factors $\boldsymbol{\mathcal{Z}}^{(k)}\in\mathbb{R}^{R_{1,k}\times\dots\times R_{k-1,k}\times I_{k}\times R_{k+1,k}\times\dots\times R_{N,k}}$ with $k\in[N]$. Hence, the rank of $\Psi$ can be naturally expressed as a matrix $\boldsymbol{R}_{\Psi}\in\mathbb{R}^{(N-1)\times(N-1)}$, which is

where $R_{i,j}$ represents the dimension of common mode between $\boldsymbol{\mathcal{Z}}^{(i)}$ and $\boldsymbol{\mathcal{Z}}^{(j)}$. We call it edge rank and it satisfies $R_{i,j}=R_{j,i}$($1\leq i<j\leq N,i,j\in\mathbb{N}_{+}$). The element-wise form of $\Psi$ decomposition can be expressed as

where $\Re$ denotes tensor contraction operation and $\Re(\boldsymbol{\mathcal{Z}}^{(1)},\cdots,\boldsymbol{\mathcal{Z}}^{(N)})$ indicates the recovered tensor generated by factors. Then we introduce the new definition as follows:

The calculation of $\Re$ in (5) can be completed with $N-1$ times matrix multiplication because the mode-n matricization of $\boldsymbol{\mathcal{X}}$ can be written as

where $\boldsymbol{\mathcal{Z}}^{(\neq n)}=\Re(\{\boldsymbol{\mathcal{Z}}^{(k)}\}_{{}^{k=1}_{k\neq n}}^{N})$ is an $N$-order tensor of size $I_{1}\times\cdots\times I_{n-1}\times I_{n+1}\times\cdots\times I_{N}\times R_{1,n}\cdots R_{n-1,n}R_{n,n+1}\cdots R_{n,N}$, obtained by contracting the subnetwork of $\Psi$ composed of N-1 factors except $\boldsymbol{\mathcal{Z}}^{(n)}$. Similarly, the $\boldsymbol{\mathcal{Z}}^{(\neq\{m,n\})},\boldsymbol{\mathcal{Z}}^{(\leq m)}$, and $\boldsymbol{\mathcal{Z}}^{(>m)}$ are defined as $\Re(\{\boldsymbol{\mathcal{Z}}^{(k)}\}_{{}^{k=1}_{k\neq m,n}}^{N}),\Re(\{\boldsymbol{\mathcal{Z}}^{(k)}\}_{{k=1}}^{m})$, and $\Re(\{\boldsymbol{\mathcal{Z}}^{(k)}\}_{{k=m+1}}^{N})$, respectively.

Note that the TN representation (5) does not demand a concrete topology strictly, and $\Psi$ conceptually generalizes a family of TD models, including TT and TR representation. This unified representation gives us the chance to learn adaptive decomposition topologies for various data. Another tensor form of $\Psi$ decomposition can be formulated as

where $\boldsymbol{z}^{(k)}(r_{1,k},\cdots,r_{k-1,k},r_{k,k+1},\cdots,r_{k,N})\in\mathbb{R}^{I_{k}}$ denote $\overline{r_{1,k}\cdots r_{k-1,k}r_{k,k+1}\cdots r_{k,N}}$th mode-$k$ fiber of factor $\boldsymbol{\mathcal{Z}}^{(k)}$. Then the reconstructed tensors $\boldsymbol{\mathcal{X}}$ can be expressed as the superposition of the rank-1 tensors. In general, TN representation with arbitrary topology is essentially an undirected graph composed of several vertices and edges, and exist a bijective with the simple graph [48]. If condition $R_{i,j}>1,1\leq i<j\leq N$ is satisfied, then the TN representation of $\Psi$ can be regard as a complete graph, as illustrated graphically in Fig.2(f).

Since the topology of the $\Psi$ is not strictly limited. For the TN representation with $N$ factors, there exist $2^{\frac{N(N-1)}{2}}$ kind of topology when taking no account of the edge rank magnitude, from the $null\ graph$ (e.g., TN representation with $N$ isolated vertices) to a fully connected $complete\ graph$. Hence, the selection of TD models can also be viewed as a topology searching process, which is a discrete optimization problem analogous to the layer-wise architecture search in convolutional neural networks [50]. From (5), we can observe that the edge rank determines the topology and complexity of $\Psi$. Supposing that all the elements in $R_{\Psi}$ are equal to $R$ and $I_{1}=\cdots=I_{N}=I$, then the number of parameters requires of $\Psi$ decomposition is $\mathcal{O}(NIR^{N-1})$ and the computational complexity of operation $\Re$ is $\mathcal{O}(\sum_{k=2}^{N}I^{k}R^{k(N-k)+k-1})$. However, such storage complexity increases exponentially with the tensor order $N$ and the contraction is computationally too expensive for large-scale data. In order to solve this problem, we set the maximum connections of each latent factor as $t$, where $t\in\mathbb{N}^{+}$ is a constant and satisfies $1\leq t<<N$. The existence of $t$ decreases the degree of freedom of feasible topology and contraction complexity. Thus, the $\Psi$ decomposition required parameters are $\mathcal{O}(NIR^{t})$, which is linear with the tensor order, and this property reduces the complexity of calculation and storage significantly.

The relationship of the rank of $\Psi$ and multilinear rank is established in the following theorem.

As a side note, the generalized TN representation defined in this section prohibits the existence of internal factors (e.g., the cores tensor in Tucker decomposition) since they can be eliminated by tensor renormalization group (TRG) [61] algorithm or tensor contraction strategies. For instance, an efficient TR decomposition algorithm is proposed in [62] base on Tucker compression.

Based on subspace clustering [55] theory, high-dimensional data can be regarded as the combination of low-rank components from different subspaces. As such, an $N$-order tensors $\boldsymbol{\mathcal{X}}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ can be represented by an addition of multiple components as

where $\boldsymbol{\mathcal{A}}_{i}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ represents the $i$th low-rank component for $i=1,\cdots,r$. We can observe that if each component $A_{i}$ is a rank-1 tensor, then (9) is equivalent to CP decomposition and $r$ is just CP-rank.

Most of the high-dimensional data are complicated and mode-interrelated. The TD model with simple topology (e.g., ring-shaped TR) to capture the intrinsic low-rank structure inside the data and only require linear storage complexity [43]. However, the connections involved in topology only exist in the adjacent factors, leading to exponential correlation decay and expecting a larger rank to capture more global features. On the contrary, the TD model with complex topology can achieve better results, e.g., FCTN [46], but the storage and computational complexity are exponential with the order of the data. In order to better weigh the representation capability and complexity of TN models. As shown in Fig.3, MTNR aims to discover TN topologies from data and manipulate multiple TD models with different topologies to decompose components separately, which is critical compared with other TD models. Then, (9) can be rewritten as

where $\Psi_{i}$ represents the $i$th TD models with a simple topological structure for $i=1,\cdots,r$, and the corresponding latent factor $\{\boldsymbol{\mathcal{Z}}^{(k)}_{i}\}_{k=1}^{N}$ is obtained via $\Psi_{i}(\boldsymbol{\mathcal{A}}_{i})$. From (10), we see that MTNR can be considered as a combination of multiple TD models, which provides MTNR with more compelling representation and generalization capabilities. The amount of parameters for MTNR is $\mathcal{O}(rNIR^{t})$, which is linear to the tensor order. Note that the structure of each TN model in MTNR is data-adaptive to better capture the low-rank structure and reduce approximation deviation. Besides, the combination of multiple identical TD models retains the properties of a single one, such as inverse permutation invariance in TT, and circular dimensional permutation invariance in TR.

A key problem of low-rank approximation based on TN representation is to search adaptive topology for various complicated and mode-imbalanced data. Existing data-driven approaches are difficult for data with different orders and sizes (such as neural architecture search and reinforcement learning). In this part, we present a novel efficient adaptive topology learning (ATL) algorithm for MTNR.

The main objective of ATL is to obtain a low-rank approximation of data with less storage resources. Given an $N$-order tensor $\boldsymbol{\mathcal{X}}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ and relative error $\epsilon$, the optimization problems of MTNR can be formulated as

Here $\mathcal{P}(\cdot)$ denotes storage cost function and $\gamma_{i}$ is the predefined upper bound of the $i$th low-rank component representation. In fact, instead of specifying the number of components $r$, we choose to sequentially optimize each low-rank component to fit the current residual estimation, which can reduce the complexity of the topological search and obtain more stable outcomes. To solve the optimization problem of each low-rank component is based on the following two strategies.

1) Rank incremental strategy. The rank incremental strategy [44, 51] suggests that tensors with TN representation starts from the rank-1 tensor, successively selects a factor pair and increases its corresponding edge rank to greatly reduce approximate error. The topology and ranks obtained in this manner have better data adaptability. Specifically, for the $k$th low-rank component, $\boldsymbol{\mathcal{A}}_{k}=\Re(\boldsymbol{\mathcal{Z}}^{(1)}_{k},\cdots,\boldsymbol{\mathcal{Z}}^{(N)}_{k})$, the corresponding optimization problem can be derived from (11) as

where $\boldsymbol{\mathcal{T}}=\boldsymbol{\mathcal{X}}-\sum_{i=1}^{k-1}\Re(\boldsymbol{\mathcal{Z}}^{(1)}_{i},\cdots,\boldsymbol{\mathcal{Z}}^{(N)}_{i})$ represents residual estimation tensor. The (12) includes $N$ inter-coupled variables, so the well-known ALS [43] scheme or gradient descent algorithm [63] can be exploited to obtain the numerical solution. The principle of the ALS scheme is to update each variable sequentially while fixing the others until all the variables satisfy the convergence criterion. Then the subproblem w.r.t.the $n$th factor variable $\boldsymbol{\mathcal{Z}}^{(n)}_{k}\in\mathbb{R}^{R_{n,1}^{k}\times\dots R_{n,n-1}^{k}\times I_{n}\times R_{n,n+1}^{k}\dots\times R_{n,N}^{k}}$ can be expressed in a mode-$n$ matrix form as

which is a least-square optimization problem and has a closed-form solution

All factors $\{\boldsymbol{\mathcal{Z}}^{(1)}_{k},\cdots,\boldsymbol{\mathcal{Z}}^{(N)}_{k}\}$ are circulantly updated until satisfy $\frac{||\boldsymbol{\mathcal{A}}_{k}^{S+1}-\boldsymbol{\mathcal{A}}_{k}^{S}||_{F}}{\boldsymbol{\mathcal{A}}_{k}^{S}}\leq\delta$, where $S$ is current iteration number and $\delta$ is a specific error level. In this context, we will identify a promising factor pair and increase its corresponding edge rank according to the following projection error measurement strategy if the complexity restraints are satisfied.

2) Projection error measurement strategy. The residual tensor $\boldsymbol{\mathcal{T}}$ of size $I_{1}\times\cdots\times I_{N}$ is approximated by the $k$th low-rank component $\boldsymbol{\mathcal{A}}_{k}$, with TN representation $\Re(\boldsymbol{\mathcal{Z}}^{(1)}_{k},\cdots,\boldsymbol{\mathcal{Z}}^{(N)}_{k})$, where $\boldsymbol{\mathcal{Z}}^{(i)}_{k}\in\mathbb{R}^{R_{i,1}^{k}\times\dots R_{i,i-1}^{k}\times I_{i}\times\dots\times R_{i,N}^{k}}$. Since the correlation within different modes of the reconstructed tensor is established through the connection within the factors, we can increase the edge rank $R_{i,j}^{k}$ to improve the correlation between the $i$ and $j$ modes of $\boldsymbol{\mathcal{A}}_{k}$. Each selection for an $N$-order tensor produces $\frac{N(N-1)}{2}$ cases. A simple technique is greedy search [44], which uses brute-force search to test all options and for each trial it requires several additional iterations to return the most promising edges to improve the model performance. However, that is too computationally expensive. Inspired by [51], we propose an improved projection error measurement strategy for identifying the optimal factor pair. For $i,j\in\mathbb{N}^{+}$ satisfies $1\leq i<j\leq N$, consider the following problem

where $\boldsymbol{E}_{(i,j)}$ of size ${I_{i}I_{j}\times\prod_{k\neq i,j}I_{k}}$ denotes the mode-$(i,j)$ matricization of the approximation error tensor $\boldsymbol{\mathcal{T}}-\boldsymbol{\mathcal{A}}_{k}$ , and $W_{i,j}$ is viewed as the error projection matrix on the factors $\boldsymbol{Z}^{(i)}_{k}$ and $\boldsymbol{Z}^{(j)}_{k}$, computed by $W_{i,j}=(\boldsymbol{Z}^{(\{i,j\})}_{k\left\langle 2\right\rangle})^{\dagger}\boldsymbol{E}_{\left\langle i,j\right\rangle}$. We use the $w_{i,j}={||W_{i,j}||_{F}}$, which we called projection error measurement, to evaluate the importance or sensitivity of the factors pair $(\boldsymbol{Z}^{(i)}_{k},\boldsymbol{Z}^{(j)}_{k})$. In each iteration, the order of factors is updated randomly to evade the influence of mode arrangement. In section V, we demonstrate $w$ can effectively measure the importance of the local topology of the TN representation. Moreover, we set three conditions to guarantee the effectiveness of the selection process.

The above conditions are used to ensure the diversity and feasibility of the TD topologies generated by ATL. In addition, these topologies are robust to the arrangement of data modes. Overall, we will continuously collect the low-rank components until the stop criterion $||\boldsymbol{\mathcal{X}}-\sum_{i=1}^{r}\boldsymbol{\mathcal{A}}_{i}||_{F}\leq\epsilon||\boldsymbol{\mathcal{X}}||_{F}$ holds. Algorithm 1 summarizes the whole learning process of MTNR in detail. The significance of the low-rank components obtained by MTNR is decreasing gradually, and the corresponding TN topology is expected to seek the optimal one under the current structure error. In this way, MTNR is prone to form multiple TN models with different topologies with linear parameters.

An interesting conjecture is whether it is possible to perform multilinear operations in a latent factor space instead of a multilinear space for tensors with TN representation. This section gives the affirmative answer and theoretically establishes basic algebra operations, including multilinear, Hadamard, outer, inner, Kronecker, and mode-n Khatri-Rao products and addition operation. These properties allow us to process large-scale data with linear storage cost and significantly reduce the computational complexity. In [42, 43], the authors establish basic multilinear operations for the tensors with TT and TR format, and here we further extend it to a generalized scenario and thus we have the following propositions.

The multilinear product is performed on each factor and its result is also given in a TN format. For instance, if the number of connections of each factor is no more than $t$, then the computational complexity of (16) and (17) is equivalent to $\mathcal{O}(IR^{t}J)$ and $\mathcal{O}(NIR^{t})$, respectively.