# A Folded Concave Penalty Regularized Subspace Clustering Method to Integrate Affinity and Clustering

Authors: Wenjuan Zhang; Xiangchu Feng; Feng Xiao; Yunmei Chen
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Most sparse or low-rank-based subspace clustering methods divide the processes of getting the affinity matrix and the final clustering result into two independent steps. We propose to integrate the affinity matrix and the data labels into a minimization model. Thus, they can interact and promote each other and finally improve clustering performance. Furthermore, the block diagonal structure of the representation matrix is most preferred for subspace clustering. We define a folded concave penalty (FCP) based norm to approximate rank function and apply it to the combination of label matrix and representation vector. This FCP-based regularization term can enforce the block diagonal structure of the representation matrix effectively. We minimize the difference ofl1 norm and l2 norm of the label vector to make it have only one nonzero element since one data only belong to one subspace. The index of that nonzero element is associated with the subspace from which the data come and can be determined by a variant of graph Laplacian regularization. We conduct experiments on several popular datasets. The results show our method has better clustering results than several state-of-the-art methods.


---

## Body

## 1. Introduction

In machine learning and data mining, clustering is one of the most important topics in unsupervised learning. Given a set of data points, clustering is to partition these points into several groups, with each of which called a cluster, such that data points in the same group have higher similarities than those in different groups. In the past decades, an enormous number of clustering algorithms have been proposed, such as K-means and its variants [1, 2], spectral clustering [3], nonnegative matrix factorization (NMF) [4], and subspace clustering [5]. In this paper, we focus on the methods of subspace clustering.Contemporary is the era of high-dimensional data explosion. However, there is redundancy information included in those high-dimensional data so that their intrinsic dimension is often much smaller. In many computer vision and machine learning problems, one often assumes that the data are drawn from a union of multiple low-dimensional linear subspaces. Thus, subspace clustering of such data has been studied extensively. Nowadays, many works proposed the assumption of linear subspace may not always be true for many real high-dimensional data. The proposed data may be better modeled by nonlinear manifolds [6–8]. The common strategy employed in these works is to use the logarithm mapping projecting data onto the tangent space at each data point which is a linear space, so that all the strategies applicable to linear space can be used. These methods finally still need to establish a model in linear space. Therefore, research of modeling methods in linear space is still essential. The existing methods for subspace clustering can be roughly divided into four groups: statistical learning-based methods, factorization-based methods, algebra-based methods, and sparsity-based methods (e.g., Sparse Subspace Clustering (SSC) [9] and Low-Rank Representation (LRR)) [10]. In this paper, we focus on the fourth group.In recent years, a lot of methods basing on deep learning [11] have been proposed. These methods obtained extremely competitive results in many fields on image and computer vision. A discussion hot point in computational imaging is if it is time to discard the classic methods and fully replace them with deep learning-based methods. On the one hand, a prerequisite for deep learning-based methods is a huge number of samples. However, there exist some situations where no data or only a small number of data can be obtained. In this case, the knowledge-based modeling methods are more suitable. On the other hand, classic methods have a clear structure and theoretical guarantee. They are based on the knowledge of the problem we are trying to solve rather than seeking for best performance by intuitively choosing architectures or trial and error. To the best of our knowledge, most of the existing learning-based clustering methods only learn some autoencoder features [12]. The final clustering is still obtained by applying k-means or SSC. Another challenge for deep learning is that a clustering model trained from some datasets may not be effective for other sets, but classic methods have better generalization ability.LetX=x1,x2,…,xn∈Rm×nm<n be a collection of m-dimensional data drawn from the union of linear subspaces Sii=1c. Each Si includes ni data of X. The task of subspace clustering is to cluster the data in X according to those independent subspaces. For each j∈1,2,…,n, consider the data xj as a linear combination of all data in X, i.e., xj=Xzj, here zj=Zkjk=1n is called a representation vector, we assume Zjj=0 to avoid the trivial solution. Suppose xj∈Sii∈1,2,…,c, then only the coefficients associated with the data from Si are not zero, and the others are all zero. Assuming Aj=k:Zkj≠0, we want to find the solution to the following problem:(1)argminzj∈Rn:Zkj=0k∈Ajc,Zjj=0xj−Xzj22,j=1,2,…,n.which means to find the oracle solution [9].According to the above statement, there must be at least one matrixZ=Zijn×n∈Rn×n satisfying(2)X=XZ,s.t.Zjj=0j=1,2,…,n.Equation (2) actually has an infinite amount of solutions. Any solution is called a representation matrix. When handling 2D data, with each data being a matrix, [13] shows the strategy of converting all data to vectors severely damages inherent structural information and correlations of the original data. They proposed to learn a 2D projection matrix such that the most expressive structural information is retained in the spanned subspace. In our work, we still consider the vectorized data for simplicity since our method is also suitable for the projected vectorized data, and it is not within the scope of this paper to discuss how to deal with 2D data.A good representation matrix should have the properties of sparsity between subspaces and density within a subspace, which means each query dataxj is represented by a small number of subspaces, and once one subspace is selected, it is in favor of using more data from the same subspace. The work of [14] introduced a family of new regression models and estimated a representation model while accounting for discriminativeness between clusters. Here we achieve this property of the representation matrix by forcing it to have block diagonal structure since the block diagonal structure of Z directly induces a segmentation of the data (each block corresponds to a cluster). Reference [15] stated that under the ideal conditions, i.e., the data are noiseless and the subspaces are independent (i.e., none of the subspaces can be represented by other subspaces), as long as the regularizer for Z satisfies the EBD (Enforced Block Diagonal) conditions, and the optimal representation matrix is block diagonal. However, as X contains noise, which is inevitable in any application, Z may not be a strict block diagonal matrix. Therefore, it is difficult to decide how large the representation coefficient between two data should be to group them into the same subspace. Usually, many previous subspace clustering methods are to find a matrix Z firstly; then using Z+Z′/2 as an affinity matrix, the spectral clustering such as normalized cuts can be applied to get the subspace clustering result, just as the classic SSC and LRR and many other variants thereafter have done. All these methods divide the solution of the representation matrix and the final clustering result into two independent steps. We propose to integrate the affinity matrix and the data labels into a model to make them interact and promote each other and finally improve the clustering performance.Furthermore, in terms of the penalty for representation matrixZ, most methods based on SSC and LRR seek Z with the most sparse or lowest rank constraint. In fact, for subspace clustering, it is more important for Z to have block diagonal structure than to be the most sparse or lowest rank matrix. We give a low-rank-based regularization term to enforce the block diagonal structure of Z directly. This regularization term is applied to a combination of the semisupervised label matrix and representation vector zj other than Z. Note that the rank function of a matrix is the l0-norm of the singular value vector and solving such a l0 minimization problem is usually difficult or even NP-hard. The standard approach is to replace the rank function with the convex nuclear norm [16, 17]. It has been proved that under certain incoherence assumptions on the singular values of the matrix, solving the convex nuclear norm regularized problem leads to a near-optimal low-rank solution [18]. On the other hand, it is pointed out that the nuclear norm is not accurate for rank approximation. Recent works develop various more accurate approximations to the rank function, such as the log-determinant rank approximation [19, 20], which significantly improves the learning performance. In addition, the nuclear norm of a matrix is the l1-norm of the singular values vectors. Fan and Li pointed out that l1-norm penalty overpenalizes large entries of vectors; therefore, nuclear norm overpenalizes large singular values. Moreover, they proposed three criteria for good penalty functions [21]: unbiasedness, sparsity, and continuity at the origin. The l1-norm satisfies both sparsity and continuity, but it is biased.Recently, nonconvex penalties have drawn more and more attention to sparse learning problems because people believe that one of the possible solutions of nonconvex penalization problem could overcome the drawbacks of the unique solution of convex penalization problem. As a common practice, thel1-norm can be replaced by the lq-norm with 0<q<1 if a more sparse solution is expected to be obtained [22, 23]. However, no theoretical guarantee with lq-norm is made for reducing the modeling bias of l1-norm. Based on those three properties proposed by Fan and Li, they proposed a new penalty function called the smoothly clipped absolute deviation penalty (SCAD) [21]. Recently, Zhang proved that a so-called min-max concave plus (MCP) penalty [24] also possesses three properties and achieves better performance than SCAD. Both SCAD and MCP are nonconvex and nearly unbiased. Extensive experiments [21, 24–30] have demonstrated the superiority of SCAD and MCP over the l1-norm penalty. Furthermore, folded concave penalty (FCP) methods, including SCAD and MCP, have been shown to have strong oracle property for high-dimensional sparse estimation. As described above, we do expect to get the oracle solution of problem (1).In this paper, a FCP regularized subspace clustering model is presented as follows:(3)mingjj∈P\S∈Δ+Z12X−XZF2+α∑j∈P\Sgj1−gj2+β2∑i∈PSorj∈P\Sgi−gj22Zij+Zji+12∑i∈S∑j∈Sgi−gj22pZij+Zji+γ∑j∈PGDiagzjPλ,a.We define a subspace dependent label matrixG=g1,g2,…,gn∈Rc×n, where gj=g1j,g2j,…,gcjT∈Rcj=1,2,…,n is a label vector for data xj; here, c is the number of subspaces and n is the number of data. Since we do not know c, the dimension of gj only needs to be set larger than c and at most equals to minm,n. Here, we still use c to denote the dimension of gj. In our work, we mainly discuss the semisupervised case; i.e., some data already have labels and the others do not. Index set for all data and the labeled data are denoted as P and S separately; then P\S represents index set for the unlabeled data. For every j∈S, we assume gij=1 when xj is in ith class, while gij=0 otherwise. The label vectors for j∈P\S need to be solved, and the set of all the unknown labels is defined as Δ+=g|g=gkk=1c,gk≥0,∑k=1cgk=1. Encouraged by the good properties of the FCP penalty, we give FCP-based norm ⋅Pλ,a to approximate rank function. The last term of our model (3) is to obtain rank minimization for matrix multiplication GDiagzj. α, β, and γ are parameters used to balance roles of the three regularization terms. It is obvious that the larger the parameter, the more important the corresponding term in the minimization problem.We give three regularization terms. The first one is minimizing the difference ofl1 norm and l2 norm of the label vector gj to make it have only one nonzero element. The clustering result for each data is induced by the index of that nonzero element. The second one is a variant of the graph Laplace regularization, which captures the nonlinear structures of the data. This term makes sure the data from the same subspace have the same label as much as possible. Therefore, the nonzero element of each label vector can properly correspond to the subspace from which the data is drawn. We apply a low-rank constraint to the combination of the label matrix and representation vector, as indicated in the third regularizer, to enforce Z to better satisfy block diagonal structure. In our work, the clustering result, namely the label for each data, is directly solved from the model rather than using spectral clustering methods. The labels and the representation matrix are contained in two regularization terms. The first part of the third term of (3) makes the nonzero element of each label vector accurately correspond to the subspace from which each query data comes if the representation matrix Z has the block diagonal structure. Vice versa, if each label has only one nonzero element which is associated with the accurate subspace, the second part of the third term and the fourth term make Z better meet the block diagonal structure. Therefore, the labels and the representation matrix interact and promote each other during the whole computing process.The problem can be solved by using the Alternating Direction Method of Multiplier (ADMM) framework. The resulting nonconvex FCP minimization problem can be solved by the Linear Local Approximation (LLA) method [23], which solves the problem by minimizing a surrogate function that upper bounds the objective functional. The surrogate function is constructed by linearizing the penalty function. LLA guarantees to decrease the objective function value in each iteration. Due to the nonconvex of the FCP problem, there are usually multiple local solutions, and the oracle property is established only for one of the local solutions. Breheny and Huang [25] have shown that with a Lasso-based initialization, LLA can avoid local maxima and saddle points, and with a high probability, an oracle solution can be obtained by using one-step LLA. In addition, once the oracle estimator is obtained, the LLA algorithm converges; namely, it produces the same estimator in the next iteration. We use the result of singular value thresholding as the initialization, which corresponds to the Lasso-based solution when applying to the nuclear norm minimization problem.Some notations used in this work are defined as follows. For a vectorx=x1,x2,…,xnT, x1=∑i=1nxi and x2=∑i=1nxi2 are l1 norm and l2 norm, respectively. Diagx is a diagonal matrix with diagonal entries being x. For a matrix X=Xij, XF=∑Xij2 denotes the Frobenius norm, X∗=∑σiX is the nuclear norm, and here, σiX is the ith singular value of X. X represents the element-wise absolute value of X. XT denotes the transpose of X. DiagX describes the diagonal matrix with diagonal components being Xii. diagX is a vector with entries Xii. trX is the trace of the square matrix X. I and 0 denote the identity matrix and the zero matrix. X≥0 means all entries of X are nonnegative.The remainder of this paper is organized as follows. InSection 2.1, we primarily give the three regularization terms then the low-rank-based semisupervised subspace clustering model is proposed. In Section 2.2, we define an MCP- and SCAD-based norm to approximate rank function. Then a FCP-based nonconvex minimization model results for subspace clustering. In Section 3, for solving the proposed model, we present an algorithm that combines several approaches such as ADMM, LLA, weighted singular value thresholding, and so on. In Section 4, we conduct a series of simulations with several datasets to demonstrate the superiority of our method. In Section 5, we conclude this paper with some summation and future plans.


