Tucker-O-Minus Decomposition for Multi-view Tensor Subspace Clustering

We give a brief introduction about notations and preliminaries in this section. Throughout this paper, we use lower case letters, bold lower case letters, bold upper case letters, and calligraphic letters to denote scalars, vectors, matrices and tensors, respectively, e.g., $a$, $\mathbf{a}$, $\mathbf{A}$ and $\mathcal{A}$. Some other frequently used notations are listed in Table 1, where $\mathcal{A}$ is a 3rd-order tensor and $\mathbf{A}$ is a matrix.

This section reviews some closely related works, including low-rank approximation based multi-view subspace clustering, and multi-view graph clustering.

Given a 4th-order tensor $\mathcal{X}\in\mathbb{R}^{I_{1}\times I_{2}\times I_{3}\times I_{4}}$, the mathematical formulation of the TOMD is as follows:

where $\{D_{1},\cdots,D_{6}\}$ are geometrical indexes, each of which is shared two tensors and should be contracted. $\mathbf{U}^{(i)}\in\mathbb{R}^{I_{i}\times R_{i}}(i=1,\cdots,4)$ are factor matrices, $\mathcal{G}^{(n)}$, $n=1,\cdots,5$, are the factor tensors. Specifically, $\mathcal{G}^{(1)}\in\mathbb{R}^{D_{4}\times R_{1}\times D_{1}\times D_{5}}$, $\mathcal{G}^{(2)}\in\mathbb{R}^{D_{1}\times R_{2}\times D_{2}}$, $\mathcal{G}^{(3)}\in\mathbb{R}^{D_{2}\times R_{3}\times D_{3}\times D_{6}}$, $\mathcal{G}^{(4)}\in\mathbb{R}^{D_{3}\times R_{4}\times D_{4}}$, and $\mathbf{G}^{(5)}\in\mathbb{R}^{D_{5}\times D_{6}}$. $[R_{1},\cdots,R_{4},D_{1},\cdots,D_{6}]^{\text{T}}$ is denoted as the rank of TOMD.

From the graphical illustration of TOMD in Fig. 1, it can be clearly seen that the overall architecture of our proposed tensor network is relatively compact and balanced. In this way, based on the Tucker format, O-minus structure is further applied to enhance the relationships among the adjacent and non-adjacent modes of $\mathcal{X}$, simultaneously. In addition, the computational complexity of tensor network contraction can be controlled.

To compute the Tucker-O-Minus decomposition, we employ the alternation least squares (ALS) algorithm, which has been widely used for CPD, Tucker decomposition and TR decomposition [4, 23, 57]. Supposing that we have a 4th-order tensor $\mathcal{X}\in\mathbb{R}^{I_{1}\times I_{2}\times I_{3}\times I_{4}}$, the optimization model for approximation a tensor $\mathcal{X}$ by the proposed TOMD can be formulated as follows:

From Fig. 1, Theorem 1 and Theorem 2, the optimization problem (6) can be changed into a few subproblems by alternating least squares method. In detail, fixing all but one factor, the problem can reduce to three least-squares problems:

1. 1.

   Subproblem with respect to $\mathbf{U}^{(n)}(n=1,\cdots,4)$:

   $$\min\limits_{\mathbf{U}^{(n)}}\|\mathbf{X}_{(n)}-\mathbf{U}^{(n)}(\mathbf{A}_{(n)})\|_{\text{F}}.$$

   (7)

2. 2.

   Subproblem with respect to $\mathcal{G}^{(n)}(n=1,\cdots,4)$:

   $$\min\limits_{\mathbf{G}_{(2)}^{(n)}}\|\mathbf{X}_{(n)}-\mathbf{U}^{(n)}(\mathbf{G}_{(2)}^{(n)})(\mathbf{A}^{\neq n})\|_{\text{F}}.$$

   (8)

3. 3.

   Subproblem with respect to $\mathcal{G}^{(5)}$:

   $$\min\limits_{\mathbf{g}^{(5)}}\|\mathbf{x}-(\mathbf{g}^{(5)})\tilde{\mathbf{A}}_{\langle 2\rangle}\|_{\text{F}}.$$

   (9)

