## 3 Ssrhe
### Spatial-Spectral Hypergraph Embedding
In the low-dimensional embedded space, the spatial-spectral embedding of test sample \(\mathbf{x}_{t}\) can be given as follows:  
\[\mathbf{y}_{t}=\mathbf{P}^{T}\mathbf{x}_{t} \tag{33}\]  
In summary, SSRHE compacts the samples from the same class and spatial neighborhood while separates interclass samples, and the embedding features possess stronger discriminative power that ensures good classification performance. The steps of the proposed SSRHE method are shown in Algorithm 1. ```
0: HSI dataset \(\mathbf{X}=\left[\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{N}\right] \in R^{D\times N}\), corresponding class label set \(\mathbf{L}\), tradeoff parameters \(\alpha\), \(\beta\), weighted coefficient \(\varphi\), spatial neighborhood size \(T\), reduced dimensionality \(d\). 1: According to ADMM, compute sparse coefficient matrix \(\mathbf{S}\);
2: Compute the weights of intraclass and interclass hyperedge by Equations (8) and (9);
3: Compute the intraclass hyper-Laplacian matrix: \(\mathbf{L}^{w}=\mathbf{D}_{v}^{w}-\mathbf{H}^{w}\mathbf{W}^{w}(\mathbf{D}_{v}^ {w})^{-1}(\mathbf{H}^{w})^{T}\);
4: Compute the interclass hyper-Laplacian matrix: \(\mathbf{L}^{b}=\mathbf{D}_{v}^{b}-\mathbf{H}^{b}\mathbf{W}^{b}\left(\mathbf{D }_{e}^{b}\right)^{-1}\left(\mathbf{H}^{b}\right)^{T}\);
5: Compute the local spatial neighborhood preserving scatter matrix:
6:
7: Compute the extended total scatter matrix: \(\mathbf{S}^{b}=\sum_{i=1}^{N}\left(\mathbf{x}_{i}-\overline{\mathbf{x}} \right)(\mathbf{x}_{i}-\overline{\mathbf{x}})^{T}\);
8: Solve the generalized eigenvalue problem:
9:
10: Obtain the optimal projection matrix with largest eigenvalues corresponding eigenvectors:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21: Low-dimensional spatial-spectral embedding features of test samples:\(\mathbf{Y}=\mathbf{P}^{T}\mathbf{X}\)
```  
**Algorithm 1** SSRHE. In this paper, we adopt big \(O\) notation to analyze the computational complexity of SSRHE. Spatial neighborhood size and the number of sparse iterations are denoted as \(T\) and \(t\), respectively. The sparse coefficient matrix \(\mathbf{S}\) is computed with the cost of \(O(Nt)\). The weight of intraclass hyperedge and the weight of interclass hyperedge both take \(O\left(N^{2}\right)\). The intraclass incidence matrix \(\mathbf{H}^{w}\) and the interclass incidence matrix \(\mathbf{H}^{b}\) are both calculated with \(O\left(N^{2}\right)\). The cost of diagonal matrices \(\mathbf{W}^{w}\), \(\mathbf{W}^{b}\), \(\mathbf{D}_{w}^{w}\), \(\mathbf{D}_{v}^{w}\), \(\mathbf{D}_{e}^{w}\), and \(\mathbf{D}_{e}^{b}\) are \(O(8N)\)). The intraclass hyper-Laplacian matrix \(\mathbf{L}^{w}\) and the interclass hyper-Laplacian matrix \(\mathbf{L}^{b}\) both cost \(O\left(N^{3}\right)\). The local spatial neighborhood preserving scatter matrix \(\mathbf{S^{w}}\) takes \(O\left(DNT^{2}\right)\). The extended total scatter matrix \(\mathbf{S^{b}}\) costs \(O\left(DN\right)\). The costs of matrix \(\mathbf{M^{w}}\) and \(\mathbf{M^{b}}\) are both \(O\left(DN^{2}\right)\). \(\mathbf{XX^{T}}\) costs \(O\left(DN\right)\). It takes \(O\left(D^{3}\right)\) to deal with the generalized problem of Equation (32). The total time complexity of SSRHE is \(O\left(D^{3}+DN^{2}+N^{3}\right)\).