Spectral Clustering Through Courant–Fischer

From Lloyd’s algorithm to graph Laplacians and random walks

Will Gao · March 2025

Contents

1 K-means clustering
1.1 Lloyd's algorithm
1.2 Objective and descent
2 Spectral clustering
2.1 A balanced two-cluster problem
2.2 Graph Laplacian form
2.3 The Courant–Fischer theorem
2.4 Solution of the spectral relaxation
3 Probabilistic interpretation

These notes develop $k$ -means and spectral clustering from an optimization viewpoint. After proving the descent and finite termination of Lloyd's algorithm, we formulate a balanced graph-partitioning problem, derive its spectral relaxation, and show how the resulting Fiedler vector is related to the eigenmodes of a random walk on a similarity graph.

These notes grew out of Prof. Alexis Drouot's MATH 480 course at the University of Washington, Seattle (Winter 2025). I have reorganized and expanded my course notes and have done my best to ensure correctness, but errors may remain.

1K-means clustering

Let $x_1,\dots,x_N \in \R^d$ be the data and let $1 \le k \le N$ be the desired number of clusters. K-means seeks centers $C = (C_1,\dots,C_k) \in (\R^d)^k$ around which the data cluster.

1.1Lloyd's algorithm

Fix a deterministic rule for breaking ties between equally close centers. Choose initial centers $C^0 = (C^0_1,\dots,C^0_k)$ , often as $k$ distinct points sampled from $x_1,\dots,x_N$ .

For $m = 0,1,2,\dots$ , repeat the following steps.

Given $C^m$ , assign every data point to a nearest center. If $a_m(j) \in \{1,\dots,k\}$ is the assigned label of $x_j$ , then
$a_m(j) \in \argmin_{1 \le \ell \le k} \norm{x_j - C^m_\ell}.$
Define the corresponding sets of indices by $I^m_\ell = \{\, j \in \{1,\dots,N\} : a_m(j) = \ell \,\}$ . Thus $\{1,\dots,N\} = \bigsqcup_{\ell=1}^{k} I^m_\ell$ .
Assuming each $I^m_\ell$ is nonempty, replace each center by the mean of its assigned observations:
$C^{m+1}_\ell = \frac{1}{\abs{I^m_\ell}} \sum_{j \in I^m_\ell} x_j, \qquad \ell = 1,\dots,k.$
Stop if $C^{m+1} = C^m$ ; otherwise continue.

The displayed update requires every $I^m_\ell$ to be nonempty. In an implementation, empty clusters need an explicit rule, such as retaining the old center or reinitializing it in a way that does not increase the objective. For the theoretical discussion below, we assume that all clusters remain nonempty.

1.2Objective and descent

Define the $k$ -means objective

E(C) = \sum_{j=1}^{N} \min_{1 \le \ell \le k} \norm{x_j - C_\ell}^2 .

It is often convenient to introduce an assignment $a : \{1,\dots,N\} \to \{1,\dots,k\}$ and the joint objective

Q(C,a) = \sum_{j=1}^{N} \norm{x_j - C_{a(j)}}^2 .

For fixed $C$ , a nearest-center assignment minimizes $Q(C,a)$ over $a$ ; for fixed $a$ , the cluster means minimize $Q(C,a)$ over $C$ .

Lemma 1.1 (The sample mean minimizes squared distance). Let $z_1,\dots,z_n \in \R^d$ and $\bar z = n^{-1}\sum_{j=1}^{n} z_j$ . Then $\bar z$ is the unique solution of

\min_{c \in \R^d} \sum_{j=1}^{n} \norm{z_j - c}^2 .

Proof. Let $f(c) = \sum_{j=1}^{n}\norm{z_j - c}^2$ . Expanding gives

f(c) = n\norm{c}^2 - 2c\T \sum_{j=1}^{n} z_j + \sum_{j=1}^{n}\norm{z_j}^2 = n\norm{c - \bar z}^2 + \sum_{j=1}^{n}\norm{z_j}^2 - n\norm{\bar z}^2 .

The final two terms do not depend on

c

, and the first is nonnegative with equality exactly when

c = \bar z

\square

Theorem 1.2 (Monotonicity and finite termination). Assume that ties are broken deterministically and all clusters remain nonempty. The iterates of Lloyd's algorithm satisfy