Moreover, 9 factors (i.e., $\{\mathcal{G}^{(n)}\}_{n=1}^{5},\{{\mathbf{U}}^{(n)}\}_{n=1}^{4}$) can be initialized using the randomization method or truncated SVD with specific values of ranks. In our experiments, we choose the latter way to initialize all factors, and the stopping condition is $\|\mathcal{X}_{\text{last}}-\mathcal{X}_{\text{new}}\|_{\text{F}}/\|\mathcal{X}_{\text{last}}\|_{\text{F}}\leq\text{tol}_{\text{als}},$ where $\mathcal{X}_{\text{last}}$ is the value at the last iteration, $\mathcal{X}_{\text{new}}$ is constructed from the new iteration, and $\text{tol}_{\text{als}}$ is a predefined threshold.

By denoting $\Phi({\cdot,\mathbf{s}})$ as an operator that reshapes a tensor using the size vector $\mathbf{s}$, the overall procedure of TOMD-ALS algorithm can be found in Algorithm 1.

To better exploit the low rank data structure in multi-view clustering, we apply the proposed TOMD to the optimization model for clustering. Given a dataset that has $V$ views $\left\{\mathbf{X}_{v}\in\mathbb{R}^{C_{v}\times N}\right\}$ $,v=1,\cdots,V$, where $C_{v}$ is the feature dimension of the $v$-th feature and $N$ is the number of data samples in each view. The proposed optimization model based on TOMD for multi-view cluster (TOMD-MVC) can be formulated as follows:

where $\{\mathcal{G}^{(n)}\}_{n=1}^{5}$ are tensor factors, and $\mathbf{L}$ is the graph Laplacian matrix of $\mathbf{M}$. $\mathbf{E}=\left[\mathbf{E}_{1};\mathbf{E}_{2};\cdots;\mathbf{E}_{V}\right]$ makes all the error matrices $\{\mathbf{E}_{v}\}$ $(v=1,\cdots,V)$ vertically connected along the columns, and function $\operatorname{\Omega}(\cdot)$ constructs the matrices $\{\mathbf{Z}_{v}\}(v=1,\cdots,V)$ into a 3rd-order tensor. Apart from that, $\mu$ and $\lambda$ are positive penalty scalars.

After obtaining the affinity matrix $\mathbf{M}$, K-means [11], spectral clustering [34] and other clustering methods can be utilized to yield the final clustering results.

The optimization problem (10) can be solved by ADMM. Since variable $\mathcal{Z}$ has appeared in the objective function and three constraints simultaneously, we introduce an extra variable $\mathcal{S}$ to make $\mathcal{Z}$ separable, which result in the equivalence of (10) as follows:

The augmented Lagrangian function of optimization model (11) is

where $\mathcal{W}$ and $\mathcal{Y}$ are Lagrangian multipliers corresponding to two equations, $\langle\cdot,\cdot\rangle$ denotes the inner product, and $\tau$ is the penalty parameter. ADMM alternately updates each variable as follows.

Solving $\mathcal{Z}$-subproblem: With the other variables fixed but let $\mathcal{Z}$ be the optimization variable, (11) becomes

where $t$ is the number of iteration. This problem can be solved by TOMD-ALS to obtain the factors $\tilde{\mathcal{G}}^{(i)}(i=1,\cdots,5)$ and $\tilde{\mathbf{U}}^{(i)}(i=1,\cdots,4)$ of tensor $(\mathcal{S}^{t}-\frac{\mathcal{Y}^{t}}{\tau^{t}})$. Accordingly, the $\mathcal{Z}$-subproblem has following solution:

Solving $\mathcal{S}$-subproblem: Similarly, letting $\mathcal{S}$ be the only variable, (11) becomes

By separating above problem into $V$ subproblems, each of which can be solved by:

Solving $\mathbf{E}$-subproblem: The optimization subproblem with respect to $\mathbf{E}$ is:

Let $\mathbf{H}_{v}^{t}=\mathbf{X}_{v}-\mathbf{X}_{v}\mathbf{S}_{v}^{t+1}+\frac{\mathbf{W}_{v}^{t}}{\tau^{t}}$, then $\mathbf{H}^{t}$ is constructed by vertically concatenating the matrices $\left\{\mathbf{H}_{v}\right\},v=1,\cdots,V$. As it is suggested in [26], (17) has a closed-form solution:

where $\mathbf{H}_{i}^{t}$ and $\mathbf{E}_{i}^{t+1}$ denote the $i$-th column of $\mathbf{H}^{t}$ and $\mathbf{E}^{t+1}$, respectively.

