# Rethinking _k_ -means from manifold learning perspective

Quanxue Gao, Qianqian Wang, Han Lu, Wei Xia, and Xinbo Gao  This work is
supported in part by National Natural Science Foundation of China under Grants
62176203; in part by the Open Project Program of State Key Laboratory of
Multimodal Artificial Intelligence Systems under Grant 202200035; in part by
Natural Science Basic Research Plan in Shaanxi Province (Grant 2020JZ-19), and
in part by the Fundamental Research Funds for the Central Universities and the
Innovation Fund of Xidian University. (Corresponding author: Quanxue Gao.)Q.
Gao, Q. Wang, H. Lu and W. Xia are with the State Key laboratory of Integrated
Services Networks, Xidian University, Xi’an 710071, China.X. Gao is with the
Chongqing Key Laboratory of Image Cognition, Chongqing University of Posts and
Telecommunications, Chongqing 400065, China.

###### Abstract

Although numerous clustering algorithms have been developed, many existing
methods still leverage _k_ -means technique to detect clusters of data points.
However, the performance of _k_ -means heavily depends on the estimation of
centers of clusters, which is very difficult to achieve an optimal solution.
Another major drawback is that it is sensitive to noise and outlier data. In
this paper, from manifold learning perspective, we rethink _k_ -means and
present a new clustering algorithm which directly detects clusters of data
without mean estimation. Specifically, we construct distance matrix between
data points by Butterworth filter such that distance between any two data
points in the same clusters equals to a small constant, while increasing the
distance between other data pairs from different clusters. To well exploit the
complementary information embedded in different views, we leverage the tensor
Schatten _p_ -norm regularization on the 3rd-order tensor which consists of
indicator matrices of different views. Finally, an efficient alternating
algorithm is derived to optimize our model. The constructed sequence was
proved to converge to the stationary KKT point. Extensive experimental results
indicate the superiority of our proposed method.

###### Index Terms:

Multi-view clustering, tensor Schatten _p_ -norm, non-negative matrix
factorization.

##  1 Introduction

Clustering, which belongs to unsupervised learning, has been an important and
active topic in pattern analysis and artificial intelligence due to the mass
of unlabeled data in real applications. Unlike supervised learning, clustering
aims to divide data into $C$ non-overlapping clusters according to certain
properties such that the data within the same cluster are more similar to each
other than the ones in different clusters under the characteristics embedded
in data points, where $C$ is the number of clusters. During the past few
decades, a substantial amount of clustering algorithms have been proposed to
annotate data and achieve impressive performances. However, numerous existing
methods still leverage _k_ -means to obtain the clusters of data.

_k_ -means [1] directly divides data points into $C$ clusters according to the
Euclidean distances between data points and centroid of $C$ clusters which are
unknown. Although it has been widely used, one of the most important
disadvantages is that it cannot well treat nonlinearly separable data due to
the fact that Euclidean distance cannot well characterize the intrinsic
geometric structure of clusters. To alleviate this problem, the last decades
has witnessed a fast paced development of _k_ -means variants. One of the most
popular strategies is to map the original data into a high-dimensional
reproducing Kernel Hilbert Space, i.e., feature space by using kernel trick
such that the embedded features are linearly separable and then use _k_ -means
to obtain labels of data. Inspired by this, kernel _k_ -means and many
variants have been developed by selecting different kernel functions to
improve clustering performance. Despite their different motivations and
impressive experimental results in the literature, all of them need to
directly estimate the centroid of clusters which heavily depends on the
initialization of centroid matrix of clusters which is difficult in real
applications, resulting in unstableness of algorithms.

To avoid estimation of centroid matrix, Pei et al. [2] presented $k$-sum by
leveraging the relationship between spectral clustering and _K_ -means [3].
However, _k_ -sum is only suitable for single view clustering. Applied _K_
-means to multi-view clustering, many efficient methods have been proposed,
but, the performance of existing multi-view _k_ -means still heavily depends
on the initialization of centroid matrix which is difficult to select a
suitable value in real applications. This reduces the flexibility of these
algorithms. Finally, existing multi-view _k_ -means cannot well exploit the
complementary information embedded in views. To handle the aforementioned
limitations, from manifold learning perspective, we rewrite _k_ -means and
propose a novel clustering algorithm which directly estimates the clusters of
data without estimation of centroid matrix. To our best knowledge, the
proposed model is the first work to rethink _k_ -means from manifold learning
perspective and make it sense. To be specific, existing _k_ -means methods
differ from the problem addressed in our paper in three ways:

  * •

Our method builds a bridge between _k_ -means and manifold learning, which
helps integrate manifold learning and clustering into a uniform framework.

  * •

Our method directly achieves the clusters of data without estimation of
centroid matrix, while existing multi-view _k_ -means and variants don’t.

  * •

We use butterworth filter to map distance between data points in the original
space into a hidden space such that the distance between the points in the
same neighborhood is small and approximately equal, and distance between
points in different neighborhoods are very large. Thus, our method can well
handle non-linearly separable data.

  * •

For multi-viewing clustering, existing _k_ -means and variants assume that
label indicator matrices of all views are identical and do not consider the
affect of different views for clustering. In our method, we relax this strict
constraint and employ tensor Schatten $p$-norm minimization regularization on
the third tensor which is composed of indicator labels of views. Thus, our
method well exploits the complementary information embedded in views.

  * •

We develop an optimization algorithm for the proposed method and prove it
always converges to the KKT stationary point mathematically.

##  2 Related work

With the fast paced development of sensor technology, multi-view data have
become the mainstream of object representation in real applications and help
provide some complementary information which are important for clustering.
Inspired by it, many multi-view clustering methods have been proposed during
the last decades, two of the most representative techniques are subspace
clustering and spectral clustering. Subspace clustering aims to find a low-
dimensional subspace or embedding that fits each cluster of points. One of the
most representative techniques is low-rank representation technique [4] which
views original samples as dictionary to learn affinity matrix. Applied it to
multi-view clustering, Luo _et al_. proposed CSMSC [5], which splits multi-
view data into view consensus and view-specific by minimizing least square
error. To well exploit complementary information, tensor singular value
decomposition (t-SVD) based tensor nuclear norm has received much attention
for multi-view clustering [6, 7]. Inspired by tensor nuclear norm, Gao et al.
proposed an enhanced weighted tensor Schatten _p_ -norm minimization, which
can well approximates the object rank and characterizes the complementary
relationship between views [8], and then presented novel multi-view subspace
clustering methods [9, 10]. All of them have achieved good clustering
performance in some scenarios, but all of them almost need post-processing
such as spectral clustering to get discrete label matrix of data. This results
in sub-optimal performance.

Spectral clustering converts data clustering into graph segmentation and
mainly contains the following two steps: (1) Construct similarity matrix
$\bf{S}$ which well depicts the structure of data and calculate Laplacian
matrix of $\bf{S}$; (2) Perform eigen-decomposition on the Laplacian matrix to
achieve spectral embedding for clustering [11, 12, 13]. Due to the good
clustering accuracy on arbitrary shaped data and well defined mathematics,
spectral clustering has become one of the most popular techniques for multi-
view clustering [14, 15]. To further reduce the computational complexity which
is caused by similarity matrix construction and eigen-decomposition of large
laplacian matrix, many fast spectral clustering methods have been presented,
one of the most efficient strategies is anchor-based spectral clustering. To
improve the quality of $S$ and well exploit complementary information between
views, many spectral clustering based methods have been presented for both
single view and multi-view clustering by different graph learning strategies
such as self-weighted graph learning [16] and low-rank tensor constrained
spectral clustering (LTCPSC) [17].

Although the motivations of existing clustering methods are different, many
methods need to leverage _k_ -means to get clusters of data. _k_ -means
achieves clusters of single view data by Euclidean distance between data
points and centers. Applied _k_ -means to multi-view clustering, Bick and
Scheffer proposed naive multi-view K-means [18]. To improve robustness of
algorithm to noise and outlier, Cai et al. [19] proposed robust multi-view _K_
-means (RMKMC) which leverages L21-norm instead of Euclidean distance to
measure residual error. Han et al. [20] proposed MVASM which takes into
account the difference between views for clustering and exploits the view-
consensus information embedded in views. Although the aforementioned methods
can obtain impressive clustering performance, all of them directly obtains
clusters of data in the original data space. This will reduce the flexibility
of algorithm for high dimensional data due to the fact that the distance among
data points can’t appropriately characterize the relationship between them
[21].

To improve clustering accuracy for high-dimensional data which is ubiquitous
in real applications, dimension reduction technique such as PCA is used to
obtain low-dimensional representation and then _k_ -means is performed to get
clusters [22]. To get an optimal subspace which is better for clustering, a
reasonable strategy is to simultaneously both learn subspace and realize
clustering [23, 24]. For example, Ding et al. [23] proposed an adaptive
dimension reduction approach that integrates linear discriminant analysis
(LDA) into _k_ -means processing for single view clustering. Inspired by this
efficient work, xu et al. [25] extend it to multi-view clustering and proposed
discriminatively embedded _k_ -means which integrates LDA into multi-view _k_
-means. To improve robustness of algorithm to outliers and noise, Xu et al.
[26] proposed a robust projected multi-view _k_ -means which is called re-
weighted discriminatively embedded _k_ -means (RDEKM). RDEKM takes into
account the difference between views and simultaneously learns projection
matrix and clusters of data by _k_ -means in the low-dimensional space.

However, the aforementioned clustering methods can’t well capture nonlinear
structure embedded in data which is important for clustering. To solve this
limitation, kernel trick is one of the most efficient methods. Inspired by it,
kernel _k_ -means is proposed by using a kernel function, which maps data into
a embedded high-dimensional space such that the embedded features are linearly
separable [27]. However, it is difficult to select a suitable kernel function
for data and single kernel can’t well exploit the complementary information
embedded in heterogeneous features. To alleviate this problem, multiple kernel
strategy are with great potential to integrate complementary information into
_k_ -means for improving clustering accuracy [28, 29]. Liu et al. [30]
proposed Multiple kernel _k_ -means with matrix-induced regularization which
well considers the correlation among kernel functions. However, the
aforementioned methods still need discretization procedure to get discrete
label matrix. This results in sub-optimal clustering accuracy.

Although the above _k_ -means variants can achieve impressive clustering
performance, the performance of them heavily depends on initialization of
centroid matrix of clusters. In real applications, it is difficult to select a
suitable centroid matrix for clustering. Thus, the aforementioned clustering
method are unstable and inflexible. To alleviate this problem, _k_ -means++ is
proposed by using a reasonable strategy to initialize centroid matrix. Another
an efficient method is _k_ -multiple means [31]. It simultaneously learns
centroid of $m$ sub-clusters, which is larger than the number of classes, and
similarity matrix with connected components constraint. But all of them still
involve the estimation of centroid matrix of clusters, which is difficult in
real applications. To avoid centroid estimation, Pei et al. [2] presented
$k$-sum by leveraging the relationship between spectral clustering and _K_
-means [3]. However, _k_ -sum and _k_ -multiple means are suitable for single
view clustering. To apply them to multi-view clustering, they can’t well
exploit the complementary information embedded in views. Different from
existing work, our proposed model rethinks _k_ -means from manifold learning
perspective and provides an efficient model which helps make _k_ -means sense.
Moreover, our work avoids estimation of centroid matrix and well exploits the
complementary information of views.

For convenience, we introduce the notations used throughout the paper. We use
bold calligraphy letters for third-order tensors,
${\bm{\mathcal{M}}}\in{\mathbb{R}}{{}^{{n_{1}}\times{n_{2}}\times{n_{3}}}}$,
bold upper case letters for matrices, ${\bf{M}}$, bold lower case letters for
vectors, ${\bf{m}}$, and lower case letters such as ${m_{ijk}}$ for the
entries of ${\bm{\mathcal{M}}}$. Moreover, the $i$-th frontal slice of
${\bm{\mathcal{M}}}$ is ${\bm{\mathcal{M}}}^{(i)}$.
$\overline{{\bm{\mathcal{M}}}}$ is the discrete Fourier transform (DFT) of
${\bm{\mathcal{M}}}$ along the third dimension,
$\overline{{\bm{\mathcal{M}}}}=\mathrm{fft}({{\bm{\mathcal{M}}}},[],3)$. Thus,
$\bm{{\mathcal{M}}}=\mathrm{ifft}({\overline{\bm{\mathcal{M}}}},[],3)$. The
trace of matrix $\mathbf{M}$ is expressed as $tr(\mathbf{M})$. The Frobenius
norm of ${\bm{\mathcal{M}}}$ is defined as
${\left\|{\bm{\mathcal{M}}}\right\|_{F}}=\sqrt{\sum\nolimits_{i,j,k}{{{\left|{{m_{ijk}}}\right|}^{2}}}}$.