## 2. The Proposed Model

### 2.1. The Low-Rank Model Integrating Affinity and Clustering

We setGi=g1i,g2i,…,gnii∈Rc×ni as the submatrix of G composed of the label vectors for all the data from subspace Si. The ideal Gi is the elements in ith row are all one, and those in the other rows are all zero. With the expression xj=Xzjj=1,2,…,n and the ideal structure of Gi, we can automatically seek the block diagonal structure of Z by minimizing the rank of matrix multiplication GDiagzj(refer to [31, 32] for the detailed interpretation). This sparsity between subspaces and density within a subspace implied by the block diagonal structure are preferred to the aim of subspace segmentation. So, we first give a minimization model as below. Here for every j∈P\S, we set Ij=i|gij≠0,i=1,2,…,c, and #Ij denotes the number of elements in Ij.(4)mingjj∈P\S∈Δ+,Z12X−XZF2+γ∑j∈PrankGDiagzjs.t.For everyj∈P\S,#Ij=1andIjcorresponds to the subspacethe dataxjis from.It is rational for the label vectorgj to have only one nonzero element since, in real application; one data only belongs to one subspace. For example, it is impossible for one face image belonging to two persons. Since gj has only one nonzero element if and only if gj1−gj2=0. Under the constraint of gjj∈P\S∈Δ+, its unique nonzero element has a value of one. For the simplicity of computing, we relax gj1−gj2=0 as enabling the difference of l1 norm and l2 norm of gj to achieve minimization and use as a regularized constraint. The problem becomes(5)mingjj∈P\S∈Δ+,Z12X−XZF2+α∑j∈P\Sgj1−gj2+γ∑j∈PrankGDiagzjs.t.for everyj∈P\S,Ijcorresponds to the subspace the dataxjis from.Now the problem is how to make sure the nonzero element ofgj properly associate with the subspace the query data come. To do this, we use the following term:(6)β2∑i∈P\Sorj∈P\Sgi−gj22Zij+Zji+12∑i∈S∑j∈Sgi−gj22pZij+Zji.We denote elements ofZ as Ziji,j∈1,2,…,n. The quantity of Zij+Zji describes the similarity between xi and xj. We analyze from the following several aspects:(1)
For the casei∈P\S, j∈S, or i∈S, j∈P\S, that is, one of xi and xj already has a label. Taking i∈P\S, j∈S for instance, since xj already has a label, xi should belong to the same subspace with xj as Zij+Zji is large enough. This can be achieved by the first part of formula (6). In this case, the index of the nonzero elements of the unknown label gi can be properly correlated to the subspace to which the data belongs.(2)
As neitherxi and xj has a label, the first part of (6) also works for this case. Since both gi and gj have only one nonzero element, indexes of their nonzero elements must be the same as Zij+Zji is large enough. Therefore, data xi and xj can be clustered into the same subspace, but which subspace cannot be decided. Figure 1 shows labels can be properly propagated from labeled data to unlabeled data; then the index of the nonzero element of each label can correspond to the accurate subspace even in this case.(3)
If bothxi and xj have labels, which means gi and gj do not need to be solved, we only do not know the representation coefficient. If xi and xj are in the same subspace, namely, gi−gj22=0, Zij and Zji should be large. If xi and xj are not in the same subspace, i.e., gi−gj22=2, Zij and Zji had better be zero. To this end, we use the second part of (6). Here the parameter p needs to be taken a large value.Figure 1
Semisupervised subspace clustering.
(a)(b)Using all the dataxjj=1,2,…,n as nodes, xi and xj have a connection between them as Zij+Zji is large enough, and no connection as Zij+Zji is small; then we obtain a graph of all data. Since for each data, the most similar data must come from the same subspace with it, each node must have a connection with at least one node in the same subspace. When there is at least one labeled data in each subspace, the label can be propagated from the labeled node to unlabeled nodes through formula (6). Therefore, the connected nodes can share the same label. This can be simply illustrated by Figure 1, in which there are only two classes and two labeled data (one for each subspace).So far, we obtain the complete low-rank-based semisupervised subspace clustering model(7)mingjj∈P\S∈Δ+Z12X−XZF2+α∑j∈P\Sgj1−gj2+β2∑i∈PSorj∈P\Sgi−gj22Zij+Zji+12∑i∈S∑j∈Sgi−gj22pZij+Zji+γ∑j∈PrankGDiagzj.The minimization problem (7) is difficult to solve due to the combined nature of rank function. The standard approach is to replace rank function with the nuclear norm. Considering the fact that matrix nuclear norm is prone to overpenalize large singular values and thus usually leads to a biased estimation and the advantages of FCP over l1 norm described in lots of works, we will utilize the FCP of singular value vector of a matrix to approximate rank function; thus, the model (7) is transformed into our model (3) presented in the introduction section, where matrix norm ⋅Pλ,a is defined as follows:(8)Ipλ,a=∑k=1cPλ,aσkI.σkI is the kth singular value of matrix I∈Rc×n with c≤n. We choose the function Pλ,a⋅ as Pλ,aMCP⋅ or Pλ,aSCAD⋅ defined as following separately. MCP is of the following form:(9)Pλ,aMCPt≔aλ22ift≥aλλt−t22aotherwise,a>1.SCAD is of the following form:(10)Pλ,aSCADt≔λtt≤λaλt−0.5t2+λ2a−1λ<t<aλλ2a+12t≥aλ,a>2.The matrix FCP norm defined in (8) satisfies the following properties.Proposition 1.
Fora∈1,∞(MCP) or a∈2,∞(SCAD), then(1)
Ipλ,a≥0, with equality iff I=0(2)
Ipλ,a≤λI∗, and lima⟶∞IPλ,a=λI∗(3)
IPλ,ais unitarily invariant, that is, UIVPλ,a=IPλ,a whenever U and V are orthonormal(4)
IPλ,a is concave w. r. t. matrix I, where I=IijProperty (1) is obvious. The second property can be easily verified since both SCAD and MCP penalty functions are upper bounded by Lasso penalty function and tend to Lasso penalty function as a⟶∞. The third property is true due to the fact that singular values are not changed from I to UIV whenever U and V are orthonormal. The fourth property holds because of the concavity of the FCP penalty function. It is worth noting that the matrix FCP is not a real norm since it does not satisfy the triangle inequality of a norm.


