# Robust Spectral Clustering via Low-Rank Sample Representation

Authors: Hao Liang; Hai-Tang Guan; Stanley Ebhohimhen Abhadiomhen; Li Yan
Journal: Applied Computational Intelligence and Soft Computing
 (2022)

---

## Abstract

Traditional clustering methods neglect the data quality and perform clustering directly on the original data. Therefore, their performance can easily deteriorate since real-world data would usually contain noisy data samples in high-dimensional space. In order to resolve the previously mentioned problem, a new method is proposed, which builds on the approach of low-rank representation. The proposed approach first learns a low-rank coefficient matrix from data by exploiting the data’s self-expressiveness property. Then, a regularization term is introduced to ensure that the representation coefficient of two samples, which are similar in original high-dimensional space, is close to maintaining the samples’ neighborhood structure in the low-dimensional space. As a result, the proposed method obtains a clustering structure directly through the low-rank coefficient matrix to guarantee optimal clustering performance. A wide range of experiments shows that the proposed method is superior to compared state-of-the-art methods.


---

## Body

## 1. Introduction

Clustering is a powerful technique in unsupervised machine learning, which requires a measure of similarity to group data samples intok classes. Therefore, traditional clustering algorithms such as k-means [1] perform clustering on original data samples directly by assuming that alike samples reside around a centroid. This assumption is noted in [2] as too restrictive in a real-world setting where two samples can be far away from each other yet belong to the same cluster, and vice versa. Furthermore, as real-world data is often high dimensional, the k-means approach is also computationally inefficient. Thus, efforts were made in literature [3] to enhance its efficiency. However, the robustness needed for accurate clustering under the aforementioned real-world circumstances was largely ignored, as they do not consider data quality.Therefore, considering that corresponding low-dimensional subspaces exist for high-dimensional data, Zheng et al. [4] and Cai et al. [5] proposed graph regularized sparse coding (GraphSC) and graph regularized nonnegative matrix (GNMF), respectively, to tackle the previously mentioned lapses. The object of both methods is such that discriminability and computational efficiency can be enhanced simultaneously to improve clustering performance. Nonetheless, as they do not fully utilize the self-expressiveness property of data, a good representation of data cannot be guaranteed in all cases. As a result, subsequent spectral-based approaches were built on the self-expressiveness property of data where a data sample can be represented by a combination of the bases in a whole dataset [6]. Specifically, low-rank representation (LRR) [7] and sparse subspace clustering (SSC) [8] are the two classical methods, and the newer ones are formed using either of their principles. An example is Laplacian regularized low-rank representation (LapLRR) [9] proposed to improve LRR’s global data structure initiative by further capturing data’s intrinsic nonlinear geometric information. Similarly, Zhang et al. [10] proposed spectral-spatial sparse subspace clustering (S4C) using the SSC’s L1-norm regularization strategy. Besides, considering the local data structure that LRR previously ignored, low-rank representation with adaptive graph regularization (LRR_AGR) [11] was proposed to learn optimal clustering. However, because real-world data often contain noise, these spectral methods cannot guarantee that two similar samples in the original high-dimensional space will have a close representation coefficient in the low-dimensional space.To address the previously mentioned concern, a new method that adopts LRR’s approach to first learn data’s low-rank coefficient matrix is proposed. A regularization term is then introduced to ensure that the samples’ neighborhood structure is maintained in the low-dimensional space. Thus, the proposed method learns optimal clustering structure directly from the low-rank coefficient matrix without spectral postprocessing. It is achieved by imposing a constraint on the low-rank coefficient matrix to promote a robust affinity matrix, a rank constraint is further utilized to make the affinity matrix express the clustering structure.(1)
We propose a novel method that uses the LRR strategy first to obtain data’s low-rank coefficient matrix, of which a regularization term is also introduced to ensure that samples’ neighborhood structure is maintained in the low-dimensional space. This approach is different from the existing ones, which simply assume such a structure without a robust strategy to tackle the influence of noise.(2)
We constrain the low-rank coefficient matrix to guide a robust affinity matrix to obtain optimal clustering directly while avoiding spectral postprocessing of the affinity matrix, unlike most existing methods.(3)
Several experiments are performed to evaluate the effectiveness of the proposed method using accuracy (ACC), normalized mutual information (NMI), and purity evaluation metrics. The results demonstrate the superiority of the proposed method over similar state-of-the-art ones.


## 2. Related Work

To resolve the inefficiency of traditional clustering methods, several spectral type methods based on the self-expressiveness property of data have been proposed over the years. Therefore, one can categorize these methods into two groups according to the strategy used to obtain a given data’s low-dimensional coefficient matrix. The first group has methods like those mentioned in [10, 12–14], which use the L1-norm regularization [8] to acquire the coefficient matrix. For example, Zhang et al. [10] proposed a spectral-spatial sparse subspace clustering algorithm for hyperspectral remote sensing images, which obtains a final clustering by applying a spectral clustering algorithm on an adjacent matrix. Also, using the L1-norm approach, Li et al. [12] proposed structured sparse subspace clustering (S3C), which learns an affinity matrix and data segmentation jointly to improve clustering accuracy. The L1-norm’s regularization main advantage lies in the fact that it can obtain a sparse representation of data samples. However, it ignores the data’s global structure; hence, it can be vulnerable to noise.In contrast, the nuclear norm regularization approach was proposed in [7] to capture a global data structure, thus providing some robustness against noise and possible outliers. Thus, the second category contains methods like those in [6, 9, 11, 15–24], which apply the aforementioned nuclear norm technique to learn the coefficient matrix. Illustratively, the LapLRR method was proposed in [9] based on the nuclear norm. LapLRR mainly focuses on capturing data’s nonlinear geometric structures to improve clustering performance. The compound rank-k projection (CRP) [23] algorithm was proposed for bilinear analysis. Specifically, CRP uses multiple rank-k projection models to enhance discriminant ability. Meanwhile, the constrained low-rank representation (CLRR) [15] emphases on increasing discriminating ability by incorporating supervision information as hard constraints. Since the LRR methods are based on affinity graph construction, Luo et al. [24] argue that the affinity measurement in the original feature space would usually suffer from the curse of dimensionality. Thus, a method was proposed, which assumes similarity between instances only if they have a larger probability of being neighbours. However, because a fixed graph often does not guarantee optimal performance, Wen et al. [11] then introduced flexibility into graph learning and proposed the LRR-AGR method. Besides, a technique founded on a finite mixture of exponential power (MoEP) was proposed in [19] to handle complex noise contamination in data. Furthermore, the recent work of [25] introduced an adaptive kernel into LRR to boost the accuracy of clustering. Besides, a coupled low-rank representation (CLR) strategy was presented in [6] to learn accurate clustering from data using the k bock diagonal regularizer [26]. Aside from that, Yan et al. [27] proposed a novel self-weighted robust linear discriminant analysis (LDA) for multiclass classification, especially with edge classes.This study also adopts the nuclear norm regularization approach. However, unlike the previously mentioned techniques, the proposed method further injects a regularization term to guarantee that two similar samples in the original high-dimensional space would have a close representation coefficient in the low-dimensional space to handle noise distortion in data more holistically.


