Question

What is the time complexity of spectral clustering and why is it so?

Answer 1

Spectral Clustering is a clustering method that uses the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering the data in fewer dimensions.

It is a flexible class of clustering algorithms that can produce high-quality clusterings on small data sets, but which has limited applicability to largescale problems due to its computational complexity of O