Centralized joint sparse representation for multi-view subspace clustering

Abstract

Multi-view subspace clustering arises in many computer visional tasks such as object recognition and image segmentation. The basic idea is to measure the same instance with multiple views. In this paper, we proposed two centralized joint sparse representation models, namely, Centralized Global Joint Sparse Representation (CGJSR) and Centralized Local Joint Sparse Representation (CLJSR) for multi-view subspace clustering. CGJSR and CLJSR force the concatenated representation matrix of all views and the representation matrix of each view to be sparse respectively. Both CGJSR and CLJSR allow the sparse coefficient matrix to approach a unified latent structure with an acceptable error. Noises and outliers regularization terms are included in CGJSR and CLJSR to reduce the influence of noises and outliers. Related optimization problems are solved using the alternating direction method of multipliers. Compared with seven state-of-the-art multi-view clustering algorithms, our proposed algorithms can achieve better or comparable results on four real-world datasets.

Keywords

Sparse representation feature fusion multi-view subspace clustering

1 Introduction

In many real-world applications, data are collected from multiple views or multiple features. For example, web-pages can be represented by page-text or hyperlinks pointing to them [1]. Biometrics system can be presented by face, fingerprints or iris [2]. Since more useful information exists in multi-view dataset than in a single view, multi-view learning algorithms can result in better performances [3 –5]. In recent years, many efforts have been made to develop multi-view clustering algorithms from different viewpoints due to its widely practical applications. Multi-view clustering aims to group the samples based on the multiple representation of the sample.

Most previous multi-view clustering methods can be divided into three major categories: (1) graph-based and multi-kernel learning algorithms; (2) co-training or co-regularized style algorithms; (3) subspace learning algorUithms [6]. First, the graph-based algorithms explore the relationship among different views by fusing multiple graphs [7 –13]. Proposes a multi-view clustering algorithm which constructs a bipartite graph by disagreement minimization to connect the two-view feature [9]. Mainly fuses the corresponding weighted graphs by a common transition matrix to learn the consistent information [10]. Iteratively updates the hyper-parameters of traditional graph-based algorithms to obtain optimal graph representations and a consistent manifold without relying on any predefined parameter [11]. Mainly applies a rank constrain to the Laplacian matrix to directly output cluster indicators and proposes a new disagreement cost function to measure the difference between any two views. Similar to [11, 12], considers the rank property of the Laplacian matrix and learns a global graph [13]. Integrates Norm Regularization, Exponential Decay and p-th Root Loss into a unified weighting learning paradigm. Multiple Kernel Learning (MKL) [5 , 14–15] technique has also been used to integrate information from different features by learning a weighted combination of respective kernels, which is most related to graph-based algorithms [15]. Proposes a multi-kernel learning based multi-view clustering algorithm by adaptively estimate the kernel weight. However, for multi-view systems, weight determination during testing is important, based on the quality of views [4]. Second, Co-training and co-regularized style algorithms often construct separate learners on distinct views, then utilize the information in each learner to constrain other views [16 –18]. This kind of method should satisfy two main assumptions for success: sufficiency and conditional independence [16]. Proposes a co-training style multi-view clustering method which utilizes the spectral embedding from one view to constrain the adjacent matrices in other views [17]. Proposes two co-regularized style methods (CO-P and CO-C) which implicitly combines graphs from multiple views of the data to achieve a better result. Both the graph-based and multi-kernel learning algorithms and the co-training or co-regularized style algorithms can handle high-dimensional data by dimension reduction, but the limitation of them is that they depend tightly on a reasonable graph (kernel or spectral) based on clean data and an effective measurement method. In fact, it is hard to reasonably determine a measurement method and the similarity of the samples for a dataset with noise and outliers.

In recent years, many researchers have efforts to subspace learning methods that not only select features but also learn cleaner data by self-representation, Multi-view Canonical Correlation Analysis (CCA) and so on. This kind of algorithms supposes that the observations from different views are generated from a union of low-dimensional subspaces. These algorithms are roughly categorized: (1) multi-view CCA clustering; (2) multi-view subspace clustering. First, Multi-view CCA [19] projects the multi-view data onto a low-dimensional subspace for clustering, but such dimensionality reduction methods are specifically designed for two views. Tensor CCA in [20] extends the above CCA based algorithm to handle views more than two by analyzing the covariance tensor of different views. Second, multi-view subspace clustering methods expect to explore the latent subspace structure of samples with self-representation [21 , 25]. Introduces a low-rank tensor constrain to explore the complementary information from multi-view data based on low-rank tensor representation [6] and [26] propose multi-view subspace clustering algorithms by utilizing the tensor-singular value decomposition (t-SVD) based nuclear norm (t-TNN) [24, 27]. Extends the classical subspace clustering algorithms SSC [28], LRR [29] and LRSSC [30] to multi-view data by exploiting the self-expressiveness property of each sample in its respective view and enforcing the common representation across the views. The latent representation is divided into two parts, i.e. shared consistency and specificity, and both parts are jointly learned in [31, 32]. Adds a block diagonal constrain to the latent representation. Pairwise MLRSSC and Centroid-based MLRSSC (C-MLRSSC) in [22] respectively encourage the consistency from pair views and all views to be similar [21]. SSuts forward a diversity-induced multi-view subspace clustering (DiMSC) algorithm which utilizes the Hilbert Schmidt Independence Criterion (HSIC) to explore the complementarity of multi-view representations [33]. Combines self-representation learning and clustering in each view, and explores the consensus graph structure by common clustering indicator. Similar to [21 , 34], Preserves the diversity of each view by HSIC criterion and learns a common shared coefficient matrix by low-rank representation. Obviously, high-quality latent representation is crucial to construct an effective graph structure or to be used to clustering algorithms. Multi-view subspace clustering can embed all latent representations into a unified subspace to fuse complementary information from distinct views and doesn’t bridge any two subspaces repeatedly.

In the real word, most datasets often contain noises and outliers, and each view from a specific source should have unique effect. However, most previous multi-view subspace clustering methods either ignore the specificity of each view by using the common latent representation with no error of different views [24 , 34], or ignore the noises or outliers of samples [22 , 32]. Given these limitations, two centralized joint sparse representation algorithms, namely Centralized Global Joint Sparse Representation (CGJSR) and Centralized Local Joint Sparse Representation (CLJSR) are proposed in this paper. Fig. 1 lists the framework of our proposed algorithm. The main contributions of our algorithms are as follows:

Fig.1

Illustration of our method. Given a dataset X with V views and n samples, i.e. X ⁽¹⁾, X ⁽²⁾, … X ^(V) each view is represented by a coefficient matrix, a small additive noise term and a sparse noise term, i.e. Γ ^⁽¹⁾, Γ ^⁽²⁾, … Γ ^{^(V)}, N ⁽¹⁾, N ⁽²⁾, … N ^(V) and E ⁽¹⁾, E ⁽²⁾, … E ^(V). The view-consistent affinity matrix G is generated by the fusion of distinct coefficient matrices and is applied to spectral clustering to output the labels.

CGJSR and CLJSR not only consider the specific of representation matrix of different views, but also consider the influence of data noises and outliers.

A centralized sparse term is used to represent the consistency information from all views. The sparse representation matrices of different views are not to be exactly the same to preserve the specificity of each view. For two types of noise, the Frobenius norm is used to enhance the robustness to the small and additive noise (such as Gaussian Noise), while the l₂ norm is used to enhance the robustness to the sparse noise (such as outliers).

Compared with seven state-of-the-art multi-view clustering algorithms, our proposed algorithms can achieve better or comparable results on four real-world datasets.

