Nonconvex Multiview Subspace Clustering Framework with Efficient Method Designs and Theoretical Analysis

1 Introduction

In many real-world applications, one needs to consider how to effectively and efficiently process high-dimensional data, which is a key issue in machine learning [Slepˇcev and Thorpe, 2019; Cai et al., 2011; Tang et al., 2023], computer vision [Ho et al., 2003; Yang et al., 2008; Vidal et al., 2008], and pattern recognition [Basri and Jacobs, 2003; Ma et al., 2008]. However, such problems are extremely challenging because of the "curse of dimensionality" [Muja and Lowe, 2014]. Fortunately, some researchers have pointed out that high-dimensional data are drawn from low-dimensional subspaces. Therefore, how to efficiently recover the lowdimensional structures in datasets becomes a crucial step.

To address this issue, subspace clustering (SC) has been proposed and extensively studied, and has become the most important and fundamental tool for high-dimensional data analysis [Vidal, 2011; Liu et al., 2010]. Such technique aims to separate data samples into their exclusive groups, where each group corresponds to a subspace with highly similar characteristics. The most prevalent methods of selfrepresentation based subspace clustering are sparse subspace clustering (SSC) [Elhamifar and Vidal, 2013], low-rank representation (LRR) [Liu et al., 2012], and some of their variants [Qu et al., 2022; Liu et al., 2023c]. Specifically, SSC has the ability to seek the sparsest representation coefficients corresponding to the data from the same subspace. On the other hand, LRR is to seek a low-rank subspace representation. Despite their success, these approaches only focus on single-view features.

∗Corresponding author

In practical scenarios, however, data are often collected from different sources and can be represented by various types of features [Fang et al., 2023]. For example, a color image consists of colors, textures, and shapes, a video is a combination of visual frames and audio tracks, and a web page may contain text, images and their corresponding link. The features of different views usually have their own inherent attributes, which make it possible to provide consistent and complementary information to each other. Therefore, integrating these different heterogeneous and complementary features into clustering methods can significantly improve their performance.

To exploit complementary and consistent information from different views, many Multi-view SC (MvSC) methods have been proposed [Gao et al., 2015; Zhang et al., 2017; Li et al., 2019a; Chen et al., 2022]. Different from single-view subspace clustering methods, MvSC uses multiple features to accomplish the multi-view data clustering tasks. Therefore, the MvSC methods have superiority compared with single-view subspace clustering methods. Although these methods have achieved remarkable results in MvSC tasks, they still suffer from the following shortcomings. First, they adopt the convex nuclear norm as the low-rank constraint, which ignores significant differences between different singular values [Wang et al., 2021; Wang et al., 2022; Shan et al., 2023]. As a result, they cannot accurately capture low rankness, resulting in inferior performance. Second, the union of underlying n subspaces {Si}ni=1 is commonly disjoint [Tang et al., 2014]. As shown in Figure 1, for the data points that nearby distributed at local intersections, it is hard to identify the subspaces they really belong to. Unfortunately, these confounding points have still not been carefully handled, which may degrade the purity and distinctiveness of cross-view fusion.

To overcome above drawbacks, in this paper we propose a new MvSC model namely Nonconvex Low-Rank and Structure-Constrained MvSC (NLRSC-MvSC). Comparing with the aforementioned models, NLRSC-MvSC has two prominent advantages. First, by using the ℓq norm [Marjanovic and Solo, 2012] in our model, the intrinsic low-rank structure in multi-view data can be efficiently captured [Wang et al., 2019; Wang et al., 2020]. Thus, the mutually complementary subspace information embedding in each view can be fully exploited, so as to provide a more comprehensive and in-depth description with regard to the underlying subspaces. Second, with the aim of clustering the disjoint and confounding data samples into corresponding subspaces, a shared cross-view structure restriction is naturally imposed on each coefficient matrix. To be concrete, the correlation between inter-cluster samples can be significantly reduced with a soft penalty strategy, whereas the informative intra-cluster coefficients are sufficiently preserved. As a result, by fusing the view-specific compact representations, a more discriminative consensus fusion is yield, which can offer a better characterization of true subspace structure. In summary, the main highlights of this paper are as follows.