## 3. The Proposed Method

In this section, the proposed method is formulated first. Then, an optimization method is proposed to solve the model.


### 3.1. Model Formulation

LRR's nuclear norm regularization has been shown in many studies, not limited to those previously cited, as an effective technique for capturing a robust data coefficient matrix due to its global orientation. Thus, LRR is integrated into our model to capture the data’s low-rank coefficient matrix as follows:(1)Z∗+λ2E2,1,s.t.X=XZ+E,where Z∈ℝn×n is the low-rank coefficient matrix. E∈ℝd×n is the error matrix, assuming that part of the given data X∈ℝd×n is corrupt. However, because the level of corruption in real-world data is unknown in advance, one cannot guarantee that Z will capture an accurate similarity of the data samples. To address this concern, a regularization term ∑i,jx^i−x^j2wi,j is introduced into (1) to ensure that when samples xi and xj are similar in the original high-dimensional space, zi and zj should be similar in low-dimensional space, so that Zij = 1, otherwise 0. Thus, we have(2)minX^,Z,E∑i,jx^i−x^j2wi,j+λ1Z∗+λ2E2,1s.t.X=XZ+E,X^=XZ,where ∑i,jx^i−x^j2Wij=2trX^LWX^T. W=W+WT/2,LW=D−W and D=diag∑iWij. Once Z is obtained, existing methods directly learn an affinity matrix U such that U=Z+ZT/2. Most of these methods then apply a spectral clustering algorithm on U to obtain the clustering structure. Differently, we utilize a constraint Z=U to ensure that the coefficient of Zij and Uij is the same, in which some nonnegative constraints, diagU=0,U≥0,UT1=1, imposed on U ensures that its entries are nonnegative. As a result, a spectral postprocessing of U is then dodged by imposing a rank constraint rankLU=n−c on its Laplacian matrix to allow it to express our clustering structure using Theorem 1. Therefore, the proposed model is formulated as(3)minX^,Z,S,E2trX^LWX^T+λ1Z∗+λ2E2,1s.t.X=XZ+E,Z=U,X^=XZ,diagU=0,U≥0,UT1=1,rankLU=n−c,where LU=DU−U is the Laplacian matrix of U and DU∈ℝn×n is the diagonal matrix withith entry ∑jUij=1. λ1 and λ2 are parameters to balance the terms, respectively.Theorem 1 (see [6]).
IfU is nonnegative, the multiplicity c of the zero eigenvalue of the graph Laplacian LU corresponds to the number of connected components in the graph associated with U.


### 3.2. Optimization

To solve (3), the augmented Lagrange multiplier (ALM) [28, 29] approach is adopted, but an auxiliary term Z=S is introduced first to make it easily solvable. Besides, because the rank constraint is not linear, a similar strategy employed in [6] is followed to express the ith smallest eigenvalue of LU as θi (LU). Thus, given sufficient λ3, (3) is equal to(4)minX^,S,U,E2trX^LWX^T+λ1S∗+λ2E2,1+2λ3∑i=1cθiLUs.t.Z=S,X=XZ+E,Z=U,X^=XZ,diagU=0,U≥0,UT1=1.According to Ky Fan’s theorem [30], ∑i=1cθiLU is equivalent to minimizing TrFTLUF subject to FTF=I. Hence, we have(5)minX^,Z,S,E2trX^LWX^T+λ1S∗+λ2E2,1+2λ3TrFTLUFs.t.Z=S,X=XZ+E,Z=U,X^=XZ,FTF=I,diagU=0,U≥0,UT1=1.Following conventional practice, the augmented Lagrangian function of (5) is obtained as follows:(6)minX^,Z,S,E,U,F2trX^LWX^T+λ1S∗+λ2E2,1+2λ3TrFTLUF+Y1,Z−S+Y2,X−XZ−E+Y3,X^−XZ+Y4,Z−U+μ2Z−SF2+X−XZ−EF2+X^−XZF2+Z−UF2s.t.FTF=I,diagU=0,U≥0,UT1=1.At this point, the terms not connected in (6) are separated, where Y1, Y2, Y3, and Y4 are Lagrangian multipliers. Hence, each term’s optimal value is obtained in the following order.


#### 3.2.1.X^ Problem

When other variables are fixed,X^ can be obtained by minimizing the following formula:(7)LX^=2trX^LWX^T+Y3,X^−XZ+μ2X^−XZF2.By setting the derivative ∂L (X^)/∂X^ = 0, variable X^ is obtained as follows:(8)4X^L+μX^−XZ+Y3=0,X^=μXZ−Y34L+μI−1.


#### 3.2.2.Z Problem

When other variables are fixed,Z can be obtained by minimizing the following formula:(9)minZY1,Z−S+Y2,X−XZ−E+Y3,X^−XZ+Y4,Z−U+μ2Z−SF2+X−XZ−EF2+X^−XZ+Z−UF2.By setting the derivative ∂L (Z)/∂Z = 0, variable Z is obtained as follows:(10)Z=I+XTX−11/μXTY2+Y3−Y1+Y4/μ+S+U+XTX+XTX^−XTE2.


#### 3.2.3.S Problem

S can be achieved by solving the following problem with other variables fixed(11)S=argminSλ1μS∗+12S−Z+Y1uF2.Then,S is obtained as follows by using the singular value thresholding (SVT) operator [31]:(12)S=Sλ1/μZ+Y1μ.


#### 3.2.4.E Problem

E is obtained by solving the following minimization problem:(13)E=argminEλ2E2,1+μ2E−X−XZ+Y2uF2.DenoteT = X−XZ+1/uY2, τ=λ2/μ.Thei−th column of E is(14)E:,i=ti−τtiti,ifτ<ti,0,otherwise.


#### 3.2.5.U Problem