The paper is organized as follows. Section 2 introduces the multi-view subspace clustering problem and the related multi-view subspace clustering algorithms. In Section 3, two multi-view subspace clustering algorithms are proposed. The experimental results and analyses are presented in section 4. Finally, section 5 gives the conclusions and future work.

2 Background and related work

In this section, we list some algorithms that are most related to our work.

2.1 Multi-view subspace clustering

Given a dataset X = { X ¹, X ^², …, X ^V} of V different views, where each $X^{i} = {X_{j}^{i} \in ℝ^{d_{j} \times 1}}_{j = 1}^{n}$ is described with its own set of d_i features. Assume that the samples are drawn from a union of C subspace, the task of multi-view subspace clustering is to simultaneously cluster the samples in distinct views according to their subspaces.

Here we list some nations that will be used in the following sections: ∥ A ∥ ₁ = ∑_i,j|a_ij|, $∥ A ∥_{F} = (\sum_{ij} a_{ij}^{2})^{1 / 2}$ , ∥A ∥ _2,1 = ∑_i ∥ A_:,i ∥ ₂ and ∥ A ∥ _1,q = ∑_i ∥ A _i,: ∥ _q.

2.2 Related algorithms

Here we introduce some multi-view subspace clustering algorithms that are closely related with our work.

The C-MLRSSC in [22] enforces representations across different views towards a common centroid term. It aims to solve the following minimization problem: $\begin{matrix} \begin{matrix} \min_{Γ^{1}, Γ^{2}, \dots, Γ^{V}, G} \sum_{i = 1}^{V} (λ_{1} ∥ Γ^{i} ∥_{*} + λ_{2} ∥ Γ^{i} ∥_{1} \end{matrix} \\ + β_{i} ∥ Γ^{i} - G ∥_{F}^{2}) \\ s . t . X^{i} = X^{i} Γ^{i}, diag (Γ^{i}) = 0, i = 1, \dots V \end{matrix}$ (1) where X ⁱɛR^d_i×n is the data matrix of view i, $Γ^{i} ɛ ℝ^{n \times n}$ is the linear representation coefficient matrix for view i, and $G ɛ ℝ^{n \times n}$ denotes the consensus variable. Notice that the term $∥ Γ^{i} - G ∥_{F}^{2}$ will promote G to include complementary information of single view Γ ⁱ, but the term X ⁱ = X ⁱ Γ ⁱ does not consider the effect of data noises and outliers.

The CSMSC in [31] jointly exploits the consistency and specificity for subspace representation learning. The optimization problem is as follows: $\begin{matrix} \begin{matrix} \min_{\begin{matrix} D^{1}, D^{2}, \dots, D^{V}, G \\ E^{1}, E^{2}, \dots, E^{V} \end{matrix}} λ_{1} ∥ G ∥_{*} + λ_{2} \sum_{i = 1}^{V} ∥ D^{i} ∥_{2}^{2} \end{matrix} \\ + \sum_{i = 1}^{V} ∥ E^{i} ∥_{2, 1} \\ s . t . X^{i} = X^{i} (G + D^{i}) + E^{i}, i = 1, \dots V \end{matrix}$ (2) where $G ɛ ℝ^{n \times n}$ and $D^{i} ɛ ℝ^{n \times n}$ are learned consistent and specific self-representation matrices with data under different views. ${∥ E^{i} ∥}_{2, 1}$ encourages the columns of E ⁱ to be zero, which means that some data vectors are corrupted and the others are clean.

After obtaining the self-representation, the joint affinity matrix can be directly computed from the self-representation i.e. W = (| G | + | G |^T)/2. Then standard spectral clustering algorithm can be applied to the inferred joint affinity matrix to find the final assignment of the data points to corresponding clusters.

MVSC in [33] use a common cluster structure to guarantee the consistence among different views. The optimization problem is as follows: $\begin{matrix} \min_{\begin{matrix} Γ^{1}, Γ^{2}, \dots, Γ^{V}, F \\ E^{1}, E^{2}, \dots, E^{V} \end{matrix}} λ_{1} \sum_{i = 1}^{V} Tr (F^{T} (D^{i} - W^{i}) F) + \\ \sum_{i = 1}^{V} (∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2} + λ_{2} ∥ E^{i} ∥_{1}) \\ s . t . {(Γ^{i})}^{T} 1 = 1, Γ^{i} (j, j) = 0, \\ F^{T} F = I, i = 1, \dots V \end{matrix}$ (3) where $Γ^{i} ɛ ℝ^{n \times n}$ is the linear representation coefficient matrix for view i, and $E^{i} \in ℝ^{d_{i} \times n}$ is the sparse outliers for view i. F is the cluster indicator matrix, $W^{i} = \frac{| {(Γ^{i})}^{T} | + | (Γ^{i}) |}{2}$ and $D^{i} \in ℝ^{n \times n}$ is a diagonal matrix with diagonal elements defined as D ⁱ (j, j) = ∑_kbiWⁱ (j, k). Notice that MVSC only consider the consistence of different views.

3 Centralized joint sparse representation algorithms

Noticing that the practical data may contain noises and outliers simultaneously, and the specificity of different views is also important to the learning of self-representation matrix, two centralized joint sparse representation algorithms CGJSR and CLJSR are proposed in this section. The proposed algorithms not only consider the error of the representation matrix of different views by permitting the representation matrix not to be exactly the same, but also consider the influence of data noises and outliers by imposing different error regularization. The alternating direction method of multipliers (ADMM) is used to solve the proposed optimization models.

3.1 Centralized global joint sparse representation algorithm (CGJSR)

Given a training dataset X ={ X ¹, X ², …, X ^V } of V different views, where each $X^{i} = {X_{j}^{i} \in ℝ^{d_{i}}}_{j = 1}^{n}$ is described with its own set of d_i features. For view i, suppose that $X^{i} \in ℝ^{d_{i} \times n}$ can be represented by the linear combination of training samples from the same class, thus can be represented by all the training samples X ⁱ. Considering that data are contaminated by small additive noise $N^{i} \in ℝ^{d_{i} \times n}$ and occlusion $E^{i} \in ℝ^{d_{i} \times n}$ with arbitrary large magnitude, we have the observation model: $\begin{matrix} X^{i} = X^{i} Γ^{i} + N^{i} + E^{i}, i = 1, 2, \dots, V \end{matrix}$ (4) where ${Γ^{i}}_{i = 1}^{V} \in ℝ^{n \times n}$ are the linear representation coefficient matrices. These coefficient matrices ${Γ^{i}}_{i = 1}^{V}$ from V observation views are concatenated as Γ = [ Γ ¹, Γ ², …, Γ ^V]. As X ⁱ can be represented by samples from the same class, the concatenated matrix Γ is expected to be a row sparse matrix with only few nonzero rows. So we impose sparsity ∥ Γ ∥ _1,q on Γ and wish to solve the following optimization problem: $\begin{matrix} \begin{matrix} min_{Γ, {E^{i} |}_{i = 1}^{V}, G} \frac{1}{2} \sum_{i = 1}^{V} (∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2} # \end{matrix} \\ + λ_{3} ∥ Γ^{i} - G ∥_{F}^{2} + λ_{2} ∥ E^{i} ∥_{1}) + λ_{1} ∥ Γ_{1, q} \end{matrix}$ (5)

