Robust Kernelized Multi-View Self-Representations for Clustering by Tensor
Multi-Rank Minimization
Yanyun Qu, Jinyan Liu

Yuan Xie, Wensheng Zhang

arXiv:1709.05083v1 [] 15 Sep 2017

State Key Laboratory of Intelligent Control
Fujian Key Laboratory of Sensing and Computing
and Management of Complex Systems
for Smart City, School of Information Science
Institute of Automation, Chinese Academy of Sciences
and Engineering, Xiamen University, China
yuan.xie@ia.ac.cn, wensheng.zhang@ia.ac.cn
yyqu@xmu.edu.cn, jyliu2014@foxmail.com

Abstract
Most recently, tensor-SVD is implemented on multi-view
self-representation clustering and has achieved the promising results in many real-world applications such as face clustering, scene clustering and generic object clustering. However, tensor-SVD based multi-view self-representation clustering is proposed originally to solve the clustering problem
in the multiple linear subspaces, leading to unsatisfactory results when dealing with the case of non-linear subspaces. To
handle data clustering from the non-linear subspaces, a kernelization method is designed by mapping the data from the
original input space to a new feature space in which the transformed data can be clustered by a multiple linear clustering
method. In this paper, we make an optimization model for the
kernelized multi-view self-representation clustering problem.
We also develop a new efficient algorithm based on the alternation direction method and infer a closed-form solution.
Since all the subproblems can be solved exactly, the proposed
optimization algorithm is guaranteed to obtain the optimal
solution. In particular, the original tensor-based multi-view
self-representation clustering problem is a special case of our
approach and can be solved by our algorithm. Experimental results on several popular real-world clustering datasets
demonstrate that our approach achieves the state-of-the-art
performance.

1

Introduction

With the advent of big data, clustering attracts more and
more attentions. In the past decades, great progresses have
been made in clustering methods. The spectral clustering based methods are the mainstream clustering methods.
There are two critical factors in spectral clustering, one is
the subspace representation, and the other is the affinity matrix construction. The early spectral clustering methods focus on how to construct the affinity matrix (Ng, Jordan, and
Weiss 2002). Recently, more and more concerns are given
to subspace representation for clustering. Sparse subspace
clustering (Elhamifar and Vidal 2013) tries to find a sparse
representation for an instance, and the affinity matrix is constructed in the sparse subspace. The low-rank representation
(LRR) method (Liu et al. 2013) is a typical subspace clustering method, and it pays attention to a self-representation
Copyright c 2017, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

subspace, and the affinity matrix is constructed based on the
self-representation coefficients.
Spectral clustering has been extended to the multi-view
domain for machine learning tasks. In fact, many scientific
data have heterogeneous features, which are collected from
different domains or generated from different feature extractors. Here, we can give two typical application scenarios: 1) web-pages can be represented by using both pagetext and hyperlinks pointing to them; 2) images can be described by different kinds of features, such as color, edge
and texture. Each type of feature is regarded as a particular view, and multi-view features are combined for clustering. It has been proved that multi-view features could improve the clustering performance (Xu, Tao, and Xu 2013;
Luo et al. 2015).
Extensive studies are made in multi-view clustering methods. The existing multi-view clustering methods are divided
into three categories (Xu, Tao, and Xu 2013): 1) graph-based
approaches, 2) co-training or co-regularized approaches, 3)
subspace learning approaches. We will focus on the last category in this paper. Most existing multi-view subspace clustering (MSC) methods grasp the clustering cues only in a
2-order way and neglect the high order information, so that
they may not make the best of the consensus property and
the complementary property. Xie et al. (Xie et al. 2016)
made the multi-view features form a tensor, and utilized the
self-representation strategy as a constraint and enforced the
tensor multi-rank minimization on the objective function for
clustering. It is referred to as t-SVD-MSC. This method has
achieved the state-of-the-art multi-view clustering results on
several popular image datasets.
However, it is originally proposed to handle the data from
multiple linear subspaces on the input space, and it may
not be suitable for the data from the non-linear subspace.
Inspired by the work (Xie et al. 2016; Xiao et al. 2016),
we could use kernel-induced mapping to transform the data
from the original input space to a feature space, in which the
data reside in the union of multiple linear subspaces. Therefore, a new kernelized version of tensor-SVD multi-view
self-representation model is proposed for clustering. We
rewrite the optimization problem of tensor multi-view selfrepresentation for clustering in the kernelized version, where
the data matrix X appears only in the form of inner product.
In order to solve this optimization problem, which is actual

