Spectral clustering: Difference between revisions

Content deleted Content added
Costs: extended to cover the case of dense adjacency matrices
Line 69:
 
===Computing eigenvectors===
The cost of computing the <math>n</math>-by-<math>k</math> (with <math>k<<n</math>) matrix of selected eigenvectors of the graph Laplacian is normally proportional to the cost of multiplication of the <math>n</math>-by-<math>n</math> graph Laplacian matrix by a vector, which varies greatly whether the graph Laplacian matrix is dense or sparse. For the dense case the cost thus is <math>O(n^2)</math>. The very commonly cited in the literature cost <math>O(n^3)</math> comes from choosing <math>k=n</math> and is clearly misleading, since, e.g., in a hierarchical spectral clustering <math>k=1</math> as determined by the [[Fiedler vector]].
 
==Software==