E(C^0) \ge E(C^1) \ge E(C^2) \ge \cdots .

Moreover, equality

E(C^{m+1}) = E(C^m)

forces

C^{m+1} = C^m

. Consequently the algorithm reaches a fixed point after finitely many iterations.

Proof. Let $a_m$ denote the nearest-center assignment associated with $C^m$ . The sample-mean lemma, applied separately to every nonempty cluster, gives

E(C^m) = Q(C^m, a_m) \ge Q(C^{m+1}, a_m).

Reassigning each point to a nearest new center can only improve the joint objective, so

Q(C^{m+1}, a_m) \ge Q(C^{m+1}, a_{m+1}) = E(C^{m+1}).

This proves monotonicity. If

E(C^{m+1}) = E(C^m)

, then equality holds in the first inequality above. By uniqueness of the sample mean, every old center already equals the mean of its assigned cluster, and hence

C^{m+1} = C^m

There are only finitely many assignments, at most $k^N$ , and each assignment with nonempty clusters determines a unique tuple of cluster means. After the first update, every center tuple produced by the algorithm is therefore one of finitely many such tuples. Between two distinct center tuples the objective decreases strictly. Hence no nonfixed center tuple can repeat, and the algorithm must reach a fixed point after finitely many iterations. $\square$

Remark 1.3. The fixed point need not be a global minimizer of $E$ . K-means is sensitive to initialization, so multiple restarts or $k$ -means++ initialization are often used in practice.

2Spectral clustering

K-means can perform poorly when clusters are nonconvex, as in the familiar “two moons” example. Spectral clustering instead encodes the data as a weighted graph: nearby, similar points receive a large edge weight and should preferably receive the same label.

2.1A balanced two-cluster problem

Suppose $N$ is even and we seek two clusters of equal size. Assign labels

z_i \in \{-1,1\}, \qquad \Omega_+ = \{x_i : z_i = 1\}, \qquad \Omega_- = \{x_i : z_i = -1\}.

The balance condition is $\sum_{i=1}^{N} z_i = 0$ .

With an $\varepsilon$ -neighborhood graph, a natural disagreement energy is

E(z) = \sum_{i,j=1}^{N} \one_{\{\norm{x_i - x_j} \le \varepsilon\}} \abs{z_i - z_j}^2 .

It penalizes nearby points given opposite labels. Because the sum runs over ordered pairs $(i,j)$ , every undirected edge is counted twice.

More generally, choose a nonnegative, nonincreasing similarity function $w : [0,\infty) \to [0,\infty)$ , so that close points receive large weights. The indicator above corresponds to

w(r) = \begin{cases} 1, & r \le \varepsilon,\\[2pt] 0, & r \gt \varepsilon. \end{cases}

Relax $z_i \in \{-1,1\}$ to $z_i \in \R$ . The constraint $\sum_i z_i^2 = N$ retains the scale of the discrete labels and excludes the trivial vector $z = 0$ . The relaxed problem is

\min_{z \in \R^N} \ \sum_{i,j=1}^{N} w\!\left(\norm{x_i - x_j}\right) \abs{z_i - z_j}^2, \qquad \text{subject to } \ \sum_{i=1}^{N} z_i = 0, \quad \sum_{i=1}^{N} z_i^2 = N.

(M)

The relaxed vector embeds the data points on the real line. A two-way partition can be obtained by thresholding at zero. If an exactly balanced partition is required, assign the $N/2$ smallest coordinates to one cluster and the $N/2$ largest to the other.

2.2Graph Laplacian form

Define the symmetric weight matrix and degree matrix by

W_{ij} = w\!\left(\norm{x_i - x_j}\right), \qquad D = \diag(d_1,\dots,d_N), \qquad d_i = \sum_{j=1}^{N} W_{ij}.

The unnormalized graph Laplacian is $L = D - W$ .

Lemma 2.1 (Dirichlet energy). For every $z \in \R^N$ ,

\sum_{i,j=1}^{N} W_{ij}\abs{z_i - z_j}^2 = 2 z\T (D - W) z = z\T M z, \qquad M := 2D - 2W = 2L.

Proof. Using $W_{ij} = W_{ji}$ ,