a convex but nonsmooth objective function, we adopt the alternation direction method (ADM) (Lin, Liu, and Su 2011;
Boyd et al. 2011; Yang and Zhang 2011) with multiple
blocks of variables. ADM can theoretically guarantee to
achieve the global optimum.
The main contributions are three folds. 1) We firstly
present a kernel version of multi-view self-representation
subspace clustering, namely Kt-SVD-MSC, to deal with
the case of non-linear subspaces. An optimization model
is made for the kernel tensor based multi-view selfrepresentation, and MSC is solved in the kernel induced
feature subspace. 2) We develop a new optimization algorithm based on ADM to solve the optimization problem of
Kt-SVD-MSC. We infer the analytical solutions for the subproblems with respect to l2,1 norm and obtain the closedform solutions. More interestingly, the original t-SVD-MSC
becomes the special case of our method. Thus, the proposed
algorithm can be used to solve the optimization problem of
t-SVD-MSC. In addition, the kernel trick makes the computation efficient. 3) The proposed method achieves breakthrough clustering results on Scene-15 which is a challenging clustering dataset and achieves the state-of-the-art results on the other testing datasets, such as face clustering
and generic object clustering, which demonstrates the effectiveness of our method.
The rest of this paper is organized as follows. The t-SVDMSC is briefly introduced in section 2. The proposed KtSVD-MSC is detailed in section 3. And experimental results
are shown in section 4. Conclusions are given in Section 5.

2

the v-th learned subspace representation. The multi-view
subspace clustering problem can be reformulated as,
V
X

min
Z(v) ,E(v)

s.t.

X

(λ||E(v) ||2,1 + ||Z(v) ||∗ ),

v=1
(v)

= X(v) Z(v) + E(v) , v = 1, . . . , V,

where V denotes the number of all views and E(v) is the
noise matrix corresponding to the v-th view. From (3), the
multi-view clustering can use LRR in a direct and simple way. After obtaining the multi-view subspace representation, the affinity matrix can be constructed as A =
PV
T
1
(v)
| + |Z(v) |)/2.
v=1 (|Z
V
The limitation of (3) is that it treats each subspace representation independently, neglecting the complementarity of
different views. Thus, a tensor based clustering method is
proposed in which a tensor nuclear norm (TNN) is used as
a regularization term instead of the matrix nuclear norm. A

Figure 1: The t-SVD of an n1 × n2 × n3 tensor.
tensor nuclear norm is defined as,

Brief review of Tensor-SVD based
multi-view subspace clustering

||X ||~ :=

min(n1 ,n2 ) n3
X X
i=1

In this section, we briefly review the general procedure of
self-representation based subspace clustering methods. Low
rank representation method (LRR) (Liu et al. 2013) is a typical self-representation based subspace clustering method,
and many self-representation methods are the variant of
LRR (Liu et al. 2013). Suppose X = [x1 , x2 , . . . , xN ] ∈
Rd×N is the data matrix, whose column is a sample vector
of d dimensions in the feature space. LRR can be formulated
as the following optimization problem,

(3)

|S f (i, i, k)|,

(4)

k=1

where X is a tensor. The tensor singular value decomposition is X = U ∗ S ∗ V T , where U and V are orthogonal
tensors of size n1 × n1 × n3 and n2 × n2 × n3 respectively,
and S is an f-diagonal tensor of size n1 × n2 × n3 , as shown
in Fig.1 . And the tensor multi-rank minimization problem

min λ||E||2,1 + ||Z||∗ ,
Z,E

s.t.

(1)
X = XZ + E

where Z = [z1 , z2 , . . . , zN ] ∈ RN ×N is the coefficient matrix with each zi being the new coding of sample xi . k k∗
is the nuclear norm, k k2,1 denotes the l2,1 norm of a matrix. E is the corresponding noise matrix. After obtaining
the self-representation matrix Z, the affinity matrix is constructed as,
1
A = (|Z| + |ZT |)
(2)
2
where | | represents the absolute operator. And then, spectral clustering is utilized with the affinity matrix A to generate the clustering result.
LRR can be extended to multi-view clustering. Let X(v)
denote the feature matrix of the v-th view and Z(v) denote

Figure 2: The rotated coefficient tensor in our approach.
for multi-view self-representation clustering is formulated
as,
min λ||E||2,1 + ||Z||~ ,
Z(v) ,E(v)

s.t.

X(v) = X(v) Z(v) + E(v) , v = 1, . . . , V,
Z = Φ(Z(1) , Z(2) , . . . , Z(V ) ),
E = [E(1) ; E(2) ; . . . , E(V ) ],

(5)

where the function Φ(·) constructs the tensor Z by stacking
different representation Z(v) to a 3-mode tensor. As illustrated in Fig. 2, we rotates its dimensionality to N × V × N .
In Fig. 2, the self-representation coefficient(mode-1 fiber
marked by the gray bar in Tensor A) is transformed into
the mode-3 fiber marked by the gray bar in Tensor B. The
notation of tensor is detailed in (Xie et al. 2016).

Thus, (5) can be converted to the non-linear version of tSVD-MSC in the feature subspace F (v) as:
min λ
Z(v)

V
X

||Ψ(v) (X(v) ) − Ψ(v) (X(v) )Z(v) ||2,1 + ||Z||~ ,

v=1

Z = Φ(Z(1) , Z(2) , . . . , Z(V ) ).
(10)

3

The error term can be rewritten as:

The Proposed Method

In this section, we give the problem statement of kernelized
multi-view self-representation by tensor multi-rank minimization. The framework of the proposed method is illustrated in Fig.3.
Let X(v) denote the v-th view feature matrix whose column is the feature vector of a sample in the original subspace. We transform a feature vector in the original subspace to the non-linear feature subspace by using a kernel induced latent mapping function. In the feature subspace, t-SVD-MSC is implemented on the new feature matrix. In other words, self-representation is implemented on
the new feature vectors in the v-th view feature subspace.
And then the V -view subspace representation matrices are
obtained, denoted by Z(1) , · · · , Z(V ) . They are merged to
constructed a 3-order tensor Z. According to t-SVD-MSC
(Xie et al. 2016), this tensor needs to be rotated so as to
keep self-representation coefficient in Fourier domain. After
that, the rotated tensor Z̃ is efficiently updated by tensorSVD based tensor nuclear norm minimization in order to
grasp the high order information of the multi-view representation. Sequently, each Z(v) will be updated by using selfrepresentation method. These operations are executed iteratively until convergence is achieved. The challenging task
is how to solve the solution Z(v) under the kernel induced
feature subspace. In this paper, we utilize the kernel strategy to avoid finding the explicit non-linear mapping function and high complication complexity in a high-dimension
subspace.
Following the existing kernel-based method (Cristianini,
Shawe-Taylor, and Kandola 2002; Hofmann, Schölkopf, and
Smola 2008), for the v-th view, let K(v) ∈ RN ×N denote the
kernel matrix, and let ker(v) (x, y) denote the kernel function, we have:
(v)

(v)

(v)

Kij = ker(v) (xi , xj ),

∀i, j = 1, . . . , N.

(6)

where the kernel function ker(v) (x, y) induces a mapping
(v)
ψ (v) : Rd → F (v) (usually implicitly defined), in which
F (v) is referred to as the new feature space (Shawe-Taylor
and Cristianini 2004). Given the mapping ψ (v) , function
ker(v) (·, ·) can be rewritten as:
ker(v) (x, y) = ψ (v) (x)T ψ (v) (y).
(v)

(7)
(v)

Let’s define Ψ(v) (X(v) ) = [ψ (v) (x1 ), . . . , ψ (v) (xN )],
and the kernel matrix of the v-th view can be calculated as:
K(v) = Ψ(v) (X(v) )T Ψ(v) (X(v) ).
(8)
Furthermore, the reconstruction error in feature space
F (v) can be expressed as:
E(v) = Ψ(v) (X(v) ) − Ψ(v) (X(v) )Z(v) .

(9)

kΨ(v) (X(v) ) − Ψ(v) (X(v) )Z(v) k2,1
= kΨ(v) (X(v) )P(v) k2,1
PN
(v) 1
(v)T
K(v) pi ) 2 ,
=
i=1 (pi

(11)

where P(v)
=
I − Z(v)
∈
RN ×N and
(v)
(v)
(v)
(v)
P
= [p1 , . . . , pN ]. Let’s define h (P(v) ) =
q
PN
(v)T
(v)
pi K(v) pi ). Consequently, the problem (10)
i=1
can be reformulated as:
min