U is obtained by solving the following minimization problem:(15)minU2λ3TrFTLUF+Y4,Z−U+μ2Z−UF2.For simplicity,∑i,jFi−Fj2Ui,j is equivalent to TrGTU, where Gij=Fi−Fj22; then, we rewrite (15) as(16)minUTrGTU+μ2U−Z+Y4μF2.DenotingN=Z+Y4/μ, we get(17)minUiUi−Ni−Gi/μ22s.t.diagU=0,U≥0,UT1=1.Considering the previously mentioned constraints, we have the following:(18)minUi∑jUi−Ni−Gi/μ2λ422−η1TUi−1−ζTUis.t.Uii=0.Then, taking the derivative with respect toUi and setting it to zero, that is,(19)Ui−1Ni−Gi/μ2λ4−η1−ζ=0.Thej entry of Ui is shown as follows:(20)Uij−Nij−Gij/μ2λ4−η−ζi=0.According to KKT conditions,(21)Uij=Nij−Gij/μ2λ3+η+.


#### 3.2.6.F Problem

When other variables are fixed,F can be obtained by solving the following minimization problem:(22)LF=minFTrFTLUFs.t.FTF=I,where LU is the Laplacian matrix of U. This problem can be simply solved via eigenvalue decomposition, and its solutions are the set of c eigenvectors corresponding to the first c smallest eigenvalues of LU.The complete solution is given in Algorithm 1.Algorithm 1: The proposed algorithm.
Input: Data X, clusters size c, parameter λ1, λ2,λ3Initialize:X^=Z=S=E=U=F=0,Y1=0,Y2=0,Y3=0,Y4=0,; ρ=1.01; μ=0.01; μmax =  108; ϵ=10−5;While not converged do(1)
UpdateX^ by equation (8);(2)
UpdateZ by equation (10);(3)
UpdateS by equation (12);(4)
UpdateE by equation (14);(5)
UpdateU by equation (21);(6)
UpdateF by equation (22);Y1=Y1+μZ−SY2=Y2+μX−XZ−EY3=Y3+μX^−XZY4=Y4+μZ−U(11)
Updateμ by μ=minρμ,maxμ(12)
Check the convergence conditions:Z−S∞<ϵ,X−XZ−E∞<ϵ, X^−XZ∞<ϵ and Z−U∞<ϵOutput:U


### 3.3. Computational Complexity

The inverse of a matrix, eigen decomposition, and SVT's nuclear norm minimization problem are three key aspects that define the computing cost of our proposed algorithm. Specifically, the eigen decomposition costsOn2c, where c is the number of clusters. The inverse of a matrix and nuclear norm minimization cost is On3 each. As a result, the total computational complexity of each iteration is On3+2n2c because the cost of computing multipliers and basic matrix operations like addition, subtraction, and division are negligible compared with the cost of other operations.


## 3.1. Model Formulation

LRR's nuclear norm regularization has been shown in many studies, not limited to those previously cited, as an effective technique for capturing a robust data coefficient matrix due to its global orientation. Thus, LRR is integrated into our model to capture the data’s low-rank coefficient matrix as follows:(1)Z∗+λ2E2,1,s.t.X=XZ+E,where Z∈ℝn×n is the low-rank coefficient matrix. E∈ℝd×n is the error matrix, assuming that part of the given data X∈ℝd×n is corrupt. However, because the level of corruption in real-world data is unknown in advance, one cannot guarantee that Z will capture an accurate similarity of the data samples. To address this concern, a regularization term ∑i,jx^i−x^j2wi,j is introduced into (1) to ensure that when samples xi and xj are similar in the original high-dimensional space, zi and zj should be similar in low-dimensional space, so that Zij = 1, otherwise 0. Thus, we have(2)minX^,Z,E∑i,jx^i−x^j2wi,j+λ1Z∗+λ2E2,1s.t.X=XZ+E,X^=XZ,where ∑i,jx^i−x^j2Wij=2trX^LWX^T. W=W+WT/2,LW=D−W and D=diag∑iWij. Once Z is obtained, existing methods directly learn an affinity matrix U such that U=Z+ZT/2. Most of these methods then apply a spectral clustering algorithm on U to obtain the clustering structure. Differently, we utilize a constraint Z=U to ensure that the coefficient of Zij and Uij is the same, in which some nonnegative constraints, diagU=0,U≥0,UT1=1, imposed on U ensures that its entries are nonnegative. As a result, a spectral postprocessing of U is then dodged by imposing a rank constraint rankLU=n−c on its Laplacian matrix to allow it to express our clustering structure using Theorem 1. Therefore, the proposed model is formulated as(3)minX^,Z,S,E2trX^LWX^T+λ1Z∗+λ2E2,1s.t.X=XZ+E,Z=U,X^=XZ,diagU=0,U≥0,UT1=1,rankLU=n−c,where LU=DU−U is the Laplacian matrix of U and DU∈ℝn×n is the diagonal matrix withith entry ∑jUij=1. λ1 and λ2 are parameters to balance the terms, respectively.Theorem 1 (see [6]).
IfU is nonnegative, the multiplicity c of the zero eigenvalue of the graph Laplacian LU corresponds to the number of connected components in the graph associated with U.


## 3.2. Optimization

To solve (3), the augmented Lagrange multiplier (ALM) [28, 29] approach is adopted, but an auxiliary term Z=S is introduced first to make it easily solvable. Besides, because the rank constraint is not linear, a similar strategy employed in [6] is followed to express the ith smallest eigenvalue of LU as θi (LU). Thus, given sufficient λ3, (3) is equal to(4)minX^,S,U,E2trX^LWX^T+λ1S∗+λ2E2,1+2λ3∑i=1cθiLUs.t.Z=S,X=XZ+E,Z=U,X^=XZ,diagU=0,U≥0,UT1=1.According to Ky Fan’s theorem [30], ∑i=1cθiLU is equivalent to minimizing TrFTLUF subject to FTF=I. Hence, we have(5)minX^,Z,S,E2trX^LWX^T+λ1S∗+λ2E2,1+2λ3TrFTLUFs.t.Z=S,X=XZ+E,Z=U,X^=XZ,FTF=I,diagU=0,U≥0,UT1=1.Following conventional practice, the augmented Lagrangian function of (5) is obtained as follows:(6)minX^,Z,S,E,U,F2trX^LWX^T+λ1S∗+λ2E2,1+2λ3TrFTLUF+Y1,Z−S+Y2,X−XZ−E+Y3,X^−XZ+Y4,Z−U+μ2Z−SF2+X−XZ−EF2+X^−XZF2+Z−UF2s.t.FTF=I,diagU=0,U≥0,UT1=1.At this point, the terms not connected in (6) are separated, where Y1, Y2, Y3, and Y4 are Lagrangian multipliers. Hence, each term’s optimal value is obtained in the following order.


### 3.2.1.X^ Problem