\sum_{i,j=1}^{N} W_{ij}(z_i - z_j)^2 = \sum_{i,j} W_{ij} z_i^2 + \sum_{i,j} W_{ij} z_j^2 - 2\sum_{i,j} W_{ij} z_i z_j = 2 z\T D z - 2 z\T W z = 2 z\T (D - W) z. \ \square

In particular, $M$ is positive semidefinite because its quadratic form is a sum of nonnegative terms. Also $M\one = 0$ , since $D\one = W\one$ .

2.3The Courant–Fischer theorem

For a real symmetric matrix $A \in \R^{n \times n}$ and $x \ne 0$ , define the Rayleigh quotient

R_A(x) = \frac{x\T A x}{x\T x}.

Theorem 2.2 (Courant–Fischer). Let the eigenvalues of $A$ be ordered as $\lambda_1 \ge \cdots \ge \lambda_n$ . For $k = 1,\dots,n$ ,

\lambda_k = \max_{\substack{S \le \R^n \\ \dimm S = k}} \ \min_{\substack{x \in S \\ x \ne 0}} R_A(x), \qquad\qquad \lambda_k = \min_{\substack{T \le \R^n \\ \dimm T = n-k+1}} \ \max_{\substack{x \in T \\ x \ne 0}} R_A(x).

Proof. Because $A$ is symmetric, it has an orthonormal eigenbasis $v_1,\dots,v_n$ , with $A v_i = \lambda_i v_i$ . If $x = \sum_{i=1}^{n} c_i v_i$ , then

R_A(x) = \frac{\sum_{i=1}^{n} \lambda_i c_i^2}{\sum_{i=1}^{n} c_i^2},

a weighted average of the eigenvalues.

Take $S_0 = \operatorname{span}\{v_1,\dots,v_k\}$ . Every nonzero $x \in S_0$ satisfies $R_A(x) \ge \lambda_k$ , and equality is attained at $v_k$ . Hence the max–min is at least $\lambda_k$ .

Conversely, let $S$ be any $k$ -dimensional subspace and set $V = \operatorname{span}\{v_k,\dots,v_n\}$ , whose dimension is $n-k+1$ . The dimension formula gives

\dimm(S \cap V) \ge k + (n-k+1) - n = 1.

For a nonzero

x \in S \cap V

R_A(x) \le \lambda_k

. Thus

\min_{x \in S \setminus \{0\}} R_A(x) \le \lambda_k

for every

S

, proving the max–min formula. The min–max formula follows by the same argument with the roles of the top and bottom eigenspaces reversed.

\square

2.4Solution of the spectral relaxation

Theorem 2.3 (Fiedler-vector solution). Let the eigenvalues of $M = 2(D-W)$ be

0 = \mu_1 \le \mu_2 \le \cdots \le \mu_N,

counted with multiplicity. If the weighted graph is connected, then

\mu_1 = 0

is simple and an associated unit eigenvector is

v_1 = \frac{\one}{\sqrt{N}}.

Every solution of (M) has the form

z^{*} = \sqrt{N}\, v,

where

v

is a unit eigenvector in the eigenspace of the second-smallest eigenvalue

\mu_2

. The minimum value is

N\mu_2

Proof. Choose an orthonormal eigenbasis $v_1,\dots,v_N$ of $M$ with $v_1 = \one/\sqrt{N}$ . The balance constraint $z\T\one = 0$ implies

z = \sum_{r=2}^{N} \alpha_r v_r,

and the norm constraint gives

\sum_{r=2}^{N} \alpha_r^2 = N.

Therefore

z\T M z = \sum_{r=2}^{N} \mu_r \alpha_r^2 \ \ge\ \mu_2 \sum_{r=2}^{N} \alpha_r^2 = N\mu_2 .

Equality holds exactly when

z

lies in the

\mu_2

-eigenspace and has norm

\sqrt{N}

\square

Remark 2.4. If the graph has $c \gt 1$ connected components, then the nullspace of $M$ has dimension $c$ . A nonconstant vector in that nullspace can be orthogonal to $\one$ , so the relaxed minimum is zero and components can be separated without cutting a positive-weight edge. The connectedness assumption is what makes the first nonconstant mode the usual Fiedler vector.

3Probabilistic interpretation

