This is the linear-algebra view of spectral clustering — instead of watching a spatial point cloud, you watch the actual matrices the algorithm operates on.
1. Similarity: W_ij = exp(-‖xi - xj‖² / 2σ²) kept only for each
point's k nearest neighbours (sparse graph)
2. Degree: D_ii = Σ_j W_ij
3. Laplacian: L = D - W (unnormalized graph Laplacian)
4. Eigen: L v_m = λ_m v_m , 0 = λ₁ ≤ λ₂ ≤ … ≤ λ_K
5. Embedding: each point i → (v₂(i), v₃(i), …, v_K(i)) ∈ R^(K-1)
6. Cluster: run k-means on that low-dimensional spectral embedding
Panel 1 is L itself, drawn as an N×N heatmap (bright cell = edge weight, dark = no edge). With "Reorder by cluster" on, rows/columns are permuted by the spectral assignment — a correct clustering makes the sparsity pattern collapse into visible block-diagonal chunks, one block per cluster. Panel 2 is the sorted eigenvalue spectrum λ₁…λ_N — the "eigengap" between λ_K and λ_(K+1) is the classic heuristic for how many clusters actually exist in the data: a wide gap after λ_K means K clusters are well separated. Panel 3 is the actual spectral embedding (v₂ plotted against v₃, or against point index when K=2) that k-means clusters — notice it can be nearly linearly separable even when the original (x,y) layout (panel 4, shown for reference) is not.
All four panels are recomputed from scratch by the same from-scratch cyclic Jacobi eigenvalue solver and from-scratch k-means used elsewhere on this site — no external linear-algebra library.
- Shape — moons and rings are non-convex, so plain k-means on raw (x,y) cuts through them; the spectral embedding untangles them first.
- σ (bandwidth) — too large blurs the whole graph into one block; too small fragments it into many tiny ones.
- k-NN — lets the graph "unroll" curved clusters by only connecting close neighbours, instead of every pair of points.
- Eigengap — the theoretical justification for picking K: a large λ_(K+1) − λ_K gap says the graph is almost exactly K disconnected pieces.