Content deleted Content added
→Relationship with k-means: agree with https://en.wikipedia.org/wiki/Talk:Spectral_clustering and delete incomprehensible details |
→Constructing graph Laplacian: move the info from another section to be deleted |
||
Line 72:
Moreover, a normalized Laplacian has exactly the same eigenvectors as the normalized adjacency matrix, but with the order of the eigenvalues reversed. Thus, instead of computing the eigenvectors corresponding to the smallest eigenvalues of the normalized Laplacian, one can equivalently compute the eigenvectors corresponding to the largest eigenvalues of the normalized adjacency matrix, without even talking about the Laplacian matrix.
Naive constructions of the graph [[adjacency matrix]], e.g., using the RBF kernel, make it dense, thus requiring <math>n^2</math> memory and <math>n^2</math> AO to determine each of the <math>n^2</math> entries of the matrix. Nystrom method<ref>{{Cite journal|last=Fowlkes|first=C|date=2004|title=Spectral grouping using the Nystrom method.|url=https://escholarship.org/uc/item/29z29233|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=26|issue=2|pages=214–25|doi=10.1109/TPAMI.2004.1262185|pmid=15376896|s2cid=2384316}}</ref> can be used to approximate the similarity matrix, but the approximate matrix is not elementwise positive<ref>{{Cite journal|last=S. Wang, A. Gittens, and M. W. Mahoney|year=2019|title=Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds|journal=Journal of Machine Learning Research|volume=20|pages=1–49|arxiv=1706.02803}}</ref>, i.e. cannot be interpreted as a distance-based similarity.
Algorithms to construct the graph adjacency matrix as a [[sparse matrix]] are typically based on a [[nearest neighbor search]], which estimate or sample a neighborhood of a given data point for nearest neighbors, and compute non-zero entries of the adjacency matrix by comparing only pairs of the neighbors. The number of the selected nearest neighbors thus determines the number of non-zero entries, and is often fixed so that the memory footprint of the <math>n</math>-by-<math>n</math> graph adjacency matrix is only <math>O(n)</math>, only <math>O(n)</math> sequential arithmetic operations are needed to compute the <math>O(n)</math> non-zero entries, and the calculations can be trivially run in parallel.
| |||