Nonlinear subspace clustering by functional link neural networks

To facilitate our review, we first present some relevant definitions and notations. Let $\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}]\in\mathbb{R}^{d\times n}$ and $\mathbf{Z}=[\mathbf{z}_{1},\mathbf{z}_{2},\cdots,\mathbf{z}_{n}]\in\mathbb{R}^{n\times n}$ denote the data matrix and self-representation matrix, respectively, where $\mathbf{x}_{i}$ is the $i$th sample of $\mathbf{X}$, $d$ denotes the data dimension, and $n$ is the data number.

The objective of SSC is to uncover the sparse linear structure of data points. This is achieved by imposing the constraint of sparsity upon the representation matrix, which can be expressed as follows:

where the utilization of the $l_{1}$-norm serves the purpose of pursuing a sparse representation, the vector $diag(\cdot)\in\mathbb{R}^{n}$ is constructed from the diagonal entries of $\mathbf{Z}$, and the constraint $diag(\mathbf{Z})=\mathbf{0}$ is imposed to prevent the emergence of trivial solutions. Solving the optimization problem as stated in (1) can be achieved by implementing the Alternating Direction Method of Multipliers (ADMM) [47].

LRR utilizes the inherent property of low rank to capture the global features of data. The formulation of the corresponding objective function is presented as:

where the $l_{2,1}$-norm is employed to enforce row sparsity on the error matrix, enabling the identification and removal of outliers that diverge from the underlying subspaces, $\lVert\mathbf{Z}\rVert_{*}$ computes the summation of singular values within $\mathbf{Z}$, and $\lambda$ is a balance parameter. A notable distinction between SSC and LRR lies in their methodologies: SSC relies on the $l_{1}$-norm to induce sparsity, whereas LRR utilizes the nuclear norm to encourage a low-rank structure.

It is seen from the second panel of Figure 1 that the FLNN is a single-layer neural network, comprised of an input layer that is functionally expanded and an accompanying output layer. Notably, there is an absence of a hidden layer within this configuration. The input layer can be expanded by some nonlinear functions [42], such as Chebyshev polynomials, Legendre polynomials, trigonometric functions, etc, which is useful to strengthen the learning capability of the network. For example, consider the $i$th element $x_{i}$ in a vector $\mathbf{x}$, an enhanced representation by using a second-order trigonometric polynomial is given by $\varphi(x_{i})=[x_{i},\sin(\pi x_{i}),\cos(\pi x_{i}),\sin(2\pi x_{i}),\cos(2\pi x_{i})]$. The FLNN has a simpler structure than the traditional feed-forward neural network, as it does not have any hidden layers. This reduces the computational complexity and the number of parameters that need to be trained.

As described above, we denote $\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}]\in\mathbb{R}^{d\times n}$ and $\mathbf{Z}=[\mathbf{z}_{1},\mathbf{z}_{2},\cdots,\mathbf{z}_{n}]\in\mathbb{R}^{n\times n}$ as the data matrix and self-representation matrix, respectively. The input sample $\mathbf{x}_{i}$ is expanded by a nonlinear function $\varphi(\cdot)$, and then pass through a layer of multiple neurons. With an activation function, the output is provided by

where $\mathbf{h}_{i}\in\mathbb{R}^{\hat{d}\times 1}$ represents the output vector with $\hat{d}$ being the expanded dimension via functional expansion, $\rho(\cdot)$ denotes the activation function, $\mathbf{W}\in\mathbb{R}^{\hat{d}\times\hat{d}}$ is the parameter matrix to be trained, which plays a pivotal role in generating outputs that closely approximate the actual results, and $\varphi(\mathbf{x}_{i})\in\mathbb{R}^{\hat{d}\times 1}$ is the input vector after functional expansion. In this paper, we select a typical expansion function, namely trigonometric polynomial, for $\varphi(\mathbf{x}_{i})$. The choice of trigonometric polynomials is motivated by their inherent simplicity and computational efficiency. Moreover, they provide orthonormal bases, a feature that greatly simplifies the process of calculating expansion coefficients, thereby enhancing the overall computational performance. Specifically, we employ a second-order expansion because it achieves a balance between performance and computational complexity. While higher-order expansions could potentially be used, they would significantly increase the computational complexity. We find that a second-order expansion is sufficient to achieve good performance while maintaining an acceptable level of complexity. Consequently, the dimension of the transformed data is $\hat{d}=5d$.

By stacking each $\mathbf{h}_{i}$, the output matrix $\mathbf{H}$ of the output layer is defined as

Using the output matrix $\mathbf{H}$, our approach conducts subspace clustering in the nonlinear domain.

The objective function $J$ of FLNNSC is comprised of three components, i.e.,

where $J_{1}$ is served to learn the self-representation matrix, $J_{2}$ is used to impose the grouping effect, and $J_{3}$ is employed to avoid the model over-fitting.