## 2.1. The Low-Rank Model Integrating Affinity and Clustering

We setGi=g1i,g2i,…,gnii∈Rc×ni as the submatrix of G composed of the label vectors for all the data from subspace Si. The ideal Gi is the elements in ith row are all one, and those in the other rows are all zero. With the expression xj=Xzjj=1,2,…,n and the ideal structure of Gi, we can automatically seek the block diagonal structure of Z by minimizing the rank of matrix multiplication GDiagzj(refer to [31, 32] for the detailed interpretation). This sparsity between subspaces and density within a subspace implied by the block diagonal structure are preferred to the aim of subspace segmentation. So, we first give a minimization model as below. Here for every j∈P\S, we set Ij=i|gij≠0,i=1,2,…,c, and #Ij denotes the number of elements in Ij.(4)mingjj∈P\S∈Δ+,Z12X−XZF2+γ∑j∈PrankGDiagzjs.t.For everyj∈P\S,#Ij=1andIjcorresponds to the subspacethe dataxjis from.It is rational for the label vectorgj to have only one nonzero element since, in real application; one data only belongs to one subspace. For example, it is impossible for one face image belonging to two persons. Since gj has only one nonzero element if and only if gj1−gj2=0. Under the constraint of gjj∈P\S∈Δ+, its unique nonzero element has a value of one. For the simplicity of computing, we relax gj1−gj2=0 as enabling the difference of l1 norm and l2 norm of gj to achieve minimization and use as a regularized constraint. The problem becomes(5)mingjj∈P\S∈Δ+,Z12X−XZF2+α∑j∈P\Sgj1−gj2+γ∑j∈PrankGDiagzjs.t.for everyj∈P\S,Ijcorresponds to the subspace the dataxjis from.Now the problem is how to make sure the nonzero element ofgj properly associate with the subspace the query data come. To do this, we use the following term:(6)β2∑i∈P\Sorj∈P\Sgi−gj22Zij+Zji+12∑i∈S∑j∈Sgi−gj22pZij+Zji.We denote elements ofZ as Ziji,j∈1,2,…,n. The quantity of Zij+Zji describes the similarity between xi and xj. We analyze from the following several aspects:(1)
For the casei∈P\S, j∈S, or i∈S, j∈P\S, that is, one of xi and xj already has a label. Taking i∈P\S, j∈S for instance, since xj already has a label, xi should belong to the same subspace with xj as Zij+Zji is large enough. This can be achieved by the first part of formula (6). In this case, the index of the nonzero elements of the unknown label gi can be properly correlated to the subspace to which the data belongs.(2)
As neitherxi and xj has a label, the first part of (6) also works for this case. Since both gi and gj have only one nonzero element, indexes of their nonzero elements must be the same as Zij+Zji is large enough. Therefore, data xi and xj can be clustered into the same subspace, but which subspace cannot be decided. Figure 1 shows labels can be properly propagated from labeled data to unlabeled data; then the index of the nonzero element of each label can correspond to the accurate subspace even in this case.(3)
If bothxi and xj have labels, which means gi and gj do not need to be solved, we only do not know the representation coefficient. If xi and xj are in the same subspace, namely, gi−gj22=0, Zij and Zji should be large. If xi and xj are not in the same subspace, i.e., gi−gj22=2, Zij and Zji had better be zero. To this end, we use the second part of (6). Here the parameter p needs to be taken a large value.Figure 1
Semisupervised subspace clustering.
(a)(b)Using all the dataxjj=1,2,…,n as nodes, xi and xj have a connection between them as Zij+Zji is large enough, and no connection as Zij+Zji is small; then we obtain a graph of all data. Since for each data, the most similar data must come from the same subspace with it, each node must have a connection with at least one node in the same subspace. When there is at least one labeled data in each subspace, the label can be propagated from the labeled node to unlabeled nodes through formula (6). Therefore, the connected nodes can share the same label. This can be simply illustrated by Figure 1, in which there are only two classes and two labeled data (one for each subspace).So far, we obtain the complete low-rank-based semisupervised subspace clustering model(7)mingjj∈P\S∈Δ+Z12X−XZF2+α∑j∈P\Sgj1−gj2+β2∑i∈PSorj∈P\Sgi−gj22Zij+Zji+12∑i∈S∑j∈Sgi−gj22pZij+Zji+γ∑j∈PrankGDiagzj.The minimization problem (7) is difficult to solve due to the combined nature of rank function. The standard approach is to replace rank function with the nuclear norm. Considering the fact that matrix nuclear norm is prone to overpenalize large singular values and thus usually leads to a biased estimation and the advantages of FCP over l1 norm described in lots of works, we will utilize the FCP of singular value vector of a matrix to approximate rank function; thus, the model (7) is transformed into our model (3) presented in the introduction section, where matrix norm ⋅Pλ,a is defined as follows:(8)Ipλ,a=∑k=1cPλ,aσkI.σkI is the kth singular value of matrix I∈Rc×n with c≤n. We choose the function Pλ,a⋅ as Pλ,aMCP⋅ or Pλ,aSCAD⋅ defined as following separately. MCP is of the following form:(9)Pλ,aMCPt≔aλ22ift≥aλλt−t22aotherwise,a>1.SCAD is of the following form:(10)Pλ,aSCADt≔λtt≤λaλt−0.5t2+λ2a−1λ<t<aλλ2a+12t≥aλ,a>2.The matrix FCP norm defined in (8) satisfies the following properties.Proposition 1.
Fora∈1,∞(MCP) or a∈2,∞(SCAD), then(1)
Ipλ,a≥0, with equality iff I=0(2)
Ipλ,a≤λI∗, and lima⟶∞IPλ,a=λI∗(3)
IPλ,ais unitarily invariant, that is, UIVPλ,a=IPλ,a whenever U and V are orthonormal(4)
IPλ,a is concave w. r. t. matrix I, where I=IijProperty (1) is obvious. The second property can be easily verified since both SCAD and MCP penalty functions are upper bounded by Lasso penalty function and tend to Lasso penalty function as a⟶∞. The third property is true due to the fact that singular values are not changed from I to UIV whenever U and V are orthonormal. The fourth property holds because of the concavity of the FCP penalty function. It is worth noting that the matrix FCP is not a real norm since it does not satisfy the triangle inequality of a norm.