##  3 Rethinking for K-Means

Suppose ${\mathbf{X}}^{(v)}=[\mathbf{x}_{1}^{(v)}\textrm{, }\ldots\textrm{ ,
}\mathbf{x}_{N}^{(v)}]^{\textrm{T}}\in\mathbb{R}^{N\times d_{v}}$ denote the
data matrix of the $v$-th view ($v=1,2,\cdots,V$), where $N$ and $V$ are the
number of samples and views, respectively, $d_{v}$ is the feature dimension of
the $v$-view. The label matrix is denoted by
$\mathbf{Y}=[\mathbf{y}_{1}\textrm{, }\ldots\textrm{ ,
}\mathbf{y}_{N}]^{\textrm{T}}\in\left\\{0,1\right\\}^{N\times C}$, where
$\mathbf{y}_{i}$ is indicator vector of the $i$-th sample; $y_{ij}=\textrm{1}$
if $\mathbf{x}_{i}$ belongs to the $j$-th cluster; $y_{ij}=\textrm{0}$,
otherwise. $C$ is the cluster number of data.

_K_ -means aims to partition data points
$\mathbf{x}_{1}^{(v)},\mathbf{x}_{2}^{(v)},\cdots,\mathbf{x}_{N}^{(v)}$ into
$C$ clusters according to the Euclidean distance between the data points and
the centroid points
$\mathbf{u}_{1}^{(v)},\mathbf{u}_{2}^{(v)},\cdots,\mathbf{u}_{C}^{(v)}$ such
that the data points in the same clusters are as close as possible and the
distances between different clusters are as large as possible. Objective
function of multi-view $K$-means can be reformulated as [18]