As for each view i, $∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2}$ denotes the small and dense noises of data, and ∥ E ⁱ ∥ ₁ is the sparse occlusion matrix. Notice that the term $∥ Γ^{i} - G ∥_{F}^{2}$ will promote G to include complementary information of single view Γ ⁱ, thus the unified latent structure G can best represent the relationship between each view. λ₁, λ₂ and λ₃ are nonnegative parameters which control the sparsity of global sparse coefficients, the sparsity of occlusion term and the coefficient approximation error between the coefficient matrix and centralized term respectively.

Once $\hat{G}$ is obtained, the nonnegative and symmetric affinity matrix can be constructed by W = | G | + | G |^T. The clustering results of the data ${X^{i}}_{i = 1}^{V}$ are then achieved by applying spectral clustering algorithms such as the Normalized Cuts [36].

3.2 Centralized local joint sparse representation algorithm (CLJSR)

The sparsity of concatenated matrix Γ may lead to the loss of data information by setting most rows of Γ to zero. This simple operation may not fully exploit data information. In order to overcome this shortcoming, a Centralized Local Joint Sparse Representation (CLJSR) model is proposed by replacing ∥ Γ ∥ _1,q with ∥ Γ ⁱ ∥ _1,q and solving the following optimization problem: $\begin{matrix} \begin{matrix} min_{\begin{matrix} Γ^{1}, \dots, Γ^{V} \\ E^{1}, \dots, E^{V}, G \end{matrix}} \frac{1}{2} \sum_{i = 1}^{V} (∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2} \end{matrix} \\ + λ_{1} ∥ Γ^{i} ∥_{1, q} + λ_{2} ∥ E^{i} ∥_{1} + λ_{3} ∥ Γ^{i} - G ∥_{F}^{2}) \end{matrix}$ (6)

As for each view i, Γ ⁱ is a row sparse matrix with only few nonzero rows, as X ⁱ can be represented by samples from the same class. The meanings of ∥ E ⁱ ∥ ₁ and $∥ Γ^{i} - G ∥_{F}^{2}$ are the same as those in the former model CGJSR. λ₁, λ₂ and λ₃ control the effect caused by the sparsity of local-coefficient matrix Γ ⁱ, the sparsity of occlusion matrix and the coefficient approximation error between the coefficient matrix and centralized term respectively.

3.3 Optimization via ADMM

In this section, an optimization algorithm by the popular ADMM algorithm [36, 37] is developed to solve Equations (5) and (6). Because the solving processes of Equations (5) and (6) are similar, here we only present the detailed program for solving Equation (6).

Firstly, two auxiliary variables $U^{i} \in ℝ^{d_{i} \times n}$ and $V^{i} \in ℝ^{n \times n}$ are introduced to make the objective function separable and ensure each step has a closed-solution. Equation (6) can be converted to the following equivalent problem:

$\begin{array}{l} \min_{\begin{matrix} Γ^{1}, \dots, Γ^{V} \\ E^{1}, \dots, E^{V}, G \end{matrix}} \frac{1}{2} \sum_{i = 1}^{V} (‖ X^{i} - X^{i} Γ^{i} - E^{i} ‖_{F}^{2} + λ_{1} ‖ V^{i} ‖_{1, q} \\ + λ_{2} ‖ U^{i} ‖_{1} + λ_{3} ‖ Γ^{i} - G ‖_{F}^{2}) \\ s .t . E^{i} = U^{i}, Γ^{i} = V^{i} \end{array}$ (7)

The augmented Lagrange function is given by:

$\begin{matrix} L (Γ^{i}, E^{i}, G, U^{i}, V^{i}; A_{E^{i}}, A_{Γ^{i}}) = \frac{1}{2} \sum_{i = 1}^{V} ( \\ ∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2} + λ_{1} ∥ V^{i} ∥_{1, q} + λ_{2} ∥ U^{i} ∥_{1} \\ + λ_{3} ∥ Γ^{i} - G ∥_{F}^{2} + < A_{E^{i}}, E^{i} - U^{i} > \\ + \frac{α_{E}}{2} ∥ E^{i} - U^{i} ∥_{F}^{2} + < A_{Γ^{i}}, Γ^{i} - V^{i} > \\ + \frac{α_{Γ}}{2} ∥ Γ^{i} - V^{i} ∥_{F}^{2}) \end{matrix}$ (8) where < A , B > represents for the trace of A ^T B , A _{E
ⁱ} > 0 and A _{Γ

ⁱ} > 0 are the Lagrange multipliers, α_E > 0 and α_Γ > 0 are penalty parameters for penalizing the violation of equality constraints. The ADMM algorithm updates the variables Γ ⁱ, E ⁱ, G , U ⁱ and V ⁱ alternatively, by minimizing L with other variables fixed.

1) Update Γ ⁱ

The objective function in Equation (8) with E ⁱ, G , U ⁱ and V ⁱ fixed can be written as: $\begin{matrix} \begin{matrix} min_{Γ^{i}} \frac{1}{2} (∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2} + λ_{3} ∥ Γ^{i} - G ∥_{F}^{2} \end{matrix} \\ + < A_{Γ^{i}}, Γ^{i} - V^{i} > + \frac{α_{Γ}}{2} ∥ Γ^{i} - V^{i} ∥_{F}^{2}) \end{matrix}$ (9)

Computing the derivative of Equation (9) with respect to Γ ⁱ and setting it zero, the solution of Equation (9) can be obtained by: $\begin{matrix} \begin{matrix} Γ_{t + 1}^{i} = {(2 X^{i^{T}} X^{i} + (2 λ_{3} + α_{Γ}) I)}^{- 1} \end{matrix} \\ [2 X^{i^{T}} (X^{i} - E_{t}^{i}) + 2 λ_{3} G_{t} + α_{Γ} V_{t}^{i} - A_{Γ^{i}, t}] \end{matrix}$ (10) where I is an identity matrix whose dimension is n.

2) Update Eⁱ

The objective function in Equation (8) with Γ ⁱ, G , U ⁱ and V ⁱ fixed can be written as: $\begin{matrix} \begin{matrix} min_{E^{i}} \frac{1}{2} (∥ X^{i} - X^{i} Γ^{i} - E^{i} ∥_{F}^{2} \end{matrix} \\ + < A_{E^{i}}, E^{i} - U^{i} > + \frac{α_{E}}{2} ∥ E^{i} - U^{i} ∥_{F}^{2}) \end{matrix}$ (11)

Computing the derivative of Equation (11) with respect to E ⁱ and setting it zero, the solution of Equation (11) can be obtained by: $\begin{matrix} \begin{matrix} E_{t + 1}^{i} = {(2 + α_{E})}^{- 1} \\ (2 X^{i} - 2 X^{i} Γ_{t + 1}^{i} + α_{E} U_{t}^{i} - A_{E^{i}, t}) \end{matrix} \end{matrix}$ (12)

3) Update G

Fixed the variables except G , the third sub-problem on G is written as: $\begin{matrix} min_{G} \frac{1}{2} \sum_{i = 1}^{V} (λ_{3} Γ^{i} - G_{F}^{2}) \end{matrix}$ (13)

Calculating the derivative of Equation (13) with respect to G and setting it zero, the solution of Equation (13) is as follows: $\begin{matrix} G_{t + 1} = \frac{1}{V} \sum_{i = 1}^{V} Γ_{t + 1}^{i} \end{matrix}$ (14)

4) Update V ⁱ

The objective function in Equation (8) with Γ ⁱ, E ⁱ, G and U ⁱ fixed can be written as: $\begin{matrix} \begin{matrix} min_{V^{i}} \frac{1}{2} (λ_{1} ∥ V^{i} ∥_{1, q} + < A_{Γ^{i}}, Γ^{i} - V^{i} > \end{matrix} \\ + \frac{α_{Γ}}{2} ∥ Γ^{i} - V^{i} ∥_{F}^{2}) \end{matrix}$ (15)