When other variables are fixed,X^ can be obtained by minimizing the following formula:(7)LX^=2trX^LWX^T+Y3,X^−XZ+μ2X^−XZF2.By setting the derivative ∂L (X^)/∂X^ = 0, variable X^ is obtained as follows:(8)4X^L+μX^−XZ+Y3=0,X^=μXZ−Y34L+μI−1.


### 3.2.2.Z Problem

When other variables are fixed,Z can be obtained by minimizing the following formula:(9)minZY1,Z−S+Y2,X−XZ−E+Y3,X^−XZ+Y4,Z−U+μ2Z−SF2+X−XZ−EF2+X^−XZ+Z−UF2.By setting the derivative ∂L (Z)/∂Z = 0, variable Z is obtained as follows:(10)Z=I+XTX−11/μXTY2+Y3−Y1+Y4/μ+S+U+XTX+XTX^−XTE2.


### 3.2.3.S Problem

S can be achieved by solving the following problem with other variables fixed(11)S=argminSλ1μS∗+12S−Z+Y1uF2.Then,S is obtained as follows by using the singular value thresholding (SVT) operator [31]:(12)S=Sλ1/μZ+Y1μ.


### 3.2.4.E Problem

E is obtained by solving the following minimization problem:(13)E=argminEλ2E2,1+μ2E−X−XZ+Y2uF2.DenoteT = X−XZ+1/uY2, τ=λ2/μ.Thei−th column of E is(14)E:,i=ti−τtiti,ifτ<ti,0,otherwise.


### 3.2.5.U Problem

U is obtained by solving the following minimization problem:(15)minU2λ3TrFTLUF+Y4,Z−U+μ2Z−UF2.For simplicity,∑i,jFi−Fj2Ui,j is equivalent to TrGTU, where Gij=Fi−Fj22; then, we rewrite (15) as(16)minUTrGTU+μ2U−Z+Y4μF2.DenotingN=Z+Y4/μ, we get(17)minUiUi−Ni−Gi/μ22s.t.diagU=0,U≥0,UT1=1.Considering the previously mentioned constraints, we have the following:(18)minUi∑jUi−Ni−Gi/μ2λ422−η1TUi−1−ζTUis.t.Uii=0.Then, taking the derivative with respect toUi and setting it to zero, that is,(19)Ui−1Ni−Gi/μ2λ4−η1−ζ=0.Thej entry of Ui is shown as follows:(20)Uij−Nij−Gij/μ2λ4−η−ζi=0.According to KKT conditions,(21)Uij=Nij−Gij/μ2λ3+η+.


### 3.2.6.F Problem

When other variables are fixed,F can be obtained by solving the following minimization problem:(22)LF=minFTrFTLUFs.t.FTF=I,where LU is the Laplacian matrix of U. This problem can be simply solved via eigenvalue decomposition, and its solutions are the set of c eigenvectors corresponding to the first c smallest eigenvalues of LU.The complete solution is given in Algorithm 1.Algorithm 1: The proposed algorithm.
Input: Data X, clusters size c, parameter λ1, λ2,λ3Initialize:X^=Z=S=E=U=F=0,Y1=0,Y2=0,Y3=0,Y4=0,; ρ=1.01; μ=0.01; μmax =  108; ϵ=10−5;While not converged do(1)
UpdateX^ by equation (8);(2)
UpdateZ by equation (10);(3)
UpdateS by equation (12);(4)
UpdateE by equation (14);(5)
UpdateU by equation (21);(6)
UpdateF by equation (22);Y1=Y1+μZ−SY2=Y2+μX−XZ−EY3=Y3+μX^−XZY4=Y4+μZ−U(11)
Updateμ by μ=minρμ,maxμ(12)
Check the convergence conditions:Z−S∞<ϵ,X−XZ−E∞<ϵ, X^−XZ∞<ϵ and Z−U∞<ϵOutput:U


## 3.2.1.X^ Problem

When other variables are fixed,X^ can be obtained by minimizing the following formula:(7)LX^=2trX^LWX^T+Y3,X^−XZ+μ2X^−XZF2.By setting the derivative ∂L (X^)/∂X^ = 0, variable X^ is obtained as follows:(8)4X^L+μX^−XZ+Y3=0,X^=μXZ−Y34L+μI−1.


## 3.2.2.Z Problem

When other variables are fixed,Z can be obtained by minimizing the following formula:(9)minZY1,Z−S+Y2,X−XZ−E+Y3,X^−XZ+Y4,Z−U+μ2Z−SF2+X−XZ−EF2+X^−XZ+Z−UF2.By setting the derivative ∂L (Z)/∂Z = 0, variable Z is obtained as follows:(10)Z=I+XTX−11/μXTY2+Y3−Y1+Y4/μ+S+U+XTX+XTX^−XTE2.


## 3.2.3.S Problem

S can be achieved by solving the following problem with other variables fixed(11)S=argminSλ1μS∗+12S−Z+Y1uF2.Then,S is obtained as follows by using the singular value thresholding (SVT) operator [31]:(12)S=Sλ1/μZ+Y1μ.


## 3.2.4.E Problem

E is obtained by solving the following minimization problem:(13)E=argminEλ2E2,1+μ2E−X−XZ+Y2uF2.DenoteT = X−XZ+1/uY2, τ=λ2/μ.Thei−th column of E is(14)E:,i=ti−τtiti,ifτ<ti,0,otherwise.


## 3.2.5.U Problem

U is obtained by solving the following minimization problem:(15)minU2λ3TrFTLUF+Y4,Z−U+μ2Z−UF2.For simplicity,∑i,jFi−Fj2Ui,j is equivalent to TrGTU, where Gij=Fi−Fj22; then, we rewrite (15) as(16)minUTrGTU+μ2U−Z+Y4μF2.DenotingN=Z+Y4/μ, we get(17)minUiUi−Ni−Gi/μ22s.t.diagU=0,U≥0,UT1=1.Considering the previously mentioned constraints, we have the following:(18)minUi∑jUi−Ni−Gi/μ2λ422−η1TUi−1−ζTUis.t.Uii=0.Then, taking the derivative with respect toUi and setting it to zero, that is,(19)Ui−1Ni−Gi/μ2λ4−η1−ζ=0.Thej entry of Ui is shown as follows:(20)Uij−Nij−Gij/μ2λ4−η−ζi=0.According to KKT conditions,(21)Uij=Nij−Gij/μ2λ3+η+.


## 3.2.6.F Problem