For a general weighted graph with degree matrix $D$ , the associated random walk has transition matrix $P = D^{-1}W$ , provided every degree is positive. This matrix is row-stochastic, although it need not be symmetric even when $W$ is symmetric.

To make the spectral relation especially transparent, we now consider the special case of a symmetric, nonnegative, row-stochastic transition matrix $P$ , so $\sum_{j=1}^{N} P_{ij} = 1$ for every $i$ . It may be viewed as the transition matrix of a random walk on the data graph, with $P_{ij} = \Prob(Y_{t+1} = j \mid Y_t = i)$ .

For the column probability vector

F(t) = \big(\Prob(Y_t = 1),\ \dots,\ \Prob(Y_t = N)\big)\T,

the usual row-transition convention gives

F(t+1) = P\T F(t) = P F(t), \qquad F(t) = P^t F(0),

where the second equality uses symmetry. Symmetry and stochasticity imply that the uniform distribution $\tfrac{1}{N}\one$ is stationary.

Lemma 3.1 (Spectrum of a symmetric stochastic matrix). Assume the graph of $P$ is connected. Order the eigenvalues as

1 = \eta_1 \gt \eta_2 \ge \cdots \ge \eta_N \ge -1.

Then

u_1 = \frac{\one}{\sqrt{N}}

is a unit eigenvector for

\eta_1 = 1

, and the eigenvalue

1

is simple.

Proof. Since $P\one = \one$ , the number $1$ is an eigenvalue. For any $x \in \R^N$ , symmetry, nonnegativity, and $2\abs{x_i x_j} \le x_i^2 + x_j^2$ yield

\abs{x\T P x} \le \sum_{i,j} P_{ij}\abs{x_i x_j} \le \tfrac{1}{2}\sum_{i,j} P_{ij}\left(x_i^2 + x_j^2\right) = x\T x.

Thus every eigenvalue lies in

[-1,1]

If $P v = v$ , choose an index $r$ for which $v_r = \max_i v_i$ (replacing $v$ by $-v$ if needed). Then

v_r = \sum_j P_{rj} v_j \le \sum_j P_{rj} v_r = v_r .

Equality forces every neighbor of

r

with positive transition probability to have the same value

v_r

. Connectivity propagates this equality to all vertices, so

v

is proportional to

\one

. Hence the eigenspace for

1

is one-dimensional. A real symmetric matrix is orthogonally diagonalizable, so algebraic and geometric multiplicities agree and

\eta_2 \lt 1

\square

Let $u_1,\dots,u_N$ be an orthonormal eigenbasis of $P$ . The spectral decomposition gives

P^t = \sum_{j=1}^{N} \eta_j^t\, u_j u_j\T .

Consider the Laplacian-form matrix $M_P = 2I - 2P$ . The matrices $M_P$ and $P$ have the same eigenvectors, and an eigenvalue $\eta$ of $P$ corresponds to the eigenvalue $2(1-\eta)$ of $M_P$ . The second-smallest eigenvector of $M_P$ is therefore a second-largest eigenvector of $P$ .

If $z$ is normalized so that $\norm{z} = \sqrt{N}$ , take

u_1 = \frac{\one}{\sqrt{N}}, \qquad u_2 = \frac{z}{\sqrt{N}}.

Then

P^t = \frac{1}{N}\one\one\T + \frac{1}{N}\,\eta_2^t\, z z\T + \sum_{j=3}^{N} \eta_j^t\, u_j u_j\T .

Thus the spectral-clustering coordinate is the nonconstant eigenmode associated with the second-largest eigenvalue of the transition matrix. When the nontrivial spectrum is nonnegative, this is also the slowest-decaying nonconstant mode.

Remark 3.2 (Periodicity). Connectedness alone does not ensure that $P^t$ converges: for example, a random walk on a bipartite graph can have eigenvalue $-1$ . If the chain is also aperiodic, then

\abs{\eta_j} \lt 1 \quad \text{for all } j \ge 2,

and

P^t \longrightarrow \frac{1}{N}\one\one\T .

A common fix is the lazy walk

\widetilde{P} = \frac{I+P}{2}

. It preserves the eigenvectors and transforms each eigenvalue

\eta_j

into

(1+\eta_j)/2 \in [0,1]

. In particular, for the lazy walk the second-largest eigenvalue corresponds to the slowest-decaying nonconstant mode.