The last two items can be formulated into complete squares, so Equation (15) can be converted into the following problem:

$min_{V^{i}} \frac{1}{2} (\frac{λ_{1}}{α_{Γ}} ∥ V^{i} ∥_{1, q} + \frac{1}{2} ∥ Γ^{i} + α_{Γ}^{- 1} A_{Γ^{i}} - V^{i} ∥_{F}^{2})$ (16)

Due to the separable structure of Equation (16), it can be solved by minimizing it with respect to each row of V ⁱ separately. Let $r_{j}^{i}$ , $a_{j}^{i}$ and $v_{j}^{i}$ denote the jth row of matrices Γ ⁱ, A _{Γ

ⁱ} and V ⁱ respectively. Referring the method in reference [6], for each row j = 1, 2, …, n, Equation (16) is reformulated as the following subproblem: $\begin{matrix} v_{j, t + 1}^{i} = \underset{v^{i}}{argmin} \frac{1}{2} {| | z - v_{j, t}^{i} | |}_{2}^{2} + η {| | v_{j, t}^{i} | |}_{q} \end{matrix}$ (17) where $z = r_{j, t + 1}^{i} + a_{j, t}^{i} α_{Γ}^{- 1}$ and $η = \frac{λ_{1}}{α_{Γ}}$ . One can derive the solution of Equation (17) for any q. Here we focus on the case of q = 2 and the solution of Equation (17) is as follows: $\begin{matrix} v_{j, t + 1}^{i} = {(1 - \frac{η}{z_{2}})}_{+} z \end{matrix}$ (18) where (v) ₊ is a vector which indicates max(v_i, 0) for each element in the vector. 5) Update U ⁱ

The objective function in Equation (8) with Γ ⁱ, Eⁱ, G and V ⁱ fixed can be written as: $\begin{matrix} \begin{matrix} min_{U^{i}} \frac{1}{2} (λ_{2} {| | U^{i} | |}_{1} + < A_{E^{i}}, E^{i} - U^{i} \end{matrix} > \\ + \frac{α_{E}}{2} ∥ E^{i} - U^{i} ∥_{F}^{2}) \end{matrix}$ (19)

The last two items can be formulated into complete squares, so Equation (19) can be converted into the following problem:

$min_{U^{i}} \frac{1}{2} (\frac{λ_{2}}{α_{E}} {| | U^{i} | |}_{1} + \frac{1}{2} ∥ E^{i} + α_{E}^{- 1} A_{E^{i}} - U^{i} ∥_{F}^{2})$ (20)

It is shown in reference [24] that the Equation (20) can be solved in closed form using the shrinkage-thresholding operator as $\begin{matrix} U_{t + 1}^{i} = S (E_{t + 1}^{i} + α_{E}^{- 1} A_{E^{i}, t}, \frac{λ_{2}}{α_{E}}) \end{matrix}$ (21) where S (a, b) is defined as following: $S (a, b) = {\begin{matrix} s g n (a) (| a | - b) | a | \geq b \\ 0 others \end{matrix}$ .

6) Update the multipliers A _Γ and A _E $\begin{matrix} A_{Γ^{i}, t + 1} = A_{Γ^{i}, t} + α_{Γ} (Γ_{t + 1}^{i} - V_{t + 1}^{i}) \end{matrix}$ (22) $\begin{matrix} A_{E^{i}, t + 1} = A_{E^{i}, t} + α_{E} (E_{t + 1}^{i} - U_{t + 1}^{i}) \end{matrix}$ (23)

The complete algorithm is outlined in Table 1.

Table 1

Multi-view subspace clustering algorithm via CLJSR model

Input: Unlabeled samples ${X^{i}}_{i = 1}^{V}$ , hyperparameters λ₁, λ₂, λ₃
Initialization:
Set Γ ₀, V ₀, U ₀, A _{E ,0}, A _{Γ ,0} as zero matrices.
While not converged do
1. Update Γ ⁱ, i = 1, 2, …, V by Equation (10).
2. Update E ⁱ, i = 1, 2, …, V by Equation (12).
3. Update G by Equation (14).
4. Update V ⁱ, i = 1, 2, …, V by Equation (18).
5. Update U ⁱ, i = 1, 2, …, V by Equation (21).
6. Update, A _V and A _Z by Equation (22) and (23).
end while
${\hat{E}}^{i} = E_{t + 1}^{i} (i = 1 \dots D), {\hat{Γ}}^{i} = Γ_{t + 1}^{i}, \hat{G} = G_{t + 1}$ .
Put $\hat{G}$ into the spectral clustering algorithm.
Output: the clustering results of all samples.

3.4 Computational complexity

The proposed CLJSR which adopts ADMM method to solve CLJSR model, mainly includes the computation of Γ ⁱ, Eⁱ, G, Vⁱ, Uⁱ and lagrange multiplier A_{Γ

ⁱ}, A_{E
ⁱ}. Noticed that (2X^{i
^T}Xⁱ + (2λ₃ + α_Γ) I) is constant, it only need to be calculated once and its complexity is $O (n^{3})$ induced by the multiplication of two n × n matrices. In each iteration, the complexity of updating Γ ⁱ, E ⁱ, V ⁱ and U ⁱ are $O (n^{3} + n^{2} d_{i})$ , $O (n^{2} d_{i})$ , $O (2 n^{2})$ and $O ({nd}_{i})$ induced by the computation of n × d_i matrix multiplied by d_i × n matrix and n × n matrix multiplied by n × n matrix, the multiplication of d_i × n matrix and n × n matrix, the calculation of l₂ norms for n row vectors and the element comparison operation of a n × n matrix, and the comparison operation of each element of a d_i × n matrix, respectively. Therefore, the overall complexity of CLJSR is $O (n^{3} + t \sum_{i = 1}^{V} (n^{3} + n^{2} d_{i} + n^{2} d_{i} + 2 n^{2} + {nd}_{i})),$ where t is the number of iterations and V is the number of the views. Ordinarily, the number of the samples n in each view is larger than the dimension of the data d_i. Then, the overall time complexity of CLJSR is O (tVn³). The solving process of CGJSR is the same as former except that the shrinkage operation of V n × n matrices is replaced by that of a n × nV matrix with the same time complexity. Therefore, the time complexity of CGJSR is also O (tVn³).

4 Experimental results

In this section, the performance of the proposed algorithms CGJSR and CLJSR is evaluated on four datasets including MSRC-V1, NGs, UCI Digits and ORL. We compare the performance of the proposed algorithms CGJSR and CLJSR with seven state-of-the-art multi-view subspace clustering methods such as: co-regularized information-based multi-view spectral clustering algorithms (Co-P and Co-C [17]), Centroid-based multi-view low-rank sparse subspace clustering algorithm (Centroid-based MLRSSC (C-MLRSSC) [22]), multiple graph learning-based clustering algorithms (AMGL [10] and MVGL [12]), multi-view subspace clustering algorithm (MVSC [33]) and clustering algorithm with consistency and specificity (CSMSC [31]).

The parameters of the proposed algorithms and the state-of-the-art algorithms are tuned by grid search method to achieve the best clustering accuracy. Our programs are written in Matlab2017b on a computer with Intel (R) Core i7-6700 2.6 GHz, 12GB RAM memory and Microsoft Windows 10.0.

4.1 Description of dataset

MSRC-V1 1 scene dataset consists of 240 images with 8 classes. Similar to the work in [33], we select 7 classes including airplane, car, bicycle, cow, face, tree and building as test dataset with additive noise. The five views are represented by Color Moment (CM, 24 features), HOG (576 features), GIST (512 features), LBP (256 features) and CENTRIST (CENT, 254 features) respectively.