• We propose a novel MvSC model that simultaneously imposes low-rank and structural constraints on viewspecific representations by leveraging the nonconvex ℓq norm and soft penalty strategy. It can comprehensively explore the complementary and consistent connections among multiple coefficient matrices, thereby further facilitating the effectual cross-view fusion.
• We establish an efficient algorithm to solve the corresponding optimization problem. Furthermore, rigorous mathematical proof shows that the sequence generated by our proposed algorithm converges to a KKT point.
• Extensive experiments on various multi-view datasets validate the effectiveness and superiority of our proposed model over several state-of-the-art multi-view clustering models.

2 RelatedWork

2.1 Multi-view Subspace Clustering

As a fundamental tool for processing multi-view data, MvSC has become an active topic in machine learning and computer vision in recent years. Generally speaking, most existing MvSCmethods have three steps, including i) learn the coefficient matrices of the data samples via "self-expressiveness"; ii) construct the affinity graph by fusing the learned coefficient representations; iii) apply the spectral clustering method [Ng et al., 2001] on affinity graph to get the final clustering result. How to accurately learn a coefficient matrix is crucial for these methods. To this end, the LRR strategy is commonly used to recover the underlying subspaces, which can fully capture the global structure of the data. However, the resultant optimization problem is NP-hard due to the discreteness of the rank function. To alleviate this problem, a common approach is to use nuclear norm as its convex relaxation. In real world, the multi-view data may contain errors (e.g., noise and outliers). Thus, the ℓ2,1 norm can be used to reduce their interference. Along this line of research, a large number of MvSC models have been proposed [Zhang et al., 2017; Luo et al., 2018; Chen et al., 2022]. In [Zhang et al., 2017], Zhang et al. proposed a latent MvSC (LMvSC) model to explore the complementarity of multiple views. In [Chen et al., 2022], Chen et al. proposed a multi-view LRR (MvLRR) model by using symmetric LRR fusion, which can more comprehensively explore the underlying low-rank subspace. In [Luo et al., 2018], Luo et al. proposed a model that can learn consistent and specific representations simultaneously. Although these methods have achieved satisfactory results in MvSC tasks, there are still some shortcomings. On the one hand, the nuclear norm as the low-rank constraint may result in a severe loss of multi-view information. On the other hand, these methods enforce the elements across representations to be consistent, which neglects the difference in value magnitudes between and within views.

2.2 Nonconvex ℓq(0 < q < 1) Regularization

In the region of compressed sensing [Chartrand, 2007; Chartrand and Yin, 2008], the nonconvex regularization methods related to the ℓq norm [Marjanovic and Solo, 2012] have received extensive attention, and a large number of theoretical results and algorithms have been proposed to solve the corresponding optimization problems. Comparing with its convex counterparts, using the ℓq norm can obtain more sparse solution and requires fewer measurements. In general, the minimization problem associated with ℓq norm can be solved by the following non-trivial optimization problem

where λ > 0 is a parameter. However, it is in general difficult to provide a thorough theoretical understanding for finding a global solution. Besides, how to choose a proper q to yield the best result is also an open issue. Fortunately, recent researches [Xu et al., 2012; Cao et al., 2013] have shown that the efficiency of ℓ1/2 and ℓ2/3 regularizations is very high, and their corresponding closed-form thresholding formulas can be easily obtained.

Lemma 1 ([Xu et al., 2012]). For any λ > 0, the optimal solution to

is given by

where ψλ(x) = arccos((λ/4)(x/3)-3/2 ) and γ = 3 3√2/4(2λ)2/3 .

Lemma 2 ([Cao et al., 2013]). For any λ > 0, the optimal solution to

is given by

where Φλ(x) = (2x/φλ(x) - φλ(x)2 )1/2 with φλ(x) = (2/√3)(2λ)1/4 (cosh(arccosh(27x2 (2λ)-3/2 /16)/3))1/2 and γ = 2/3(3(2λ)3 )1/4 .

Accordingly, to improve the efficiency of our proposed method without sacrificing performance, we only consider the nonconvex ℓq regularization with q ∈ {1/2, 2/3}.

3 Methodology

This section firstly formulates the proposed NLRSC-MvSC model by utilizing the cross-view and underlying structure information comprehensively. Then, an effective algorithm with convergence guarantee is devised to address the resultant optimization problem.

3.1 ProblemDefinition

Given multi-view data X = {X1, X2, . . . , XV }, where each Xv ∈ Rdv×n denotes the v-th feature matrix. The purpose of MvSC is to divide the given samples into k groups. To improve the performance of MvSC method, the two general prior principles, i.e., Complementarity and Consistency, should be fully considered.

