## 3 SSC and LRR Clustering with LLE Regularization
### Solutions to LLE-SSC and LLE-LRR
\(Q[\cdot]\) is the soft-thresholding operator defined on the diagonal element \(\mathbf{\Sigma}_{ii}\) of \(\mathbf{\Sigma}\) as follows:\[Q[\mathbf{\Sigma}_{ii}]= \begin{cases}\mathbf{\Sigma}_{ii}-1,&\text{if }\mathbf{\Sigma}_{ii}>1;\\ \mathbf{\Sigma}_{ii}+1,&\text{if }\mathbf{\Sigma}_{ii}<-1;\\ 0,&\text{otherwise}.\end{cases}  \tag{25}\]  
Once the above two steps are solved, the solutions to the proposed LLE-SSC and LLE-LRR models will be obtained. The complete algorithm for the data representation is summarized in Algorithm 1. It is denoted that the convergence of the ADMM method could not be guaranteed as being discussed in [30]. However, our following experiments show that the algorithm always converges. As to the complexity of Algorithm 1, the main computational cost of the algorithm is determined by the step 2, 3, 5 and 6. For the dataset \(\mathbf{X}\) with \(n\) sample vectors in the dimension of \(D\), the step 2 is to get the LLE weights \(\mathbf{W}^{*}\) by solving (8) and its complexity is \(\mathcal{O}(Dn^{2}+(D+K)K^{2}n)\), where \(K\) is the maximal neighbours of the data samples. The calculation of \(\mathbf{L_{M}}\) in the step 3 has the complexity of \(\mathcal{O}(n^{2})\) according to (10). Step 5 is to solve the data representation matrix \(\mathbf{Z}\) by the linear equation in (18), which has the complexity of \(\mathcal{O}(T_{0}(n^{2})^{2})\), where \(T_{0}\) is the maximal iterations of (18). The complexity of step 6 is different for LLE-SSC and LLE-LRR methods; the former has the complexity of \(\mathcal{O}(n^{2})\) and the latter has the complexity of \(\mathcal{O}(rn^{2})\), where \(r\) is the estimated rank of the data representation matrix \(\mathbf{S}\) or \(\mathbf{Z}\). Inductively, we obtain the final complexity of Algorithm 1, i.e., \(\mathcal{O}(TT_{0}n^{4}+(D+T+1)n^{2}+(D+K)K^{2}n)\) for LLE-SSC and \(\mathcal{O}(TT_{0}n^{4}+(D+Tr+1)n^{2}+(D+K)K^{2}n)\) for LLE-LRR, respectively. ```
1:The dataset \(\mathbf{X}\), maximal iteration number \(T\), parameters \(\lambda_{1},\lambda_{2},\gamma\). 2:The data representation \(\mathbf{Z}\). 3:Initialization: \(\mathbf{Z}^{0}=0,\mathbf{S}^{0}=0,\mathbf{Z}=\mathbf{S},t=0,\mathbf{G}= \mathbf{I},\rho=1.3\). 4:Obtain \(\mathbf{W}^{*}\) by solving (8);
5:Calculate \(\mathbf{L_{M}}\) by (10);
6:while\(t<T\)do
7: Calculate \(\mathbf{Z}^{t}\) by (18);
8: If LLE-SSC, calculate \(\mathbf{S}^{t}\) by (23);
9: If LLE-LRR, calculate \(\mathbf{S}^{t}\) by (24);
10: Update \(\mathbf{G}\leftarrow\mathbf{G}+\gamma(\mathbf{Z}^{t}-\mathbf{S}^{t})\);
11: Update \(\gamma\leftarrow\rho\gamma\);
12: Update \(t\gets t+1\);
13:endwhile
```  
**Algorithm 1** Solution to the data representation for LLE-SSC and LLE-LRR. Based on the above LLE-SSC anf LLE-LRR data representation algorithm, we can finally obtain the subspace clustering algorithm as shown in Algorithm 2. ```
1:The data for clustering \(\mathbf{X}\). 2:The clustering results of \(\mathbf{X}\). 3:Obtain the sparse representation \(\mathbf{Z}\) of \(\mathbf{X}\) by Algorithm 1;
4:Calculate the affinity matrix \(\mathbf{W}=(|\mathbf{Z}|+|\mathbf{Z}^{T}|)/2\);
5:Calculate the Laplace matrix \(\mathbf{L_{W}}\) by (5);
6:Implement \(\text{NCut}(\mathbf{L_{W}})\) to get the final clustering result of \(\mathbf{X}\). ```  
**Algorithm 2** Subspace clustering based on LLE-SSC and LLE-LRR.