λ

V
X

Z(v) ,P(v)

h(v) (P(v) ) + ||Z||~ ,

v=1

Z = Φ(Z(1) , Z(2) , . . . , Z(V ) ),

(12)

P(v) = I − Z(v) , v = 1, . . . , V.
Obviously, after converting the non-linear version (10) into
the formulation in (12), we can solve this optimization problem by using the kernel trick without computing a explicit
non-linear mapping function Ψ(v) (X(v) ) and high computational complexity.

3.1

Optimization

In this subsection, we solve the problem (12) by using alternating direction minimizing(ADM)(Lin, Liu, and Su 2011).
According to the Augmented Lagrange Multiplier (ALM)
(Lin, Chen, and Ma 2010), we introduce multiple blocks of
Lagrange multipliers: the matrix Yv , (v = 1, 2, · · · , V ) and
the tensor W , and introduce the auxiliary tensor variable
G to replace Z in the TNN regularization term (Xie et al.
2016). The optimization problem can be transferred to minimize the following unconstrained problem:
L(Z(1) , . . . , Z(V ) ; P(1) , . . . , P(V ) ; Y1 , . . . , YV ; W; G)
= kGk~ + λ

V
X

h(v) (P(v) )

v=1

+

V 
X
v=1

hYv , I

(v)

(v)

−Z

(v)

−P

µ
i + kI(v) − Z(v) − P(v) k2F
2

ρ
+ hW, Z − Gi + ||Z − G||2F .
2

(13)
where µ and ρ are actually the penalty parameters, which are
adjusted by using adaptive updating strategy as suggested in
(Lin, Liu, and Su 2011).
ADM is adopted for updating Z(v) , P(v) , G and Yv (v =
1, 2, · · · , V ). The detailed procedure for the v-th view can
be partitioned into four steps alternatingly.