## 3. Optimization

To solve problem (3), the original problem is converted to the following equivalent problem:(11)mingjj∈P\S∈Δ+,Z,Q,yjj∈P\S,Jjj∈P12X−XZF2+α∑j∈P\Syj1−gj2+γ∑j∈PJjPλ,a+β2∑i∈P\Sorj∈P\Sgi−gj22Qij+Qji+12∑i∈S∑j∈Sgi−gj22pQij+Qjis.t.Jj=GDiagzj,j∈P,Q=Z,yj=gj,j∈P\S.The solution to problem (11) is difficult to achieve directly. We adopt the Augmented Lagrangian Multiplier (ALM) scheme to derive the following unconstrained optimization problem:(12)mingjj∈P\S∈Δ+,Z,Q,yjj∈P\S,Jjj∈P12X−XZF2+α∑j∈P\Syj1−gj2+β2∑i∈P\Sorj∈P\Sgi−gj22Qij+Qji+12∑i∈S∑j∈Sgi−gj22pQij+Qji+γ∑j∈PJjPλ,a+∑j∈PtrYjTGDiagzj−Jj+trFTZ−Q+∑j∈P\SujTyj−gj+μ2∑j∈PGDiagzj−JjF2+μ2Z−QF2+μ2∑j∈P\Syj−gj22,where Yj∈Rc×nj∈P, F∈Rn×n, uj∈Rcj∈P\S are Lagrangian multipliers and μ>0 is the penalty parameter. Instead of optimizing all arguments simultaneously, as gjj∈P\S, Z, Q, yjj∈P\S, Jjj∈P are separable, we solve them individually and iteratively for k=0,1,2,….(1)
By fixinggjkj∈P\S, Qk, yjkj∈P\S, Jjkj∈P, we optimize every column zjj∈P of Z by the following subproblem: (13)zjk+1=argminzj12xj−Xzj22+trYjkTGkDiagzj+fjkTzj+μk2GkDiagzj−JjkF2+zj−qjk22,herefjk is jth column of Fk and qjk is jth column of Qk. Then the solution can be achieved via solving a linear system as follows:(14)XTX+μkDiagGkTGk+μkIzjk+1=XTxj+diagμkJjkT−YjkTGk+μkqjk−fjk.(2)
By fixingZk+1, Qk, yjkj∈P\S, Jjkj∈P, we optimize every gjj∈P\S by the following subproblem:(15)gjk+1=argmingjj∈P\S∈Δ+−α∑j∈P\Sgj2+β2∑i∈P\Sorj∈P\Sgi−gj22Qijk+Qjik+∑i∈PtrYikTGDiagzik+1−∑j∈P\SujkTgj+μk2∑i∈PGDiagzik+1−JikF2+∑j∈P\Syjk−gj22.The above problem can be solved using the following equation:(16)gjk+1=2β∑i∈PQjik+Qijkgik+∑i∈PμkJi,jk−Yi,jkZjik+1+ujk+μkyjk2β∑i∈PQjik+Qijk+μk∑i∈PZjik+12+μk−α1/gjk2.Here,Ji,jk and Yi,jk represent jth column of matrix Jik and Yik separately. Zjik+1 is the jth element of vector zi. gjk+1 is then projected onto the set Δ+=g|g=gkk=1c,gk≥0,∑k=1cgk=1 by the algorithm presented by [33].(3)
Fori∈P\S or j∈P\S, the optimized Qijk+1 can be obtained using a weighted soft-thresholding algorithm(17)β2μkgik+1−gjk+122Qij+12Qij−Zijk+1+Fijkμk2.Asi∈S and j∈S, since gi and gj are known, we get Qij from the following equation:(18)12μkgi−gj22pQij+12Qij−Zijk+1+Fijkμk2.(4)
To updateyjj∈P\S, the following subproblem is solved:(19)yjk+1=argminyjαμkyj1+12yj−gjk+1−ujkμk22.Problem (18) can be solved by the soft-thresholding operator.(5)
To updateJjj∈P, the following subproblem is solved:(20)Jjk+1=argminJjγμkJjPλ,a+12Jj−Gk+1Diagzjk+1+YjkμkF2,which can be solved through LLA by using the result of singular value thresholding as the initial value for Jj.The Lagrangian multipliers are updated as follows:(21)Yjk+1=Yjk+μkGk+1Diagzjk+1−Jjk+1,j∈P,(22)Fk+1=Fk+μkZk+1−Qk+1,(23)ujk+1=ujk+μkyjk+1−gjk+1,j∈P\S.Steps (14)–(23) are repeated until the convergence conditions are attained. In this algorithm, the penalty parameter μk starts with μ0=10−9, then μk+1=maxρμk,109 in each iteration step with ρ=1.1.