7 Newsgroups (NGs) 2 dataset with 500 documents and 5 topics is a subset of the 20 Newsgroup dataset. It consists of three views and each view is constructed by applying a specific pre-processing method to each document. The detail of extraction method is introduced in [38].

UCI Handwritten Digits dataset (UCI Digits) 3 includes 2000 samples from 10-digit classes (200 samples per class). It is a natural multi-view dataset and is composed of six feature representations using the Fourier descriptors (76 features), Karhunen-Loeve coefficients (64 features), profile correlations (216 features), morphological (6 features), Zernike moment (47 features) and pixel averages in 2×3 windows (240 features). Specific steps can be referred to [16] and [12].

The ORL 4 face dataset covers 10 different images of 40 distinct subjects. These images present different facial expressions at different times and under diverse illuminations. The GIST (512 features), LBP (59 features), HOG (864 features) and CENT (254 features) are selected as four independent views to describe these images.

The detailed information is descripted in Table 2 and some specific instances of the MSRC-V1 and ORL datasets are displayed in Fig. 2 and Fig. 3 respectively.

Table 2
Statistics of the experimental datasets

Data sets Class No. of each class No. of samples No. of views

MSRC-V1 7 30 210 5

NGs 5 100 500 3

UCI Digits 10 200 2000 6

ORL 40 10 400 4

Data sets	Class	No. of each class	No. of samples	No. of views
MSRC-V1	7	30	210	5
NGs	5	100	500	3
UCI Digits	10	200	2000	6
ORL	40	10	400	4

Fig.2

The sample image of the MSRC-V1 dataset.

Fig.3

The sample image of the ORL dataset.

4.2 Comparison of multi-view subspace clustering algorithms

4.2.1 Experimental results

We evaluate clustering performance using five different metrics: normalized mutual information (NMI), F-score, Precision, Recall, and adjusted rand index (Adj-RI). For all the metrics, higher value means better result. Each algorithm runs 20 times and the average value and standard deviation are recorded. Table 3 displays the results. The best results of the nine algorithms are highlighted in bold type. It can be seen from the Table 3 that:

On MSRC-V1, NGs and ORL dataset, CLJSR performs better than other seven state-of-the-art multi-view subspace clustering algorithms on all metrics. On UCI Digits dataset, the F-score, Precision and Adj-RI of CLJSR are 5.03%, 5.13% and 5.57% higher than the best results of the other seven state-of-art multi-view subspace clustering algorithms, though the NMI and Recall of CLJSR are 0.22% and 1.56% lower than that of MVGL algorithm.

Compared with the other seven state-of-art multi-view subspace clustering algorithms, CGJSR can achieve the best results on MSRC-V1 and NGs datasets on all metrics. On UCI Digits dataset, the F-score, Precision and Adj-RI of CGJSR are 4.97%, 5.11 % and 5.53% higher than the best results of the other seven state-of-art multi-view subspace clustering algorithms, though the NMI and Recall of CGJSR are 0.45% and 1.44% lower than that of MVGL algorithm. On ORL dataset, the F-score, Precision and Adj-RI of CGJSR are 0.19%, 1.26% and 0.20% higher than the best results of the other seven state-of-art multi-view subspace clustering algorithms, though the NMI and Recall of CGJSR are 0.45% and 3.54% lower than that of MVGL algorithm.

CLJSR performs slightly better than CGJSR, which means that the sparsity of the representation coefficient matrix of each view can make use of more discriminant information than the sparsity of the concatenated matrix of the representation coefficient matrix for multi-view subspace clustering problem.

Table 3
Clustering results of nine multi-view clustering algorithms on four datasets

Dataset Algorithms NMI F-score Precision Recall Adj-RI

MSRC-V1 CO-P 0.6118 (0.0371) 0.5936 (0.0529) 0.5774 (0.0600) 0.6115 (0.0465) 0.5257 (0.0631)

CO-C 0.6554 (0.0482) 0.6349 (0.0590) 0.6198 (0.0624) 0.6509 (0.0058) 0.5743 (0.0693)

AMGL 0.6908 (0.0223) 0.6145 (0.0300) 0.5409 (0.0351) 0.7126 (0.0309) 0.5421 (0.0370)

MVGL 0.7532 (0) 0.6736 (0) 0.5860 (0) 0.7921 (0) 0.6117 (0)

MVSC 0.6248 (0.0338) 0.5971 (0.0474) 0.5587 (0.0606) 0.6428 (0.0281) 0.5263 (0.0591)

CSMSC 0.7898 (0.0044) 0.7884 (0.0055) 0.7838 (0.0061) 0.7930 (0.0049) 0.7541 (0.0064)

C-MLRSSC 0.4068 (0.0421) 0.3812 (0.0434) 0.3753 (0.0437) 0.3873 (0.0432) 0.2796 (0.0508)

CGJSR 0.8201 (0.0033) 0.7978 (0.0016) 0.7896 (0.0017) 0.8062 (0.0015) 0.7648 (0.0019)

CLJSR 0.8221 (0.0070) 0.7983 (0.0050) 0.7900 (0.0049) 0.8068 (0.0052) 0.7654 (0.0059)

NGs CO-P – – – – –

CO-C – – – – –

AMGL – – – – –

MVGL 0.4385 (0) 0.5357 (0) 0.3890 (0) 0.8603 (0) 0.3086 (0)

MVSC 0.8111 (0.0517) 0.8387 (0.0817) 0.8127 (0.1215) 0.8737 (0.0315) 0.7949 (0.1085)

CSMSC 0.9623 (0.0000) 0.9761 (0.0000) 0.9758 (0.0000) 0.9763 (0.0000) 0.9701 (0.0000)

C-MLRSSC 0.9653 (0.0423) 0.9663 (0.0666) 0.9574 (0.0937) 0.9778 (0.0316) 0.9570 (0.0860)

CGJSR 0.9670 (0.0000) 0.9801 (0.0000) 0.9800 (0.0000) 0.9801 (0.0000) 0.9752 (0.0000)

CLJSR 0.9721 (0.0000) 0.9839 (0.0000) 0.9837 (0.0000) 0.9840 (0.0000) 0.9799 (0.0000)

UCI Digits CO-P 0.7495 (0.0533) 0.7143 (0.0788) 0.7046 (0.0788) 0.7243 (0.0744) 0.6821 (0.0879)

CO-C 0.7752 (0.0490) 0.7351 (0.0784) 0.7192 (0.0858) 0.7519 (0.0710) 0.7049 (0.0877)

AMGL 0.8648 (0.0259) 0.7993 (0.0475) 0.7493 (0.0684) 0.8596 (0.0382) 0.7752 (0.0540)

MVGL 0.9038 (0) 0.8495 (0) 0.7889 (0) 0.9203 (0) 0.8315 (0)

MVSC 0.7209 (0.0224) 0.6464 (0.0445) 0.5633 (0.0659) 0.7650 (0.0194) 0.6001 (0.0534)

CSMSC 0.8575 (0.0002) 0.8548 (0.0003) 0.8520 (0.0002) 0.8576 (0.0003) 0.8387 (0.0003)

C-MLRSSC 0.8591 (0.0258) 0.8430 (0.0509) 0.8230 (0.0699) 0.8651 (0.0304) 0.8249 (0.0572)

CGJSR 0.8993 (0.0002) 0.9045 (0.0003) 0.9031 (0.0003) 0.9059 (0.0003) 0.8940 (0.0004)