Solving $\mathbf{M}$-subproblem: The optimization subproblem with respect to $\mathbf{M}$ is:

According to  (3) and  (4),  (19) can be divided into $i$ subproblems:

where $\mathbf{M}_{i}$ is the $i$-th column of matrix $\mathbf{M}$ and $(\mathbf{S}_{i})_{v}$ is the $i$-th column of matrix $\mathbf{S}_{v}$. Following [17, 7] that apply the adaptive neighbor scheme to keep $K$ largest values constant in $\mathbf{M}_{i}$ and the rest become zero, each subproblem has the solution:

where $p_{i,j}=\sum_{v=1}^{V}\|(\mathbf{s}_{i}^{l+1})_{v}-(\mathbf{s}_{j}^{l+1})_{v}\|_{2}^{2}$ and $\mathbf{p}_{i}\in\mathbb{R}^{N\times 1}$.

Updating $\mathcal{W}$, $\mathcal{Y}$ and $\tau$: By keeping other variables, i.e., $\mathcal{Z}$, $\mathcal{S}$ and $\mathbf{E}$ are fixed, the Lagrangian multipliers $\mathcal{W},\mathcal{Y}$ and the penalty parameter $\tau$ are updated as follows:

where $\beta>1$ is utilized to accelerate the convergence, and $\tau_{\text{max}}$ is the predefined maximum value of $\tau$. The affinity matrix $\mathbf{M}$, which will be put into spectral clustering algorithm to yield the final clustering results, can be calculated by $\mathbf{M}=1/V\sum_{v=1}^{V}(|\mathbf{Z}_{v}|+|\mathbf{Z}_{v}^{\mathrm{T}}|).$

To analyze the computation complexity of TOMD-MVC, we assume that $R=R_{1}=\cdots=R_{4}=D_{1}=\cdots=D_{6}$ for convenience of analysis. At each iteration, it takes $\mathcal{O}\left(IN_{1}N_{2}N_{3}VR^{4}\right)$ to update the reshaped tensor $\mathcal{Z}\in\mathbb{R}^{N_{1}\times N_{2}\times N_{3}\times V}$, where $I$ denotes number of iterations of TOMD-ALS. For $\mathcal{S}$-subproblem, we need $\mathcal{O}\left(VN^{3}\right)$ to compute its closed-form. Updating $\mathbf{E}$ and $\mathbf{M}$ cost $\mathcal{O}\left(VN^{2}\right)$ and $\mathcal{O}\left(N^{2}\right)$, respectively. Therefore, the computation in each iteration is $\mathcal{O}\left(V(IN_{1}N_{2}N_{3}R^{4}+N^{3}+N^{2})+N^{2}\right)$.

In addition, after we get the affinity matrix, we adopt the spectral clustering method to obtain the final memberships of data. Considering the spectral clustering’s computational complexity is $\mathcal{O}\left(N^{3}\right)$ [45], the overall complexity is $\mathcal{O}\left(TV(IN_{1}N_{2}N_{3}R^{4}+N^{3}+N^{2})+LN^{2}+N^{3}\right)$, where $T$ is the iteration number of TOMD-MVC.

To illustrate the superiority of our proposed tensor network, we conduct the image reconstruction experiments on several real word images¹¹1http://sipi.usc.edu/database/database.php?volume=misc: ”House”, ”Peppers”, ”Airplane (F-16)”, ”Sailboat on lake”, and ”Airplane”. Since the TOMD has been utilized for 4th-order tensors, the gray forms of these images are further transformed into $16\times 16\times 16\times 16$ tensors.

In this section, the tensors are performed by Tucker-ALS, Tucker and tensor ring decomposition ALS (TuTR-ALS), O-Minus-ALS (Ominus-ALS) and TOMD-ALS algorithms with the same Relative standard error (RSE) [52]. Beyond that, the storage costs of the different decomposition have been calculated and presented in Table 2. In addition to the time needed for pre-processing the images, reconstructing the images, and calculating the storage costs, the running time in our experiments only contains the main body in decomposition, which is also illustrated in Table 2. Considering that the speed of the iterative algorithm primarily affects the running time of those methods, we set the number of iterations for all methods to 500 in our experiment.

As results shown in Table 2, under the same conditions, we can conclude that the running time of TOMD is in the middle, but it has the lowest storage cost and can better exploit the low rank information compared to the other decompositions.