Specifically, we define $J_{1}$ as

Combining (6), (7) and (8), FLNNSC can be explicitly defined as

The formulated model is capable of exploiting the nonlinearity of data and manipulating the local structure features.

In this section, we comprehensively detail the process of addressing the optimization problem specified in equation (9). Note that the optimization problem depends on two variables, $\mathbf{W}$ and $\mathbf{Z}$. In the subsequent derivation, we update $\mathbf{W}$ and $\mathbf{Z}$ iteratively.

1) Update $\mathbf{W}$: To update $\mathbf{W}$, we keep $\mathbf{H}$ and $\mathbf{Z}$ fixed and eliminate the irrelevant term, and arrive at

A direct method to tackle the optimization problem stated in (10) is by employing the gradient descent algorithm. Upon calculating the derivative of the aforementioned objective function with respect to $\mathbf{W}$, we obtain

where $\rho^{\prime}(\cdot)$ represents the derivative of the activation function $\rho(\cdot)$. As a result, the parameter matrix $\mathbf{W}$ is updated as

where $\mu$ is the learning rate.

2) Update $\mathbf{Z}$: To update $\mathbf{Z}$, we keep $\mathbf{H}$ and $\mathbf{W}$ constant and ignore the irrelevant term, and arrive at

Additionally, (13) can be written into an equivalent form

We execute iterative updates of $\mathbf{W}$ and $\mathbf{Z}$ until the objective function converges to a stable state. Subsequent to this, we attain the self-representation $\mathbf{Z}$ and proceed with the construction of the graph as outlined in [22]. Finally, we apply spectral clustering on the resulted graph $\mathbf{G}$. A comprehensive description of the FLNNSC approach is presented in Table 3

To initiate the convergence loop, we first compute the Laplacian matrix $\mathbf{L}$ in $O(n^{2})$ time using the formula $\mathbf{L}=\mathbf{D}-\mathbf{S}$. Within the loop, we compute $\varphi(\mathbf{x}_{i})$, update $\mathbf{W}$, and compute $\mathbf{H}$ for all data points at each iteration. Given that a second-order trigonometric polynomial expansion for $\varphi(\mathbf{x}_{i})$ is used, the dimensionality after the expansion is $\hat{d}=5d$, and the complexity of computing $\varphi(\mathbf{x}_{i})$ is $O(5d)$. The update of $\mathbf{W}$ involves two terms: ($\mathbf{h}_{i}-\mathbf{H}\mathbf{z}_{i})\odot\rho^{\prime}(\mathbf{W}\varphi(\mathbf{x}_{i}))\varphi^{T}(\mathbf{x}_{i})$ and $\beta\mathbf{W}$, with complexities of $O(125d^{3}+5dn^{2}+25d^{2}+5d)$ and $O(25d^{2})$, respectively. The complexity of computing $\mathbf{H}$ is $O(125d^{3}n)$. For $n$ data points, the overall complexity within the loop is $O(125d^{3}n^{2}+125d^{3}n+5dn^{3}+50d^{2}n+10dn)$. The update of $\mathbf{Z}$ is based on solving (15) by invoking the “lyap” function. This requires a complexity of $O(2n^{3})$. Assuming $t$ iterations, the final complexity corresponding to the convergence loop is $O(t(5dn^{3}+2n^{3}+125d^{3}n^{2}+125d^{3}n+50d^{2}n+10dn))$. When the condition $d<<n$ is satisfied, the model complexity can be approximated as $O(n^{3})$.

Upon reviewing the relevant literature, it becomes clear that several existing methods, including SSC, LRR, LRSC, and LSR, primarily differ in the norm constraint imposed on the regularization term. These methods share a similar structure of objective function, which leads to an approximate computational complexity of $O(n^{3})$ when $d<<n$. However, in comparing actual running time, SSC and LRR generally take longer than LSR. This is because problems induced by sparse and nuclear norms typically require more computational resources. From the corresponding literature of SMR, we know that its complexity is also $O(n^{3})$. The computational cost of NSC is heavily dependent on the choice of feed-forward neural networks, with more layers resulting in higher costs. The KSSC method actually has a slightly higher complexity than SSC due to the additional kernel mapping. The BDR method, which introduces a block diagonal regularization, has better learning efficiency than SSC or LRR in some data scenarios. Despite this, both KSSC and BDR can be considered as having a complexity of $O(n^{3})$ from a qualitative perspective.

Therefore, we can qualitatively argue that many subspace clustering methods have a complexity of $O(n^{3})$, including our proposed method. However, it is worth noting that they exhibit discrepancy in their actual execution time.