CLJSR 0.9016 (0.0004) 0.9051 (0.0004) 0.9033 (0.0002) 0.9047 (0.0003) 0.8944 (0.0003)

ORL CO-P 0.9150 (0.0118) 0.7431 (0.0345) 0.6935 (0.0424) 0.8011 (0.0284) 0.7367 (0.0354)

CO-C 0.9234 (0.0159) 0.7615 (0.0403) 0.7110 (0.0435) 0.8206 (0.0431) 0.7556 (0.0413)

AMGL 0.9220 (0.0085) 0.6666 (0.0488) 0.5478 (0.0621) 0.8571 (0.0108) 0.6571 (0.0506)

MVGL 0.9371 (0) 0.7151 (0) 0.6023 (0) 0.8800 (0) 0.7073 (0)

MVSC 0.8910 (0.0167) 0.6129 (0.0627) 0.4875 (0.0748) 0.8345 (0.0235) 0.6014 (0.0651)

CSMSC 0.9359 (0.0061) 0.7857 (0.0240) 0.7257 (0.0354) 0.8575 (0.0150) 0.7803 (0.0247)

C-MLRSSC 0.9301 (0.0068) 0.7702 (0.0232) 0.7092 (0.0315) 0.8434 (0.0188) 0.7644 (0.0238)

CGJSR 0.9326 (0.0116) 0.7876 (0.0293) 0.7383 (0.0363) 0.8446 (0.0281) 0.7823 (0.0301)

CLJSR 0.9382 (0.0002) 0.8005 (0.0002) 0.7533 (0.0002) 0.8807 (0.0001) 0.7956 (0.0002)

Dataset	Algorithms	NMI	F-score	Precision	Recall	Adj-RI
MSRC-V1	CO-P	0.6118 (0.0371)	0.5936 (0.0529)	0.5774 (0.0600)	0.6115 (0.0465)	0.5257 (0.0631)
	CO-C	0.6554 (0.0482)	0.6349 (0.0590)	0.6198 (0.0624)	0.6509 (0.0058)	0.5743 (0.0693)
	AMGL	0.6908 (0.0223)	0.6145 (0.0300)	0.5409 (0.0351)	0.7126 (0.0309)	0.5421 (0.0370)
	MVGL	0.7532 (0)	0.6736 (0)	0.5860 (0)	0.7921 (0)	0.6117 (0)
	MVSC	0.6248 (0.0338)	0.5971 (0.0474)	0.5587 (0.0606)	0.6428 (0.0281)	0.5263 (0.0591)
	CSMSC	0.7898 (0.0044)	0.7884 (0.0055)	0.7838 (0.0061)	0.7930 (0.0049)	0.7541 (0.0064)
	C-MLRSSC	0.4068 (0.0421)	0.3812 (0.0434)	0.3753 (0.0437)	0.3873 (0.0432)	0.2796 (0.0508)
	CGJSR	0.8201 (0.0033)	0.7978 (0.0016)	0.7896 (0.0017)	0.8062 (0.0015)	0.7648 (0.0019)
	CLJSR	0.8221 (0.0070)	0.7983 (0.0050)	0.7900 (0.0049)	0.8068 (0.0052)	0.7654 (0.0059)
NGs	CO-P	–	–	–	–	–
	CO-C	–	–	–	–	–
	AMGL	–	–	–	–	–
	MVGL	0.4385 (0)	0.5357 (0)	0.3890 (0)	0.8603 (0)	0.3086 (0)
	MVSC	0.8111 (0.0517)	0.8387 (0.0817)	0.8127 (0.1215)	0.8737 (0.0315)	0.7949 (0.1085)
	CSMSC	0.9623 (0.0000)	0.9761 (0.0000)	0.9758 (0.0000)	0.9763 (0.0000)	0.9701 (0.0000)
	C-MLRSSC	0.9653 (0.0423)	0.9663 (0.0666)	0.9574 (0.0937)	0.9778 (0.0316)	0.9570 (0.0860)
	CGJSR	0.9670 (0.0000)	0.9801 (0.0000)	0.9800 (0.0000)	0.9801 (0.0000)	0.9752 (0.0000)
	CLJSR	0.9721 (0.0000)	0.9839 (0.0000)	0.9837 (0.0000)	0.9840 (0.0000)	0.9799 (0.0000)
UCI Digits	CO-P	0.7495 (0.0533)	0.7143 (0.0788)	0.7046 (0.0788)	0.7243 (0.0744)	0.6821 (0.0879)
	CO-C	0.7752 (0.0490)	0.7351 (0.0784)	0.7192 (0.0858)	0.7519 (0.0710)	0.7049 (0.0877)
	AMGL	0.8648 (0.0259)	0.7993 (0.0475)	0.7493 (0.0684)	0.8596 (0.0382)	0.7752 (0.0540)
	MVGL	0.9038 (0)	0.8495 (0)	0.7889 (0)	0.9203 (0)	0.8315 (0)
	MVSC	0.7209 (0.0224)	0.6464 (0.0445)	0.5633 (0.0659)	0.7650 (0.0194)	0.6001 (0.0534)
	CSMSC	0.8575 (0.0002)	0.8548 (0.0003)	0.8520 (0.0002)	0.8576 (0.0003)	0.8387 (0.0003)
	C-MLRSSC	0.8591 (0.0258)	0.8430 (0.0509)	0.8230 (0.0699)	0.8651 (0.0304)	0.8249 (0.0572)
	CGJSR	0.8993 (0.0002)	0.9045 (0.0003)	0.9031 (0.0003)	0.9059 (0.0003)	0.8940 (0.0004)
	CLJSR	0.9016 (0.0004)	0.9051 (0.0004)	0.9033 (0.0002)	0.9047 (0.0003)	0.8944 (0.0003)
ORL	CO-P	0.9150 (0.0118)	0.7431 (0.0345)	0.6935 (0.0424)	0.8011 (0.0284)	0.7367 (0.0354)
	CO-C	0.9234 (0.0159)	0.7615 (0.0403)	0.7110 (0.0435)	0.8206 (0.0431)	0.7556 (0.0413)
	AMGL	0.9220 (0.0085)	0.6666 (0.0488)	0.5478 (0.0621)	0.8571 (0.0108)	0.6571 (0.0506)
	MVGL	0.9371 (0)	0.7151 (0)	0.6023 (0)	0.8800 (0)	0.7073 (0)
	MVSC	0.8910 (0.0167)	0.6129 (0.0627)	0.4875 (0.0748)	0.8345 (0.0235)	0.6014 (0.0651)
	CSMSC	0.9359 (0.0061)	0.7857 (0.0240)	0.7257 (0.0354)	0.8575 (0.0150)	0.7803 (0.0247)
	C-MLRSSC	0.9301 (0.0068)	0.7702 (0.0232)	0.7092 (0.0315)	0.8434 (0.0188)	0.7644 (0.0238)
	CGJSR	0.9326 (0.0116)	0.7876 (0.0293)	0.7383 (0.0363)	0.8446 (0.0281)	0.7823 (0.0301)
	CLJSR	0.9382 (0.0002)	0.8005 (0.0002)	0.7533 (0.0002)	0.8807 (0.0001)	0.7956 (0.0002)

4.2.2 Visual representation of the affinity matrix