## 4. Experiments

To evaluate the performance of our proposed method, we conduct experiments on five benchmark datasets: the face image dataset Extended Yale B [34] and ORL [35], the object image dataset COIL20 [36], the handwriting number image dataset MNIST [37], and handwriting number and letter image dataset Alphadigits. We directly cite some results reported in [12] on the dataset ORL and Alphadigits. We compare our proposed method with ten baseline algorithms, including SSC, kernel sparse subspace clustering (KSSC) [38], SSC by orthogonal matching pursuit (SSC-OMP) [39], S3C [40], SSRSC [41], LRR, low-rank subspace clustering (LRSC) [42], efficient dense subspace clustering (EDSC) [43], TLRR [44], and KTRR [12]. Among these methods, SSC, KSSC, SSC-OMP, S3C, and SSRSC are sparse-based and LRR, LRSC, EDSC, TLRR are low-rank-based; KTRR is based on ridge regression.


### 4.1. Datasets

For the datasets used in our experiments, we briefly describe these datasets as follows: (1) Extended Yale B. The Extended Yale B Database consists of 2432 face images in total from 38 subjects, with 64 frontal face images per subject taken under different illumination conditions. Face images of each subject are a low-dimensional subspace. In our experiments, each image is downsampled from 192 × 168 to 32 × 32 pixels. (2) ORL contains face images of size 32 × 32 pixels from 40 individuals. Each individual has 10 images taken at different times, with varying facial expressions, facial details, and lighting conditions. (3) COIL20 contains 1440 grayscale images of 20 objects. Each image was downsampled to 32 × 32. (4) MNIST contains 70,000 images of handwritten digits 0–9 with a size of 28 × 28 pixels. (5) Alphadigits dataset is a binary dataset, which collects handwritten digits 0–9 and letters A–Z. Totally, there are 36 classes and 39 samples for each class, of which each example has a size of 20 × 16 pixels.


### 4.2. Evaluation Metrics

