# Tensioned Multi-View Ordered Kernel Subspace Clustering
## 3 The Proposed TMOKSC Algorithm
### The Optimization Algorithm
#### 3.2.3 Solve \(K^{(v)}\)  
During the process, we will show how to complete the missing samples.  
\[\begin{split} K^{(v)}=argmin\Big{(}& T\Big{(}K^{(v)} \Big{(}I-Z^{(v)}-{Z^{(v)}}^{T}+{Z^{(v)}}^{T}Z^{(v)}\Big{)}\Big{)}\Big{)}\\ & s.t.K^{(v)}(p_{v},p_{v})=K^{(v)}_{p},K^{(v)}\geq 0,\forall v, \end{split} \tag{17}\]  
We denote the incomplete data sample with \(p_{v}\), so \(K^{(v)}(p_{v},p_{v})=K^{(v)}_{p}\) symbolizes the multiple kernel mapping of this incomplete observation sample. While \(K^{(v)}\) represents the multiple kernel \(K^{(v)}={A^{(v)}}{A^{(v)}}^{T}\) of incomplete multi-view clustering, in order to better reflect kernel transformation of the incomplete data, we divide \(A^{(v)}\) into two parts \(A^{(v)}=\begin{bmatrix}A^{(v)}_{o}&A^{(v)}_{m}\end{bmatrix}\). \(A^{(v)}_{o}\) indicates that the corresponding data sample is complete, the size of \(A^{(v)}_{o}\text{ssn}_{o}\times\text{n}_{0}\). Correspondingly, \(A^{(v)}_{m}\) are missing parts, the size of \(A^{(v)}_{m}\) is \(\text{n}_{m}\times\text{n}_{m}\).  
Let \(B^{(v)}=\Big{(}I-Z^{(v)}-{Z^{(v)}}^{T}+{Z^{(v)}}^{T}Z^{(v)}\Big{)}=\begin{bmatrix} B^{(v)}_{oo}&B^{(v)}_{om}\\ B^{(v)}_{mo}&B^{(v)}_{mm}\end{bmatrix}\), by computing in blocks, we can reconstruct the missing part as \(A^{(v)}_{m}=-B^{(v)}_{mm}\Big{(}B^{(v)}_{om}\Big{)}^{T}A^{(v)}_{o}\), and finally we can obtain  
\[K^{(v)}=\begin{bmatrix}K^{(v)}_{o}&-K^{(v)}_{o}B^{(v)}_{om}\Big{(}\Big{(}B^{( v)}_{mm}\Big{)}^{-1}\Big{)}^{T}\\ -B^{(v)}_{om}\Big{(}B^{(v)}_{mm}\Big{)}^{-1}K^{(v)}_{o}&B^{(v)}_{om}\Big{(}B^{ (v)}_{mm}\Big{)}^{-1}K^{(v)}_{o}B^{(v)}_{om}\Big{(}\Big{(}B^{(v)}_{mm}\Big{)} ^{-1}\Big{)}^{T}\end{bmatrix}, \tag{18}\]  
With Algorithm 1, we find that the obtained kernel block matrices are highly correlated and exhibit a cooperative low-rank pattern. The TMOKSC algorithm can automatically learn the samples of missing data through the existing observational data.  
```
Input: Incomplete multi-view data samples X, the balancing parameters Output: Incomplete Multi-view subspace clustering result Step 1: Preprocess the Incomplete multi-view data samples X by Equation (3), and calculate their multi-view kernels \(K^{(v)}\) by Equation (6) Step 2: Initialize \(C^{v}\), multiply \(Y^{v}\) and give the maximum number of iterations \(k_{max}\) Step 3: Solve the following with ADMM:  While \(\big{(}\sum_{v=1}^{V}\lVert Z^{v}-C^{v}\rVert_{\infty}>\varepsilon\) and \(k<k_{max}\)) 1. Setting others, solve \(Z^{(v)}\) using Equation (14) 2. Setting others, solve \(C\) using Equation (16) 3. Setting others, solve \(K^{(v)}\) using Equation (18) 4. Update multiples \(Y^{v}\) by the formula \[Y^{v}=Y^{v}+\mu\Big{(}Z^{(v)}-C^{v}\Big{)}\] 5. Renew variables \(\mu=\min(\rho\mu,\mu_{\max}),k=k+1\) End while Step 4: Calculate the affinity matrix with weight Step 5: Get cluster result with N-cut
```  
**Algorithm 1** TMOKSC  
In the first step, the TMOKSC algorithm approximately applies a time complexity of \(O\big{(}N^{2}\big{)}\) in calculating ordered kernel functions. The second step requires a constant amount of time complexity noted as \(O(1)\) for initialization work. In the main part of the optimization, if n represents all the samples, \(\text{n}_{o}\) represents the samples we can observe, and \(\text{n}_{m}\) represents the number of samples with losses; we spent \(O\big{(}\big{(}n_{o}^{3}+3n_{o}^{2}\text{n}_{m}\big{)}\big{)}\) to solve \(Z^{(v)}\).  
Suppose the multi-view samples include V views, so it takes time of \(O\big{(}\big{(}Vn^{2}log(n)\big{)}\big{)}\) to solve \(\mathbb{C}\). It also takes time of \(O\big{(}\big{(}n_{m}^{3}+n_{0}^{2}n_{m}+2n_{0}^{2}n_{m}\big{)}\big{)}\) to solve \(K^{(v)}\), finally it takes \(O(1)\) to update the multiplier variable. Suppose the loop of optimization needs T times to converge, so the time complexity of the entire algorithm is approximately \(O\big{(}TVn^{3}\big{)}\).