Complementarity. In most practices, one data object can be described by different subspace information from multiple views, which are commonly complementary with each other. Therefore, it is of prime importance to maximize the diversity of joint representations so as to pursue a comprehensive information fusion. To this end, by leveraging the superior ℓq norm and subspace self-expressiveness property, a nonconvex low-rank MvSCmodel is proposed

where Cv denotes the v-th view's learned subspace representation, Ev denotes the error matrix for characterizing the noise and outliers, β > 0 denotes a balance parameter, and the ℓ2,q norm is a sparser error characteristic than ℓ2,1 due to the embedding of ℓq penalty.

Consistency. It is well known that all the view representations exhibit a common block diagonal structure with different value magnitudes. Instead of forcing each pair of them tend to be similar, we advocate to enhance the consistent block diagonal property across representation matrices, while retaining the diversity within them. Thus, a shared structural constraint on each subspace representation is introduced into (6), and the final NLRSC-MvSC model can be formulated as

where λ is a trade-off parameter for balancing each term, ⊙ denotes the Hadamard product [Zhang, 2017], and Wi,j ∈ [0, 1] represents the soft weight on each coefficient. Ideally, the coefficients of inter-cluster samples should be assigned the largest weight 1, while the smallest 0 is weighted on intracluster samples. However, the label information of data is unknown in unsupervised MvSC tasks. Aim to obtain an expected weight, a efficacious strategy is given as follows

where ⟨·, ·⟩ is the inner product, H = [ ˆX1; ˆX2; . . . ; ˆXV ]T ∈ RD×n with D = d1 + d2 + · · · + dV denotes the vertical concatenation of all normalized feature sets ˆXv, and ξ is set to the average of all 1 - | ⟨H;,i,H;,j⟩ |s empirically. In this way, the angle information among confounding data points can be fully exploited for accurate subspace segmentation.

3.2 Optimization

By drawing on the powerful alternating direction method of multipliers (ADMM) [Kuybeda et al., 2013; Liu et al., 2023b] framework, the nonconvex and multi-variable problem arising by model (7) can be effectively solved with the following designed algorithm.

According to the ADMMmethod, we introduce two auxiliary variables into each view-specific subproblem for the separability of Cv, and then (7) is equivalent to the following form.

Now, the Augmented Lagrangian function of constrained problem (9) can be given with three dual multipliers Mv,1,Mv,2 andMv,3, i.e.,

where Ω(A, B) = ⟨A, B⟩ + (µ/2)∥B∥2F , µ > 0 is a penalty scalar. Then, the unconstrained problem (10) can be optimized by solving the subproblem of each variable alternately.

Update Pv: Fixing the other variables, the subproblem involving with Pv can be written as

For simplicity, let Y = Cv +Mv,1/µ, and the SVD of Y be UDiag(σ(Y))VT . Its solution can be achieved by the closed-form thresholding formulas in Lemma 1 and 2

Update Sv: Fixing the other variables, the subproblem involving with Sv can be written as

Let Y = Cv +Mv,2/µ and B = (λ/µ)W. Similar to (11), we obtain

Update Cv: Fixing the other variables, the subproblem involving with Cv can be written as

The convex quadratic equation (15) can be easily solved by taking the derivative with respect to Cv and setting it to zero, we get

Update Ev: Fixing the other variables, the variable Ev can be achieved by the following subproblem

where Y can be obtained as [Liu et al., 2012]

Algorithm 1 Algorithm for solving problem (9)

Input: Multi-view data {X1,X2 . . . ,XV }, weight matrix W and parameters λ, β, q.

Initialize: Cv = Pv = Sv = 0, Ev = 0, Mv,1 = Mv,2 = Mv,3 = 0, ∀v ∈ {1, 2, . . . , V }; µ = 10-2 , µmax = 1010 , ρ = 2; ϵ = 10-6 .

Output: {C∗v }Vv=1 .

• 1: while not converged do
• 2: for v = 1 : V do
• 3: Update Pv by (12);
• 4: Update Sv by (14);
• 5: Update Cv by (16);
• 6: Update Ev by (18);
• 7: UpdateMv,1,Mv,2,Mv,3 and µ by (20)-(23);
• 8: end for
• 9: Check the convergence criterion: max{∥Cv - Pv∥∞, ∥Cv - Sv∥∞, ∥Xv - XvCv - Ev∥∞} < ϵ
• 10: end while