We use three evaluation metrics to testify the effectiveness of the proposed method, including clustering accuracy (CA), normalized mutual information (NMI), and purity. All experiments run ten times usingn random choices of subjects for each time. For each subject, we randomly select t images, of which m images are prelabeled in our method. Then the average CA, NMI, and purity are reported. We compute the clustering accuracy as follows:(24)clustering accuracy=number of correctly clustered datant−m.Clustering accuracy measures the accuracy rate of clustering. NMI measures the quality of the clusters. Purity measures the extent to which each cluster contains samples from primarily the same subject. Higher values of these metrics indicate better clustering quality. More details of the last two metrics can be found in [45]. The best results are shown in bold font. Experiments verify that there is no obvious difference between MCP and SCAD when they are applied to our model, so we do not list them separately. In all of our experiments, we use the intensity feature of each image and stretch it to a column of the data matrix X.


### 4.3. Parameter Selection

The parameters for all the methods are adjusted to obtain the best clustering results. Our method involves six parametersa, λ, α, β, γ, and p. Among these parameters, a and λ are associated with the FCP penalty functions. In our experiments, a=5 and λ=1 can obtain the best results. α, β, and γ are used to balance the roles of three regularization terms. The best choice for α is 12.5735±0.0115, for β is 100±0.8, and for γ is 7.005×10−3±2.5×10−5. Parameter p needs to be set large enough to penalize the large representation coefficients when two labeled data have different labels. We fix p=20 which can achieve the best results for all the following experimental settings.


### 4.4. Initialization and Stopping Criterion

All the variablesZ, Q, gjj∈P\S, yjj∈P\S and Lagrange multipliers Yjj∈P, F, ujj∈P\S are started with all elements being zero. Jjj∈P is initialized to G0Diagzj0 where G0 consists of the known labels and initial unknown labels gj0j∈P\S. We use three errors ∑j∈PGDiagzj−JjF, Z−QF, ∑j∈P\Syj−gj2 all less than 10−6 as the stopping criterion of iterations.


### 4.5. Performances

The average CA, NMI, and purity of all the methods on the two face image datasets; i.e., Extended Yale B and ORL, are reported in Tables1 and 2 separately. For the database Extended Yale B, we use n∈5,10 random choices of subjects for each time. For each subject, we randomly select t images, where t∈10,20,30, among which m images are prelabeled in our method. For ORL, we randomly choose n∈10,20,30 persons. Each individual has 10 images. With only a small portion of data being prelabeled, our method can achieve comparative results with the most state-of-the-art methods.Table 1
Performance on Extended Yale B.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=5t=1079.377.871.278.279.281.380.577.471.381.8m=282.5t=2082.780.474.880.881.283.682.978.673.283.8m=484.2t=3085.784.778.284.585.986.385.481.376.887.0m=587.8n=10t=1076.966.561.272.874.679.078.575.069.779.5m=280.2t=2078.367.963.375.375.481.880.676.171.381.4m=482.3t=3082.470.365.177.480.784.773.479.674.384.5m=684.9NMIn=5t=100.39980.53510.41950.37490.40340.58450.52900.46710.40230.6018m=20.6122t=200.42720.55430.44330.40340.42130.62290.54390.47340.41940.6326m=40.6433t=300.44830.58340.45840.43230.45490.64340.57450.50320.44830.6693m=50.6853n=10t=100.48370.55110.55330.47830.48550.55840.55310.53210.41990.6242m=20.6329t=200.50480.57380.57540.48930.50340.57450.56330.55830.42840.6383m=40.6508t=300.54380.61820.61370.50320.51380.60560.58440.58220.44090.6594m=60.6683Purityn=5t=100.54910.65820.56670.52860.55430.66830.63820.61820.54690.6970m=20.7094t=200.54380.66430.59850.54540.55670.67820.64330.62830.55890.7093m=40.7233t=300.55820.68020.60870.55630.57580.69630.66460.65040.57610.7276m=50.7586n=10t=100.51910.58180.46930.50840.52080.60870.55820.55910.44130.6536m=20.6676t=200.52630.60620.48760.52940.53890.61280.57230.55900.45920.6685m=40.6698t=300.53760.62650.50830.55090.55180.63850.58680.56340.47030.6856m=60.6865Table 2
Performance on ORL.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=10t=1077.674.968.576.278.482.981.278.276.887.5m=288.3n=20t=1078.573.867.375.677.581.681.679.175.489.0m=289.3n=30t=1079.173.865.473.074.779.182.879.974.790.4m=290.8NMIn=10t=100.77110.83760.72390.74340.76760.82390.84100.81180.79650.8428m=20.8656n=20t=100.82710.81970.70940.78320.81560.80530.84080.83130.78890.8804m=20.9056n=30t=100.83550.83720.73230.81840.83820.83380.86630.83590.77260.9038m=20.9210Purityn=10t=100.75200.78600.73640.74550.75640.79930.81000.80200.79130.8330m=20.8450n=20t=100.76100.76200.70490.73850.756360.75640.77850.77000.73110.8355m=20.8444n=30t=100.74830.76400.66870.74480.74110.75630.79370.76100.67730.8500m=20.8665The previous experiment targets face clustering. To show the generality of our algorithm, we also evaluate it on the COIL20 object image dataset. The results are reported in Table3. In contrast with the previous human face datasets, in which faces are well aligned and have similar structures, the object images from COIL20 are more diverse, and even samples from the same object differ from each other due to the change of viewing angle. This makes this dataset challenging for subspace clustering techniques. Experimental results are listed in Table 3. For each of the chosen 10 subjects, we randomly select t∈10,20,30 images, of which m∈2,4,5; images already have labels for our method. Similar to the above datasets, the result of our method is the best among all the eleven methods.Table 3
Performance on COIL20.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=10t=1076.970.870.670.961.676.675.473.271.876.9m=277.3t=2077.666.065.471.462.578.077.874.671.778.5m=479.4t=3080.470.270.474.964.580.179.576.372.180.4m=581.6NMIn=10t=100.52230.47780.47430.48320.42440.52030.51370.48930.46220.5365m=20.5483t=200.53320.42230.45320.50870.42380.55910.53290.51280.47230.5732m=40.5832t=300.55380.4765048080.52480.43910.56240.55930.53280.49330.6030m=50.6037Purityn=10t=100.46390.43340.41030.42830.40830.47290.48550.47340.44920.4932m=20.5039t=200.48960.40340.40930.47680.41860.48330.49160.48450.46920.5243m=40.5302t=300.50070.43400.42370.48760.42970.50290.51840.50450.47040.5508m=50.5638To further verify the effectiveness of our proposed method, we conduct experiments on two datasets containing handwritten digits, i.e., MNIST and Alphadigits. The Alphadigits database also contains 26 letters. For the MNIST database, we randomly chooset images for each digit 0–9, where t∈30,40,50, and then apply all the methods to cluster the images. For our methods, m∈5,7,8 images are prelabeled of the t images for each digit. For the Alphadigits database, we use n∈5,10 random choices of subjects. For each subject, we use all the images, among which m=6 images are prelabeled for our method. The CA, NMI, and purity are reported in Tables 4 and 5. Our method gets the best clustering result among all the compared methods.Table 4
Performance on MNIST.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=10t=3078.0564.763.174.473.578.760.679.668.480.8m=581.8t=4084.467.065.379.879.684.862.781.471.784.9m=785.9t=5086.870.368.082.884.888.465.883.274.588.8m=890.3NMIn=10t=300.72840.61480.60940.70340.70560.74930.43330.73020.61830.7500m=50.7508t=400.76030.63940.63390.75440.73060.76840.43540.74950.64430.7745m=70.7865t=500.77340.65490.64070.75960.73850.76930.44260.75280.64870.7946m=80.7905Purityn=10t=300.73390.65940.62830.70840.69480.76480.52450.72570.63840.7747m=50.7806t=400.76440.66450.63660.75850.70580.77430.54330.75040.67480.7947m=70.8019t=500.77960.67650.64440.76580.73990.80850.55740.76530.67370.8095m=80.8145Table 5
Performance on Alphadigits.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=5t=3980.779.577.380.581.281.360.882.670.484.1m=684.7n=10t=3979.577.475.178.479.579.258.479.569.881.8m=682.6NMIn=5t=390.65190.65670.58420.64320.65780.66840.28100.64670.49800.6959m=60.7121n=10t=390.55250.65210.55460.61940.63230.63280.24970.58640.49810.6650m=60.6790Purityn=5t=390.67150.69740.70540.66820.67380.70360.38410.66380.56190.7277m=60.7329n=10t=390.50560.61580.64760.63960.65430.67820.25040.52580.45510.6305m=60.6406