$\displaystyle\mathop{\min}\limits_{{{\bf{M}}^{(v)}},{\bf{Y}}}\sum\limits_{v}{\left\|{{{\bf{X}}^{(v)}}-{{\bf{M}}^{(v)}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}$
(1)

where
${\bf{M}}^{(v)}=[{\bf{u}}_{1}^{(v)},{\bf{u}}_{2}^{(v)},\cdots,{\bf{u}}_{C}^{(v)}]$
is centroid matrix of the $v$-th view, $\bf{u}_{j}^{(v)}$ denotes the
centroid, i.e. mean vector of the $j$-th cluster of the $v$-th view.

For the model (1), we have the following theorem.

###### Theorem 1

Denoted by ${A}_{1}\textrm{, }\ldots\textrm{ , }{A}_{C}$ the clusters of
multi-view data ${\bf{X}^{(v)}}$, $v=1,\cdots,V$, ${\bf{u}}_{j}^{(v)}$ is the
centroid of the $j$-th cluster of the $v$-th view, $N_{v}=|A_{v}|$ is the
number of samples in $A_{v}$, then

$\begin{array}[]{l}\mathop{\min}\limits_{{{\bf{M}}^{(v)}},{\bf{Y}}}\sum\limits_{v}{\left\|{{{\bf{X}}^{(v)}}-{{\bf{M}}^{(v)}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}=\\\
\ \ \ \ \ \ \ \ \ \ \ \
\mathop{\min}\limits_{{A_{1}},{A_{1}},...,{A_{c}}}\sum\limits_{v}{\sum\limits_{i,l}{\left\|{{\bf{x}}_{i}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}}\end{array}$
(2)

where

${S_{il}}=\left\\{{\begin{array}[]{*{20}{l}}{\left\langle{{{\bf{G}}^{{i}}},{{\bf{G}}^{{l}}}}\right\rangle,\begin{array}[]{*{20}{c}}{}\hfil\end{array}{\bf{x}}_{i}^{(v)}\in{A_{j}}\
and\ {\bf{x}}_{l}^{(v)}\in{A_{j}}}\\\
{0,\begin{array}[]{*{20}{c}}{}\hfil&{}\hfil\end{array}otherwise}\end{array}}\right.$
(3)

and

${\bf{G}}=\left\\{\begin{array}[]{l}{{\bf{Y}}},\begin{array}[]{*{20}{c}}{}\hfil\end{array}\
\ \ \ \ \ \ \ \ \ \ \ \ \ N_{1}=N_{2}=\cdots=N_{c}\\\
{\bf{Y}}{({\bf{Y}^{T}}{\bf{Y}})^{-{\textstyle{1\over
2}}}},\begin{array}[]{*{20}{c}}{}\hfil&{}\hfil\end{array}otherwise\end{array}\right.$
(4)

_Proof:_

Since ${A}_{1}\textrm{, }\ldots\textrm{ , }{A}_{C}$ are the clusters of data,
then,

$\begin{array}[]{l}\mathop{\min}\limits_{{{\bf{M}}^{(v)}},{\bf{Y}}}\sum\limits_{v}{\left\|{{{\bf{X}}^{(v)}}-{{\bf{M}}^{(v)}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}=\\\
\ \ \ \ \ \ \ \ \ \ \
\mathop{\min}\limits_{{A_{1}},{A_{1}},...,{A_{c}}}\sum\limits_{v}{\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{\left\|{{\bf{x}}_{i}^{(v)}-{\bf{u}}_{j}^{(v)}}\right\|_{F}^{2}}}\end{array}$
(5)

Since all views are independent, thus, for each view such as the $v$-th view,
we have

$\begin{array}[]{l}\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{\left\|{{{\bf{x}}_{i}^{(v)}}-{\bf{u}}_{j}^{(v)}}\right\|_{F}^{2}}\\\
=\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{tr}({{\bf{x}}_{i}^{(v)}}^{T}{{\bf{x}}_{i}^{(v)}}-2{{\bf{x}}_{i}^{(v)}}^{T}{{\bf{u}}_{j}^{(v)}}+{{{\bf{u}}_{j}^{(v)}}^{T}}{{\bf{u}}_{j}^{(v)}})\\\
=\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{tr}({{\bf{x}}_{i}^{(v)}}^{T}{{\bf{x}}_{i}^{(v)}}-{{\bf{x}}_{i}^{(v)}}^{T}{{\bf{u}}_{j}^{(v)}})\end{array}$
(6)

and

$\begin{array}[]{l}\frac{1}{{2N_{v}}}\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{\sum\limits_{{\bf{x}}_{l}^{(v)}\in{A_{j}}}{\left\|{{{\bf{x}}_{i}^{(v)}}-{{\bf{x}}_{l}^{(v)}}}\right\|_{F}^{2}}}\\\
=\frac{1}{{2N_{v}}}\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{\sum\limits_{{\bf{x}}_{l}^{(v)}\in{A_{j}}}{tr}}(2{{\bf{x}}_{i}^{(v)}}^{T}{{\bf{x}}_{i}^{(v)}}-2{{\bf{x}}_{i}^{(v)}}^{T}{{\bf{x}}_{l}^{(v)}})\\\
=\frac{1}{{2N_{v}}}\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{tr}(2n{{\bf{x}}_{i}^{(v)}}^{T}{{\bf{x}}_{i}^{(v)}}-2n{{\bf{x}}_{i}^{(v)}}^{T}{{\bf{u}}_{j}^{(v)}})\\\
=\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{tr}({{\bf{x}}_{i}^{(v)}}^{T}{{\bf{x}}_{i}^{(v)}}-{{\bf{x}}_{i}^{(v)}}^{T}{\bf{u}}_{j}^{(v)})\end{array}$
(7)

According to Eq. (6) and Eq. (7), we have

$\begin{array}[]{l}\sum\limits_{{\bf{x}}_{i}^{(v)}\in{A_{j}}}{\left\|{{{\bf{x}}_{i}^{(v)}}-{\bf{u}}_{j}^{(v)}}\right\|_{F}^{2}}\\\
\ \ \ \ \ \ \ \ \ \ \ \ \
=\frac{1}{{2N_{v}}}\sum\limits_{{{\bf{x}}_{i}^{(v)}\in{A_{j}}},{{\bf{x}}_{l}^{(v)}\in{A_{j}}}}{\left\|{{{\bf{x}}_{i}}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}}\\\
\ \ \ \ \ \ \ \ \ \ \ \ \
=\sum\limits_{{{\bf{x}}_{i}^{(v)}},{{\bf{x}}_{l}^{(v)}}}{\left\|{{{\bf{x}}_{i}}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}\end{array}$
(8)

Since all views are independent, thus we have

$\sum\limits_{v}{\left\|{{{\bf{X}}^{(v)}}-{{\bf{M}}^{(v)}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}=\sum\limits_{v}{\sum\limits_{i,l}{\left\|{{{\bf{x}}_{i}}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}}$
(9)

Then, the model (2) holds.

Theorem 1 indicates that _k_ -means can be viewed as a manifold learning
technique.

###### Theorem 2

Denoted by ${{\bf{D}}_{v}}$ distance matrix between data points of the $v$-th
view, the elements ${{\bf{D}}_{v}}(i,l)$ of ${\bf{D}}_{v}$ are
${{\bf{D}}_{v}}(i,l)=\left\|{{\bf{x}}_{i}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}$,
then

$\begin{array}[]{l}\mathop{\min}\limits_{{{\bf{M}}^{(v)}},{\bf{Y}}}\sum\limits_{v}{\left\|{{{\bf{X}}^{(v)}}-{{\bf{M}}^{(v)}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}=\mathop{\min}\limits_{\bf{G}}\sum\limits_{v}{tr({{\bf{G}}^{T}}{{\bf{D}}_{v}}{\bf{G}})}\end{array}$
(10)

###### Proof 1

For each view such as the $v$-th view, we have

$\begin{array}[]{l}\sum\limits_{{{\bf{x}}_{i}^{(v)}},{{\bf{x}}_{l}^{(v)}}}{\left\|{{{\bf{x}}_{i}}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \
=\sum\limits_{i}{\sum\limits_{l}{tr}}(d_{il}^{(v)}\left\langle{{{\bf{G}}^{i}},{{\bf{G}}^{l}}}\right\rangle)\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \
=\sum\limits_{i}{tr((d_{il}^{(v)}{{\bf{G}}^{T}}){{\bf{G}}^{i}})}\\\ \ \ \ \ \
\ \ \ \ \ \ \ \ \ =tr({{\bf{G}}^{T}}{{\bf{D}}_{v}}{\bf{G}})\end{array}$ (11)

Since all views are independent, and according to Eq. (11), we have

$\begin{array}[]{l}\sum\limits_{v}{\sum\limits_{{{\bf{x}}_{i}^{(v)}},{{\bf{x}}_{l}^{(v)}}}{\left\|{{{\bf{x}}_{i}}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}}\\\
\ \ \ \ \ \ \ \
=tr(\sum\limits_{v}{{{\bf{G}}^{T}}{{{\bf{D}}_{v}}}{\bf{G}}})\\\ \ \ \ \ \ \ \
\ =\sum\limits_{v}{tr({{\bf{G}}^{T}}{{\bf{D}}_{V}}{\bf{G}})}\end{array}$ (12)

then,

$\begin{array}[]{l}\mathop{\min}\limits_{{A_{1}},{A_{1}},...,{A_{c}}}\sum\limits_{v}{\sum\limits_{i,l}{\left\|{{\bf{x}}_{i}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}}=\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathop{\min}\limits_{\bf{G}}\sum\limits_{v}{tr({{\bf{G}}^{T}}{{\bf{D}}_{v}}{\bf{G}})}\end{array}$
(13)

According to theorem 1 and Eq. (13), we have

$\begin{array}[]{l}\mathop{\min}\limits_{{{\bf{M}}^{(v)}},{\bf{Y}}}\sum\limits_{v}{\left\|{{{\bf{X}}^{(v)}}-{{\bf{M}}^{(v)}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}\\\
\ \ \ \ \ \ \ \ \
=\mathop{\min}\limits_{{A_{1}},{A_{1}},...,{A_{c}}}\sum\limits_{v}{\sum\limits_{i,l}{\left\|{{\bf{x}}_{i}^{(v)}-{\bf{x}}_{l}^{(v)}}\right\|_{F}^{2}{S_{il}}}}\\\
\ \ \ \ \ \ \ \ \
=\mathop{\min}\limits_{\bf{G}}\sum\limits_{v}{tr({{\bf{G}}^{T}}{{\bf{D}}_{v}}{\bf{G}})}\end{array}$
(14)

###### Remark 1

When $V=1$, Theorem 2 becomes

$\begin{array}[]{l}\mathop{\min}\limits_{{{\bf{M}}},{\bf{Y}}}{\left\|{{{\bf{X}}}-{{\bf{M}}}{{\bf{Y}}^{T}}}\right\|_{F}^{2}}=\\\
\mathop{\min}\limits_{{A_{1}},{A_{1}},...,{A_{c}}}{\sum\limits_{i,l}{\left\|{{\bf{x}}_{i}-{\bf{x}}_{l}}\right\|_{F}^{2}{S_{il}}}}=\mathop{\min}\limits_{\bf{G}}{tr({{\bf{G}}^{T}}{{\bf{D}}}{\bf{G}})}\end{array}$
(15)

which is standard _k_ -means. It indicates that $k$-sum is a special case of
our model (10).

###### Remark 2

When $V=1$, Theorem 2 becomes Ratio-cut [32], which is one of the most
representative spectral clustering models. Ratio-cut aims to get clusters
${A}_{1}\textrm{, }\ldots\textrm{ , }{A}_{c}$ by

$\displaystyle\mathop{\min}\limits_{{A_{1}},{A_{1}},...,{A_{c}}}{\sum\limits_{l=1}^{c}{\frac{\textrm{cut}\left(\mathbf{A}_{l},\overline{\mathbf{A}}_{l}\right)}{\left|\mathbf{A}_{l}\right|}}}$
(16)

where $\overline{\mathbf{A}}_{l}$ is the complement of $\mathbf{A}_{l}$;
$\left|\mathbf{A}_{l}\right|$ denotes the number of samples in
$\mathbf{A}_{l}$, and
$\textrm{cut}\left(\mathbf{A}_{l},\overline{\mathbf{A}}_{l}\right)=\sum_{i\in\mathbf{A}_{l}\textrm{,
}j\in\overline{\mathbf{A}}_{l}}{w_{ij}}$, $w_{ij}$ is the weight between the
$i$-th node and $j$-th node.

By simple algebra, the problem (16) becomes

$\quad\mathop{\min}\limits_{\mathbf{Y}\in\bm{\mathcal{I}}}{\mathrm{\emph{tr}}((\mathbf{Y}^{T}\mathbf{Y})^{-1/2}\mathbf{Y}^{T}\mathbf{L}\mathbf{Y}(\mathbf{Y}^{T}\mathbf{Y})^{-1/2})}$
(17)

where $\mathbf{L}$ is Laplacian matrix.

According to the definition of $\bf{G}$ (See Eq. (4)), we have that the model
(17) can be rewritten as

$\quad\mathop{\min}\limits_{\mathbf{G}}{\mathrm{\emph{tr}}(\mathbf{G}^{T}\mathbf{L}\mathbf{G})}$
(18)

When ${\bf{L}}$ becomes ${\bf{D}}$, the model (18) becomes the model (15). It
means that Spectral clustering is also a special case of our model (10).

Combining the aforementioned insight analysis, we have that, from manifold
learning perspective, we make _k_ -means sense and integrate _k_ -means,
manifold learning and spectral clustering into a uniform framework.

##  4 Methodogy

###  4.1 Motivation and Objective

In reality, different views contain different characteristics of the object,
thus, different views should have different similarity matrices, resulting to
different label matrices of different views. However, the model (10) neglects
this, resulting in sub-optimal performance. To further improve the
performance, combining the aforementioned insight analysis, we rewrite the
model (10) as the following unified framework for multi-view clustering:

$\displaystyle\mathop{{\rm{min}}}\limits_{{{\bf{Y}}^{(v)}},{\alpha_{\rm{v}}}}\sum\limits_{v{\rm{=1}}}^{{V}}{\alpha_{\rm{v}}^{{r}}}{\rm{tr}}({{\bf{G}}^{(v)T}}{{\bf{D}}^{(v)}}{{\bf{G}}^{(v)}}){\rm{+}}\lambda\sum\limits_{v{\rm{=1}}}^{V}{\cal
R}({{\bf{Y}}^{(v)}})$ (19)
$\displaystyle\emph{{s.t.}}\quad\quad{\textbf{Y}^{\textrm{(\emph{v})}}\in\textrm{Ind}}\textrm{,
}\sum\limits_{\textrm{\emph{v}=1}}^{\textrm{\emph{V}}}{{\alpha_{\textrm{\emph{v}}}}\textrm{
= 1}},{\rm{}}{\alpha_{\textrm{\emph{v}}}}\geq{{\textrm{0}}}$

where $\textbf{Y}^{\textrm{(\emph{v})}}$ is the label matrix of the $v$-th
view; $\mathcal{R}\textrm{(}\bullet\textrm{)}$ represents the regularizer on
${\mathbf{Y}^{(v)}}$; $\alpha_{v}^{r}$ is the adaptive weight for the $v$-th
view, which characterizes the importance of the $v$-th view, $V$ is the number
of views, $\lambda$ is a trade-off parameter, and

${\bf{G}}^{(v)}=\left\\{\begin{array}[]{l}{{\bf{Y}}}^{(v)},\begin{array}[]{*{20}{c}}{}\hfil\end{array}\
\ \ \ \ \ \ \ \ \ \ \ \ \ N_{1}=N_{2}=\cdots=N_{c}\\\
{\bf{Y}}^{(v)}{({{\bf{Y}}^{(v)T}}{\bf{Y}}^{(v)})^{-{\textstyle{1\over
2}}}},\begin{array}[]{*{20}{c}}{}\hfil&{}\hfil\end{array}otherwise\end{array}\right.$
(20)

Figure 1: Construction of tensor $\bm{\mathcal{Y}}\in\mathbb{R}^{N\times
C\times V}$. $\bm{\Delta}^{(c)}$ denotes the $c$-th frontal slice of
$\bm{\mathcal{Y}}$ ($c\in\\{1\textrm{, }2\textrm{, }\cdots\textrm{, }C\\}$).

In the model (19), the second term aims to minimize the divergence between
${\mathbf{Y}^{(v)}}$. To solve this problem, a naive method is to leverage
squared _F_ -norm to learn the discrete label matrix. As we all know, $F$-norm
is a one-dimensional and pixel-wise measurement method. Thus, it cannot well
exploit the complementary information embedded in ${\mathbf{Y}^{(v)}}$. It is
evident that the low rank approximation using tensor Schatten $p$-norm
performs very well in exploiting the complementary information embedded in
views [8, 9], thus, we minimize the divergence between ${\bf{Y}^{v}}$ by using
the tensor Schatten $p$-norm minimization on the third-order tensor
${\mathcal{Y}}$ which consists of ${\bf{Y}^{v}}$. Thus, we have

$\displaystyle\mathop{{\rm{min}}}\limits_{{{\bf{Y}}^{(v)}},{\alpha_{\rm{v}}}}\sum\limits_{v{\rm{=1}}}^{{V}}{\alpha_{\rm{v}}^{{r}}}{\rm{tr}}({{\bf{G}}^{(v)T}}{{\bf{D}}^{(v)}}{{\bf{G}}^{(v)}})\textrm{+}\lambda{\|{\bm{\mathcal{Y}}}\|_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}^{p}}$
(21)
$\displaystyle\emph{{s.t.}}\quad\quad{\textbf{Y}^{\textrm{(\emph{v})}}\in\textrm{Ind}}\textrm{,
}\sum\limits_{\textrm{\emph{v}=1}}^{\textrm{\emph{V}}}{{\alpha_{\textrm{\emph{v}}}}\textrm{
= 1}},{\rm{}}{\alpha_{\textrm{\emph{v}}}}\geq{{\textrm{0}}}$

where the $i$-th lateral slice of $\bm{\mathcal{Y}}\in\mathbb{R}^{N\times
V\times C}$ is ${\textbf{Y}}^{(v)}$ (See Fig. 1);
$\left\|\bullet\right\|_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}$ is the
tensor Schatten $p$-norm (see Definition 1).

###### Definition 1

(Tensor Schatten p-norm [8]) Given
${\bm{\mathcal{Y}}}\in{\mathbb{R}}^{n_{1}\times n_{2}\times n_{3}}$,
$h=\min(n_{1},n_{2})$, the tensor Schatten $p$-norm of tensor
${\bm{\mathcal{Y}}}$ is defined as

$\begin{array}[]{c}{\left\|{\bm{\mathcal{Y}}}\right\|_{{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}}}={\left({\sum\limits_{i=1}^{{n_{3}}}{\left\|{{{\overline{\bm{\mathcal{Y}}}}^{(i)}}}\right\|}_{{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}}^{p}}\right)^{\frac{1}{p}}}={\left({\sum\limits_{i=1}^{{n_{3}}}{\sum\limits_{j=1}^{h}{{\sigma_{j}}{{\left({{{\overline{\bm{\mathcal{Y}}}}^{(i)}}}\right)}^{p}}}}}\right)^{\frac{1}{p}}}\end{array}$
(22)

where ${\sigma_{j}}(\overline{\bm{\mathcal{Y}}}^{(i)})$ denotes the j-th
singular value of $\overline{\bm{\mathcal{Y}}}^{(i)}$.

###### Remark 3

when $p=1$, tensor Schatten p-norm of
${\bm{\mathcal{Y}}}\in{\mathbb{R}}^{n_{1}\times n_{2}\times n_{3}}$ becomes
tensor nuclear norm [8], i.e.,
${\left\|{\bm{\mathcal{Y}}}\right\|_{*}}={{\sum\limits_{i=1}^{{n_{3}}}{\sum\limits_{j=1}^{h}{{\sigma_{j}}{{\left({{{\overline{\bm{\mathcal{Y}}}}^{(i)}}}\right)}}}}}}$.
Take matrix Schatten p-norm as an example, that is for
${\bm{Y}}\in\mathbb{R}^{n_{1}\times n_{2}}$ and the singular values of
${\bm{Y}}$ denoted by $\sigma_{1},\ldots,\sigma_{h}$, we have
$\|{\bm{Y}}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}=\sigma_{1}^{p}+\cdots+\sigma_{h}^{p},\
p>0.$ Nie et al. [33] has shown that $\lim_{p\to
0}\|{\bm{Y}}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}=\\#\\{i:\sigma_{i}\neq
0\\}=\hbox{rank}({\bm{Y}}).$ And for $0\leq p\leq 1$, i.e. when $p$ is
appropriately chosen, the Schatten p-norm can give us quite effective
improvements for a tighter approximation of the rank function.

###### Remark 4

The regularizer in the proposed objective (21) is used to explore the
complementary information embedded in inter-views cluster assignment matrices
$\textbf{Y}^{(v)}$ ($v=1,2,\cdots,V$). Fig. 1 shows the construction of tensor
$\bm{\mathcal{Y}}$, it can be seen that the $c$-th frontal slice
$\bm{\Delta}^{(c)}$ describes the similarity between $N$ sample points and the
$c$-th cluster in different views. The idea cluster assignment matrix
$\textbf{Y}^{(v)}$ should satisfy that the relationship between $N$ data
points and the $c$-th cluster is consistent in different views. Since
different views usually show different cluster structures, we impose tensor
Schatten p-norm minimization [8] constraint on $\bm{\mathcal{Y}}$, which can
make sure each $\bm{\Delta}^{(c)}$ has spatial low-rank structure. Thus
$\bm{\Delta}^{(c)}$ can well characterize the complementary information
embedded in inter-views.

###  4.2 Optimization

In (21), the main difficulty in finding the discrete assignment matrix is due
to the non-convex property. To this end, we suppose the number of samples in
each cluster are equal. In this case, $N_{1}=N_{2}=\cdots=N_{c}$, according to
(20), we have ${\mathbf{Y}^{(v)}}={\mathbf{G}^{(v)}}$. Thus, (21) becomes

$\displaystyle\mathop{\textrm{min}}\limits_{\textbf{Y}^{\textrm{(\emph{v})}}\textrm{,
}\alpha_{\emph{{v}}}}\sum\limits_{\textrm{\emph{v}=1}}^{\emph{{V}}}\alpha_{\emph{{v}}}^{\emph{{r}}}\mathrm{tr}\textrm{(}{{\textbf{Y}^{\textrm{(\emph{v})}}}^{\textrm{T}}}\textbf{D}^{\textrm{(\emph{v})}}\textbf{Y}^{\textrm{(\emph{v})}}\textrm{)}\textrm{+}\lambda{\|{\bm{\mathcal{Y}}}\|_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}^{p}}$
(23)
$\displaystyle\emph{{s.t.}}\quad\quad{\textbf{Y}^{\textrm{(\emph{v})}}\in\textrm{Ind}}\textrm{,
}\sum\limits_{\textrm{\emph{v}=1}}^{\textrm{\emph{V}}}{{\alpha_{\textrm{\emph{v}}}}\textrm{
= 1}},{\rm{}}{\alpha_{\textrm{\emph{v}}}}\geq{{\textrm{0}}}$

Inspire by the augmented Lagrange multiplier (ALM) [34], we introduce an
auxiliary variable $\bm{\mathcal{J}}$ and rewrite (23) as

$\displaystyle\bm{\mathcal{L}}(\bm{\mathcal{Y}},\bm{\mathcal{J}})$
$\displaystyle=\sum\limits_{\textrm{\emph{v}=1}}^{\emph{{V}}}\alpha_{\emph{{v}}}^{\emph{{r}}}\mathrm{tr}\textrm{(}{{\textbf{Y}^{\textrm{(\emph{v})}}}^{\textrm{T}}}\textbf{D}^{\textrm{(\emph{v})}}\textbf{Y}^{\textrm{(\emph{v})}}\textrm{)}\textrm{+}\lambda{\|{\bm{\mathcal{J}}}\|_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}^{p}}$
(24)
$\displaystyle\quad+{\langle{\bm{\mathcal{Q}},\bm{\mathcal{Y}}-\bm{\mathcal{J}}}\rangle}+\frac{\mu}{2}\|\bm{\mathcal{Y}}-\bm{\mathcal{J}}\|_{F}^{2}$

where $\bm{\mathcal{Q}}$ is Lagrange multipliers; $\mu$ is a penalty
parameter. The optimization process could be separated into three steps:

$\bullet$ Solving $\mathbf{Y}^{(v)}$ with fixed $\alpha_{v}$ and
$\bm{\mathcal{J}}$. When $\alpha_{v}$ and $\bm{\mathcal{J}}$ are fixed, the
optimization w.r.t. $\mathbf{Y}^{(v)}$ in (24) becomes

$\displaystyle\mathop{\textrm{min}}\limits_{\mathbf{Y}^{(v)}\in\textrm{Ind}}$
$\displaystyle\sum\limits_{\textrm{\emph{v}=1}}^{\emph{{V}}}\alpha_{\emph{{v}}}^{\emph{{r}}}\mathrm{tr}\textrm{(}{{\textbf{Y}^{\textrm{(\emph{v})}}}^{\textrm{T}}}\textbf{D}^{\textrm{(\emph{v})}}\textbf{Y}^{\textrm{(\emph{v})}}\textrm{)}\textrm{+}\frac{\mu}{\textrm{2}}\|\bm{\mathcal{Y}}\textrm{-}\bm{\mathcal{J}}\textrm{+}\frac{\bm{\mathcal{Q}}}{\mu}\|_{F}^{2}$
(25)

Since all $\mathbf{Y}^{(v)}$’s ($v=1,\cdots,V$) are independent, then model
(25) can be decomposed into $V$ independent sub-optimization problems. In
other words, we can obtain $\mathbf{Y}^{(v)}$ ($v=1,\cdots,V$) of the
corresponding view by solving

$\displaystyle\mathop{\textrm{min}}\limits_{\mathbf{Y}^{(v)}\in\textrm{Ind}}$
$\displaystyle\alpha_{\emph{{v}}}^{\emph{{r}}}\mathrm{tr}\textrm{(}{{\textbf{Y}^{\textrm{(\emph{v})}}}^{\textrm{T}}}\textbf{D}^{\textrm{(\emph{v})}}\textbf{Y}^{\textrm{(\emph{v})}}\textrm{)}\textrm{+}\frac{\mu}{\textrm{2}}\|\mathbf{Y}^{(v)}\textrm{-}\mathbf{S}^{(v)}\|_{F}^{2}$
(26)

where
$\mathbf{S}^{(v)}\textrm{=}\mathbf{J}^{(v)}\textrm{-}\frac{1}{\mu}\mathbf{Q}^{(v)}$.

It is hard to directly get the optimal solution of (26) due to the discrete
constraint. Sine all rows of $\mathbf{Y}^{(v)}$ are independent, we
sequentially solve $\mathbf{Y}^{(v)}$ row by row with fixed the other rows. To
update the $k$-th row, we assume the other rows of $\mathbf{Y}^{(v)}$ are
known. Then, the optimization w.r.t. the $k$-th row in (26) becomes

$\displaystyle\mathop{\textrm{min}}\limits_{\mathbf{y}_{k}^{\textrm{(\emph{v})}}\in\textrm{Ind}}\alpha_{\emph{{v}}}^{\emph{{r}}}\sum\limits_{{{i,j}=1}}^{\emph{{N}}}d_{ij}^{\textrm{(\emph{v})}}\mathrm{tr}(\mathbf{y}_{i}^{\textrm{(\emph{v})}}{\mathbf{y}_{j}^{\textrm{(\emph{v})}}}^{\textrm{T}})+\frac{\mu}{2}\|\mathbf{y}_{k}^{\textrm{(\emph{v})}}\textrm{-}\mathbf{s}_{k}^{\textrm{(\emph{v})}}\|_{F}^{2}$
(27) $\displaystyle\Leftrightarrow$
$\displaystyle\mathop{\textrm{min}}\limits_{\mathbf{y}_{k}^{\textrm{(\emph{v})}}\in\textrm{Ind}}\alpha_{\emph{{v}}}^{\emph{{r}}}{\mathbf{y}_{k}^{\textrm{(\emph{v})}}}^{\textrm{T}}(2\sum\limits_{i\mathrm{=}1,i\mathrm{\neq}k}^{\emph{{N}}}d_{ki}^{\textrm{(\emph{v})}}\mathbf{y}_{i}^{\textrm{(\emph{v})}})-\mu{\mathbf{y}_{k}^{\textrm{(\emph{v})}}}^{\textrm{T}}\mathbf{s}_{k}^{\textrm{(\emph{v})}}$

Since $d_{kk}^{\textrm{(\emph{v})}}\mathrm{=}0$, thus, the problem (27) can be
rewritten as

$\displaystyle\mathop{\textrm{min}}\limits_{\mathbf{y}_{k}^{\textrm{(\emph{v})}}\in\textrm{Ind}}2\alpha_{\emph{{v}}}^{\emph{{r}}}{\mathbf{y}_{k}^{\textrm{(\emph{v})}}}^{\textrm{T}}(\sum\limits_{i\mathrm{=}1}^{\emph{{N}}}d_{ki}^{\textrm{(\emph{v})}}\mathbf{y}_{i}^{\textrm{(\emph{v})}})-\mu{\mathbf{y}_{k}^{\textrm{(\emph{v})}}}^{\textrm{T}}\mathbf{s}_{k}^{\textrm{(\emph{v})}}$
(28) $\displaystyle\Leftrightarrow$
$\displaystyle\mathop{\textrm{min}}\limits_{\mathbf{y}_{k}^{\textrm{(\emph{v})}}\in\textrm{Ind}}{\mathbf{y}_{k}^{\textrm{(\emph{v})}}}^{\textrm{T}}(2\alpha_{\emph{{v}}}^{\emph{{r}}}{\textbf{Y}_{*}^{\textrm{(\emph{v})}}}^{\textrm{T}}\mathbf{d}_{k}^{\textrm{(\emph{v})}}-\mu\mathbf{s}_{k}^{\textrm{(\emph{v})}})$

where
$\mathbf{d}_{k}^{\textrm{(\emph{v})}}\textrm{=}[d_{k1}^{\textrm{(\emph{v})}},d_{k2}^{\textrm{(\emph{v})}},\cdots,d_{kn}^{\textrm{(\emph{v})}}]^{\textrm{T}}$,
$d_{ii}^{\textrm{(\emph{v})}}\textrm{=}0$;
$\textbf{Y}_{*}^{\textrm{(\emph{v})}}$ is the cluster assignment matrix before
$\mathbf{y}_{k}^{(v)}$ is updated. Then, the optimal solution of (25) can be
reformulated as

$\displaystyle
y_{ip}^{\textrm{(\emph{v})}}=\begin{cases}1\textrm{,}&p=\mathop{\textrm{arg
min}}\limits_{j}(2\alpha_{\emph{{v}}}^{\emph{{r}}}{\textbf{Y}_{*}^{\textrm{(\emph{v})}}}^{\textrm{T}}\mathbf{d}_{i}^{\textrm{(\emph{v})}}-\mu\mathbf{s}_{i}^{\textrm{(\emph{v})}})_{j}\\\
0\textrm{,}&\quad\quad\mbox{{otherwise}}.\end{cases}$ (29)

$\bullet$ Solving $\alpha_{v}$ with fixed $\bm{\mathcal{Y}}$ and
$\bm{\mathcal{J}}$. When $\bm{\mathcal{Y}}$ and $\bm{\mathcal{J}}$ are fixed,
the optimization w.r.t. $\alpha_{v}$ in (24) is equivalent to

$\displaystyle\mathop{\textrm{min}}\limits_{\alpha_{\emph{{v}}}}\sum\limits_{\textrm{\emph{v}=1}}^{\emph{{V}}}\alpha_{\emph{{v}}}^{\emph{{r}}}\mathrm{tr}\textrm{(}{{\textbf{Y}^{\textrm{(\emph{v})}}}^{\textrm{T}}}\textbf{D}^{\textrm{(\emph{v})}}\textbf{Y}^{\textrm{(\emph{v})}}\textrm{)}$
$\displaystyle\emph{{s.t.}}\quad\sum\limits_{\textrm{\emph{v}=1}}^{\textrm{\emph{V}}}{{\alpha_{\textrm{\emph{v}}}}\textrm{
= 1}},{\rm{}}{\alpha_{\textrm{\emph{v}}}}\geq{{\textrm{0}}}$ (30)

According to the Lagrange multiplier method, we establish the Lagrangian
function as

$\displaystyle\bm{\mathcal{L}}(\alpha_{1},\ldots,\alpha_{V},\gamma)=\sum\limits_{v=1}^{V}\alpha_{v}^{r}\mathbf{M}_{v}+\gamma\left(1-\sum\limits_{v=1}^{V}{\alpha_{v}}\right)$
(31)

where $\gamma$ is a parameter;
${\mathbf{M}_{v}}=\mathrm{tr}\textrm{(}{{\textbf{Y}^{\textrm{(\emph{v})}}}^{\textrm{T}}}\textbf{D}^{\textrm{(\emph{v})}}\textbf{Y}^{\textrm{(\emph{v})}}\textrm{)}$.

According to the KKT conditions, we have

$\displaystyle\begin{cases}\frac{\partial\bm{\mathcal{L}}}{\partial\alpha_{v}}=r\alpha_{v}^{r\mathrm{-}1}\textbf{M}_{v}\mathrm{-}\gamma\mathrm{-}\theta_{v}=0,\quad
v=1,\ldots,V\\\ \theta_{v}\alpha_{v}=0,\quad v=1,\ldots,V\\\ \theta_{v}\geq
0,\quad v=1,\ldots,V\\\
1\mathrm{-}\sum\limits_{v=1}^{V}{\alpha_{v}}=0\end{cases}$ (32)

In light of some simple algebra, we have

$\displaystyle\alpha_{v}=\frac{(\mathbf{M}_{v})^{\frac{1}{1-r}}}{\sum\limits_{v=1}^{V}(\mathbf{M}_{v})^{\frac{1}{1-r}}}$
(33)

$\bullet$ Solving $\bm{\mathcal{J}}$ with fixed $\bm{\mathcal{Y}}$ and
$\alpha_{v}$. In this case, $\bm{\mathcal{J}}$ can be obtained by solving

$\displaystyle\bm{\mathcal{J}}^{*}=\mathop{\arg\min}_{\bm{\mathcal{J}}}\frac{\lambda}{\mu}{\|{\bm{\mathcal{J}}}\|_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}^{p}}+\frac{1}{2}\|\bm{\mathcal{Y}}-\bm{\mathcal{J}}+\frac{\bm{\mathcal{Q}}}{\mu}\|_{F}^{2}$
(34)

To solve model (34), we first introduce Theorem 3 [8].

###### Theorem 3

Given third-order tensor ${\bm{{\cal
A}}{\in\mathbb{R}^{{n_{1}}\times{n_{2}}\times{n_{3}}}}}$ whose t-SVD denotes
by ${\bm{{\cal A}}\\!=\\!\bm{{\cal U}}*\bm{{\cal S}}\\!*\\!{\bm{{\cal
V}}^{\mathrm{T}}}}$. For the problem

$\arg{\rm{}}\mathop{\min}\limits_{\bm{{\cal X}}}\mu\left\|\bm{{\cal
X}}\right\|_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}^{p}+\frac{1}{2}\left\|{\bm{{\cal
X}}-\bm{{\cal A}}}\right\|_{F}^{2},$ (35)

the optimal solution is

${{\bm{{\cal X}}}^{*}}={\rm{}}{\Gamma_{\mu}}\left[\bm{{\cal
A}}\right]{\rm{}}={\rm{}}\bm{{\cal
U}}*\mathrm{ifft}({P_{\mu}}\left({\overline{\bm{{\cal A}}}}\right))*{\bm{{\cal
V}}^{\mathrm{T}}},$ (36)

where ${P_{\mu}}(\bar{\bm{{\cal
A}}}){\in\mathbb{R}^{{n_{1}}\times{n_{2}}\times{n_{3}}}}$ is a f-diagonal
tensor whose diagonal elements can be obtained by the GST algorithm introduced
in Lemma 1 of [8].

According to Theorem 3, let ${\bm{{\mathcal{Y}}}{\rm{}}+{\rm{}}\frac{\bm{{\cal
Q}}}{\mu}{\rm{}}}=\bm{{\mathcal{U}}}*\bm{{\Sigma}}*\bm{{\mathcal{V}}}^{\mathrm{T}}$,
then the solution of (34) is

$\displaystyle{{\bm{{\cal J}}}^{*}}$
$\displaystyle={\rm{}}\Gamma{{}_{\frac{\lambda}{\mu}}}\left[{\bm{{\mathcal{Y}}}{\rm{}}+{\rm{}}\frac{\bm{{\cal
Q}}}{\mu}{\rm{}}}\right]{\rm{}}={\rm{}}{{\bm{{\cal
U}}}_{\bm{{\cal}}}}*\mathrm{ifft}({P_{\frac{\lambda}{\mu}}}\left({\overline{\bm{{\mathcal{Y}}}{\rm{}}+{\rm{}}\frac{\bm{{\cal
Q}}}{\mu}}{\rm{}}}\right))*{\bm{{\cal V}}}^{\mathrm{T}}{\rm{}}$ (37)

Finally, Algorithm 1 lists the pseudo code of the optimization procedure about
the model (23).

Input: Data matrices $\\{{\mathbf{X}}^{(v)}\\}_{v=1}^{V}\in\mathbb{R}^{N\times
d_{v}}$; anchors number $\theta$; cluster number $C$.

Output: Cluster assignment matrix $\mathbf{K}$

1 Initialize: $\lambda$, $\Omega$, $r$, $p$, $\bm{{\mathcal{J}}}$,
${{\bf{D}}^{(v)}}$, $\bm{{\mathbf{Y}^{(v)}}}$, ${\alpha_{v}}={\frac{1}{V}}$,
($v=1\ldots V$), $\rho=1.1$, $\mu={10^{-4}}$, ${\mu_{\max}}={10^{10}}$.

2 Construct $\mathbf{H}^{(v)}$ according to Eq. (39);

3 while  _not converge_ do

4 Update ${\bm{{\mathcal{Y}}}}$ by solving Eq. (29);

5 Update ${\bm{{\mathcal{J}}}}$ by solving Eq. (34);

6 Update ${\bm{{\mathcal{Q}}}}$ by
${\bm{{\mathcal{Q}}}}{\rm{=}}{\bm{{\mathcal{Q}}}}{\rm{+}}\mu{\rm{(}}{\bm{{\mathcal{Y}}}}{\rm{-}}{\bm{{\mathcal{J}}}}{\rm{)}}$;

7 Update ${\alpha_{v}}$ by Eq. (33) ($v=1\ldots V$);

8 Update $\mu$ by $\mu=\min\left({\rho\mu,{\mu_{\max}}}\right)$;

9

10 end while

11Calculate the cluster assignment matrix K by
$k_{il}=\begin{cases}1\textrm{,}&l=\mathop{\arg\max}\limits_{j}\left(\sum\limits_{v=1}^{\textrm{\emph{V}}}\alpha_{v}^{r}\textbf{Y}^{(v)}\right)_{ij}\\\
0\textrm{,}&\quad\quad\mbox{otherwise}.\end{cases}$

return: The cluster assignment matrix $\mathbf{K}$

Algorithm 1 Solving the Model (24)

###  4.3 $\mathbf{D}^{(v)}$ Construction

It is well known that $K$-means cannot well separate clusters which are non-
linearly separable in input space due to the Euclidean distance between data
poins. To address this issue, it is useful to take the advantage of adjacency
matrix, which can well characterize the intrinsic structure of arbitrarily-
shaped clusters, and good property of anchor graph, we use small adjacency
matrix $\mathbf{B}^{(v)}\in\mathbb{R}^{N\times\theta}$ to construct distance
matrix $\mathbf{D}^{(v)}$, where $\theta\ll N$ is the number of anchors. To be
specific, we firstly construct $\mathbf{B}^{(v)}\in\mathbb{R}^{N\times\theta}$
by [14], then calculate the symmetric and doubly-stochastic adjacency matrix
$\mathbf{W}^{(v)}$ by [35], i.e.,

$\displaystyle\mathbf{W}^{(v)}=\mathbf{B}^{(v)}{\Delta^{(v)}}^{\textrm{-1}}{\mathbf{B}^{(v)}}^{\textrm{T}}$
(38)

where $\Delta^{(v)}\in\mathbb{R}^{\theta\times\theta}$ is a diagonal matrix
and $\Delta_{jj}^{(v)}=\sum\nolimits_{i=1}^{N}{b^{v}_{ij}}$, $b^{v}_{ij}$ is
the $i$-th row $j$-th column element of ${\bf{B}}^{v}$.

According to the relationship between similarity and distance for data points,
to improve the clustering performance and stableness of _k_ -means, inspired
by the Butterworth filters, we calculate $d^{v}_{ij}$, which is the $i$-th row
$j$-th column element of ${\bf{D}}^{v}$, by

$\displaystyle
h^{(v)}_{ij}=\sqrt{\frac{1}{1+({\frac{w^{(v)}_{ij}}{\Omega}})^{4}}}$ (39)

where $\Omega$ is a hyperparameter.

Fig.2 shows the curve of the model (39). It can be seen that the model (39)
increases the distance between similar and dissimilar samples, while reducing
the distance between similar samples. This indicates that Eq. (39) helps
increase the separability of samples.

Figure 2: Distance vs. similarity under different $\Omega$’s.

###  4.4 Complexity Analysis

To better illustrate the efficiency of the proposed model, computational
complexity and storage complexity are analyzed in this section.

_Computational complexity:_ Our method consists of two stages: 1) Construction
of $\\{\mathbf{H}^{(v)}\\}_{v=1}^{V}$, 2) Iterative updating (24). The first
stage takes $\bm{\mathcal{O}}(VN\theta d+VN\theta\log(\theta))$ for the anchor
graph construction, where $d=\sum\nolimits_{v=1}^{V}d_{v}$; $V$, $\theta$ and
$N$ are the number of views, anchors and samples, respectively. The second
stage mainly focuses on solving two variables ($\bm{\mathbf{Y}}^{(v)}$ and
$\bm{\mathcal{J}}$), the complexity in updating these two variables are
$\bm{\mathcal{O}}(NC)$ and $\bm{\mathcal{O}}(VNC\log(VN)+V^{2}NC)$, where $C$
is the number of clusters. For $\theta,C\ll N$, the main complexity in this
stage is $\bm{\mathcal{O}}(VNC\log(VN))$. Thus, the main computational
complexity of our method is $\bm{\mathcal{O}}(VN\theta d)$, which is linear to
the number of samples.

_Storage complexity:_ The model involves several variable stores in the
optimization process, including $\\{\textbf{Y}^{\textrm{(\emph{v})}}\textrm{,
}\textbf{D}^{\textrm{(\emph{v})}}\\}_{\textrm{\emph{v} =
1}}^{\textrm{\emph{V}}}$, tensor $\bm{\mathcal{J}}$ and $\bm{\mathcal{Y}}$.
According to the size of these variables and considering the number of views,
their storage complexity is $\bm{\mathcal{O}}(\textrm{\emph{VNC}})$,
$\bm{\mathcal{O}}(\textrm{\emph{VN}}^{\textrm{2}})$,
$\bm{\mathcal{O}}(\textrm{\emph{VNC}})$, and
$\bm{\mathcal{O}}(\textrm{\emph{VNC}})$, respectively. Thus, the total storage
complexity of the proposed method is
$\bm{\mathcal{O}}(\textrm{\emph{3VNC}}+\textrm{\emph{VN}}^{\textrm{2}})$.

###  4.5 Class Equilibrium Analysis

In this section, we have shown that our model (23) can guarantee that the
numbers of samples of all clusters are approximately identical, i.e,
$N_{1}=N_{2}=\cdots=N_{c}$.

In the first term in the model (23), all views are independent, thus for the
sake of description, we ignore the variable $v$ and rewrite the first term as

$\begin{array}[]{l}tr({{\bf{Y}}^{T}}{\bf{D}}{\bf{Y}})=\sum\limits_{i,l}{\left\|{{{\bf{x}}_{i}}-{{\bf{x}}_{j}}}\right\|_{2}^{2}\left\langle{{{\bf{y}}^{i}},{{\bf{y}}^{j}}}\right\rangle}\\\
=\sum\limits_{k=1}^{c}{\sum\limits_{\scriptstyle{{\bf{x}}_{i}}\in{{\bf{A}}_{k}}\hfill\atop\scriptstyle{{\bf{x}}_{j}}\in{{\bf{A}}_{k}}\hfill}{{{\bf{d}}_{ij}}}}\end{array}$
(40)

According to (39), we have the distances between data points within the same
cluster are approximately identical, which can be denoted by constant
${{\overline{\overline{{\bf{d}}}}}}$ in our model, thus, the model (40) can be
approximately rewritten as

$\begin{array}[]{l}tr({{\bf{Y}}^{T}}{\bf{D}}{\bf{Y}})=\sum\limits_{k=1}^{c}{{\overline{\overline{{\bf{d}}}}}{N_{k}}({N_{k}}-1)}\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
=\sum\limits_{k=1}^{c}{N_{k}^{2}{\overline{\overline{{\bf{d}}}}}}-\sum\limits_{k=1}^{c}{{\overline{\overline{{\bf{d}}}}}}{N_{k}}\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
={\overline{\overline{{\bf{d}}}}}\sum\limits_{k=1}^{c}{N_{k}^{2}}-{\overline{\overline{{\bf{d}}}}}N\end{array}$
(41)

Let
${\bf{b}}={[1,1,...,1]^{T}}\in{R^{c}},{\bf{a}}=[{N_{1}},{N_{2}},...,{N_{c}}]^{T}$,
according to cauchy-schwarz inequality, we have

${\left\langle{{\bf{a}},{\bf{b}}}\right\rangle^{2}}\leq{\left\|{\bf{a}}\right\|^{2}}{\left\|{\bf{b}}\right\|^{2}}$
(42)

then,

$\begin{array}[]{l}N_{1}^{2}+N_{2}^{2}+...+N_{c}^{2}\geq\frac{{{{({N_{1}}+{N_{2}}+...+{N_{c}})}^{2}}}}{c}=\frac{{{N^{2}}}}{c}\end{array}$
(43)

If and only if ${N_{1}}={N_{2}}=...={N_{c}}$, the equation is satisfied.

###  4.6 Convergence Analysis of Algorithm 1

######  Lemma 1 (Proposition 6.2 of [36])

Suppose $F:\mathbb{R}^{n_{1}\times n_{2}}\rightarrow\mathbb{R}$ is represented
as $F(X)=f\circ\sigma(X)$, where $X\in\mathbb{R}^{n_{1}\times n_{2}}$ with SVD
$X=U\mathrm{diag}(\sigma_{1},\ldots,\sigma_{n})V^{\mathrm{T}}$,
$n=\min(n_{1},n_{2})$, and $f$ is differentiable. The gradient of $F(X)$ at
$X$ is

$\frac{\partial F(X)}{\partial X}=U\mathrm{diag}(\theta)V^{\mathrm{T}},$ (44)

where $\theta=\frac{\partial f(y)}{\partial y}|_{y=\sigma(X)}$.

###### Theorem 4

[Convergence Analysis of Algorithm 1] Let
$P_{k}=\\{\bm{{\mathcal{Y}}}_{k},\bm{{\mathcal{J}}}_{k},\bm{{\mathcal{Q}}}_{k}\\},\
1\leq k<\infty$ in (23) be a sequence generated by Algorithm 1, then

  1. 1.

$P_{k}$ is bounded;

  2. 2.

Any accumulation point of $P_{k}$ is a stationary KKT point of (23).

####  4.6.1 Proof of the 1st part

To minimize $\mathcal{J}$ at step $k+1$ in (34), the optimal
$\mathcal{J}_{k+1}$ needs to satisfy the first-order optimal condition
$\lambda\nabla_{\bm{\mathcal{J}}}\|\bm{\mathcal{J}}_{k+1}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}+\mu_{k}(\bm{\mathcal{J}}_{k+1}-\bm{{\mathcal{Y}}}_{k+1}-\dfrac{1}{\mu_{k}}\bm{{\mathcal{Q}}}_{k})=0.$

Recall that when $0<p<1$, in order to overcome the singularity of
$(|\eta|^{p})^{\prime}=p\eta/|\eta|^{2-p}$ near $\eta=0$, we consider for
$0<\epsilon\ll 1$ the approximation

$\partial|\eta|^{p}\approx\dfrac{p\eta}{\max\\{\epsilon^{2-p},|\eta|^{2-p}\\}}.$

Letting
$\overline{\bm{\mathcal{J}}}^{(i)}={\overline{\bm{\mathcal{U}}}}^{(i)}\mathrm{diag}\left(\sigma_{j}(\overline{\bm{\mathcal{J}}}^{(i)})\right){\overline{\bm{\mathcal{V}}}}^{(i)\mathrm{H}},$
then it follows from Defn. 1 and Lemma 1 that

$\displaystyle\frac{\partial\|{\overline{\bm{\mathcal{J}}}}^{(i)}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}}{\partial{\overline{\bm{\mathcal{J}}}}^{(i)}}={\overline{\bm{\mathcal{U}}}}^{(i)}\mathrm{diag}\left(\dfrac{p\sigma_{j}(\overline{\bm{\mathcal{J}}}^{(i)})}{\max\\{\epsilon^{2-p},|\sigma_{j}(\overline{\bm{\mathcal{J}}}^{(i)})|^{2-p}\\}}\right){\overline{\bm{\mathcal{V}}}}^{(i)\mathrm{H}}.$

And then one can obtain

$\displaystyle\dfrac{p\sigma_{j}(\overline{\bm{\mathcal{J}}}^{(i)})}{\max\\{\epsilon^{2-p},|\sigma_{j}(\overline{\bm{\mathcal{J}}}^{(i)})|^{2-p}\\}}\leq\dfrac{p}{\epsilon^{1-p}}$
$\displaystyle\Longrightarrow\left\|\frac{\partial\|{\overline{\bm{\mathcal{J}}}}^{(i)}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}}{\partial{\overline{\bm{\mathcal{J}}}}^{(i)}}\right\|^{2}_{F}\leq\sum^{N}_{i=1}\dfrac{p^{2}}{\epsilon^{2(1-p)}}.$

So
$\frac{\partial\|{\overline{\bm{\mathcal{J}}}}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}}{\partial{\overline{\bm{\mathcal{J}}}}}$
is bounded.

Let us denote $\widetilde{\mathbf{F}}_{V}=\frac{1}{\sqrt{V}}\mathbf{F}_{V}$,
$\mathbf{F}_{V}$ is the discrete Fourier transform matrix of size $V\times V$,
$\mathbf{F}^{\mathrm{H}}_{V}$ denotes its conjugate transpose. For
$\bm{\mathcal{J}}=\overline{\bm{\mathcal{J}}}\times_{3}\widetilde{\mathbf{F}}_{V}$
and using the chain rule in matrix calculus, one can obtain that

$\nabla_{\bm{\mathcal{J}}}\|\bm{\mathcal{J}}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}=\frac{\partial\|{\bm{\mathcal{J}}}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}}{\partial{\overline{\bm{\mathcal{J}}}}}\times_{3}\widetilde{\mathbf{F}}_{V}^{\mathrm{H}}$

is bounded.

And it follows that

$\displaystyle\bm{{\mathcal{Q}}}_{k+1}=\bm{{\mathcal{Q}}}_{k}+\mu_{k}(\bm{{\mathcal{Y}}}_{k+1}-\bm{\mathcal{J}}_{k+1})$
$\displaystyle\Longrightarrow\lambda\nabla_{\bm{\mathcal{J}}}\|\bm{\mathcal{J}}_{k+1}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}=\bm{{\mathcal{Q}}}_{k+1},$

$\\{\bm{{\mathcal{Q}}}_{k+1}\\}$ appears to be bounded.

Moreover, by using the updating rule

$\bm{{\mathcal{Q}}}_{k}=\bm{{\mathcal{Q}}}_{k-1}+\mu_{k-1}(\bm{\mathcal{Y}}_{k}-\bm{\mathcal{J}}_{k}),$

we can deduce

$\displaystyle\mathcal{L}_{\mu_{k}}\left(\bm{{\mathcal{Y}}}_{k+1},\bm{{\mathcal{J}}}_{k+1},\bm{{\mathcal{Q}}}_{k}\right)\leq\mathcal{L}_{\mu_{k}}\left(\bm{{\mathcal{Y}}}_{k},\bm{{\mathcal{J}}}_{k},\bm{{\mathcal{Q}}}_{k}\right)$
(45)
$\displaystyle=\mathcal{L}_{\mu_{k-1}}\left(\bm{{\mathcal{Y}}}_{k},\bm{{\mathcal{J}}}_{k};\bm{{\mathcal{Q}}}_{k-1}\right)$
$\displaystyle+\frac{\mu_{k}+\mu_{k-1}}{2\mu^{2}_{k-1}}\|\bm{{\mathcal{Q}}}_{k}-\bm{{\mathcal{Q}}}_{k-1}\|_{F}^{2}+\frac{\|\bm{{\mathcal{Q}}}_{k}\|_{F}^{2}}{2\mu_{k}}-\frac{\|\bm{{\mathcal{Q}}}_{k-1}\|_{F}^{2}}{2\mu_{k-1}}.$

Thus, summing two sides of (45) from $k=1$ to $n$, we have

$\displaystyle\mathcal{L}_{\mu_{n}}\left(\bm{{\mathcal{Y}}}_{n+1},\bm{{\mathcal{J}}}_{n+1},\bm{{\mathcal{Q}}}_{n}\right)\leq\mathcal{L}_{\mu_{0}}\left(\bm{{\mathcal{Y}}}_{1},\bm{{\mathcal{J}}}_{1},\bm{{\mathcal{Q}}}_{0}\right)$
(46) $\displaystyle+$
$\displaystyle\frac{\|\bm{{\mathcal{Q}}}_{n}\|_{F}^{2}}{2\mu_{n}}-\frac{\|\bm{{\mathcal{Q}}}_{0}\|_{F}^{2}}{2\mu_{0}}+\sum_{k=1}^{n}\left(\frac{\mu_{k}+\mu_{k-1}}{2\mu^{2}_{k-1}}\|\bm{{\mathcal{Q}}}_{k}-\bm{{\mathcal{Q}}}_{k-1}\|_{F}^{2}\right).$

Observe that

$\sum_{k=1}^{\infty}\frac{\mu_{k}+\mu_{k-1}}{2\mu_{k-1}^{2}}<\infty,$

we have the right-hand side of (46) is finite and thus
$\mathcal{L}_{\mu_{n}}\left(\bm{{\mathcal{Y}}}_{n+1},\bm{{\mathcal{J}}}_{n+1},\bm{{\mathcal{Q}}}_{n}\right)$
is bounded. Notice

$\displaystyle\mathcal{L}_{\kappa_{n}}\left(\bm{{\mathcal{Y}}}_{n+1},\bm{{\mathcal{J}}}_{n+1},\bm{{\mathcal{Q}}}_{n}\right)=\sum_{v=1}^{V}\mathrm{tr}(\textbf{Y}_{n+1}^{(v)}\textbf{D}^{(v)}\textbf{Y}_{n+1}^{(v)\mathrm{T}})$
$\displaystyle+\lambda\|\bm{\mathcal{J}}_{n+1}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}+\frac{\mu_{n}}{2}\|\bm{\mathcal{Y}}_{n+1}-\bm{\mathcal{J}}_{n+1}+\frac{\bm{{\mathcal{Q}}}_{n}}{\mu_{n}}\|_{F}^{2},$
(47)

and each term of (4.6.1) is nonnegative, following from the boundedness of
$\mathcal{L}_{\mu_{n}}\left(\bm{{\mathcal{Y}}}_{n+1},\bm{{\mathcal{J}}}_{n+1},\bm{{\mathcal{Q}}}_{n}\right)$,
we can deduce each term of (4.6.1) is bounded. And
$\|\bm{{\mathcal{J}}}_{n+1}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}$
being bounded implies that all singular values of $\bm{{\mathcal{J}}}_{n+1}$
are bounded and hence $\|\bm{{\mathcal{J}}}_{n+1}\|^{2}_{F}$ (the sum of
squares of singular values) is bounded. Therefore, the sequence
$\\{\bm{{\mathcal{J}}}_{k}\\}$ is bounded. Considering the positive semi-
definiteness of matrix $\textbf{D}^{(v)}$, we can deduce
$\textbf{Y}^{(v)}_{n+1}$ is bounded and thus the sequence
$\\{\bm{{\mathcal{Y}}}_{k}\\}$ is bounded.

####  4.6.2 Proof of the 2nd part

From Weierstrass-Bolzano theorem, there exists at least one accumulation point
of the sequence $P_{k}$. We denote one of the points
$P^{*}=\\{\bm{{\mathcal{Y}}}^{*},\bm{{\mathcal{J}}}^{*},\bm{{\mathcal{Q}}}^{*}\\}$.
Without loss of generality, we assume $\\{\mathcal{P}_{k}\\}^{+\infty}_{k=1}$
converge to $P^{*}.$

Note that from the updating rule for $\bm{{\mathcal{Q}}}$, we have

$\bm{{\mathcal{Q}}}_{k+1}=\bm{{\mathcal{Q}}}_{k}+\mu_{k}(\bm{{\mathcal{Y}}}_{k}-\bm{{\mathcal{J}}}_{k})\Longrightarrow\bm{{\mathcal{J}}}^{*}=\bm{{\mathcal{Y}}}^{*}.$

In the $\bm{\mathcal{J}}$-subproblem, we have

$\lambda\nabla_{\bm{\mathcal{J}}}\|\bm{\mathcal{J}}_{k+1}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}=\bm{{\mathcal{Q}}}_{k+1}\Longrightarrow\bm{{\mathcal{Q}}}^{*}=\lambda\nabla_{\bm{\mathcal{J}}}\|\bm{\mathcal{J}}^{*}\|^{p}_{{\scriptsize{{\emph{\tiny{\textbf{Sp}}}}⃝}}}.$

In (25), we have

$\alpha_{\emph{{v}}}^{\emph{{r}}}\partial\mathrm{tr}(\textbf{Y}^{(v)}_{k+1}\textbf{D}^{(v)}\textbf{Y}^{(v)T}_{k+1})-\mu_{k}(\textbf{J}_{k+1}^{(v)}-\textbf{Y}_{k+1}^{(v)}+\textbf{Q}_{k}^{(v)}/\mu_{k})=0.$

Now by the updating rule
${\bm{{\mathcal{Q}}}}{\rm{=}}{\bm{{\mathcal{Q}}}}{\rm{+}}\mu{\rm{(}}{\bm{{\mathcal{Y}}}}{\rm{-}}{\bm{{\mathcal{J}}}}{\rm{)}}$,
we can see

$\displaystyle\textbf{Q}_{k+1}^{(v)}=2\alpha_{\emph{{v}}}^{\emph{{r}}}\textbf{Y}^{(v)}_{k+1}\textbf{D}^{(v)}\Longrightarrow\textbf{Q}^{(v)*}=2\alpha_{\emph{{v}}}^{\emph{{r}}}\textbf{Y}^{(v)*}\textbf{D}^{(v)},$

Therefore, one can see that the sequences
$\bm{{\mathcal{Y}}}^{*},\bm{{\mathcal{J}}}^{*},\bm{{\mathcal{Q}}}^{*}$ satisfy
the KKT conditions of the Lagrange function (23).

##  5 Experiments

We evaluate our model on two toy datasets and six benchmark datasets through
some experiments implemented on a Windows 10 desktop computer with a 2.40GHz
Intel Xeon Gold 6240R CPU, 64 GB RAM, and MATLAB R2021a (64-bit).

###  5.1 Experiments on A Toy Dataset

Experiments in this section are conducted to verify the effectiveness of our
method for non-linearly separable clusters. First, we construct two toy
datasets called two-moon and three-ring, respectively, which contain 2 views
each dataset. The two-moon dataset contains 200 samples belonging to 2 non-
linearly separable clusters. Each sample is represented by a 2D coordinate,
and the second view is obtained by performing FFT on the first view. The
three-ring dataset contains 200 samples belonging to 3 non-linearly separable
clusters, with each cluster represented by a 2D coordinate. The second view is
obtained by performing FFT on the first view. Figure 3 shows the clustering
results of our method with the Euclidean distance and the distance constructed
by our proposed function (39), respectively. The visualization indicates that
the performance of our method is significantly improved when using our
proposed function (39) to calculate the distance between data points, compared
with the Euclidean distance. This indicates that our method is capable of
separating non-linearly separable clusters well in the input space.

(a) Euclidean distance on three-ring (b) Our function on three-ring (c)
Euclidean distance on two-moon (d) Our function on two-moon

Figure 3: Clustering performance of our proposed method with different
distance matrices on two toy datasets.

###  5.2 Experimental on Benchmark Datasets

####  5.2.1 Datasets:

We do experiments to evaluate the effectiveness of our method on the following
widely used six multi-view benchmark datasets: MSRC [37],
ORL111http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html, HW
[38], and Mnist4 [39] are common real benchmark datasets, while Reuters [40]
and NUS-WIDE [41] are two large-scale datasets. Table I provides detailed
information for these datasets, where the numbers in parentheses indicate
feature dimensions.

TABLE I: The information of datasets. Datasets | MSRC | ORL | HW | Mnist4 | Reuters | NUS-WIDE
---|---|---|---|---|---|---
Data Type | images | images | images | images | documents | images
Size | 210 | 400 | 2000 | 4000 | 18758 | 30000
Classes | 7 | 40 | 10 | 4 | 6 | 31
View#1 | CM(24) | Intensity(4096) | FOU(76) | ISO(30) | English(21531) | CH(64)
View#2 | HOG(576) | LBP(3304) | FAC(216) | LDA(9) | France(24892) | CM(225)
View#3 | GIST(512) | Gabor(6750) | ZER(47) | DNPE(30) | German(34251) | CORR(144)
View#4 | LBP(256) | - | MOR(6) | - | Italian(15506) | EDH(73)
View#5 | CENT(254) | - | - | - | Spanish(11547) | WT(128)

####  5.2.2 Competing Algorithms:

The following representative methods are adopted to evaluate the performance
of our model:

  * •

SC [11], Classical single view spectral clustering;

  * •

RMKMC [19], Multi-view _k_ -means clustering on big data;

  * •

FRMVK [42], Feature-reduction multi-view _k_ -means;

  * •

RDEKM [26], Re-weighted discriminatively embedded _k_ -means for multi-view
clustering;

  * •

MVASM [20], Multi-view _k_ -means clustering with adaptive sparse memberships
and weight allocation;

  * •

WMCFS [43], Weighted multi-view clustering with feature selection;

  * •

Co-Reg [13], Co-regularized multi-view SC;

  * •

CSMSC [5], Consistent and specific multi-view subspace clustering;

  * •

MVGL [16], Graph learning for multi-view clustering;

  * •

LTCPSC [17], Low-rank tensor constrained co-regularized multi-view spectral
clustering;

  * •

ETLMSC [15], Essential tensor learning for multi-view spectral clustering.

####  5.2.3 Metrics:

The widely used 3 metrics are applied to evaluate the performance of our
method, (1) Accuracy (ACC) [44]; (2) Normalized Mutual Information (NMI) [45];
(3) Purity [46]. These indicators measure the consistency between the true
labels and the predicted labels from different perspectives, and a higher
value of indicator means better clustering performance.

####  5.2.4 Parameters:

There are five parameters in our model, $\lambda$, $r$, $p$, and $\Omega$. In
the experiments, we set $\lambda\in$[0.1, 1, 5, 10, 50, 100], $p$ from 0.1 to
1 with the interval 0.1, $r$ from 3 to 10 with the interval 1, and
$\Omega\in$[0.0001, 0.0005, 0.001, 0.003, 0.005, 0.01, 0.03, 0.05, 0.1]. For
the anchor ratio $\theta$, we set $\theta=0.5$ on the MSRC, ORL, Mnist4, and
HW databases, $\theta=0.1$ on the Reuters database, and $\theta=0.02$ on the
NUS-WIDE database. The small anchor ratio of Reuters and NUS-WIDE are set to
reduce memory consumption. Because $\Omega$ is only relevant to the adjacency
matrix, we tune $\Omega$ while keeping other parameters fixed, and tune other
parameters with fixed $\Omega$.

####  5.2.5 Results

We do experiments on six datasets and record the metrics comparison in Tables.
II and III. SC (best) records the best results among all views. The following
can be observed:

First, most multi-view clustering methods achieve better results than single-
view SC. It is because the information embedded in different views is
complementary and the multi-view methods use this information well. Second,
compared with the multi-view $k$-means RMKMC, FRMVK, RDEKM, and MVASM, our
method achieves better performance. What’s more, the results of our method are
better than the state-of-the-art multi-view spectral clustering algorithms.
This is because our method is suitable for both linearly and non-linearly
separate clusters in the input space, takes full advantage of the
complementary information among multi-views, and the considers of the
difference among different views. Finally, on two large-scale datasets Reuters
and NUS-WIDE, some methods such as RDEKM and CSMSC cannot work on computers
with small memory due to the out-of-memory. However, in this case, our method
can work and obtain great results by setting a low anchor rate, as shown in
Table. III, especially in NUS-WIDE, our method significantly and consistently
outperforms all competitors, which demonstrates the effectiveness on large-
scale datasets.

TABLE II: The results on MSRC, HW, ORL, and Mnist4 datasets. Datasets | MSRC | HW | ORL | Mnist4
---|---|---|---|---
Methods | ACC | NMI | Purity | ACC | NMI | Purity | ACC | NMI | Purity | ACC | NMI | Purity
SC (best) | 0.663 | 0.534 | 0.675 | 0.639 | 0.616 | 0.653 | 0.727 | 0.868 | 0.762 | 0.713 | 0.558 | 0.713
RMKMC | 0.700 | 0.604 | 0.700 | 0.804 | 0.785 | 0.839 | 0.543 | 0.749 | 0.620 | 0.895 | 0.739 | 0.895
FRMVK | 0.391 | 0.292 | 0.391 | 0.790 | 0.777 | 0.806 | 0.368 | 0.589 | 0.383 | 0.882 | 0.715 | 0.882
RDEKM | 0.900 | 0.808 | 0.900 | 0.764 | 0.755 | 0.793 | 0.783 | 0.578 | 0.765 | 0.715 | 0.881 | 0.714
MVASM | 0.604 | 0.619 | 0.644 | 0.726 | 0.842 | 0.644 | 0.393 | 0.575 | 0.539 | 0.892 | 0.734 | 0.892
WMCFS | 0.566 | 0.600 | 0.619 | 0.679 | 0.590 | 0.641 | 0.630 | 0.787 | 0.690 | 0.892 | 0.729 | 0.892
CSMSC | 0.758 | 0.735 | 0.793 | 0.806 | 0.793 | 0.867 | 0.857 | 0.935 | 0.882 | 0.643 | 0.645 | 0.832
MVGL | 0.690 | 0.663 | 0.733 | 0.811 | 0.809 | 0.831 | 0.765 | 0.871 | 0.815 | 0.912 | 0.785 | 0.910
Co-Reg | 0.635 | 0.578 | 0.659 | 0.784 | 0.758 | 0.795 | 0.668 | 0.824 | 0.713 | 0.785 | 0.602 | 0.786
ETLMSC | 0.962 | 0.937 | 0.962 | 0.938 | 0.893 | 0.938 | 0.958 | 0.991 | 0.970 | 0.934 | 0.847 | 0.934
LTCPS | 0.981 | 0.957 | 0.981 | 0.920 | 0.869 | 0.920 | 0.981 | 0.994 | 0.983 | 0.929 | 0.813 | 0.929
Ours | 1.000 | 1.000 | 1.000 | 0.994 | 0.986 | 0.994 | 1.000 | 1.000 | 1.000 | 0.992 | 0.969 | 0.992
TABLE III: The results on Reuters and NUS-WIDE datasets.

Datasets | Reuters | NUS-WIDE
---|---|---
Methods | ACC | NMI | Purity | ACC | NMI | Purity
SC (best) | 0.269 | 0.002 | 0.272 | 0.131 | 0.019 | 0.140
RMKMC | 0.422 | 0.259 | 0.531 | 0.125 | 0.123 | 0.221
FRMVK | 0.272 | 0.000 | 0.272 | 0.124 | 0.095 | 0.200
RDEKM | OM | OM | OM | OM | OM | OM
MVASM | 0.458 | 0.136 | 0.814 | 0.141 | 0.096 | 0.254
WMCFS | 0.427 | 0.278 | 0.530 | OM | OM | OM
CSMSC | OM | OM | OM | OM | OM | OM
MVGL | 0.271 | 0.021 | 0.281 | OM | OM | OM
Co-Reg | 0.563 | 0.326 | 0.552 | 0.119 | 0.114 | 0.214
ETLMSC | OM | OM | OM | OM | OM | OM
LTCPS | OM | OM | OM | OM | OM | OM
Ours | 0.682 | 0.638 | 0.824 | 0.510 | 0.708 | 0.673

(a) MSRC

(b) ORL

(c) HW

(d) Mnist4

Figure 4: Clustering performance vs. $r$ on four datasets.

(a) MSRC

(b) ORL

(c) HW

(d) Mnist4

Figure 5: Clustering performance vs. $p$ on four datasets.

(a) MSRC (b) ORL

Figure 6: The values of error with iterations on MSRC and ORL datasets

####  5.2.6 Effect of parameter $r$

In (33), if $r\rightarrow\infty$, the weight assigned to each view will be
equal, and if $r\rightarrow 1$, the weight of the view with the minimum value
of $\mathbf{M}_{v}$ will be 1, and others will be 0. The strategy of using $r$
not only avoids the trivial solution to the weight distribution of the
different views but also controls the whole weights by exploiting one
parameter.

Fig. 4 reveals the performances of our method on MSRC, ORL, HW, and Mnist4
datasets by showing three metrics (ACC, NMI, Purity) at different $r$, and we
set $r$ from $3$ to $10$. It can be observed that when $r$ is in the range of
$3$ to $9$, the clustering performance changes little on the four datasets,
and the results on MSRC and HW datasets decrease when $r$ is equal to 10. This
confirms that parameter $r$ plays an important role in our model.

####  5.2.7 Effect of parameter $p$

Taking MSRC, ORL, HW, and Mnist4 datasets as examples, we analyze the effect
of $p$ on clustering. Specifically, we change $p$ from 0.1 to 1 with the
interval of 0.1, then we report the ACC, NMI, and Purity in Fig. 5. It is
observed that the results under different $p$ are distinguished on HW and
Mnist4 datasets, This demonstrates that the addition of $p$ has an effect on
improving the clustering performance.

(a) NUS-WIDE (b) Reuters

Figure 7: Running time vs. number of samples for the same number of iterations
on NUS-WIDE and Reuters Datasets

####  5.2.8 Complexity Verification

On the NUS-WIDE and Reuters datasets, we change the number of samples while
keeping the number of iterations constant and recorded the time taken to run
the MATLAB code, as shown in Figure 7. It can be observed that the running
time is approximately proportional to the number of samples, providing
evidence that the computational complexity of our model scales linearly with
N.

####  5.2.9 Convergence

The convergence of our method on the MSRC and ORL datasets are shown in this
section. We calculate the error of $\mathbf{J}^{(v)}$ and $\mathbf{Y}^{(v)}$
from Algorithm 1 at each number of iterations by the Frobenius norm, i.e.
$Error=\sum_{i=1}^{V}{\|\mathbf{J}^{(v)}-\mathbf{Y}^{(v)}\|_{F}^{2}}$, and
record the results in Figure 6. It is observed that the value of the error
decreases as the number of iterations increases and approaches 0 in less than
150 iterations. This further indicates that our proposed algorithm can
converge in practical applications.

##  6 Conclusion

In this paper, we rethink _k_ -means from manifold learning perspective and
propose a novel distance-based discrete multi-view clustering which directly
achieves clusters of data without centroid estimation. This builds a bridge
between manifold learning and clustering. To improve clustering performance,
we employ anchor graph and Butterworth filter to construct distance matrix. It
helps increase the distance between similar and dissimilar samples, while
reducing the distance between similar samples. To well exploit the
complementary information embedded in different views, we leverage the tensor
Schatten _p_ -norm regularization on the 3rd-order tensor which consists of
indicator matrices of different views. Extensive experimental results indicate
the superiority of our proposed method.

## References

  * [1] J. A. Hartigan and M. A. Wong, “Algorithm as 136: A k-means clustering algorithm,” _Journal of the royal statistical society. series c (applied statistics)_ , vol. 28, no. 1, pp. 100–108, 1979.
  * [2] S. Pei, F. Nie, R. Wang, and X. Li, “Efficient clustering based on A unified view of $k$-means and ratio-cut,” in _NeurIPS_ , 2020\.
  * [3] I. S. Dhillon, Y. G. Guan, and B. Kulis, “kernel k-means, spectral clustering and normalized cuts,” in _ACM SIGKDD international conference on knowledge discovery and data mining_ , 2004.
  * [4] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, “Robust recovery of subspace structures by low-rank representation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 1, pp. 171–184, 2013.
  * [5] S. Luo, C. Zhang, W. Zhang, and X. Cao, “Consistent and specific multi-view subspace clustering,” in _AAAI_ , 2018, pp. 3730–3737.
  * [6] Y. Xie, D. Tao, W. Zhang, Y. Liu, L. Zhang, and Y. Qu, “On unifying multi-view self-representations for clustering by tensor multi-rank minimization,” _Int. J. Comput. Vis._ , vol. 126, no. 11, pp. 1157–1179, 2018.
  * [7] C. Zhang, H. Fu, J. Wang, W. Li, X. Cao, and Q. Hu, “Tensorized multi-view subspace representation learning,” _Int. J. Comput. Vis._ , vol. 128, no. 8, pp. 2344–2361, 2020.
  * [8] Q. Gao, P. Zhang, W. Xia, D. Xie, X. Gao, and D. Tao, “Enhanced tensor RPCA and its application,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 43, no. 6, pp. 2133–2140, 2021.
  * [9] W. Xia, X. Zhang, Q. Gao, X. Shu, J. Han, and X. Gao, “Multi-view subspace clustering by an enhanced tensor nuclear norm,” _IEEE Trans. Cybern._ , vol. 52, no. 9, pp. 8962–8975, 2022.
  * [10] W. Xia, Q. Gao, Q. Wang, and X. Gao, “Tensor completion-based incomplete multiview clustering,” _IEEE Trans. Cybern._ , vol. 52, no. 12, pp. 13 635–13 644, 2022.
  * [11] A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” in _NIPS_ , 2001, pp. 849–856.
  * [12] L. Bai, J. Liang, and Y. Zhao, “Self-constrained spectral clustering,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 45, no. 4, pp. 5126–5138, 2023.
  * [13] A. Kumar, P. Rai, and H. D. III, “Co-regularized multi-view spectral clustering,” in _NeurIPS_ , 2011, pp. 1413–1421.
  * [14] W. Xia, Q. Gao, Q. Wang, X. Gao, C. Ding, and D. Tao, “Tensorized bipartite graph learning for multi-view clustering,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 45, no. 4, pp. 5187–5202, 2023.
  * [15] J. Wu, Z. Lin, and H. Zha, “Essential tensor learning for multi-view spectral clustering,” _IEEE Trans. Image Process._ , vol. 28, no. 12, pp. 5910–5922, 2019.
  * [16] K. Zhan, C. Zhang, J. Guan, and J. Wang, “Graph learning for multiview clustering,” _IEEE Trans. Cybern._ , vol. 48, no. 10, pp. 2887–2895, 2018\.
  * [17] H. Xu, X. Zhang, W. Xia, Q. Gao, and X. Gao, “Low-rank tensor constrained co-regularized multi-view spectral clustering,” _Neural Networks_ , vol. 132, pp. 245–252, 2020.
  * [18] S. Bickel and T. Scheffer, “Multi-view clustering,” in _International Conference on Data Mining_ , 2004, pp. 19–26.
  * [19] C. Xiao, F. Nie, and H. Huang, “Multi-view k-means clustering on big data,” in _Proceedings of the 23rd International Joint Conference on Artificial Intelligence_ , 2013, pp. 2598–2604.
  * [20] J. Han, J. Xu, F. Nie, and X. Li, “Multi-view k-means clustering with adaptive sparse memberships and weight allocation,” _IEEE Trans. Knowl. Data Eng._ , vol. 34, no. 2, pp. 816–827, 2022.
  * [21] K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft, “When is nearest neighbor meaningful,” in _Proceedings of the 7th International Conference on Database Theory_ , 1999, pp. 217–235.
  * [22] R. O. Duda, P. E. Hart, and D. G. Stork, “Pattern classification,” _Wiley,second_ , 2002.
  * [23] C. H. Q. Ding and T. Li, “Adaptive dimension reduction using discriminant analysis and _K_ -means clustering,” in _Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007_ , vol. 227. ACM, 2007, pp. 521–528.
  * [24] C. H. Q. Ding, X. He, H. Zha, and H. D. Simon, “Adaptive dimension reduction for clustering high dimensional data,” in _Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002), 9-12 December 2002, Maebashi City, Japan_. IEEE Computer Society, 2002, pp. 147–154.
  * [25] J. Xu, J. Han, and F. Nie, “Discriminatively embedded k-means for multi-view clustering,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 5356–5364.
  * [26] J. Xu, J. Han, F. Nie, and X. Li, “Re-weighted discriminatively embedded k-means for multi-view clustering,” _IEEE Trans. Image Process._ , vol. 26, no. 6, pp. 3016–3027, 2017.
  * [27] B. Schölkopf, A. Smola, and K. Müller, “Nonlinear component analysis as a kernel eigenvalue problem,” _Neural Computation_ , vol. 10, no. 5, pp. 1299–1319, 1998.
  * [28] S. Yu, L. Tranchevent, X. Liu, W. Glanzel, J. A. K. Suykens, B. De Moor, and Y. Moreau, “Optimized data fusion for kernel k-means clustering,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 34, no. 5, pp. 1031–1039, 2012.
  * [29] X. Liu, X. Zhu, M. Li, L. Wang, E. Zhu, T. Liu, M. Kloft, D. Shen, J. Yin, and W. Gao, “Multiple kernel k-means with incomplete kernels,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , p. 1191–1204, 2020\.
  * [30] X. Liu, Y. Dou, J. Yin, L. Wang, and E. Zhu, “Multiple kernel k-means clustering with matrix-induced regularization,” in _International Conference on Artificial Intelligence_ , 2016, pp. 1888–1894.
  * [31] F. Nie, C. L. Wang, and X. Li, “K-multiple-means: A multiple-means clustering method with specified k clusters,” in _the 25th ACM SIGKDD International Conference_ , 2019, pp. 959–967.
  * [32] L. W. Hagen and A. B. Kahng, “New spectral methods for ratio cut partitioning and clustering,” _IEEE Trans. Comput. Aided Des. Integr. Circuits Syst._ , vol. 11, no. 9, pp. 1074–1085, 1992.
  * [33] F. Nie, H. Wang, X. Cai, H. Huang, and C. Ding, “Robust matrix completion via joint schatten p-norm and lp-norm minimization,” in _ICDM_ , 2012, pp. 566–574.
  * [34] Z. Lin, R. Liu, and Z. Su, “Linearized alternating direction method with adaptive penalty for low-rank representation,” in _NeurIPS_ , 2011, pp. 612–620.
  * [35] W. Liu, J. He, and S. Chang, “Large graph construction for scalable semi-supervised learning,” in _ICML_ , 2010, pp. 679–686.
  * [36] A. S. Lewis and H. S. Sendov, “Nonsmooth analysis of singular values. part i: Theory,” _Set-Valued Analysis_ , vol. 13, no. 3, pp. 213–241, 2005.
  * [37] J. M. Winn and N. Jojic, “LOCUS: learning object classes with unsupervised segmentation,” in _ICCV_ , 2005, pp. 756–763.
  * [38] D. Dua and C. Graff, “UCI machine learning repository,” 2017.
  * [39] L. Deng, “The MNIST database of handwritten digit images for machine learning research,” _IEEE Signal Process. Mag._ , vol. 29, no. 6, pp. 141–142, 2012.
  * [40] C. Apté, F. Damerau, and S. M. Weiss, “Automated learning of decision rules for text categorization,” _ACM Trans. Inf. Syst._ , vol. 12, no. 3, pp. 233–251, 1994.
  * [41] T. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y. Zheng, “NUS-WIDE: a real-world web image database from national university of singapore,” in _CIVR_ , 2009.
  * [42] M. Yang and K. P. Sinaga, “A feature-reduction multi-view k-means clustering algorithm,” _IEEE Access_ , vol. 7, pp. 114 472–114 486, 2019.
  * [43] Y. Xu, C. Wang, and J. Lai, “Weighted multi-view clustering with feature selection,” _Pattern Recognit._ , vol. 53, pp. 25–35, 2016.
  * [44] D. Cai, X. He, and J. Han, “Document clustering using locality preserving indexing,” _IEEE Trans. Knowl. Data Eng._ , vol. 17, no. 12, pp. 1624–1637, 2005.
  * [45] P. A. Estévez, M. Tesmer, C. A. Perez, and J. M. Zurada, “Normalized mutual information feature selection,” _IEEE Trans. Neural Networks_ , vol. 20, no. 2, pp. 189–201, 2009.
  * [46] R. Varshavsky, M. Linial, and D. Horn, “Compact: A comparative package for clustering assessment,” in _ISPA Workshops_ , vol. 3759, 2005, pp. 159–167.