spectral clustering instrument

Definition	Clustering the rows of the row-normalized spectral embedding, which reads the angle and discards the density. Chapter 3 section 3.3 and chapter 9. Also row normalization.
Example	Row-normalize the two lowest nontrivial eigenvectors of the Laplacian and run k-means on the angles.
Book	Data Mining as Observation, draft 0.2, commit `f3914f0`; entry id `spectral-clustering`, kind instrument.
Status	no ledger row names this entry. Corrections: none recorded.
Defining equation	Book equation 0.19.
Assumptions and scope	Clustering the rows of the row-normalized spectral embedding, which reads the angle and discards the density. Row normalization puts every row on the unit sphere, keeps the cosine between rows, and ignores a positive rescaling, and the Laplacian’s quadratic form is nonnegative, zero on constants, and positive across any edge. Ng, Jordan, and Weiss normalized because it improved results, and chapter 3 says why. The Euclidean distance in the embedding converges to degree noise and the angle keeps the geodesics. The row normalization applies to eigenvectors of the normalized Laplacian, whose leading vector is proportional to the square root of the degree and not constant.
Prior art	none recorded
Evidence	`geometric-observation/chapters/ch09_legibility.md:10-41`, `lean/DataMiningAsObservation/SpectralEmbedding.lean`, `lean/DataMiningAsObservation/Laplacian.lean`
Reviewed	semantic review 2026-09-06; generated 2026-09-10 from records at the commits on the provenance page.

Clustering the row-normalized spectral embedding.

Equation

Book equation 0.19.

\[L=I-D^{-1/2}AD^{-1/2},\qquad D=\operatorname{diag}(d_1,\dots,d_n),\qquad L\,u_k=\lambda_k u_k,\ \ 0=\lambda_1\le\lambda_2\le\cdots.\]

Book equation 3.3.

\[X_i=r_i\,\theta_i,\qquad r_i\ \to\ \frac1{\sqrt{d_i}},\qquad \theta_i=\frac{X_i}{\|X_i\|}\in S^{m-1}.\]

Conditions

Clustering the rows of the row-normalized spectral embedding, which reads the angle and discards the density. Row normalization puts every row on the unit sphere, keeps the cosine between rows, and ignores a positive rescaling, and the Laplacian’s quadratic form is nonnegative, zero on constants, and positive across any edge.
Ng, Jordan, and Weiss normalized because it improved results, and chapter 3 says why. The Euclidean distance in the embedding converges to degree noise and the angle keeps the geodesics.
The row normalization applies to eigenvectors of the normalized Laplacian, whose leading vector is proportional to the square root of the degree and not constant.

Conditions are curated in entries.toml rather than read from a record.

Ledger

none

First stated

Ng, Jordan, and Weiss, on spectral clustering, 2002, as chapter 3 section 3.3 and chapter 9 section 9.1 of Data Mining as Observation read it, with the angular reading in the-angular-observer/theorem.md:110-146.

Measurements

Where the book states it	Numbers, as the book’s sources table records them	Source
chapter 9 section 9.1	the geodesic-rank reader discards the radius, row normalization is the angular projection	`geometric-observation/chapters/ch09_legibility.md:10-41`; `the-angular-observer/theorem.md:110-146`

Failures and corrections

none

Invariance envelope

none declared

Machine checked

lean/DataMiningAsObservation/SpectralEmbedding.lean, theorems dot_self_nonneg, rowNormalize_unit, dot_rowNormalize, rowNormalize_smul, at observation-data-mining f3914f0; what the check covers is stated in the book’s appendix C.

lean/DataMiningAsObservation/Laplacian.lean, theorems quad_eq, quad_nonneg, quad_const, quad_pos_of_edge, at observation-data-mining f3914f0; what the check covers is stated in the book’s appendix C.

Used in

Data Mining as Observation chapters 0, 3, 9.

spectral embedding; Laplacian; k-means; recognizer; geodesic distance.

Status

Generated 2026-09-10 by encyclopedia/generate.py; book at observation-data-mining f3914f0; the commit of every record is listed in the encyclopedia’s provenance.

← Spearman correlationspectral decomposition →