When other variables are fixed,F can be obtained by solving the following minimization problem:(22)LF=minFTrFTLUFs.t.FTF=I,where LU is the Laplacian matrix of U. This problem can be simply solved via eigenvalue decomposition, and its solutions are the set of c eigenvectors corresponding to the first c smallest eigenvalues of LU.The complete solution is given in Algorithm 1.Algorithm 1: The proposed algorithm.
Input: Data X, clusters size c, parameter λ1, λ2,λ3Initialize:X^=Z=S=E=U=F=0,Y1=0,Y2=0,Y3=0,Y4=0,; ρ=1.01; μ=0.01; μmax =  108; ϵ=10−5;While not converged do(1)
UpdateX^ by equation (8);(2)
UpdateZ by equation (10);(3)
UpdateS by equation (12);(4)
UpdateE by equation (14);(5)
UpdateU by equation (21);(6)
UpdateF by equation (22);Y1=Y1+μZ−SY2=Y2+μX−XZ−EY3=Y3+μX^−XZY4=Y4+μZ−U(11)
Updateμ by μ=minρμ,maxμ(12)
Check the convergence conditions:Z−S∞<ϵ,X−XZ−E∞<ϵ, X^−XZ∞<ϵ and Z−U∞<ϵOutput:U


## 3.3. Computational Complexity

The inverse of a matrix, eigen decomposition, and SVT's nuclear norm minimization problem are three key aspects that define the computing cost of our proposed algorithm. Specifically, the eigen decomposition costsOn2c, where c is the number of clusters. The inverse of a matrix and nuclear norm minimization cost is On3 each. As a result, the total computational complexity of each iteration is On3+2n2c because the cost of computing multipliers and basic matrix operations like addition, subtraction, and division are negligible compared with the cost of other operations.


## 4. Experiments

### 4.1. Experimental Settings