Figure 3: The framework of our method. a) Feature extraction for multi-view representation, obtaining the multi-view features
{X(v) }Vv=1 , b) Feature transformation from the input space to the new feature space, c) Multi-view self-representation in the
kernel induced feature space, d) Tensor construction by stacking the kernel multi-view self-representation {Z(v) }Vv=1 , and then
solving the subspace representations optimal solution by using t-SVD based tensor multi-rank minimization
1. Z(v) -subproblem: When P, and G are fixed, we define
(v)
(v)
Φ−1
and Φ−1
, and then we will
(v) (W) = W
(v) (G) = G
solve the following subproblem for updating the subspace
representation Z(v) :
µ
||I − Z(v) − P(v) ||2F
2
ρ
+ hW(v) , Z(v) − G(v) i + ||Z(v) − G(v) ||2F .
2
(14)
By setting the derivative of (14) to zero, the closed-form of
Z(v) can be obtained by
min hYv , I − Z(v) − P(v) i +
Z(v)

∗

Z(v) =(µI + Yv + ρG(v) − µP(v) − W(v) )/(µ + ρ).
(15)
(v)
The solution is denoted by Zt+1 .

(v)

(v)

where Σ(v) = diag(σ1 , . . . , σrK , 0, . . . , 0) and rK is the
(v)
(v)
rank of Matrix K(v) . And we define ci (respectively, pi )
as the ith column of C(v) (respectively, P(v) ) and scalar τ =
(v)
µ/λ. We have the solution pi according to (Xiao et al.
2016):
(
(v)
(v)
(v)
p̂(v) , if ||[1/σ1 , . . . , 1/σrK ] ◦ tu || > 1/τ
(v)∗
pi
=
(v)
(v) (v)
ci − VK tu , otherwise
(18)
where ◦ is the element multiplication operator, and a ◦ b is
a new vector whose ith element is ai bi .
T (v)
(v)
(v)
Let’s define tu = VK (v) ci ∈ RrK , where VK (v) ∈
(v)
(v)
RN ×rK is formed by the first rK columns of V(v) , and the
(v)
vector p̂ is defined as
(v)2

(v)

(v)

2. P(v) -subproblem: After obtaining Zt+1 , we solve the
optimization solution P(v) by fixing the other parameters.

p̂(v) = ci

− VK (v) ([

σ1

(v)2

,...,
(v)2

α(v) + σ1

σrK

(v)2

α(v) + σrK

]T ◦ t(v)
u )

(19)
where α(v) is a positive scalar, satisfying
µ
min λh(v) (P(v) ) + hYv , I − Z(v) − P(v) i + kI − Z(v) − P(v) k2F
(v)2
σi
1
2
P(v)
(v)T
(v)
t
diag({
}
= 2 (20)
(v) )tu
u
µ
(v)2 2 1≤i≤rK
(v)
(v)
(v)
(v)
(v)
2
τ
(α + σri )
= min λh (P ) + ||I − Z − P + Yv /µ||F
2
P(v)
(v)
(v)
(v)
µ
In particular, when k[1/σ1 , . . . , 1/σrK ] ◦ tu k > 1/τ , the
= min λh(v) (P(v) ) + ||P(v) − C(v) ||2F
(v)
equation in (20) (with respect to α) has a unique positive
2
P
(16)
root, which can be obtained by the bisection method (Burden
where C(v) = I − Z(v) + Yv /µ, and we have dropped the
and Faires 2011).
terms that are irrelevant to P(v) .
Note that it is nontrivial to solve the problem in (16),
3. G(v) -subproblem: When Z(v) , (v = 1, 2, . . . , V), are
where the objective function is convex but nonsmooth. In
fixed, we solve the following subproblem in order to update
order to explain how to solve the second subproblem, we
the tensor G,
formulate the SVD of the v-th view kernel matrix as,
ρ
1
T
G ∗ = argmin ||G||~ + ||G − (Z + W)||2F .
(21)
(17)
K(v) = V(v) Σ(v)2 V(v)
2
ρ
G

Let’s define F = Z + ρ1 W. According to (Xie et al.
2016), let fft(F , [ ], 3) denote the Fourier transform along
the third dimension and ifft(G f , [ ], 3) denote the inverse
Fourier transform along the third dimension . The solution
of the optimization problem (21) can be achieved through
Algorithm 1.The detail can be found in (Xie et al. 2016).

Algorithm 2: Kt-SVD-MSC
Input: Multi-view feature matrices:
X(1) , X(2) , . . . , X(V ) , λ, cluster number C, and
the SVD of K(v)
Output: Clustering results C
1

Algorithm 1: t-SVD based Tensor Nuclear Norm Minimization
Input: Observed tensor F ∈ Rn1 ×n2 ×n3
Output: tensor G
1
2
3

F f = fft(F , [ ], 3);
for j = 1 : n3 do
(j)
(j)
(j)
(j)
[U f , S f , V f ] = SVD(F f );
(j)
Jf

4

7
8
9

(j)

(j)

(j)

(j)

G f = U f S f,n3 V f
end
G = ifft(G f , [ ], 3);
Return tensor G.

3
4
5
6
7

=

1, . . . , min(n1 , n2 );
(j)
(j) (j)
S f,n3 = S f J J ;

5
6

= diag{(1 −

τ0
)+ }, i
(j)
S f (i,i)

2

8
9
10
11
12

T

;

13
14
15
16
17
18

4. Updating the Lagrange multipliers Y(v) , W , µ, and
ρ:
Yv∗ = Yv + µ(I − Z(v) − P(v) ),
(22)
∗
W = W + ρ(Z − G),
(23)
µ = min(ηµ, µmax ),
(24)
ρ = min(ηρ, ρmax ).
(25)
where µmax and ρmax are presetting parameters.
We summarize the algorithm for Kt-SVD-MSC in Algorithm 2.

4

https://cvc.yale.edu/projects/yalefaces/yalefaces.html
https://cvc.yale.edu/projects/yalefacesB/yalefacesB.html
3
http://www.uk.research.att.com/facedatabase.html
4
http://www-cvr.ai.uiuc.edu/ponce grp/data/
5
http://www.cs.columbia.edu/CAVE/software/softlib/
2

20
21
22
23
24
25
26

Experimental Results and Analysis

In this section, in order to estimate the proposed method, we
implement it on six challenging image clustering datasets:
Yale1 , Extended YaleB2 , ORL3 , Notting-Hill (Zhang et al.
2009), Scene-154 , COIL-205 . The first three datasets are
three typical face datasets, and Nottting-Hill is a video face
dataset. Scene-15 are for scene clustering, and COIL-20 is
for generic object clustering. Table 1 shows the details of the
six datasets, such as the number of images and the number of
classes. We use six popular criteria to evaluate a clustering
method: Normalized Mutual Information (NMI), Accuracy
(ACC), Adjusted Rank index (AR), F-score, Precision and
Recall. For all the criteria, the higher the score is, the better the performance is. In all datasets, we use the average
1

19

Initialize Z(v) = Yv = 0, i = 1, . . . , V ; P(v) = In
G = W = 0;
µ = ρ = 10−5 , η = 2, µmax = 1013 , ρmax = 1013 ,
ε = 10−7 ;
while not converge do
for v = 1 : V do
// Solving Z
Update {Z(v) }Vv=1 by using (15);
end
// Solving P
Update P by solving (18);
for v = 1 : V do
// Solving Y
Update {Y(v) }Vv=1 by using (22);
end
Obtain Z = Φ(Z(1) , Z(2) , . . . , Z(V ) );
// Solving G;
Update G by using Algorithm 1;
Update W by using (23);
Update parameters µ and ρ by using (24) and (25),
respectively;
Check the convergence conditions:
||I − Z(v) − P(v) ||∞ < ε and
||Z(v) − G(v) ||∞ < ε;
end
Obtain the affinity matrix by
PV
T
A = V1 v=1 (|Z(v) | + |Z(v) |)/2;
Apply the spectral clustering method with the affinity
matrix A;
Return Clustering result C.

of ten runs as the final results. In the Section 1 of supplemental material, we present more clustering results, such
as the mean and standard deviation of the six criteria. All
experiments are implemented in Matlab on a workstation
with 4GHz CPU, 32GB RAM, and TITANX GPU(12GB
caches). To promotethe culture of reproducible research,
source codes accompanying this work can be achieved at
http://pan.baidu.com/s/1bp4JUqz (password: m9qo).
Table 1: Statistics of different test datasets
Dataset
Images
Objective
Clusters
Yale
165
Face
15
Extended YaleB
640
Face
10
ORL
400
Face
10
Notting-Hill
4660
Face
5
Scene-15
4485
Scene
15
COIL-20
1440 Generic Object
20

We take different strategies for clustering to deal with different applications. As for face clustering, three types of features are extracted: intensity, LBP (Ojala, Pietikainen, and
Maenpaa 2002), and Gabor (Lades et al. 1993). The LBP
feature is extracted from an image with the sampling size
of 8 pixels and the blocking number of 7 × 8. The Gabor
feature is extracted with only one scale λ = 4 at four orientations θ = {0o , 45o , 90o , 135o }. Thus, the LBP feature is of
3304 dimensions, and Gabor feature is of 6750 dimensions.
As for Scene-15, three types of features are extracted: Pyramid histograms of visual words (PHOW)(Bosch, Zisserman,
and Munoz 2007), Pairwise rotation invariant co-occurrence
local binary pattern feature (PRI-CoLBP)(Qi et al. 2014),
and CENsus TRansform hISTogram (CENTRIST)(Wu and
Rehg 2011). PHOW is extracted with dense sampling step
of 8 pixels and 300 words and is of 1800 dimensions. PRICoLBP is of 1180 dimensions. Three level features are extracted to form CENTRIST, which contains 1, 5, 25 blocks
respectively. CENTRIST is of 1240 dimensions. COIL-20
uses the same features as those used for face clustering. And
the feature are extracted from a normalized image with size
of 32 × 32.
In the experiments, we implement a linear kernel on each
view on Yale and ORL and implement linear kernels and
Gaussian kernels on different views on Extended YaleB,
Scene-15, Notting-Hill and COIL-20. We compare our approach with eight representative clustering methods: the
standard spectral clustering algorithm with the most informative view (SPCbest), LRR algorithm with the most informative view (LRRbest), robust multi-view spectral clustering via low-rank and sparse decomposition (RMSC)(Xia
et al. 2014), diversity-induced multi-view subspace clustering (DiMSC) (Cao et al. 2015), low-rank tensor constrained
multi-view subspace clustering (LTMSC) (Zhang et al.
2015), the tensor-SVD multi-view clustering method with
tensor multi-rank minimization (t-SVD-MSC)(Xie et al.
2016), the tensor-SVD with unrotated coefficient tensor (UtSVD-MSC), and exclusivity-consistency regularized MSC
(ECMSC) (Wang et al. 2017). The first two methods are
the single view baselines. The RMSC, DiMSC, and LTMSC
are three state-of-the-art methods in multi-view clustering.
As for ECMSC, only clustering results on Yale, Extended
YaleB, ORL were published. Thus, we run the code provided
by the authors on Notting Hill, Scene-15 and COIL-20 and
obtain the clustering results by tuning the parameters. The
comparison results are shown in Table 2 ∼ 7. We compare
our approach with the eight methods on each dataset. Moreover, confusion matrices of the t-SVD-MSC and the proposed method is shown in Fig. 1 in supplemental material,
in which the superiority of the proposed method can be easily observed. On the six real-world datasets, our approach
achieves the best clustering performance in terms of the
six criteria. The clustering performance of Kt-SVD-MSC is
higher by (0.0917, 0.1052, 0.1425, 0.1290, 0.1438, 0.1140)
than t-SVD-MSC (Xie et al. 2016) and is higher
by (0.1937, 0.2255, 0.3295, 0.2935, 0.3453, 0.2243) than
ECMSC (Wang et al. 2017) in terms of the average gain
of clustering performance on the six datasets. The results
demonstrate that the kernel version of tensor-SVD is helpful

for self-representation multi-view clustering, and the proposed method achieves the best performance among nine
compared methods.
Furthermore, we investigate how the parameter λ influences the clustering performance in terms of NMI and ACC.
In (12), the proposed model contains only one tuning parameter λ which balances the effects of the two parts. And
the choice of λ is set empirically on the testing data of each
dataset. In Fig. 4, we plot the curves of NMI and ACC with
the change of the parameter λ. In each curve, a red circle denotes the λ value where the clustering performance(NMI or
ACC) achieves the highest value. It also demonstrates that
most settings of λ can make NMI or ACC achieve higher
value than the other compared methods. Thus, Fig.4 implies
that our approach is stable with regards of λ.

(a)

(b)

Figure 4: The effect of the parameter λ to NMI and ACC on
Scene-15 dataset. a) λ affects NMI, b) λ affects ACC
Thanks to ADM and the inferred closed-form solution,
the proposed optimization model Kt-SVD-MSC converges
fast. In order to discuss the convergence of our approach,
we define the reconstruction error as (26) and matching error
as (27). We plot two curves for the two errors on Scene-15.
The reconstruction error curve is signed by the solid line
and the matching error curve is signed by the dotted line.
Observing the changes of the reconstruction error and the
matching error with the increase of the iterations in Fig.5, we
find that both curves decrease severely to approximate zero
during 15 iterations and they become flat after 15th iteration.
Thus, Fig.5 demonstrates the proposed Kt-SVD-MSC can
converge fast.