## 4.1. Datasets

For the datasets used in our experiments, we briefly describe these datasets as follows: (1) Extended Yale B. The Extended Yale B Database consists of 2432 face images in total from 38 subjects, with 64 frontal face images per subject taken under different illumination conditions. Face images of each subject are a low-dimensional subspace. In our experiments, each image is downsampled from 192 × 168 to 32 × 32 pixels. (2) ORL contains face images of size 32 × 32 pixels from 40 individuals. Each individual has 10 images taken at different times, with varying facial expressions, facial details, and lighting conditions. (3) COIL20 contains 1440 grayscale images of 20 objects. Each image was downsampled to 32 × 32. (4) MNIST contains 70,000 images of handwritten digits 0–9 with a size of 28 × 28 pixels. (5) Alphadigits dataset is a binary dataset, which collects handwritten digits 0–9 and letters A–Z. Totally, there are 36 classes and 39 samples for each class, of which each example has a size of 20 × 16 pixels.


## 4.2. Evaluation Metrics

We use three evaluation metrics to testify the effectiveness of the proposed method, including clustering accuracy (CA), normalized mutual information (NMI), and purity. All experiments run ten times usingn random choices of subjects for each time. For each subject, we randomly select t images, of which m images are prelabeled in our method. Then the average CA, NMI, and purity are reported. We compute the clustering accuracy as follows:(24)clustering accuracy=number of correctly clustered datant−m.Clustering accuracy measures the accuracy rate of clustering. NMI measures the quality of the clusters. Purity measures the extent to which each cluster contains samples from primarily the same subject. Higher values of these metrics indicate better clustering quality. More details of the last two metrics can be found in [45]. The best results are shown in bold font. Experiments verify that there is no obvious difference between MCP and SCAD when they are applied to our model, so we do not list them separately. In all of our experiments, we use the intensity feature of each image and stretch it to a column of the data matrix X.


## 4.3. Parameter Selection

The parameters for all the methods are adjusted to obtain the best clustering results. Our method involves six parametersa, λ, α, β, γ, and p. Among these parameters, a and λ are associated with the FCP penalty functions. In our experiments, a=5 and λ=1 can obtain the best results. α, β, and γ are used to balance the roles of three regularization terms. The best choice for α is 12.5735±0.0115, for β is 100±0.8, and for γ is 7.005×10−3±2.5×10−5. Parameter p needs to be set large enough to penalize the large representation coefficients when two labeled data have different labels. We fix p=20 which can achieve the best results for all the following experimental settings.


## 4.4. Initialization and Stopping Criterion

All the variablesZ, Q, gjj∈P\S, yjj∈P\S and Lagrange multipliers Yjj∈P, F, ujj∈P\S are started with all elements being zero. Jjj∈P is initialized to G0Diagzj0 where G0 consists of the known labels and initial unknown labels gj0j∈P\S. We use three errors ∑j∈PGDiagzj−JjF, Z−QF, ∑j∈P\Syj−gj2 all less than 10−6 as the stopping criterion of iterations.


## 4.5. Performances