In order to demonstrate the effectiveness of the proposed method, several experiments were performed on COIL20 (https://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php), UCI (https://archive.ics.uci.edu/ml/datasets/Optical+Recognition+of+Handwritten+Digits), ORL (http://cam-orl.co.uk/facedatabase.html), FERET (https://www.nist.gov/itl/products-and-services/color-FERET-database), and BBC (http://mlg.ucd.ie/datasets/segment.html) datasets (See Table 1 for a summary of each dataset and Figure 1 for images of some datasets). Thus, using accuracy (ACC), normalized mutual information (NMI), and purity (PUR) metrics, the performance of the proposed method was evaluated in comparison with Kmeans, LapLRR [9], GraphSC [4], GNMF [5], LRR_AGR [11], and nonnegative self-representation (NSFRC) [32] state-of-the-art methods. For each method, the parameter settings in the corresponding literature were adopted. Therefore, each of these methods are described as follows.LapLRR [9]: it uses LRR’s nuclear norm strategy to capture data’s intrinsic nonlinear geometric informationGraphSC [4]: it considers the local manifold structure of the data to learn a sparse representationGNMF [5]: it constructs an affinity graph to encode the geometrical information of dataLRR-AGR [11]: it learns optimal clustering by considering the local data structure that LRR previously ignoredNSFRC [32]: it uncovers data’s intrinsic structure by joint nonnegative self-representation and adaptive distance regularizationTable 1
Summary of the datasets.
DatasetClassDimensionNumber of samplesCOIL202010241440UCI102402000ORL404096400FERET20010241400BBC54659685Figure 1
Example images of (a) ORL, (b) FERET, and (c) UCI datasets.
(a)(b)(c)


### 4.2. Experimental Results

This section analyzes the results of various experiments conducted to evaluate the proposed method’s effectiveness. Note that the best results are highlighted in bold fonts in the tables


#### 4.2.1. Clustering Performance on Original Data

Tables2–6 display the clustering results concerning ACC, NMI, and PUR of different algorithms on COIL20, UCI, ORL, FERET, and BBC benchmark datasets, respectively. On COIL20 dataset, the proposed method has the best result in all evaluation metrics, followed closely by NSFRC in ACC and LRR_AGR in NMI. This performance is not surprising because LRR_AGR considers the local data structure of the data to improve its performance, while NSFRC, on the other hand, uses an adaptive affinity matrix learning approach to uncover the intrinsic structure of data to boost clustering performance. Besides, it is also not shocking that Kmeans has the worst performance on COIL20 dataset because it performs clustering directly on the original data, promoting noise interference on the clustering structure. Furthermore, one may observe that Kmeans has its best performance on the UCI dataset compared to other datasets. However, its performance is far below that of others methods, especially the proposed method and NSFRC. It can also be observed that NSFRC and LRR_AGR performances are consistently close to the proposed method on ORL, FERET, and BBC datasets. Specifically, on ORL datasets, both NSFRC and LRR_AGR have a performance of 85.45% and 81.45%, respectively, in ACC, which is lesser than that of the proposed method with 1.28% and 5.28%, respectively. This performance is also maintained in the relatively difficult datasets of FERET and BBC. Overall, the proposed method has more excellent performance to demonstrate the effectiveness of the regularization term in our model.Table 2
Clustering results of different algorithms on Coil 20 dataset.
ACCNMIPURKmeans67.7883.4778.91LapLRR66.0679.1482.23GraphSC82.1292.0579.51GNMF81.6390.3182.03LRR_AGR85.1295.3385.14NSFRC88.5693.1287.67Proposed method88.7094.3988.47Table 3
Clustering results of different algorithms on UCI dataset.
ACCNMIPURKmeans75.5872.7158.44LapLRR81.7378.9272.11GraphSC80.1281.5681.58GNMF82.1279.9682.72LRR_AGR82.7783.5286.47NSFRC83.2188.5688.71Proposed method85.5390.3687.05Table 4
Clustering results of different algorithms on ORL dataset.
ACCNMIPURKmeans48.9534.5113.63LapLRR71.7758.5153.13GraphSC78.9270.4365.56GNMF78.0672.7369.31LRR_AGR81.4575.4571.22NSFRC85.4574.1272.34Proposed method86.7375.6173.87Table 5
Clustering results of different algorithms on FERET dataset.
ACCNMIPURKmeans43.2322.7130.38LapLRR55.1342.9452.73GraphSC49.3444.1550.66GNMF55.3049.2853.31LRR_AGR60.6653.2352.34NSFRC61.9652.8752.15Proposed method63.2853.7753.52Table 6
Clustering results of different algorithms on BBC dataset.
ACCNMIPURKmeans38.1210.9115.66LapLRR55.1231.5537.83GraphSC60.2744.6238.91GNMF59.6543.9245.08LRR_AGR61.2347.1236.12NSFRC53.6745.2341.97Proposed method62.1348.2342.39


#### 4.2.2. Clustering Performance on Data Corrupted with Pepper Noise and Stripe Occlusion

In this section, several experiments are performed to evaluate the robustness of each algorithm against noise and occlusion. To perform this experiment, two settings were adopted. First, stripe occlusion of various degrees (0, 5%, 10%, and 15%) were randomly applied to ORL and FERET datasets. Second, pepper noise of various degrees (the same as previously mentioned) were randomly applied to the UCI dataset. Therefore, Figures2–4 present each algorithm’s performance on corrupted ORL, FERET, and UCI datasets, respectively. Although it can be seen clearly from these figures that all methods have performance degradation as the corruption level increases, our proposed method shows more robustness than other methods on the three datasets. More specifically, the proposed method’s performance maintained a steadier drop on the ORL dataset than a sharp one obtained by the NSFRC method in the ACC evaluation metric. It can also be observed that its performance in NMI is better with a 10% degree of stripe occlusion than in the 5% case, which confirms that the proposed method can guarantee superior robustness to a large extent. Besides, its performance on the UCI dataset under the random pepper noise corruption further validate above with a clear improvement over the other compared methods.Figure 2
Clustering performances of different algorithms on corrupted ORL dataset.Figure 3
Clustering performances of different algorithm on corrupted FERET dataset.Figure 4
Clustering performances of different algorithm on corrupted UCI dataset.


### 4.3. Parameter Sensitivity

This section uses some experiments to show the sensitivity of parameters concerning clustering ACC of the proposed method. We can find that there are three regularization parameters, that is,λ1λ2, and λ3, needed to be set in advance. These parameters, respectively, balance the importance of low-rank constraint term, error term, and rank constraint. Generally, the larger the parameter value is, the more important or impact the corresponding term is. To demonstrate the effects of these three parameters for data clustering, a candidate parameter range set of 10−3,10−2,10−1,1,10+1,10+2 is first defined for the three parameters, and then, the proposed method is performed with different combinations of the parameters for data clustering. We first fixed parameters λ1 and λ2 and then executed the proposed method with different parameter values of λ3 to show the influence on the clustering ACC.From Figure5, it is obvious to see that the clustering ACC is insensitive to parameter λ3 when λ3≤0.01. This is mainly because if parameter λ3 is too large, the corresponding rank constraint term will play the dominant role in the graph learning while ignoring the local and global structure preservation. In this case, although the obtained graph still has corresponding connected components, it cannot reveal the intrinsic structure of data. In the experiments, we can select a small value in the range of 10−3,10−2,10−1 for parameter λ3. Figure 6 shows the clustering ACC versus different values of parameters λ1 and λ2 when parameter λ3 is fixed. As shown in this figure, the clustering ACC is sensitive to parameter λ2 to some extent, and the best clustering result can be obtained when parameters λ1 and λ2 are in a feasible range. This is mainly because a very large or very small parameter λ2 leads to a small error or large error that cannot compensate well for the sparse data noise. In this case, the model cannot learn the intrinsic similarity graph for data clustering. Thus, in the experiments, we can select the two parameters in the candidate range of 10−1,1,10,10+2 according to the degree of noise corruptions of data.Figure 5
The parameter study ofλ3 on COIL20 and ORL.Figure 6
The parameter study ofλ2andλ3 on COIL20 and ORL.As far as we know, it is still an open problem to adaptively select these optimal parameters for different datasets. In the experiments, we first fix parameterλ3 since this parameter is insensitive to the clustering ACC and then perform the method to find the optimalλ1 and λ2 in a candidate domain where the optimal parameters may exist. Then, by a similar strategy, we fix parameters λ1 and λ2 to find the optimal value of parameter λ3 in a candidate domain. Finally, the optimal combination of these parameters can be obtained in the 3D candidate space, composed of three candidate domains of parameters.


### 4.4. Convergence Study

The convergence of the ADMM-style algorithm with two blocks has been generally proven in [29]. There are six blocks (including X^,Z,S,E,U,F) in Algorithm 1, and the objective function is not smooth; it would not be easy to prove the convergence in theory. For X^, Z, and U, their subproblems have clear analytical solutions. With continuous iteration, they can be expected to reach the optimal solution. The subproblems of F can be solved by solving the characteristic equations. For the S subproblem, the SVT [33, 34] method is used to solve it. For the E subproblem, the effectiveness and convergence of the solution have also been confirmed [35]. Therefore, we can expect the algorithm to reach a local optimal solution. In Figure 7, we further verify the algorithm's convergence on the actual dataset.Figure 7
The convergence curve of the proposed method on COIL20 and ORL.Furthermore, Table7 lists each method’s average computation runtime on three benchmark datasets. According to the record, it can be observed that although the computational time of the proposed method is not the most efficient, it is at the same level as most methods.Table 7
Computation time (in seconds) of each method on three benchmark datasets. The experiments are conducted on an eight-core windows with each core’s CPU at 4.2 GHz; the total memory is 16 G.
COIL20UCIBBCKmeans7.183.726.41LapLRR92.1363.5775.93GraphSC53.5432.1842.42GNMF78.4958.8168.35LRR_AGR77.2165.5172.61NSFRC120.1587.5281.64Proposed method88.9367.5973.46


## 4.1. Experimental Settings

In order to demonstrate the effectiveness of the proposed method, several experiments were performed on COIL20 (https://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php), UCI (https://archive.ics.uci.edu/ml/datasets/Optical+Recognition+of+Handwritten+Digits), ORL (http://cam-orl.co.uk/facedatabase.html), FERET (https://www.nist.gov/itl/products-and-services/color-FERET-database), and BBC (http://mlg.ucd.ie/datasets/segment.html) datasets (See Table 1 for a summary of each dataset and Figure 1 for images of some datasets). Thus, using accuracy (ACC), normalized mutual information (NMI), and purity (PUR) metrics, the performance of the proposed method was evaluated in comparison with Kmeans, LapLRR [9], GraphSC [4], GNMF [5], LRR_AGR [11], and nonnegative self-representation (NSFRC) [32] state-of-the-art methods. For each method, the parameter settings in the corresponding literature were adopted. Therefore, each of these methods are described as follows.LapLRR [9]: it uses LRR’s nuclear norm strategy to capture data’s intrinsic nonlinear geometric informationGraphSC [4]: it considers the local manifold structure of the data to learn a sparse representationGNMF [5]: it constructs an affinity graph to encode the geometrical information of dataLRR-AGR [11]: it learns optimal clustering by considering the local data structure that LRR previously ignoredNSFRC [32]: it uncovers data’s intrinsic structure by joint nonnegative self-representation and adaptive distance regularizationTable 1
Summary of the datasets.
DatasetClassDimensionNumber of samplesCOIL202010241440UCI102402000ORL404096400FERET20010241400BBC54659685Figure 1
Example images of (a) ORL, (b) FERET, and (c) UCI datasets.
(a)(b)(c)


## 4.2. Experimental Results

This section analyzes the results of various experiments conducted to evaluate the proposed method’s effectiveness. Note that the best results are highlighted in bold fonts in the tables


### 4.2.1. Clustering Performance on Original Data

Tables2–6 display the clustering results concerning ACC, NMI, and PUR of different algorithms on COIL20, UCI, ORL, FERET, and BBC benchmark datasets, respectively. On COIL20 dataset, the proposed method has the best result in all evaluation metrics, followed closely by NSFRC in ACC and LRR_AGR in NMI. This performance is not surprising because LRR_AGR considers the local data structure of the data to improve its performance, while NSFRC, on the other hand, uses an adaptive affinity matrix learning approach to uncover the intrinsic structure of data to boost clustering performance. Besides, it is also not shocking that Kmeans has the worst performance on COIL20 dataset because it performs clustering directly on the original data, promoting noise interference on the clustering structure. Furthermore, one may observe that Kmeans has its best performance on the UCI dataset compared to other datasets. However, its performance is far below that of others methods, especially the proposed method and NSFRC. It can also be observed that NSFRC and LRR_AGR performances are consistently close to the proposed method on ORL, FERET, and BBC datasets. Specifically, on ORL datasets, both NSFRC and LRR_AGR have a performance of 85.45% and 81.45%, respectively, in ACC, which is lesser than that of the proposed method with 1.28% and 5.28%, respectively. This performance is also maintained in the relatively difficult datasets of FERET and BBC. Overall, the proposed method has more excellent performance to demonstrate the effectiveness of the regularization term in our model.Table 2
Clustering results of different algorithms on Coil 20 dataset.
ACCNMIPURKmeans67.7883.4778.91LapLRR66.0679.1482.23GraphSC82.1292.0579.51GNMF81.6390.3182.03LRR_AGR85.1295.3385.14NSFRC88.5693.1287.67Proposed method88.7094.3988.47Table 3
Clustering results of different algorithms on UCI dataset.
ACCNMIPURKmeans75.5872.7158.44LapLRR81.7378.9272.11GraphSC80.1281.5681.58GNMF82.1279.9682.72LRR_AGR82.7783.5286.47NSFRC83.2188.5688.71Proposed method85.5390.3687.05Table 4
Clustering results of different algorithms on ORL dataset.
ACCNMIPURKmeans48.9534.5113.63LapLRR71.7758.5153.13GraphSC78.9270.4365.56GNMF78.0672.7369.31LRR_AGR81.4575.4571.22NSFRC85.4574.1272.34Proposed method86.7375.6173.87Table 5
Clustering results of different algorithms on FERET dataset.
ACCNMIPURKmeans43.2322.7130.38LapLRR55.1342.9452.73GraphSC49.3444.1550.66GNMF55.3049.2853.31LRR_AGR60.6653.2352.34NSFRC61.9652.8752.15Proposed method63.2853.7753.52Table 6
Clustering results of different algorithms on BBC dataset.
ACCNMIPURKmeans38.1210.9115.66LapLRR55.1231.5537.83GraphSC60.2744.6238.91GNMF59.6543.9245.08LRR_AGR61.2347.1236.12NSFRC53.6745.2341.97Proposed method62.1348.2342.39


### 4.2.2. Clustering Performance on Data Corrupted with Pepper Noise and Stripe Occlusion

In this section, several experiments are performed to evaluate the robustness of each algorithm against noise and occlusion. To perform this experiment, two settings were adopted. First, stripe occlusion of various degrees (0, 5%, 10%, and 15%) were randomly applied to ORL and FERET datasets. Second, pepper noise of various degrees (the same as previously mentioned) were randomly applied to the UCI dataset. Therefore, Figures2–4 present each algorithm’s performance on corrupted ORL, FERET, and UCI datasets, respectively. Although it can be seen clearly from these figures that all methods have performance degradation as the corruption level increases, our proposed method shows more robustness than other methods on the three datasets. More specifically, the proposed method’s performance maintained a steadier drop on the ORL dataset than a sharp one obtained by the NSFRC method in the ACC evaluation metric. It can also be observed that its performance in NMI is better with a 10% degree of stripe occlusion than in the 5% case, which confirms that the proposed method can guarantee superior robustness to a large extent. Besides, its performance on the UCI dataset under the random pepper noise corruption further validate above with a clear improvement over the other compared methods.Figure 2
Clustering performances of different algorithms on corrupted ORL dataset.Figure 3
Clustering performances of different algorithm on corrupted FERET dataset.Figure 4
Clustering performances of different algorithm on corrupted UCI dataset.


## 4.2.1. Clustering Performance on Original Data

Tables2–6 display the clustering results concerning ACC, NMI, and PUR of different algorithms on COIL20, UCI, ORL, FERET, and BBC benchmark datasets, respectively. On COIL20 dataset, the proposed method has the best result in all evaluation metrics, followed closely by NSFRC in ACC and LRR_AGR in NMI. This performance is not surprising because LRR_AGR considers the local data structure of the data to improve its performance, while NSFRC, on the other hand, uses an adaptive affinity matrix learning approach to uncover the intrinsic structure of data to boost clustering performance. Besides, it is also not shocking that Kmeans has the worst performance on COIL20 dataset because it performs clustering directly on the original data, promoting noise interference on the clustering structure. Furthermore, one may observe that Kmeans has its best performance on the UCI dataset compared to other datasets. However, its performance is far below that of others methods, especially the proposed method and NSFRC. It can also be observed that NSFRC and LRR_AGR performances are consistently close to the proposed method on ORL, FERET, and BBC datasets. Specifically, on ORL datasets, both NSFRC and LRR_AGR have a performance of 85.45% and 81.45%, respectively, in ACC, which is lesser than that of the proposed method with 1.28% and 5.28%, respectively. This performance is also maintained in the relatively difficult datasets of FERET and BBC. Overall, the proposed method has more excellent performance to demonstrate the effectiveness of the regularization term in our model.Table 2
Clustering results of different algorithms on Coil 20 dataset.
ACCNMIPURKmeans67.7883.4778.91LapLRR66.0679.1482.23GraphSC82.1292.0579.51GNMF81.6390.3182.03LRR_AGR85.1295.3385.14NSFRC88.5693.1287.67Proposed method88.7094.3988.47Table 3
Clustering results of different algorithms on UCI dataset.
ACCNMIPURKmeans75.5872.7158.44LapLRR81.7378.9272.11GraphSC80.1281.5681.58GNMF82.1279.9682.72LRR_AGR82.7783.5286.47NSFRC83.2188.5688.71Proposed method85.5390.3687.05Table 4
Clustering results of different algorithms on ORL dataset.
ACCNMIPURKmeans48.9534.5113.63LapLRR71.7758.5153.13GraphSC78.9270.4365.56GNMF78.0672.7369.31LRR_AGR81.4575.4571.22NSFRC85.4574.1272.34Proposed method86.7375.6173.87Table 5
Clustering results of different algorithms on FERET dataset.
ACCNMIPURKmeans43.2322.7130.38LapLRR55.1342.9452.73GraphSC49.3444.1550.66GNMF55.3049.2853.31LRR_AGR60.6653.2352.34NSFRC61.9652.8752.15Proposed method63.2853.7753.52Table 6
Clustering results of different algorithms on BBC dataset.
ACCNMIPURKmeans38.1210.9115.66LapLRR55.1231.5537.83GraphSC60.2744.6238.91GNMF59.6543.9245.08LRR_AGR61.2347.1236.12NSFRC53.6745.2341.97Proposed method62.1348.2342.39


## 4.2.2. Clustering Performance on Data Corrupted with Pepper Noise and Stripe Occlusion

In this section, several experiments are performed to evaluate the robustness of each algorithm against noise and occlusion. To perform this experiment, two settings were adopted. First, stripe occlusion of various degrees (0, 5%, 10%, and 15%) were randomly applied to ORL and FERET datasets. Second, pepper noise of various degrees (the same as previously mentioned) were randomly applied to the UCI dataset. Therefore, Figures2–4 present each algorithm’s performance on corrupted ORL, FERET, and UCI datasets, respectively. Although it can be seen clearly from these figures that all methods have performance degradation as the corruption level increases, our proposed method shows more robustness than other methods on the three datasets. More specifically, the proposed method’s performance maintained a steadier drop on the ORL dataset than a sharp one obtained by the NSFRC method in the ACC evaluation metric. It can also be observed that its performance in NMI is better with a 10% degree of stripe occlusion than in the 5% case, which confirms that the proposed method can guarantee superior robustness to a large extent. Besides, its performance on the UCI dataset under the random pepper noise corruption further validate above with a clear improvement over the other compared methods.Figure 2
Clustering performances of different algorithms on corrupted ORL dataset.Figure 3
Clustering performances of different algorithm on corrupted FERET dataset.Figure 4
Clustering performances of different algorithm on corrupted UCI dataset.


## 4.3. Parameter Sensitivity

This section uses some experiments to show the sensitivity of parameters concerning clustering ACC of the proposed method. We can find that there are three regularization parameters, that is,λ1λ2, and λ3, needed to be set in advance. These parameters, respectively, balance the importance of low-rank constraint term, error term, and rank constraint. Generally, the larger the parameter value is, the more important or impact the corresponding term is. To demonstrate the effects of these three parameters for data clustering, a candidate parameter range set of 10−3,10−2,10−1,1,10+1,10+2 is first defined for the three parameters, and then, the proposed method is performed with different combinations of the parameters for data clustering. We first fixed parameters λ1 and λ2 and then executed the proposed method with different parameter values of λ3 to show the influence on the clustering ACC.From Figure5, it is obvious to see that the clustering ACC is insensitive to parameter λ3 when λ3≤0.01. This is mainly because if parameter λ3 is too large, the corresponding rank constraint term will play the dominant role in the graph learning while ignoring the local and global structure preservation. In this case, although the obtained graph still has corresponding connected components, it cannot reveal the intrinsic structure of data. In the experiments, we can select a small value in the range of 10−3,10−2,10−1 for parameter λ3. Figure 6 shows the clustering ACC versus different values of parameters λ1 and λ2 when parameter λ3 is fixed. As shown in this figure, the clustering ACC is sensitive to parameter λ2 to some extent, and the best clustering result can be obtained when parameters λ1 and λ2 are in a feasible range. This is mainly because a very large or very small parameter λ2 leads to a small error or large error that cannot compensate well for the sparse data noise. In this case, the model cannot learn the intrinsic similarity graph for data clustering. Thus, in the experiments, we can select the two parameters in the candidate range of 10−1,1,10,10+2 according to the degree of noise corruptions of data.Figure 5
The parameter study ofλ3 on COIL20 and ORL.Figure 6
The parameter study ofλ2andλ3 on COIL20 and ORL.As far as we know, it is still an open problem to adaptively select these optimal parameters for different datasets. In the experiments, we first fix parameterλ3 since this parameter is insensitive to the clustering ACC and then perform the method to find the optimalλ1 and λ2 in a candidate domain where the optimal parameters may exist. Then, by a similar strategy, we fix parameters λ1 and λ2 to find the optimal value of parameter λ3 in a candidate domain. Finally, the optimal combination of these parameters can be obtained in the 3D candidate space, composed of three candidate domains of parameters.


## 4.4. Convergence Study

The convergence of the ADMM-style algorithm with two blocks has been generally proven in [29]. There are six blocks (including X^,Z,S,E,U,F) in Algorithm 1, and the objective function is not smooth; it would not be easy to prove the convergence in theory. For X^, Z, and U, their subproblems have clear analytical solutions. With continuous iteration, they can be expected to reach the optimal solution. The subproblems of F can be solved by solving the characteristic equations. For the S subproblem, the SVT [33, 34] method is used to solve it. For the E subproblem, the effectiveness and convergence of the solution have also been confirmed [35]. Therefore, we can expect the algorithm to reach a local optimal solution. In Figure 7, we further verify the algorithm's convergence on the actual dataset.Figure 7
The convergence curve of the proposed method on COIL20 and ORL.Furthermore, Table7 lists each method’s average computation runtime on three benchmark datasets. According to the record, it can be observed that although the computational time of the proposed method is not the most efficient, it is at the same level as most methods.Table 7
Computation time (in seconds) of each method on three benchmark datasets. The experiments are conducted on an eight-core windows with each core’s CPU at 4.2 GHz; the total memory is 16 G.
COIL20UCIBBCKmeans7.183.726.41LapLRR92.1363.5775.93GraphSC53.5432.1842.42GNMF78.4958.8168.35LRR_AGR77.2165.5172.61NSFRC120.1587.5281.64Proposed method88.9367.5973.46


## 5. Conclusion

A novel method is proposed in this study that injects a regularization term into LRR to ensure that the neighborhood structure of data samples in the original high-dimensional space is also maintained in the low-dimensional space. With this strategy, the proposed method guarantees robust clustering performance that resolves the limitation of most existing methods. This fact is demonstrated experimentally, with several results showing that the proposed method substantially outperformed similar state-of-the-art methods in ACC, NMI, and PUR evaluation metrics. Thus, our approach will be extended to multiview learning in future work based on several works [36], which shows that it can improve single view learning models.



---

*Source: 7540956-2022-04-29.xml*