Reconerror =

V
1 X
kX (v) − X (v) Z (v) − E (v) k∞ (26)
V v=1

M atcherror =

5

V
1 X (v)
kZ − G(v) k∞
V v=1

(27)

Conclusions

In this paper, we proposed a kernel version of selfrepresentation multi-view clustering with tensor multi-rank
minimization. A new optimization model for the robust kernel tensor-SVD representation is made. After that, ADM algorithm is implemented on solving this optimization prob-

Table 4: Clustering results (mean) on ORL. We set λ =
0.01 in proposed Kt-SVD-MSC.
Method
SPCbest
LRRbest
RMSC
DiMSC
LTMSC
Ut-SVD-MSC
t-SVD-MSC
ECMSC
Kt-SVD-MSC

Figure 5: Convergence curve on Scene-15.
Table 2: Clustering results (mean) on Yale. We set λ =
0.21 in proposed Kt-SVD-MSC.
Method
SPCbest
LRRbest
RMSC
DiMSC
LTMSC
Ut-SVD-MSC
t-SVD-MSC
ECMSC
Kt-SVD-MSC

NMI
0.654
0.709
0.684
0.727
0.765
0.756
0.953
0.773
0.987

ACC
0.618
0.697
0.642
0.709
0.741
0.733
0.963
0.771
0.982

