Abstract: Classical spectral clustering algorithms consist of two separate stages.One is spectral embedding,computing eigenvalue decomposition of a Laplacian matrix to obtain a relaxed continuous indication matrix.The other is post processing,applying k-means or spectral rotation to round the real matrix into the binary cluster indicator matrix.Such a separate scheme is not guaranteed to achieve jointly optimal result because of the loss of useful information.Meanwhile,there are difficulties of low clustering precision,high storage cost for the similarity matrix and high computational complexity for the eigenvalue decomposition of Laplacian matrix.The existing joint model adopts an orthonormal real matrix to approximate the orthogonal but nonorthonormal cluster indicator matrix.The error of approximating a nonorthonormal matrix is inevitably large.To overcome the drawback,we propose replacing the nonorthonormal cluster indicator matrix with an improved orthonormal cluster indicator matrix.The proposed method is capable of obtaining better performance because it is easy to minimize the difference between two orthonormal matrices.Furthermore,a novel landmark-based joint spectral embedding and spectral rotation algorithm is proposed based on the sparse representation by landmark points,which greatly solves the effective computation of spectral clustering for large scale dataset.Experimental results on benchmark datasets demonstrate the effectiveness of the proposed method.

Key words: Joint spectral clustering, Landmark representation, Spectral clustering, Spectral embedding, Spectral rotation