We visualize the affinity matrices learned from nine different algorithms in Fig. 4 to directly present the relationship of all samples in the latent subspace. The ORL dataset is taken in this experiment. Brighter parts represent larger coefficient values. Note that MVGL, MVSC, CSMSC, C-MLRSSC, CGJSR and CLJSR aim to learn the unified coefficient matrix as the latent representation, while CO-P, CO-C and AMGL regard the indicator vectors as the latent representation which is used to construct an affinity matrix by Gaussian kernel criterion. As can be seen from Fig. 4 (a)-(c), the affinity matrix of CO-P, CO-C and AMGL are dense which can’t eliminate the influence of noise well. Fig. 4 (d)-(e) show that the affinity matrices of MVGL and MVSC are too sparse to lose some useful relevant information. It can be seen from Fig. 4 (f)-(i) that compared with CSMSC and C-MLRSSC, CGJSR and CLJSR can output more sparse coefficients which are more robust to noise and outliers. The visual representations of Fig. 4 are consistent with the precision of the ORL dataset in table 4, which demonstrates that a balance affinity matrix between preserving information and denoising can perform better.

Fig.4

The visual representation of similarity matrix on ORL dataset. (a)-(i) visualize the affinity matrices of CO-P, CO-C, AMGL, MVGL, MVSC, CSMSC, C-MLRSSC, CGJSR, CLJSR by gray graph, respectively. The whiter the point is, the closer the corresponding samples are.

Table 4

Clustering results with different number of views on MSRC-V1 dataset for CGJSR

No. of views	NMI	Adj-RI
CM	0.2759 (0.0046)	0.1357 (0.0026)
CM-HOG	0.6712 (0.0093)	0.5915 (0.0110)
CM-HOG-GIST	0.7472 (0.0024)	0.7054 (0.0024)
CM-HOG-GIST-LBP	0.7766 (0.0000)	0.7340 (0.0000)
CM-HOG-GIST-LBP-CENT	0.8201 (0.0033)	0.7648 (0.0019)

Note: The data in brackets is the standard deviation of running 20 times. The result of MVGL is unique, so the standard deviation is always equal to zero, which is marked as 0. For CO-P, CO-C and AMGL algorithms, their basic equation is standard spectral clustering model, which is represented as $min_{U} tr (U^{'} LU) s . t . U^{'} U = I$ . In order to compute the eigenvalue matrix U of the corresponding Laplacian matrix, CO-P, CO-C and AMGL algorithm use eig and eigs functions of MATLAB, respectively. However, the NGs dataset is so sparse that the result matrices of eig and eigs functions include Nan values, which leads to CO-P, CO-C and AMGL algorithms errors or process interruptions. We use ‘-’ to mark these results.

4.3 Sensitivity analysis

In this part, we present the sensitivity analysis including parameter sensitivity, the effect of the number of views, and noise sensitivity of CGJSR and CLJSR algorithms.

4.3.1 Effect of the key term

As can be seen from the model (5) and (6), the performance of CGJSR and CLJSR algorithms is closely related to the sparsity term, noise occlusion regularization and the centralized term. Referring to [4], we expect to explore the importance of each key term to the model by varying λ₁, λ₂ and λ₃. The subspace clustering task with 5 views from MSRC-V1 dataset is chosen to do the experiments. According to the results of grid search, λ₁, λ₂ and λ₃ are set as 0.0001, 0.001, 0.01 respectively, since it is the most stable parameter setting in the grid search process.

(1) Effect of sparsity

Consider the parameter λ₁ ∈ {0, 0.00005, 0.0001, 0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1} with λ₂ = 0.001 and λ₃ = 0.01 and study the relationship between the sparsity term and the NMI. From Fig. 5 (a), we can see that the NMI values of CGJSR and CLJSR are slightly increasing with λ₁ varying from 0 to 0.01. If λ₁ exceeds 0.01, it will lead to a sharp drop. This demonstrates that the l_1,q sparse constrain is conductive to improving the precision, while the centralized representation matrix is too sparse will lead to a lack of structure information.

Fig.5

The effect of sparsity term λ₁, noise regulation λ₂ and centralized term λ₃ on the clustering NMI on MSRC-V1 dataset.

(2) Effect of noise regularization

Consider the parameter λ₂ ∈ {0, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1} with λ₁ = 0.0001 and λ₃ = 0.01 and study the relationship between the noise regularization and the NMI. From Fig. 5 (b), we can see that the noise regulation term is important to the clustering model. The NMI curve increases sharply when λ₂ is from 0 to 0.001. The NMI starts decreasing when λ₂ is greater than 0.001.

(3) Effect of centralized term

Consider the parameter λ₃ ∈ {0, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1} with λ₁ = 0.0001 and λ₂ = 0.001 and study the relationship between the centralized term and the NMI. From Fig. 5 (c), we can see that CGJSR and CLJSR obtain maximum NMI when λ₃ equals to 0.01. These results are superior to the results of λ₃ = 0, which means that considering the error of the sparse representation matrix of each view is very essential.

4.3.2 Effect of the number of views

Here we discuss the effect of the number of views on CGJSR and CLJSR algorithms. MSRC-V1 dataset including Color Moment (CM), HOG, GIST, LBP, CENT of five views is used to do the experiments, setting the different view number from 1 to 5. As shown in Table 4-5, with the increase of the number of views, the NMI and Adi-RI of CGJSR and CLJSR algorithm grow rapidly. When the number of views reaches five, CGJSR and CLJSR algorithms achieve the best results which shows the validity of multi-view subspace clustering algorithms.

Table 5
Clustering results with different number of views on MSRC-V1 dataset for CLJSR

No. of views NMI Adj-RI

CM 0.2793 (0.0054) 0.1384 (0.0028)

CM-HOG 0.6760 (0.0112) 0.6333 (0.0148)

CM-HOG-GIST 0.7497 (0.0060) 0.7037 (0.0065)

CM-HOG-GIST-LBP 0.7564 (0.0045) 0.7108 (0.0052)

CM-HOG-GIST-LBP-CENT 0.8221 (0.0070) 0.7654 (0.0002)

No. of views	NMI	Adj-RI
CM	0.2793 (0.0054)	0.1384 (0.0028)
CM-HOG	0.6760 (0.0112)	0.6333 (0.0148)
CM-HOG-GIST	0.7497 (0.0060)	0.7037 (0.0065)
CM-HOG-GIST-LBP	0.7564 (0.0045)	0.7108 (0.0052)
CM-HOG-GIST-LBP-CENT	0.8221 (0.0070)	0.7654 (0.0002)

4.3.3 Noise immunity

In the noise immunity experiment, ORL dataset is taken to evaluate the performance of nine algorithms.

All data is manually disturbed by Gaussian White Noise with different variance σ² ={ 0, 0.002, 0.004, 0.006, 0.008, 0.01 }. As can be seen from Fig. 6, the NMI and Adj-RI of all algorithms have a different degree of reduction as the noise level σ increases. The performance of the proposed CGJSR and CLJSR algorithms is not much degraded with the increase of noise level. The NMI and Adj-RI of CLJSR algorithm are higher than that of the other seven algorithms at most of the noise level. The NMI and Adj-RI of CGJSR is only inferior to CLJSR when the noise level is below 0.004, though the NMI or Adj-RI of CGJSR is a little lower than that of CLJSR, AMGL and CSMSC when the noise level exceeds 0.004.

Fig.6

The clustering results with different levels of noise variance on ORL dataset for nine algorithms.

4.3.4 Convergence analysis

We study the convergence of CGJSR and CLJSR in terms of max error on the MSRC-V1 dataset. From Fig. 7, if the error threshold is 1e^-4, the CGJSR and CLJSR converge fast within 10 iterations. If the error threshold is 1e^-6, the CLJSR can converge with around 50 iterations and the CGJSR requires 5 more iterations to reach convergence.

Fig.7

5 Conclusions

We propose two centralized joint sparse representation models for multi-view subspace clustering problem. These two algorithms not only preserve the specificity of each view, but also well describe the data representation together with noise and outliers. Specifically, CGJSR encourages the concatenated representation matrix to be row sparse, while CLJSR imposes the sparsity constraint on the row vectors of each views’ representation matrix. Furthermore, a unified latent structure is obtained for clustering. The Alternating direction method of multipliers (ADMM) algorithm is developed to solve the two models. Experimental results on four real-world datasets demonstrate the effectiveness of our approach. In the future, we will extend this algorithm to large-scale datasets and improve the efficiency of our algorithms.

Footnotes

Acknowledgments

The research was supported by the National Natural Science Foundation of China (NSFC) (Grant NO. 61502175, 61273295), the Humanities and social sciences research and planning fund of the Ministry of Education of China (x2lxY9180090) and the Natural Science Foundation of Guangdong Province (2016A030313545).

References

Eric

, et al., Using web structure for classifying and describing web pages, International Conference on World Wide Web ACM, Hawaii (2002).

Zhang

, et al., Multitask multivariate common sparse representations for robust multimodal biometrics recognition, IEEE International Conference on Image Processing (2015), 202–206.

Zhang

, Patel

V.M.

and Chellappa

, Robust multimodal recognition via multitask multivariate low-rank representations, IEEE International Conference and Workshops on Automatic Face and Gesture Recognition 1 (2015), 1–8.

Sumit

, et al., Joint sparse representation for robust multimodal biometrics recognition, IEEE Transactions on Pattern Analysis & Machine Intelligence 36(1) (2014), 113–126.

Gönen

and Alpaydn

, Multiple kernel learning algorithms, Machine Learning Research 12 (2011), 2211–2268.

Xie

, et al., On unifying multi-view self-representations for clustering by tensor multi-rank minimization, International Journal of Computer Vision 126(11) (2018), 1157–1179.

Shu

, et al., Integration of single-view graphs with diffusion of tensor product graphs for multi-view spectral clustering, Proceedings of the AAAI Conference on Artificial Intelligence (2015).

, Spectral clustering with two views, Proceedings of the International Conference on Machine Learning (2005).

Xia

, et al., Robust multi-view spectral clustering via low-rank and sparse decomposition, Association for the Advance of Artificial Intelligence (2014).

10.

Nie

, Li

and Li

, Parameter-free auto-weighted multiple graph learning: a framework for multiview clustering and semi-supervised classification, in Proceeding of the 25th International Joint Conference on Artificial Intelligence (IJCAI) (2016), 1881–1887.

11.

Zhan

and Nie

, et al., Multiview consensus graph clustering, IEEE Transactions on Image Processing 28(3) (2019), 1261–1270.

12.

Zhan

, et al., Graph learning for multiview clustering, IEEE Transactions on Cybernetics 48 (2018), 2887–2895.

13.

Tian

, Nie

and Li

X.L.

, A unified weight learning paradigm for multi-view learning, International Conference on Artificial Intelligence and Statistics (AISTATS) (2019).

14.

Gehler

and Nowozin

, On feature combination for multiclass object classification, IEEE International Conference on Computer Vision (2009), 221–228.

15.

Guo

, et al., Multiple kernel learning based multi-view spectral clustering, IEEE International Conference on Pattern recognition (ICPR) (2014), 3774–3779.

16.

Kumar

and Daumé

, A co-training approach for multi-view spectral clustering, in Proceedings of the International Conference on Machine Learning (2011).

17.

Kumar

, Rai

and Daumé

, Co-regularized multi-view spectral clustering, Advances in Neural Information Processing Systems (2011), 1413–1421.

18.

Zhao

, et al., A subspace co-training framework for multi-view clustering, IEEE Pattern Recognition 41 (2014), 73–82.

19.

Chaudhuri

, et al., Multi-view clustering via canonical correlation analysis, Proceedings of the International Conference on Machine Learning (2009), 129–136.

20.

Luo

, et al., Tensor canonical correlation analysis for multi-view dimension reduction, IEEE Transactions on Knowledge and Data Engineering 27(11) (2015), 3111–3124.

21.

Cao

, et al, IEEE Conference on Computer Vision and Pattern Recognition (2015), 586–5949.

22.

Brbić

and Kopriva

, Multi-view low-rank sparse subspace clustering, Pattern Recognition 73 (2018), 247–258.

23.

Zhang

, Patel

V.M.

and Chellappa

, Low-rank and joint sparse representations for multi-modal recognition, IEEE Transactions on Image Processing 26(10) (2017), 4741–4752.

24.

Abavisani

and Patel

V.M.

, Multimodal sparse and low-rank subspace clustering, Information Fusion 39 (2018), 168–177.

25.

Zhang

, et al., Low-rank tensor constrained multi-view subspace clustering, IEEE International Conference on Computer Vision (2015), 1582–1590.

26.

Yin

, et al., Multiview subspace clustering via tensorial t-product representation, IEEE Transactions on Neural Networks and Learning Systems 30(3) (2019), 851–864.

27.

Kilmer

, et al., Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging, Machine Learning Research 34 (2013), 148–172.

28.

Elhamifar

and Vidal

, Sparse subspace clustering: algorithm, theory, and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence 35(11) (2013), 2765–2781.

29.

Liu

, et al., Robust recovery of subspace structures by low-rank representation, IEEE Transactions on Pattern Analysis & Machine Intelligence 35(1) (2013), 96171–184.

30.

Wang

Y.X.

, Xu

and Leng

, Provable subspace clustering: when LRR meets SSC, International Conference on Neural Information Processing Systems (2013), 64–72.

31.

Luo

, et al., Consistent and specific multi-view subspace clustering, The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI) (2018), 3730–3737.