1) Datasets: We consider four publicly available datasets: Extended Yale B [48], USPS [49], COIL20 and and ORL [9]. We use PCA to perform dimensionality on the raw datasets. For implementing PCA, we reduce the data dimensionality to a default dimensionality. Since the determination of the number of principal components is influenced by the number of cluster, we set the number of principal components (default dimensionality) to be $clusters\times 6$. A brief description of each dataset is provided below:

1) Extended Yale B: Extended Yale B is a widely known and challenging face recognition dataset extensively utilized in computer vision research. It comprises 2414 frontal face images categorized into 38 subjects, with each subject containing approximately 64 images taken under different illumination conditions.

2) USPS: USPS is a popular handwritten digit dataset widely used for handwriting recognition tasks. It consists of 92898 handwritten digit images covering ten digits (0–9), each image sized $16\times 16$ pixels, with 256 gray levels per pixel.

3) COIL20: COIL20 has images of 20 different objects observed from various angles. Each object has 72 gray scale images, resulting in a total of 1440 images in the dataset.

4) ORL: ORL comprises 400 images of 40 distinct individuals. These images, taken at different times, showcase varying lighting conditions, facial expressions (open/closed eyes, smiling/not smiling), and facial details (with/without glasses).

2) Compared methods: We compare FLNNSC and CCSC with several baselines, including SSC [3], LRR [5], LRSC [50], NSC [39], SMR [22], KSSC [31], LSR1 and LSR2 [20], Kernel Truncated Regression Representation (KTRR) [34], BDR-B and BDR-Z [9].

3) Evaluation metrics: We evaluate the clustering performance by clustering accuracy (CA), normalized mutual information (NMI), adjusted rand index (ARI) , and F1 score. All methods are performed 20 times, and the resulting mean values of the metrics are recorded.

4) Parameter settings: For a fair comparison, we use the code (if available as open source) provided on the respective open source platform for existing subspace clustering algorithms. For all competing algorithms, we carefully adjust the parameters to achieve optimal performance or adopt the recommended parameters as stated in the corresponding papers. For all the methods, we turn the parameters in the range $[10^{-4},10^{-3},10^{-2},...,10^{2},10^{3},10^{4}]$, and then select the parameter with the best performance. The optimal parameter selections of various algorithms are presented in Table 4.

In the following, we will conduct extensive experiments to validate our proposed model, including clustering performance comparison, affinity graph analysis, parameter sensitivity and convergence analysis, as well as execution time analysis.

We consider Friedman test [51] to validate the superiority of the proposed model. Specifically, in terms of datasets, we select Extended Yale B with 10 subjects, USPS, COIL20, and ORL. Regarding methods, we choose SSC, LRR, LRSC, NSC, SMR, KSSC, LSR1, KTRR, BDR-B, and our FLNNSC. For each dataset, we sort various models in ascending order based on their accuracy and use the index of the sorted values as the rank for the corresponding model, and the rank matrix is shown in Table 7.

After obtaining the rank matrix, we calculate the rank value for each method. Let $rank_{i,j}$ be the rank of the $i$-th method on the $j$-th dataset, then the rank of the $i$-th model is:

where $N$ denotes the number of datasets. Assuming that rank of each method follows a normal distribution, the corresponding chi-square statistic is [52]:

where $k$ is the number of methods. Finally, we can use the chi-square distribution to compute the $p$-value. By applied the friedman function in Matlab, we calculate a $p$-value of $0.0039$. As this value is lower than the significance level of $0.05$, we reject the null hypothesis. This suggests that there is a significant difference in the performance of the various methods. To visually represent these differences, we have plotted a bar chart of mean rank, as shown in Fig. 7. It is evident from the chart that KTRR, BDR-B, and FLNNSC significantly outperform the other methods in terms of mean rank (calculated using equation (24)). Notably, our method, FLNNSC, achieves a higher rank value than both KTRR and BDR-B.

In subspace clustering, when the data exhibits evident nonlinearity characteristics, the combination method, i.e., CCSC, shows comparable clustering performance to FLNNSC under the optimal parameter settings. If one select CCSC, it is crucial to carefully tune an extra balance parameter $\lambda$. This is because the selection of $\lambda$ impacts the performance. Therefore, in such cases, we recommend FLNNSC. If the data also exhibits significant linear characteristics that cannot be ignored, CCSC outperforms FLNNSC due to its ability to dynamically adjust the balance between linear and nonlinear representations. In this case, we recommend CCSC, with the tuning of $\lambda$ over the range of (0.5, 1).

Moreover, the proposed FLNNSC algorithm, using a functional link neural network for nonlinear representation, has higher computational efficiency compared to traditional neural network-based subspace clustering methods. Remarkably, to enhance the capacity for capturing the data’s nonlinearity, one can employ a higher-order functional expansion for FLNN. This may lead to performance improvements, but this enhancement introduces a trade-off by increasing computational intricacy.