  Spectral clustering is one of the most popular unsupervised machine learning
methods. Constructing similarity matrix is crucial to this type of method. In
most existing works, the similarity matrix is computed once for all or is
updated alternatively. However, the former is difficult to reflect
comprehensive relationships among data points, and the latter is time-consuming
and is even infeasible for large-scale problems. In this work, we propose a
restarted clustering framework with self-guiding and block diagonal
representation. An advantage of the strategy is that some useful clustering
information obtained from previous cycles could be preserved as much as
possible. To the best of our knowledge, this is the first work that applies
restarting strategy to spectral clustering. The key difference is that we
reclassify the samples in each cycle of our method, while they are classified
only once in existing methods. To further release the overhead, we introduce a
block diagonal representation with Nystr\"{o}m approximation for constructing
the similarity matrix. Theoretical results are established to show the
rationality of inexact computations in spectral clustering. Comprehensive
experiments are performed on some benchmark databases, which show the
superiority of our proposed algorithms over many state-of-the-art algorithms
for large-scale problems. Specifically, our framework has a potential boost for
clustering algorithms and works well even using an initial guess chosen
randomly.