The average CA, NMI, and purity of all the methods on the two face image datasets; i.e., Extended Yale B and ORL, are reported in Tables1 and 2 separately. For the database Extended Yale B, we use n∈5,10 random choices of subjects for each time. For each subject, we randomly select t images, where t∈10,20,30, among which m images are prelabeled in our method. For ORL, we randomly choose n∈10,20,30 persons. Each individual has 10 images. With only a small portion of data being prelabeled, our method can achieve comparative results with the most state-of-the-art methods.Table 1
Performance on Extended Yale B.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=5t=1079.377.871.278.279.281.380.577.471.381.8m=282.5t=2082.780.474.880.881.283.682.978.673.283.8m=484.2t=3085.784.778.284.585.986.385.481.376.887.0m=587.8n=10t=1076.966.561.272.874.679.078.575.069.779.5m=280.2t=2078.367.963.375.375.481.880.676.171.381.4m=482.3t=3082.470.365.177.480.784.773.479.674.384.5m=684.9NMIn=5t=100.39980.53510.41950.37490.40340.58450.52900.46710.40230.6018m=20.6122t=200.42720.55430.44330.40340.42130.62290.54390.47340.41940.6326m=40.6433t=300.44830.58340.45840.43230.45490.64340.57450.50320.44830.6693m=50.6853n=10t=100.48370.55110.55330.47830.48550.55840.55310.53210.41990.6242m=20.6329t=200.50480.57380.57540.48930.50340.57450.56330.55830.42840.6383m=40.6508t=300.54380.61820.61370.50320.51380.60560.58440.58220.44090.6594m=60.6683Purityn=5t=100.54910.65820.56670.52860.55430.66830.63820.61820.54690.6970m=20.7094t=200.54380.66430.59850.54540.55670.67820.64330.62830.55890.7093m=40.7233t=300.55820.68020.60870.55630.57580.69630.66460.65040.57610.7276m=50.7586n=10t=100.51910.58180.46930.50840.52080.60870.55820.55910.44130.6536m=20.6676t=200.52630.60620.48760.52940.53890.61280.57230.55900.45920.6685m=40.6698t=300.53760.62650.50830.55090.55180.63850.58680.56340.47030.6856m=60.6865Table 2
Performance on ORL.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=10t=1077.674.968.576.278.482.981.278.276.887.5m=288.3n=20t=1078.573.867.375.677.581.681.679.175.489.0m=289.3n=30t=1079.173.865.473.074.779.182.879.974.790.4m=290.8NMIn=10t=100.77110.83760.72390.74340.76760.82390.84100.81180.79650.8428m=20.8656n=20t=100.82710.81970.70940.78320.81560.80530.84080.83130.78890.8804m=20.9056n=30t=100.83550.83720.73230.81840.83820.83380.86630.83590.77260.9038m=20.9210Purityn=10t=100.75200.78600.73640.74550.75640.79930.81000.80200.79130.8330m=20.8450n=20t=100.76100.76200.70490.73850.756360.75640.77850.77000.73110.8355m=20.8444n=30t=100.74830.76400.66870.74480.74110.75630.79370.76100.67730.8500m=20.8665The previous experiment targets face clustering. To show the generality of our algorithm, we also evaluate it on the COIL20 object image dataset. The results are reported in Table3. In contrast with the previous human face datasets, in which faces are well aligned and have similar structures, the object images from COIL20 are more diverse, and even samples from the same object differ from each other due to the change of viewing angle. This makes this dataset challenging for subspace clustering techniques. Experimental results are listed in Table 3. For each of the chosen 10 subjects, we randomly select t∈10,20,30 images, of which m∈2,4,5; images already have labels for our method. Similar to the above datasets, the result of our method is the best among all the eleven methods.Table 3
Performance on COIL20.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=10t=1076.970.870.670.961.676.675.473.271.876.9m=277.3t=2077.666.065.471.462.578.077.874.671.778.5m=479.4t=3080.470.270.474.964.580.179.576.372.180.4m=581.6NMIn=10t=100.52230.47780.47430.48320.42440.52030.51370.48930.46220.5365m=20.5483t=200.53320.42230.45320.50870.42380.55910.53290.51280.47230.5732m=40.5832t=300.55380.4765048080.52480.43910.56240.55930.53280.49330.6030m=50.6037Purityn=10t=100.46390.43340.41030.42830.40830.47290.48550.47340.44920.4932m=20.5039t=200.48960.40340.40930.47680.41860.48330.49160.48450.46920.5243m=40.5302t=300.50070.43400.42370.48760.42970.50290.51840.50450.47040.5508m=50.5638To further verify the effectiveness of our proposed method, we conduct experiments on two datasets containing handwritten digits, i.e., MNIST and Alphadigits. The Alphadigits database also contains 26 letters. For the MNIST database, we randomly chooset images for each digit 0–9, where t∈30,40,50, and then apply all the methods to cluster the images. For our methods, m∈5,7,8 images are prelabeled of the t images for each digit. For the Alphadigits database, we use n∈5,10 random choices of subjects. For each subject, we use all the images, among which m=6 images are prelabeled for our method. The CA, NMI, and purity are reported in Tables 4 and 5. Our method gets the best clustering result among all the compared methods.Table 4
Performance on MNIST.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=10t=3078.0564.763.174.473.578.760.679.668.480.8m=581.8t=4084.467.065.379.879.684.862.781.471.784.9m=785.9t=5086.870.368.082.884.888.465.883.274.588.8m=890.3NMIn=10t=300.72840.61480.60940.70340.70560.74930.43330.73020.61830.7500m=50.7508t=400.76030.63940.63390.75440.73060.76840.43540.74950.64430.7745m=70.7865t=500.77340.65490.64070.75960.73850.76930.44260.75280.64870.7946m=80.7905Purityn=10t=300.73390.65940.62830.70840.69480.76480.52450.72570.63840.7747m=50.7806t=400.76440.66450.63660.75850.70580.77430.54330.75040.67480.7947m=70.8019t=500.77960.67650.64440.76580.73990.80850.55740.76530.67370.8095m=80.8145Table 5
Performance on Alphadigits.
MethodsSSCLRRLRSCKSSCSSC-OMPEDSCS3CSSRSCTLRRKTRROur methodCA (%)n=5t=3980.779.577.380.581.281.360.882.670.484.1m=684.7n=10t=3979.577.475.178.479.579.258.479.569.881.8m=682.6NMIn=5t=390.65190.65670.58420.64320.65780.66840.28100.64670.49800.6959m=60.7121n=10t=390.55250.65210.55460.61940.63230.63280.24970.58640.49810.6650m=60.6790Purityn=5t=390.67150.69740.70540.66820.67380.70360.38410.66380.56190.7277m=60.7329n=10t=390.50560.61580.64760.63960.65430.67820.25040.52580.45510.6305m=60.6406


## 5. Conclusion

We propose a novel nonconvex formulation for the subspace segmentation problem. In our work, the labels of all data are directly solved from the model rather than using spectral clustering algorithms. We give two regularization constraints about the label vectors. One is to force the label vector only to have one nonzero element by minimizing the difference ofl1 norm and l2 norm. Another is to make sure data from the same subspace have the same label as much as possible so that the index of that nonzero element of each label vector can indicate the subspace from which the data come. Due to many advantages of FCP over l1 norm, we present an FCP-based low-rank approximation norm and apply it to the combination of semisupervised label matrix and representation vector. This term can enforce the representation matrix better meeting block diagonal structure. The labels and the representation matrix are contained in two regularization terms. Therefore, they can interact and promote each other during the computing process. We give a solving algorithm based on ADMM, LLA, weighted singular value thresholding, weighted soft thresholding, and so on.In the future, we will continue conducting research on estimation or learning methods for the parameters in our proposed model because we have to tune those parameters in order to achieve better results. It is possibly better to integrate the classical knowledge-based approaches into the deep learning architecture, making the algorithm enjoy both the flexibility of the deep learning-based methods and the clear structure of the classical approaches.



---

*Source: 6641180-2021-05-17.xml*