AR
0.440
0.512
0.485
0.535
0.570
0.584
0.910
0.590
0.973

F-score Precision Recall
0.475
0.457 0.500
0.547
0.529 0.567
0.517
0.500 0.535
0.564
0.543 0.586
0.598
0.569 0.629
0.610
0.591 0.630
0.915
0.904 0.927
0.617
0.584 0.653
0.975
0.971 0.979

Table 3: Clustering results (mean) on Extended YaleB.
We set λ = 0.05 in proposed Kt-SVD-MSC.
Method
SPCbest
LRRbest
RMSC
DiMSC
LTMSC
Ut-SVD-MSC
t-SVD-MSC
ECMSC
Kt-SVD-MSC

NMI
0.360
0.627
0.157
0.636
0.637
0.479
0.667
0.759
0.893

ACC
0.366
0.615
0.210
0.615
0.626
0.470
0.652
0.783
0.896

AR
0.225
0.451
0.060
0.453
0.459
0.274
0.500
0.544
0.813

F-score Precision Recall
0.308
0.296 0.310
0.508
0.481 0.539
0.155
0.151 0.159
0.504
0.481 0.534
0.521
0.485 0.539
0.350
0.327 0.375
0.550
0.514 0.590
0.597
0.513 0.718
0.832
0.821 0.842