32.

Guo

J.P.

and Yin

W.B.

, et al., Multi-view subspace clustering with block diagonal representation, IEEE Access (2019).

33.

Gao

, et al., Multi-view subspace clustering, IEEE International Conference on Computer Vision (ICCV) (2015), 4238–4246.

34.

Tang

and Liu

X.W.

, et al., Learning a joint affinity graph for Multiview subspace clustering, IEEE Transactions on Multimedia 21(7) (2019), 1724–1736.

35.

Shi

J.B.

and Malik

, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8) (2000), 888–905.

36.

Yang

and Zhang

, Alternating direction algorithms for 1l problems in compressive sensing, SIAM Journal on Scientific Computing 33(1) (2011), 250–278.

37.

Boyd

, et al., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations & Trends in Machine Learning 3(1) (2011), 1–122.

38.

Grimal

and Bisson

, Amélioration de la co-similaritépour la classification de documents, Conférence Francophone d’Apprentissage (Cap), (2011).

Centralized joint sparse representation for multi-view subspace clustering

Abstract

Keywords

1 Introduction

2.1 Multi-view subspace clustering

2.2 Related algorithms

3.1 Centralized global joint sparse representation algorithm (CGJSR)

4 Experimental results

4.1 Description of dataset

Table 2 Statistics of the experimental datasets Data sets Class No. of each class No. of samples No. of views MSRC-V1 7 30 210 5 NGs 5 100 500 3 UCI Digits 10 200 2000 6 ORL 40 10 400 4

4.2.1 Experimental results

4.3.1 Effect of the key term

Footnotes

Acknowledgments

References

Table 2
Statistics of the experimental datasets

Data sets Class No. of each class No. of samples No. of views

MSRC-V1 7 30 210 5

NGs 5 100 500 3

UCI Digits 10 200 2000 6

ORL 40 10 400 4