Accelerated sparse Kernel Spectral Clustering for large scale data
  clustering problems
Mihaly Novak Rocco Langone Carlos Alzate Johan Suykens
An improved version of the sparse multiway kernel spectral clustering (KSC)
is presented in this brief. The original algorithm is derived from weighted
kernel principal component (KPCA) analysis formulated within the primal-dual
least-squares support vector machine (LS-SVM) framework. Sparsity is achieved
then by the combination of the incomplete Cholesky decomposition (ICD) based
low rank approximation of the kernel matrix with the so called reduced set
method. The original ICD based sparse KSC algorithm was reported to be
computationally far too demanding, especially when applied on large scale data
clustering problems that actually it was designed for, which has prevented to
gain more than simply theoretical relevance so far. This is altered by the
modifications reported in this brief that drastically improve the computational
characteristics. Solving the alternative, symmetrized version of the
computationally most demanding core eigenvalue problem eliminates the necessity
of forming and SVD of large matrices during the model construction. This
results in solving clustering problems now within seconds that were reported to
require hours without altering the results. Furthermore, sparsity is also
improved significantly, leading to more compact model representation,
increasing further not only the computational efficiency but also the
descriptive power. These transform the original, only theoretically relevant
ICD based sparse KSC algorithm applicable for large scale practical clustering
problems. Theoretical results and improvements are demonstrated by
computational experiments on carefully selected synthetic data as well as on
real life problems such as image segmentation.