lem. We provide the closed-form solutions for the l2,1 normrelated subproblems so that the subproblems can be efficiently solved. Extensive experimental results on three
types of applications: face clustering, scene clustering, and
generic object clustering have clearly demonstrated that the
proposed self-representation multi-view clustering method
based on kernelized tensor-SVD is effective and efficient.
In the nine compared clustering methods, our approach
achieves the breakthrough clustering performance on Scene15 which is a challenging clustering dataset and achieves the
state-of-the-art clustering results on the other datasets.

NMI
0.884
0.895
0.872
0.940
0.930
0.874
0.993
0.947
0.994

ACC
0.725
0.773
0.723
0.838
0.795
0.765
0.970
0.854
0.971

AR
0.655
0.724
0.645
0.802
0.750
0.666
0.967
0.810
0.972

F-score Precision Recall
0.664
0.610 0.728
0.731
0.701 0.754
0.654
0.607 0.709
0.807
0.764 0.856
0.768
0.766 0.837
0.675
0.643 0.708
0.968
0.946 0.991
0.821
0.783 0.859
0.972
0.956 0.991

Table 5: Clustering results (mean) on Notting-Hill. We
set λ = 0.009 in proposed Kt-SVD-MSC.
Method
SPCbest
LRRbest
RMSC
DiMSC
LTMSC
Ut-SVD-MSC
t-SVD-MSC
ECMSC
Kt-SVD-MSC

NMI
0.723
0.579
0.585
0.799
0.779
0.837
0.900
0.817
0.973

ACC
0.816
0.794
0.807
0.837
0.868
0.933
0.957
0.767
0.992

AR
0.712
0.558
0.496
0.787
0.777
0.847
0.900
0.679
0.981

F-score Precision Recall
0.775
0.780 0.776
0.653
0.672 0.636
0.603
0.621 0.586
0.834
0.822 0.827
0.825
0.830 0.814
0.880
0.900 0.861
0.922
0.937 0.907
0.764
0.637 0.954
0.985
0.989 0.981

Table 6: Clustering results (mean) on Scene-15. We set
λ = 0.0018 in proposed Kt-SVD-MSC.
Method
SPCbest
LRRbest
RMSC
DiMSC
LTMSC
Ut-SVD-MSC
t-SVD-MSC
ECMSC
Kt-SVD-MSC

NMI
0.421
0.426
0.564
0.269
0.571
0.555
0.858
0.463
0.966

ACC
0.437
0.445
0.507
0.300
0.574
0.510
0.812
0.457
0.984

AR
0.270
0.272
0.394
0.117
0.424
0.375
0.771
0.303
0.967

F-score Precision Recall
0.321
0.314 0.329
0.324
0.316 0.333
0.437
0.425 0.450
0.181
0.173 0.190
0.465
0.452 0.479
0.422
0.389 0.460
0.788
0.743 0.839
0.357
0.318 0.408
0.969
0.971 0.968

Table 7: Clustering results (mean) on COIL-20. We set
λ = 0.0009 in proposed Kt-SVD-MSC.
Method
SPCbest
LRRbest
RMSC
DiMSC
LTMSC
Ut-SVD-MSC
t-SVD-MSC
EMSC
Kt-SVD-MSC

NMI
0.806
0.829
0.800
0.846
0.860
0.841
0.884
0.942
0.992

ACC
0.672
0.761
0.685
0.778
0.804
0.788
0.830
0.782
0.990

AR
0.619
0.720
0.637
0.732
0.748
0.732
0.786
0.781
0.983

F-score Precision Recall
0.640
0.596 0.692
0.734
0.717 0.751
0.656
0.620 0.698
0.745
0.739 0.751
0.760
0.741 0.776
0.746
0.731 0.760
0.800
0.785 0.808
0.794
0.695 0.925
0.984
0.984 0.985

References
[Bosch, Zisserman, and Munoz 2007] Bosch, A.; Zisserman,
A.; and Munoz, X. 2007. Image classification using random