Update Mv,1,Mv,2,Mv,3 and µ: The multipliers and penalty scalar can be updated by



where ρ > 1 denotes the step size for convergence. The details of our proposed optimization scheme are stated in Algorithm 1.

With the obtained set of optimal subspace representations {C∗v }Vv=1 , the compact affinity graph G can be constructed by the following fusion mechanism

Then, the clustering labels for MvSC can be achieved by conducting the spectral clustering [Ng et al., 2001] on G.

3.3 Theoretical Analysis

Computational Complexity. The time complexity of our proposed algorithm is mainly to solve the subproblems involving with Pv, Sv,Cv and Ev, respectively. To be specific, updating Pv takes O(n3 ) due to SVD operation. The complexity of updating Sv is O(n2 ). For variable Cv, its updating relies on the operations of SVD, matrix multiplication and inverse, thus the complexity is O(n3 + n2dv). Besides, updating Ev with matrix multiplication costs O(n2dv) time. Consequently, the Algorithm 1 has the computational complexity of O(KV n3 ) (assuming dmax ≤ n), where dmax = max{d1, d2, . . . , dV }, K denotes the number of iterations.

Convergence Analysis. In addition to the terrific performance, it is also indispensable to establish the rigorous convergence guarantee of the proposed algorithm. Thus, a reliable analysis is theoretically provided in following Theorem 1, which demonstrates that the sequence generated by our proposed algorithm converges to a stationary KKT critical point. The detailed proof is provided in the supplementary material 1 .

Table 1: Statistical details of benchmark datasets. Clu. and Sam. denote the Cluster and Sample, respectively.

Theorem 1. Let the sequence {Θk = (Ckv , Pkv , Skv , Ekv ; Mkv,1 , Mkv,2 , Mkv,3 )}∞k=1 be generated by Algorithm 1. Then, we have

1. The sequence {Θk }∞k=1 is bounded, and has at least one accumulation point.
2. Any accumulation point Θ∗ satisfies

4 Experiments

In this section, we evaluate our proposed NLRSC-MvSC model on five benchmark datasets in comparison with ten representative clustering models. Then, the clustering performance and robustness of NLRSC-MvSC are analyzed.

4.1 Datasets and Experimental Setting

Datasets. In our experiments, five popular datasets under different clustering scenarios are selected. Their brief descriptions are reported as follows, and detailed statistical data are shown in Table 1.

• Yale is a face dataset which contains 165 data samples from 15 subjects in each view. And three types of features are extracted, i.e., Intensity, LBP and Gabor.
• MSRC-v1 is a object dataset. It consists of 7 subjects with 210 images in each view. Six image features are adopted, that is, HOG, SIFT, LBP, CENT, GIST and CMT.
• BBC4view is a news text dataset with four different views. Each includes 685 documents from five topics.
• 100leaves is a object dataset consists of 1600 leaf samples belonging to 100 plant species. The shape, margin and texture features of each leaf are employed as three different views.

1 https://github.com/wangzhi-swu/NLRSC-MvSC.

• ProteinFold contains 12 distinct view features. Each has 27-fold classes with 694 protein domains.

ComparedModels. In order to demonstrate the superiority of our proposed model, ten representative clustering models are selected as the competitors. One of them is the classical LRR model, which performs single-view clustering on the features that concatenated by all views. The rest are multi-view clustering models, including DiMvSC [Cao et al., 2015], LMvSC [Zhang et al., 2017], MvLRSSC-Pairwise [Brbi´c and Kopriva, 2018], MvLRSSC-Centroid [Brbi´c and Kopriva, 2018], LS-MvSC [Kang et al., 2020], MvLRR [Chen et al., 2022], EOMvSC-CA [Liu et al., 2022], MvLPL [Liu et al., 2023a] and MMvGC [Tan et al., 2023]. To ensure fairness, we run the source codes provided by their authors with the parameters recommended in articles.

Clustering Metrics. Four metrics are employed as the comprehensive evaluation of clustering performance, including accuracy (ACC), normalized mutual information (NMI), adjusted rand index (ARI) and F1-score (F1). The higher the scores of metrics, the better the clustering performance. All experiments are conducted by MATLAB R2020b on a Workstation with Intel(R) Xeon(R) Gold 6230 CPU@2.10GHz and 256GB RAM.