forests and ferns. In Computer Vision, 2007. ICCV 2007.
IEEE 11th International Conference on, 1–8. IEEE.
[Boyd et al. 2011] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.;
and Eckstein, J. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends R in Machine Learning 3(1):1–
122.
[Burden and Faires 2011] Burden, R., and Faires, J. 2011.
The bisection method. Numerical Analysis 48–56.
[Cao et al. 2015] Cao, X.; Zhang, C.; Fu, H.; Liu, S.; and
Zhang, H. 2015. Diversity-induced multi-view subspace
clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, 586–594.
[Cristianini, Shawe-Taylor, and Kandola 2002] Cristianini,
N.; Shawe-Taylor, J.; and Kandola, J. S. 2002. Spectral
kernel methods for clustering. In Advances in neural
information processing systems, 649–655.
[Elhamifar and Vidal 2013] Elhamifar, E., and Vidal, R.
2013. Sparse subspace clustering: Algorithm, theory, and
applications. IEEE transactions on pattern analysis and machine intelligence 35(11):2765–2781.
[Hofmann, Schölkopf, and Smola 2008] Hofmann,
T.;
Schölkopf, B.; and Smola, A. J. 2008. Kernel methods in
machine learning. The annals of statistics 1171–1220.
[Lades et al. 1993] Lades, M.; Vorbruggen, J. C.; Buhmann,
J.; Lange, J.; Von Der Malsburg, C.; Wurtz, R. P.; and Konen, W. 1993. Distortion invariant object recognition in the
dynamic link architecture. IEEE Transactions on computers
42(3):300–311.
[Lin, Chen, and Ma 2010] Lin, Z.; Chen, M.; and Ma, Y.
2010. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint
arXiv:1009.5055.
[Lin, Liu, and Su 2011] Lin, Z.; Liu, R.; and Su, Z. 2011.
Linearized alternating direction method with adaptive
penalty for low-rank representation. In Advances in Neural
Information Processing Systems 612–620.
[Liu et al. 2013] Liu, G.; Lin, Z.; Yan, S.; Sun, J.; Yu, Y.; and
Ma, Y. 2013. Robust recovery of subspace structures by lowrank representation. IEEE Transactions on Pattern Analysis
and Machine Intelligence 35(1):171–184.
[Luo et al. 2015] Luo, Y.; Tao, D.; Wen, Y.; Kotagiri, R.; and
Xu, C. 2015. Tensor canonical correlation analysis for
multi-view dimension reduction. IEEE Trans. on Knowledge and Data Engineering 27(11):3111–3124.
[Ng, Jordan, and Weiss 2002] Ng, A. Y.; Jordan, M. I.; and
Weiss, Y. 2002. On spectral clustering: Analysis and an
algorithm. In Advances in neural information processing
systems, 849–856.
[Ojala, Pietikainen, and Maenpaa 2002] Ojala,
T.;
Pietikainen, M.; and Maenpaa, T. 2002. Multiresolution gray-scale and rotation invariant texture classification
with local binary patterns. IEEE Transactions on pattern
analysis and machine intelligence 24(7):971–987.
[Qi et al. 2014] Qi, X.; Xiao, R.; Li, C.-G.; Qiao, Y.; Guo,
J.; and Tang, X. 2014. Pairwise rotation invariant co-

occurrence local binary pattern. IEEE Transactions on Pattern Analysis and Machine Intelligence 36(11):2199–2213.
[Shawe-Taylor and Cristianini 2004] Shawe-Taylor, J., and
Cristianini, N. 2004. Kernel methods for pattern analysis.
Cambridge university press.
[Wang et al. 2017] Wang, X.; Guo, X.; Lei, Z.; Zhang, C.;
and Li, S. Z. 2017. Exclusivity-consistency regularized
multi-view subspace clustering. CVPR.
[Wu and Rehg 2011] Wu, J., and Rehg, J. M. 2011. Centrist: A visual descriptor for scene categorization. IEEE
transactions on pattern analysis and machine intelligence
33(8):1489–1501.
[Xia et al. 2014] Xia, R.; Pan, Y.; Du, L.; and Yin, J. 2014.
Robust multi-view spectral clustering via low-rank and
sparse decomposition. In AAAI, 2149–2155.
[Xiao et al. 2016] Xiao, S.; Tan, M.; Xu, D.; and Dong, Z. Y.
2016. Robust kernel low-rank representation. IEEE transactions on neural networks and learning systems 27(11):2268–
2281.
[Xie et al. 2016] Xie, Y.; Tao, D.; Zhang, W.; Zhang, L.;
and Yanyun, Q. 2016. On unifying multi-view selfrepresentations for clustering by tensor multi-rank minimization. arXiv preprint arXiv:1610.07126.
[Xu, Tao, and Xu 2013] Xu, C.; Tao, D.; and Xu, C. 2013. A
survey on multi-view learning. Computer Science.
[Yang and Zhang 2011] Yang, J., and Zhang, Y. 2011. Alternating direction algorithms for l1 -problems in compressive
sensing. SIAM journal on scientific computing 33(1):250–
278.
[Zhang et al. 2009] Zhang, Y.-F.; Xu, C.; Lu, H.; and Huang,
Y.-M. 2009. Character identification in feature-length films
using global face-name matching. IEEE Transactions on
Multimedia 11(7):1276–1288.
[Zhang et al. 2015] Zhang, C.; Fu, H.; Liu, S.; Liu, G.; and
Cao, X. 2015. Low-rank tensor constrained multiview subspace clustering. In Proceedings of the IEEE International
Conference on Computer Vision, 1582–1590.