4.2 Performance Evaluation

The clustering performance on five datasets of all competing methods are listed in Table 2 - Table 6. The highest and second highest scores are marked in bold and underline, respectively. Then, the experimental results are analyzed as follows

• It can be seen that our proposed methods can always achieve the highest scores on all metrics and datasets. For instance, on Yale dataset, NLRSC-MvSC (q = 2/3) significantly improves the scores in terms of ACC, NMI, ARI and F1 by 3.64%, 4.89%, 6.67% and 6.29% compared to others. This indicates that the proposed model can fully utilize the consistency and complementarity of multi-view features, thereby contributing to learn a more comprehensive subspace representation.
• In order to verify the performance improvement of the consistent structural constraint in NLRSC-MvSC, we visualize the affinity graphs produced by different methods in Figure 2. It can be observed intuitively that the affinity graph constructed by our method exhibits a more distinct block diagonal structure with less deceptive pairwise correlations, as marked in MvLRR and MMvGC graphs by red boxes. Thus, our graph can provide more discriminable subspace information for clustering process. In addition, the block saliency of obtained graphs

can be quantitatively measured by the Contrast Index (CI), which is defined as [Li et al., 2019b]

where Dsum and Nsum denote the summation of affinity values belonging to the diagonal and nondiagonal blocks, respectively. As shown in Table 7, NLRSCMvSC achieves the highest score in comparison with several state-of-the-art methods. This can be attributed to the accurate subspace segmentation of confounding samples under the structural constraint.

• Furthermore, we apply the t-distributed stochastic neighbor embedding (t-SNE) technique [van der Maaten and Hinton, 2008] to compare the low rankness of fusion representations learned by NLRSC-MvSC and other nuclear norm-based methods. Specifically, we first obtain

the cluster indicator matrix F by solving the following Laplacian embedding problem [Gao et al., 2015]

where LG = A-G is Laplacian matrix, G can be constructed by (24), and A denotes a diagonal matrix with elements Ai,i = ∑j Gi,j . The optimal F ∈ Rn×c can be yield by the eigenvectors of LG corresponding to the smallest c eigenvalues, where c is the number of clusters. Then, a 2-D visualization of the clustering quality can be plotted by t-SNE with input F. It can be seen in Figures 3e and 3f that there exist more larger gaps between the clusters dyed in different colours, while the points in same cluster are closer to each other. This means that the coefficient matrix learned by NLRSC-MvSC has a more compact and lower-rank subspace structure, which better reflects the superiority of nonconvex ℓq regularization in terms of complementarity preserving.

4.3 Discussions

Parameter Sensitivity. Here, we tune the model parameters λ and β in a wide range, i.e., {10-6 , 10-5 , . . . , 1, 10} and show their impact on the clustering performance of two datasets in Figure 4. It can be seen that the ACC metric of NLRSC-MvSC stably remains at a relatively higher score, which implies that our method has the robust capability to cope with various clustering perturbations. Generally, the better clustering results can be obtained with the moderate λ and β, such as {10-3 , 10-2 , 10-1 }.

Numerical Convergence. In spite of the rigorous convergence analysis of the proposed algorithm given in Theorem 1, we also experimentally record the Maximum Error (ME) value during iterations, which is defined as ME = max{Err1,Err2, . . . , ErrV }, where Errv = max{∥Cv - Pv∥∞, ∥Cv -Sv∥∞, ∥Xv -XvCv -Ev∥∞}. As presented in Figure 5, the curves on three datasets rapidly drop to 0 within about 5 iterations and remain smooth thereafter, which demonstrates that our algorithm can achieve convergence efficiently and reliably.

5 Conclusion

In this paper, we proposed a novel NLRSC-MvSC model by employing the nonconvex ℓq regularization for multi-view data clustering. Thanks to the proposed model, the intrinsic global low-rank structure in multi-view data can be efficiently captured, and confounding points can be carefully handled. As a result, a more comprehensive subspace representation can be learned. Extensive experiment results on various datasets show the superiority of our proposed model in clustering performance.

Acknowledgments

This work was supported in part by the Natural Science Foundation of China under Grant 72374173, in part by the Fundamental Research Funds for the Central Universities under Grant SWU-XDJH202303, and in part by Chongqing Innovative Research Groups under Grant CXQT21005.