Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 8 results · all verified · 8 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 8 also cleared it.

PCA, kernel PCA, MDS, and manifold embeddings

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite centering matrices and centered data

Definition

For an integer $n \geq 1$ , let $1_{n} \in R^{n}$ be the vector whose entries are all $1$ , and let $I_{n}$ be the $n \times n$ identity matrix. The centering matrix is

$H_{n} : = I_{n} - \frac{1}{n} 1_{n} 1_{n}^{T} .$

For $v \in R^{n}$ , write $\overset{ˉ}{v} : = n^{- 1} 1_{n}^{T} v$ ; then $H_{n} v = v - \overset{ˉ}{v} 1_{n}$ . For a finite data matrix $X \in R^{n \times p}$ with $p \geq 1$ , its centered data matrix is $X_{c} : = H_{n} X$ ; each column of $X_{c}$ has sum zero.

Definition references

Hastie, Tibshirani, and Friedman, ESL II, §14.5.1, printed pp. 534–541

Cameron, Linear and Nonlinear Dimensionality Reduction, §2.2, PDF p. 4

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The maximum trace over q-dimensional orthonormal frames is the sum of the top q eigenvalues

Statement

Let $A \in R^{p \times p}$ be symmetric with eigenvalues $λ_{1} \geq \dots \geq λ_{p}$ , counted with multiplicity. For $1 \leq q \leq p$ and every $Q \in R^{p \times q}$ satisfying $Q^{T} Q = I_{q}$ ,

$tr (Q^{T} A Q) \leq \sum_{j = 1}^{q} λ_{j} .$

Equality is attained by taking the columns of $Q$ to be orthonormal eigenvectors for the $q$ largest eigenvalues. Equality holds exactly when the column space of $Q$ contains every eigenspace with eigenvalue greater than $λ_{q}$ , is orthogonal to every eigenspace with eigenvalue less than $λ_{q}$ , and uses a subspace of dimension $q - # {j : λ_{j} > λ_{q}}$ from the eigenspace with eigenvalue $λ_{q}$ .

Statement references

Cameron, Linear and Nonlinear Dimensionality Reduction, §2.1, PDF p. 3

von Luxburg, A Tutorial on Spectral Clustering, §5.2, PDF pp. 11–12

Facts & Assumptions

Given: A symmetric real matrix $A \in R^{p \times p}$ and an integer $q$ with $1 \leq q \leq p$ .

[F1]

In the standard real coordinate inner product, $⟨ x, y ⟩ = \sum_{i < p} x_{i} y_{i}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

[F2]

In an orthonormal basis, a real endomorphism is self-adjoint exactly when its matrix is symmetric (In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose).

[F3]

Every self-adjoint endomorphism of a finite-dimensional real inner-product space has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F4]

The trace of a square matrix is the sum of its diagonal entries (The trace $tr (A)$ as the sum of the diagonal entries).

[F5]

For conformable rectangular matrices $A, B$ , $tr (A B) = tr (B A)$ (For $A \in M_{m \times n} (F)$ and $B \in M_{n \times m} (F)$ , $tr (A B) = tr (B A)$ ).

Proof

1.1givenF1F2F3

By [F1] and [F2], the matrix $A$ represents a self-adjoint map on $R^{p}$ with its standard inner product; [F3] gives an orthonormal eigenbasis $u_{1}, \dots, u_{p}$ ordered with eigenvalues $λ_{1} \geq \dots \geq λ_{p}$ .

2.1step 1.1F4F5algebra

For any feasible $Q$ , put $P = Q Q^{T}$ . Since $Q^{T} Q = I_{q}$ , $P^{T} = P$ and $P^{2} = P$ , so $u_{j} = P u_{j} + (I - P) u_{j}$ is an orthogonal decomposition and $a_{j} : = u_{j}^{T} P u_{j} = ∥ Q^{T} u_{j} ∥_{2}^{2} = ∥ P u_{j} ∥_{2}^{2}$ lies in $[0, 1]$ . This decomposition gives $a_{j} = 0$ exactly when $P u_{j} = 0$ , and $a_{j} = 1$ exactly when $P u_{j} = u_{j}$ . Also $\sum_{j = 1}^{p} a_{j} = tr (P) = q$ by [F4]. The frame trace equals $tr (P A)$ by [F5]. If $U$ has columns $u_{j}$ and $Λ = U^{T} A U = diag (λ_{j})$ , [F5] and $U U^{T} = I$ give $tr (P A) = tr (U^{T} P A U) = tr ((U^{T} P U) Λ) = \sum_{j = 1}^{p} λ_{j} a_{j}$ .

3.1step 2.1algebra

Because $λ_{j} \geq λ_{q}$ for $j \leq q$ and $λ_{j} \leq λ_{q}$ for $j > q$ , $\sum_{j = 1}^{p} λ_{j} a_{j} \leq \sum_{j = 1}^{q} (λ_{j} a_{j} + λ_{q} (1 - a_{j})) \leq \sum_{j = 1}^{q} λ_{j}$ . The first inequality uses $\sum_{j} a_{j} = q$ ; the second uses $0 \leq a_{j} \leq 1$ and $λ_{j} \geq λ_{q}$ for $j \leq q$ .

4.1step 2.1step 3.1algebra

The first inequality in step 3.1 has nonnegative difference $\sum_{j > q} (λ_{q} - λ_{j}) a_{j}$ , so equality requires $a_{j} = 0$ whenever $λ_{j} < λ_{q}$ . The second has nonnegative difference $\sum_{j \leq q} (λ_{j} - λ_{q}) (1 - a_{j})$ , so equality requires $a_{j} = 1$ whenever $λ_{j} > λ_{q}$ . By step 2.1, these conditions say the chosen subspace contains all higher-eigenvalue eigenspaces, is orthogonal to all lower-eigenvalue eigenspaces, and takes its remaining dimension in the $λ_{q}$ eigenspace. Conversely, each such subspace makes both differences zero. If $A = 0$ , all eigenvalues are zero and both differences vanish for every feasible $Q$ , as does the stated equality condition.

5.1step 1.1step 3.1F3∎

Taking the first $q$ vectors of the eigenbasis from step 1.1 as the columns of $Q$ gives a feasible frame and makes the trace equal $\sum_{j = 1}^{q} λ_{j}$ . Thus the upper bound is the attained maximum, with the stated equality cases.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite configurations with equal Gram matrices have isometric linear spans

Statement

Let $n \geq 0$ , $x_{1}, \dots, x_{n} \in R^{d}$ , and $y_{1}, \dots, y_{n} \in R^{m}$ be finite lists with $⟨ x_{i}, x_{j} ⟩ = ⟨ y_{i}, y_{j} ⟩$ for every $1 \leq i, j \leq n$ , using the standard Euclidean inner products. The assignment $\sum_{i = 1}^{n} c_{i} x_{i} \mapsto \sum_{i = 1}^{n} c_{i} y_{i}$ is a well-defined linear isometry from $span {x_{i}}$ onto $span {y_{i}}$ ; when $n = 0$ both spans are zero spaces and the assignment is the unique zero map.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §18.5.2, printed pp. 670–672

Cameron, Linear and Nonlinear Dimensionality Reduction, §3, PDF pp. 4–6

Facts & Assumptions

Given: An integer $n \geq 0$ and lists $x_{1}, \dots, x_{n} \in R^{d}$ and $y_{1}, \dots, y_{n} \in R^{m}$ with equal pairwise inner products.

[F1]

The standard coordinate pairings on $R^{d}$ and $R^{m}$ are positive-definite inner products, with $⟨ u, v ⟩ = \sum_{k} u_{k} v_{k}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

Proof

1.1givenF1algebra

For any coefficients $c_{1}, \dots, c_{n}$ , bilinearity and the equal Gram entries give $∥ \sum_{i} c_{i} x_{i} ∥_{2}^{2} = \sum_{i, j} c_{i} c_{j} ⟨ x_{i}, x_{j} ⟩ = \sum_{i, j} c_{i} c_{j} ⟨ y_{i}, y_{j} ⟩ = ∥ \sum_{i} c_{i} y_{i} ∥_{2}^{2}$ . If $\sum_{i} c_{i} x_{i} = 0$ , the left side is zero, so [F1] implies $\sum_{i} c_{i} y_{i} = 0$ . Applying this to the difference of two coefficient representations shows that the assignment in the statement is well defined.

2.1step 1.1F1algebra∎

For coefficient lists $c, d$ , the same bilinear expansion gives $⟨ \sum_{i} c_{i} x_{i}, \sum_{j} d_{j} x_{j} ⟩ = \sum_{i, j} c_{i} d_{j} ⟨ x_{i}, x_{j} ⟩ = \sum_{i, j} c_{i} d_{j} ⟨ y_{i}, y_{j} ⟩ = ⟨ \sum_{i} c_{i} y_{i}, \sum_{j} d_{j} y_{j} ⟩$ . The coefficient formula is linear, and its range contains every $y_{i}$ because it maps $x_{i}$ to $y_{i}$ ; hence its range is exactly their span and it preserves inner products. If $n = 0$ , both spans are zero spaces and this is their unique zero map. Thus in every case the assignment is an onto linear isometry.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Deterministic finite nearest-neighbor lists and graph symmetrizations

Definition

Let $x_{1}, \dots, x_{n} \in R^{p}$ with $n \geq 2$ , using the Euclidean norm $∥ v ∥_{2} = (\sum_{a = 1}^{p} v_{a}^{2})^{1 / 2}$ . For $1 \leq k < n$ , the deterministic $k$ -nearest-neighbor list $N_{k} (i)$ consists of the first $k$ indices $j \neq i$ when the other indices are ordered by increasing pair $(∥ x_{i} - x_{j} ∥_{2}, j)$ lexicographically; thus equal distances are broken by increasing sample index. All graphs below have vertex set ${1, \dots, n}$ . The union symmetrization has edge ${i, j}$ when $j \in N_{k} (i)$ or $i \in N_{k} (j)$ ; the mutual symmetrization has edge ${i, j}$ exactly when both inclusions hold. Each included edge may be assigned weight $∥ x_{i} - x_{j} ∥_{2}$ . For a radius $r > 0$ , the radius graph has edge ${i, j}$ exactly when $∥ x_{i} - x_{j} ∥_{2} \leq r$ for $1 \leq i < j \leq n$ . An undirected graph is connected when every two vertices are joined by a finite edge path.

Definition references

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 572–574

Cameron, Linear and Nonlinear Dimensionality Reduction, §6 and §7, PDF pp. 9–15

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The finite centering matrix is the orthogonal projection onto the zero-sum subspace

Statement

For $n \geq 1$ , let $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ . Then $H_{n}^{T} = H_{n}$ , $H_{n}^{2} = H_{n}$ , $H_{n} 1_{n} = 0$ , and for each $v \in R^{n}$ , $H_{n} v = v - (n^{- 1} 1_{n}^{T} v) 1_{n}$ . Thus $H_{n}$ is the orthogonal projection onto ${v \in R^{n} : 1_{n}^{T} v = 0}$ .

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.5.1, printed pp. 534–541

Cameron, Linear and Nonlinear Dimensionality Reduction, §2.2, PDF p. 4

Facts & Assumptions

Given: An integer $n \geq 1$ and $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ .

[F1]

The finite centering matrix is $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ , and it acts by subtracting the mean coordinate times $1_{n}$ (Finite centering matrices and centered data).

[F2]

The standard inner product on $R^{n}$ is $⟨ u, v ⟩ = \sum_{i < n} u_{i} v_{i}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

Proof

1.1givenF1algebra

The matrix $1_{n} 1_{n}^{T}$ is symmetric, so the formula in [F1] gives $H_{n}^{T} = H_{n}$ . Also $1_{n}^{T} 1_{n} = n$ , and hence $H_{n} 1_{n} = 1_{n} - n^{- 1} 1_{n} n = 0$ .

2.1step 1.1F1F2algebra∎

Writing $J = 1_{n} 1_{n}^{T}$ , one has $J^{2} = 1_{n} (1_{n}^{T} 1_{n}) 1_{n}^{T} = n J$ , so $H_{n}^{2} = (I_{n} - J / n)^{2} = I_{n} - 2 J / n + J^{2} / n^{2} = I_{n} - J / n = H_{n}$ . The formula for $H_{n} v$ in [F1] shows that its image is zero-sum; if $1_{n}^{T} v = 0$ , then $H_{n} v = v$ . For any $v$ , the residual $v - H_{n} v = (n^{- 1} 1_{n}^{T} v) 1_{n}$ is orthogonal to every zero-sum vector by [F2]. Hence $H_{n} v$ is the orthogonal projection of $v$ onto the zero-sum subspace.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Rank-q principal component analysis by Frobenius reconstruction error

Definition

For a finite data matrix $X \in R^{n \times p}$ with $n, p \geq 1$ , set $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ and $X_{c} = H_{n} X$ . For an integer $q$ with $1 \leq q \leq p$ , a rank- $q$ PCA frame is a matrix $Q \in R^{p \times q}$ with $Q^{T} Q = I_{q}$ . Its reconstruction is $X_{c} Q Q^{T}$ , and its squared Frobenius reconstruction error is

$∥ X_{c} - X_{c} Q Q^{T} ∥_{F}^{2} = \sum_{i < n} \sum_{j < p} (X_{c} - X_{c} Q Q^{T})_{i j}^{2} .$

A rank- $q$ PCA solution is any frame minimizing this error over all such $Q$ ; its score matrix is $X_{c} Q$ . A minimizing frame need not be unique when the relevant eigenvalues are tied.

Definition references

Finite centering matrix and centered data

Frobenius matrix norm

Hastie, Tibshirani, and Friedman, ESL II, §14.5.1, printed pp. 534–541

Cameron, Linear and Nonlinear Dimensionality Reduction, §§2.1–2.2, PDF pp. 2–4

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Kernel principal component analysis for a finite positive-semidefinite Gram matrix

Definition

Given $n \geq 1$ data points and a finite symmetric Gram matrix $K \in R^{n \times n}$ satisfying $a^{T} K a \geq 0$ for every $a \in R^{n}$ , define $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ and the centered Gram matrix $K_{c} = H_{n} K H_{n}$ . The positive-semidefinite condition is an input hypothesis; no theorem that an arbitrary kernel formula produces such a matrix is assumed. For $1 \leq q \leq n$ , kernel PCA retains the $q$ largest eigenvalues $λ_{1} \geq \dots \geq λ_{n} \geq 0$ of $K_{c}$ and associated orthonormal eigenvectors $u_{1}, \dots, u_{q}$ , returning the score matrix $U_{q} diag (\sqrt{λ_{1}}, \dots, \sqrt{λ_{q}})$ . Eigenvectors inside a tied eigenspace may be chosen arbitrarily.

Definition references

Finite centering matrix

Hastie, Tibshirani, and Friedman, ESL II, §14.5.4, printed pp. 547–550, and §18.5.2, printed pp. 670–672

Cameron, Linear and Nonlinear Dimensionality Reduction, §2.2, PDF pp. 3–4

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Classical multidimensional scaling from a finite dissimilarity matrix

Definition

Let $n \geq 1$ and let $D \in R^{n \times n}$ be symmetric with nonnegative entries and zero diagonal, and write $D^{\circ 2}$ for the matrix with entries $(D^{\circ 2})_{i j} = D_{i j}^{2}$ . Define $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ and the centered matrix

$B : = - \frac{1}{2} H_{n} D^{\circ 2} H_{n} .$

For a requested dimension $q \geq 1$ , classical multidimensional scaling diagonalizes the real symmetric matrix $B$ , retains up to the $q$ largest strictly positive eigenvalues $λ_{j}$ with orthonormal eigenvectors $u_{j}$ , and returns coordinates whose columns are $u_{j} \sqrt{λ_{j}}$ . If fewer than $q$ positive eigenvalues exist, it returns only those positive-eigenvalue coordinates. For non-Euclidean dissimilarities this is a spectral procedure; it does not assert exact recovery of all entries of $D$ .

Definition references

Finite centering matrix

Hastie, Tibshirani, and Friedman, ESL II, §14.8, printed pp. 570–572, and §18.5.2, printed pp. 670–672

Cameron, Linear and Nonlinear Dimensionality Reduction, §3, PDF pp. 4–6

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Minimum-norm affine reconstruction weights for a finite LLE neighborhood

Definition

Let $x_{1}, \dots, x_{n} \in R^{p}$ , $n \geq 2$ , and $1 \leq k < n$ . For each $i$ , let $N_{i}$ be the first $k$ indices $j \neq i$ under the increasing lexicographic order of $(∥ x_{i} - x_{j} ∥_{2}, j)$ , so equal distances are broken by sample index; the norm on $R^{p}$ is $∥ z ∥_{2} = (\sum_{a = 1}^{p} z_{a}^{2})^{1 / 2}$ . The local affine reconstruction weights are the vector $w_{i} = (w_{i j})_{j \in N_{i}} \in R^{k}$ minimizing

${∥ x_{i} - \sum_{j \in N_{i}} w_{i j} x_{j} ∥}_{2}^{2} subject to \sum_{j \in N_{i}} w_{i j} = 1,$

Among all minimizers, choose the one of smallest Euclidean norm $∥ w_{i} ∥_{2} = (\sum_{j \in N_{i}} w_{i j}^{2})^{1 / 2}$ . This minimum-norm rule fixes the weights even when the local covariance matrix is singular.

Definition references

Deterministic finite neighbor lists

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 573–575

Cameron, Linear and Nonlinear Dimensionality Reduction, §7, PDF pp. 14–16

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

The top right singular subspace minimizes rank-q PCA Frobenius reconstruction error

Statement

Let $X \in R^{n \times p}$ , $n, p \geq 1$ , let $X_{c} = (I_{n} - n^{- 1} 1_{n} 1_{n}^{T}) X$ , and let $1 \leq q \leq p$ . Write $σ_{1} \geq \dots \geq σ_{p} \geq 0$ for the singular values of $X_{c}$ , padding by zeros after its rank. Among all $Q \in R^{p \times q}$ with $Q^{T} Q = I_{q}$ , the minimum of $∥ X_{c} - X_{c} Q Q^{T} ∥_{F}^{2}$ is

$\sum_{j = q + 1}^{p} σ_{j}^{2} .$

A frame is minimizing exactly when its column space contains every eigenspace of $X_{c}^{T} X_{c}$ with eigenvalue greater than $σ_{q}^{2}$ , is orthogonal to every eigenspace with eigenvalue less than $σ_{q}^{2}$ , and uses the remaining dimension inside the eigenspace with eigenvalue $σ_{q}^{2}$ . In particular a choice of $q$ right singular vectors for the $q$ largest singular values is minimizing; ties can give different minimizing subspaces.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.5.1, printed pp. 534–541

Cameron, Linear and Nonlinear Dimensionality Reduction, §§2.1–2.2, PDF pp. 2–4

Facts & Assumptions

Given: $X \in R^{n \times p}$ , $n, p \geq 1$ , and $1 \leq q \leq p$ .

[F1]

A rank- $q$ PCA frame satisfies $Q^{T} Q = I_{q}$ , reconstructs $X_{c}$ by $X_{c} Q Q^{T}$ , and minimizes the displayed squared Frobenius error (Rank-q principal component analysis by Frobenius reconstruction error).

[F2]

For a real matrix $A$ , $∥ A ∥_{F}^{2} = \sum_{i, j} a_{i j}^{2} = tr (A^{T} A)$ (The Frobenius norm $∥ A ∥_{F} = (\sum_{i, j} ∣ a_{i j} ∣^{2})^{1 / 2}$ on real or complex matrices).

[F3]

A finite-dimensional real linear map has orthonormal domain and codomain bases in which it maps each right singular basis vector to the corresponding singular value times a left singular basis vector, with zero action on the remaining domain basis vectors (Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition).

[F4]

The standard real coordinate pairing is $⟨ x, y ⟩ = \sum_{j} x_{j} y_{j}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

[F5]

The trace of a square matrix is the sum of its diagonal entries (The trace $tr (A)$ as the sum of the diagonal entries).

[F6]

For conformable rectangular matrices $A, B$ , $tr (A B) = tr (B A)$ (For $A \in M_{m \times n} (F)$ and $B \in M_{n \times m} (F)$ , $tr (A B) = tr (B A)$ ).

[F7]

The Frobenius norm satisfies $∥ X_{c} ∥_{F}^{2} = \sum_{j = 1}^{p} σ_{j}^{2}$ , with zero singular values appended after the rank (Spectral and Frobenius norms are unitarily invariant, are given by singular values, and satisfy the sharp rank comparison).

[F8]

For a symmetric matrix, maximizing $tr (Q^{T} A Q)$ over $Q^{T} Q = I_{q}$ gives the sum of the top $q$ eigenvalues, with the stated tie-space equality cases (The maximum trace over q-dimensional orthonormal frames is the sum of the top q eigenvalues).

Proof

1.1F1F2F5F6algebra

Put $C = X_{c}$ and $P = Q Q^{T}$ . Since $Q^{T} Q = I_{q}$ , $P^{T} = P$ and $P^{2} = P$ , so $C - C Q Q^{T} = C (I - P)$ and $(I - P)^{2} = I - P$ . By [F2] and [F5], $∥ C (I - P) ∥_{F}^{2} = tr ((I - P) C^{T} C (I - P))$ . Applying [F6] to cycle the first factor gives $tr (C^{T} C (I - P)^{2}) = tr (C^{T} C (I - P))$ ; then linearity gives $tr (C^{T} C) - tr (C^{T} C P)$ . Applying [F6] again gives $tr (C^{T} C P) = tr (Q^{T} C^{T} C Q)$ . Thus minimizing the reconstruction error is equivalent to maximizing $tr (Q^{T} C^{T} C Q)$ .

2.1step 1.1F3F4F8

By [F3], choose right singular vectors $v_{1}, \dots, v_{p}$ and corresponding left vectors $u_{1}, \dots, u_{r}$ such that $C v_{j} = σ_{j} u_{j}$ for $j \leq r$ and $C v_{j} = 0$ for $j > r$ , where $r = rank C$ . For $i, j \leq r$ , [F4] gives $v_{i}^{T} C^{T} C v_{j} = (C v_{i})^{T} (C v_{j}) = σ_{i} σ_{j} u_{i}^{T} u_{j}$ , which is $σ_{j}^{2}$ when $i = j$ and zero otherwise; for $j > r$ it is zero. Thus $C^{T} C$ has eigenvalues $σ_{1}^{2} \geq \dots \geq σ_{p}^{2} \geq 0$ in the basis $v_{j}$ . Applying [F8] to $A = C^{T} C$ shows that the maximum trace is $\sum_{j = 1}^{q} σ_{j}^{2}$ , attained exactly by the top-eigenspace subspaces described in the statement. Therefore the minimum error is $∥ C ∥_{F}^{2} - \sum_{j = 1}^{q} σ_{j}^{2}$ .

3.1step 2.1F3F7algebra∎

Substituting [F7] into the last expression gives $\sum_{j = q + 1}^{p} σ_{j}^{2}$ . The SVD basis in [F3] supplies a feasible frame from the top $q$ right singular vectors, so the bound is attained. If $q = p$ , the sum is empty and equals zero; if $rank C \leq q$ , every term in the tail is zero.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Double-centering a finite positive-semidefinite Gram matrix preserves positive semidefiniteness

Statement

Let $n \geq 1$ and let $K \in R^{n \times n}$ be symmetric and satisfy $a^{T} K a \geq 0$ for every $a \in R^{n}$ . With $H_{n} = I_{n} - n^{- 1} 1_{n} 1_{n}^{T}$ , the centered matrix $K_{c} = H_{n} K H_{n}$ is symmetric and positive semidefinite. Consequently it has an orthonormal eigenbasis and all its eigenvalues are nonnegative.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.5.4, printed pp. 547–550, and §18.5.2, printed pp. 670–672

Cameron, Linear and Nonlinear Dimensionality Reduction, §2.2, PDF pp. 3–4

Facts & Assumptions

Given: A symmetric positive-semidefinite matrix $K \in R^{n \times n}$ and its centering matrix $H_{n}$ .

[F1]

Kernel PCA takes a symmetric matrix $K$ with $a^{T} K a \geq 0$ for every $a$ and centers it as $K_{c} = H_{n} K H_{n}$ (Kernel principal component analysis for a finite positive-semidefinite Gram matrix).

[F2]

The finite centering matrix is symmetric (The finite centering matrix is the orthogonal projection onto the zero-sum subspace).

[F3]

The standard inner product on $R^{n}$ is $⟨ a, b ⟩ = \sum_{i < n} a_{i} b_{i}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

[F4]

In an orthonormal basis, a real matrix is self-adjoint exactly when it is symmetric (In an orthonormal basis, self-adjoint means conjugate-transpose symmetry and normal means commuting with the conjugate transpose).

[F5]

Every finite-dimensional real self-adjoint endomorphism has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

Proof

1.1F1F2algebra

Since $K^{T} = K$ and $H_{n}^{T} = H_{n}$ by [F1] and [F2], $K_{c}^{T} = (H_{n} K H_{n})^{T} = H_{n} K H_{n} = K_{c}$ .

1.2givenF1F2algebra

For every $a \in R^{n}$ , $a^{T} K_{c} a = (H_{n} a)^{T} K (H_{n} a) \geq 0$ by the input hypothesis on $K$ . Thus $K_{c}$ is positive semidefinite.

2.1step 1.1step 1.2F3F4F5∎

The standard coordinate basis is orthonormal for [F3], so [F4] makes the symmetric matrix $K_{c}$ self-adjoint and [F5] gives an orthonormal eigenbasis. If $u$ is a unit eigenvector with eigenvalue $λ$ , then $λ = u^{T} K_{c} u \geq 0$ by step 1.2. Hence every eigenvalue is nonnegative, which makes the stated kernel-PCA eigenprocedure well-defined.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Double-centering Euclidean squared distances recovers their centered Gram matrix

Statement

Let $n \geq 1$ . For every symmetric nonnegative zero-diagonal dissimilarity matrix $D$ , the matrix $B = - \frac{1}{2} H_{n} D^{\circ 2} H_{n}$ used by classical multidimensional scaling is symmetric and has a real orthonormal eigendecomposition, though it may have negative eigenvalues. If $D_{i j} = ∥ z_{i} - z_{j} ∥_{2}$ for points $z_{1}, \dots, z_{n} \in R^{d}$ , where $∥ v ∥_{2} = (\sum_{a = 1}^{d} v_{a}^{2})^{1 / 2}$ , then $B = Z_{c} Z_{c}^{T}$ for the centered row-data matrix $Z_{c} = H_{n} Z$ , so $B$ is positive semidefinite. The coordinates formed from all positive eigenvalues reproduce every pairwise distance exactly; if the requested embedding dimension is at least the number of positive eigenvalues, the truncated procedure is exact. The centered configurations obtained from $Z$ and these coordinates are related by a linear isometry between their spans, so the original configurations agree up to translation and Euclidean isometry of their affine spans.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.8, printed pp. 570–572, and §18.5.2, printed pp. 670–672

Cameron, Linear and Nonlinear Dimensionality Reduction, §3, PDF pp. 4–6

Facts & Assumptions

Given: A finite symmetric nonnegative zero-diagonal matrix $D$ , its classical-MDS matrix $B$ , and, in the Euclidean case, points $z_{i}$ with $D_{i j} = ∥ z_{i} - z_{j} ∥_{2}$ .

[F1]

Classical MDS defines $D^{\circ 2}$ entrywise and $B = - \frac{1}{2} H_{n} D^{\circ 2} H_{n}$ for symmetric nonnegative zero-diagonal $D$ (Classical multidimensional scaling from a finite dissimilarity matrix).

[F2]

The centering matrix is symmetric, annihilates $1_{n}$ , and maps onto the zero-sum subspace (The finite centering matrix is the orthogonal projection onto the zero-sum subspace).

[F3]

[F4]

[F5]

[F6]

Two finite point lists with equal Gram matrices have linearly isometric spans (Finite configurations with equal Gram matrices have isometric linear spans).

Proof

1.1F1F2F3F4F5algebra

For any permitted $D$ , $D^{\circ 2}$ is symmetric and $H_{n}$ is symmetric by [F2], so $B^{T} = B$ . The standard coordinate basis is orthonormal for [F3], so [F4] makes $B$ self-adjoint and [F5] gives a real orthonormal eigendecomposition; this justifies the spectral step even when some eigenvalues are negative.

1.2givenF1F2F3algebra

Suppose $D_{i j} = ∥ z_{i} - z_{j} ∥_{2}$ and let $Z$ be the matrix with rows $z_{i}^{T}$ . Put $s_{i} = ∥ z_{i} ∥_{2}^{2}$ . Expanding each squared distance with the coordinate inner product [F3] gives $D^{\circ 2} = s 1_{n}^{T} + 1_{n} s^{T} - 2 Z Z^{T}$ , hence $B = - \frac{1}{2} H_{n} (s 1_{n}^{T} + 1_{n} s^{T} - 2 Z Z^{T}) H_{n} = H_{n} Z Z^{T} H_{n} = Z_{c} Z_{c}^{T}$ because $H_{n} 1_{n} = 0$ and $H_{n}^{T} = H_{n}$ by [F2]. For every $a$ , $a^{T} B a = \sum_{r} ((Z_{c}^{T} a)_{r})^{2} \geq 0$ by the coordinate formula [F3], so $B$ is positive semidefinite; also $B 1_{n} = Z_{c} Z_{c}^{T} 1_{n} = 0$ . When $n = 1$ , $H_{1} = 0$ , so $Z_{c} = 0$ and $B = 0$ .

2.1step 1.2F1F5algebra

In the Euclidean-distance case of step 1.2, $B$ is positive semidefinite. By [F5], choose an orthonormal eigenbasis. For each unit eigenvector $u$ with eigenvalue $λ$ , step 1.2 gives $λ = u^{T} B u \geq 0$ . Thus the zero-eigenvalue terms vanish and $B = U_{+} Λ_{+} U_{+}^{T}$ , where $U_{+}$ contains exactly the positive-eigenvalue eigenvectors and $Λ_{+}$ is diagonal with strictly positive entries. If there are no positive eigenvalues, this is the empty decomposition and $B = 0$ . The classical-MDS coordinates from all positive eigenvalues are $Y = U_{+} Λ_{+}^{1 / 2}$ , so $Y Y^{T} = B$ . By step 1.2, $B 1_{n} = 0$ , and each column $u$ of $U_{+}$ with eigenvalue $λ > 0$ satisfies $λ u^{T} 1_{n} = u^{T} B 1_{n} = 0$ ; hence the rows of $Y$ are centered.

3.1step 2.1F1F2F3algebra

By [F2], row $i$ of $Z_{c}$ is $z_{i} - \overset{ˉ}{z}$ , where $\overset{ˉ}{z} = n^{- 1} \sum_{i} z_{i}$ . For each $i, j$ , the coordinate Gram identity gives $∥ y_{i} - y_{j} ∥_{2}^{2} = B_{i i} + B_{j j} - 2 B_{i j} = ∥ z_{i} - \overset{ˉ}{z} - (z_{j} - \overset{ˉ}{z}) ∥_{2}^{2} = ∥ z_{i} - z_{j} ∥_{2}^{2} = D_{i j}^{2}$ . Both distances are nonnegative, so $∥ y_{i} - y_{j} ∥_{2} = D_{i j}$ . The procedure retaining up to the requested dimension $q$ has the same Gram matrix when $q$ is at least the number of positive eigenvalues, so these equalities then hold for its returned coordinates.

4.1step 1.2step 2.1F6algebra∎

The row configurations of $Z_{c}$ and $Y$ have the same Gram matrix $B$ by step 1.2 and step 2.1. Applying [F6] gives an isometry between their spans. The original rows of $Z$ differ from those of $Z_{c}$ by the common translation $\overset{ˉ}{z}$ , so the original and embedded configurations are congruent after this translation. For a non-Euclidean $D$ , step 1.1 still gives a symmetric spectral problem, but step 1.2 is unavailable and no exact-distance conclusion follows.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite LLE affine least-squares weights have a unique minimum-norm minimizer

Statement

Fix $x_{i} \in R^{p}$ and a nonempty finite neighbor list $N_{i} = (j_{1}, \dots, j_{k})$ of distinct indices. The constrained problem

$\min_{w \in R^{k}} {∥ x_{i} - \sum_{s = 1}^{k} w_{s} x_{j_{s}} ∥}_{2}^{2} subject to \sum_{s = 1}^{k} w_{s} = 1$

has a nonempty affine set of minimizers, and exactly one member of that set has smallest Euclidean norm. Thus the minimum-norm rule in finite LLE defines one weight vector even when the local covariance matrix is singular. This conclusion uses no choice axiom.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 573–575

Cameron, Linear and Nonlinear Dimensionality Reduction, §7, PDF pp. 14–16

Facts & Assumptions

Given: A fixed point $x_{i} \in R^{p}$ and a nonempty finite ordered list $N_{i} = (j_{1}, \dots, j_{k})$ .

[F1]

The LLE weight problem minimizes the local reconstruction error under the affine constraint $\sum_{s} w_{s} = 1$ , then selects a minimizer of least Euclidean norm (Minimum-norm affine reconstruction weights for a finite LLE neighborhood).

[F2]

For a linear map between finite-dimensional inner-product spaces, least-squares minimizers exist and form an affine translate of the kernel (For a linear map $T : V \to W$ between finite-dimensional inner-product spaces, $x$ minimises $∥ T x - b ∥$ if and only if $T^{*} (T x - b) = 0$ , equivalently $T^{*} T x = T^{*} b$ ; minimisers exist and any two differ by an element of $\ker T$ ).

[F3]

The standard real coordinate pairing on $R^{k}$ is a positive-definite inner product (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

[F4]

A subspace of a finite-dimensional inner-product space and its orthogonal complement give a direct-sum decomposition (For a subspace $W$ of a finite-dimensional inner product space, $V = W \oplus W^{⊥}$ ).

Proof

1.1givenF1F3algebra

Let $w^{0} = (1, 0, \dots, 0) \in R^{k}$ , let $L = {z \in R^{k} : \sum_{s} z_{s} = 0}$ , and define $T : L \to R^{p}$ by $T z = \sum_{s} z_{s} x_{j_{s}}$ . Every feasible $w$ has a unique form $w = w^{0} + z$ with $z \in L$ , and its residual is $x_{i} - x_{j_{1}} - T z$ . Thus the constrained problem is an ordinary finite-dimensional least-squares problem for $T$ on the inner-product subspace $L$ .

2.1step 1.1F2choosealgebra

By [F2], choose a least-squares minimizer $z_{0} \in L$ and all minimizers are $z_{0} + N$ , where $N = \ker T \subseteq L$ . Therefore all feasible minimizing weights form the nonempty affine set $w^{0} + z_{0} + N$ . In the degenerate case $T = 0$ , $z_{0} = 0$ is a minimizer and $N = L$ , so this set contains every feasible weight.

3.1step 2.1F3F4algebra

Put $w_{*} = w^{0} + z_{0}$ . By [F4], decompose $w_{*} = u + v$ with $u \in N$ and $v \in N^{⊥}$ in $R^{k}$ . Since $- u \in N$ , $v = w_{*} - u$ remains in the affine minimizer set. For any other minimizer $v + h$ with $h \in N$ , orthogonality gives $∥ v + h ∥_{2}^{2} = ∥ v ∥_{2}^{2} + ∥ h ∥_{2}^{2}$ , which is at least $∥ v ∥_{2}^{2}$ with equality only if $h = 0$ . Hence $v$ is the unique minimum-norm minimizer. When $k = 1$ , $L = N = {0}$ and this gives the unique feasible weight $w^{0} = (1)$ .

4.1step 1.1step 2.1step 3.1∎

The proof applies the least-squares existence result once to this fixed finite-dimensional problem and uses a finite orthogonal decomposition; it selects no sequence of approximate minimizers and uses no Countable Choice.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite ISOMAP with deterministic neighborhoods and connected-graph shortest paths

Definition

Input: a finite data matrix $X \in R^{n \times p}$ with $n \geq 2$ , an embedding dimension $q \geq 1$ , and either a $k$ -nearest-neighbor parameter $1 \leq k < n$ with an explicit union or mutual symmetrization choice, or a radius $r > 0$ . Use $∥ v ∥_{2} = (\sum_{a = 1}^{p} v_{a}^{2})^{1 / 2}$ ; for the $k$ -nearest-neighbor option, each neighbor list orders candidates by increasing $(∥ x_{i} - x_{j} ∥_{2}, j)$ , so equal distances are broken by sample index. Construct the selected undirected graph and give each edge ${i, j}$ weight $∥ x_{i} - x_{j} ∥_{2}$ . If the graph is disconnected, return the status “disconnected” and do not claim finite all-pairs graph distances. If it is connected, define $d_{G} (i, j)$ as the minimum total edge weight over all paths from $i$ to $j$ ; because the graph is finite with nonnegative edge weights, a minimum occurs among its finitely many simple paths. Form the symmetric dissimilarity matrix $D_{G} = (d_{G} (i, j))$ and apply classical multidimensional scaling to $D_{G}$ with requested dimension $q$ . This finite procedure makes no guarantee that graph distances accurately approximate manifold geodesics or that the output recovers a manifold.

Definition references

Deterministic neighbor lists, radius graphs, and symmetrizations

Classical multidimensional scaling

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 572–574

Cameron, Linear and Nonlinear Dimensionality Reduction, §6, PDF pp. 9–13

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Metric distance-stress multidimensional scaling

Definition

For a symmetric nonnegative zero-diagonal dissimilarity matrix $D \in R^{n \times n}$ , $n \geq 2$ , and a target dimension $q \geq 1$ , use the Euclidean norm $∥ v ∥_{2} = (\sum_{a = 1}^{q} v_{a}^{2})^{1 / 2}$ . The metric stress of centered coordinates $Y = (y_{1}^{T}, \dots, y_{n}^{T})^{T} \in R^{n \times q}$ , with $1_{n}^{T} Y = 0$ , is

$S_{D} (Y) : = \sum_{1 \leq i < j \leq n} (D_{i j} - ∥ y_{i} - y_{j} ∥_{2})^{2} .$

Metric stress MDS is the separate optimization problem of minimizing $S_{D} (Y)$ over such centered $Y$ . It is a distance-based, generally nonconvex objective and does not define the positive-eigenvalue solution used by classical multidimensional scaling; no solver convergence or global-optimizer guarantee is part of this definition.

Definition references

Classical multidimensional scaling

Hastie, Tibshirani, and Friedman, ESL II, §14.8, printed pp. 570–571

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite locally linear embedding with minimum-norm weights and a simple constant kernel

Definition

Input: a data matrix $X \in R^{n \times p}$ with $n \geq 2$ , a neighbor count $1 \leq k < n$ , and an output dimension $1 \leq q < n$ , using $∥ v ∥_{2} = (\sum_{a = 1}^{p} v_{a}^{2})^{1 / 2}$ . For every row point $x_{i}$ , select the first $k$ other sample indices ordered by $(∥ x_{i} - x_{j} ∥_{2}, j)$ and use the minimum-Euclidean-norm affine least-squares weights on that neighborhood, with weights summing to $1$ . Form $W \in R^{n \times n}$ by placing those weights in the selected columns of row $i$ and zeros elsewhere; every row of $W$ then sums to $1$ . If $\ker (I_{n} - W) \neq span {1_{n}}$ , return the status “constant kernel not isolated” and do not specify an embedding. Otherwise put $M = (I_{n} - W)^{T} (I_{n} - W)$ and return any $Y \in R^{n \times q}$ minimizing

$tr (Y^{T} M Y) subject to Y^{T} 1_{n} = 0, Y^{T} Y = I_{q},$

where $tr$ is the sum of diagonal entries. Equivalently, take orthonormal eigenvectors for the $q$ smallest positive eigenvalues of $M$ . Ties allow multiple outputs. This finite-matrix procedure makes no guarantee of manifold recovery or consistency.

Definition references

Deterministic finite neighbor selection

Minimum-norm affine reconstruction weights

Existence and uniqueness of the minimum-norm weights

Trace minimizers are the bottom positive eigenvectors under the kernel condition ↗

Trace as the sum of diagonal entries

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 573–575

Cameron, Linear and Nonlinear Dimensionality Reduction, §7, PDF pp. 13–16

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Under the simple constant-kernel condition, LLE trace minimizers are bottom positive eigenvectors

Statement

Let $W \in R^{n \times n}$ satisfy $W 1_{n} = 1_{n}$ , put $M = (I_{n} - W)^{T} (I_{n} - W)$ , and assume $\ker (I_{n} - W) = span {1_{n}}$ . Let $0 < μ_{1} \leq \dots \leq μ_{n - 1}$ be the eigenvalues of $M$ restricted to the zero-sum subspace $1_{n}^{⊥}$ . For $1 \leq q < n$ , the minimum of $tr (Y^{T} M Y)$ over $Y \in R^{n \times q}$ with $Y^{T} 1_{n} = 0$ and $Y^{T} Y = I_{q}$ is $\sum_{j = 1}^{q} μ_{j}$ . The minimum is attained by taking the columns of $Y$ to be orthonormal eigenvectors for the $q$ smallest positive eigenvalues; when eigenvalues tie, the minimizing subspace may vary inside the tied eigenspace. The trace is the sum of diagonal entries.

Statement references

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 573–574

Cameron, Linear and Nonlinear Dimensionality Reduction, §7, PDF pp. 15–16

von Luxburg, A Tutorial on Spectral Clustering, §5.2, PDF pp. 11–12

Facts & Assumptions

Given: A real matrix $W$ with row sums one, so $W 1_{n} = 1_{n}$ , the matrix $M = (I_{n} - W)^{T} (I_{n} - W)$ , the simple-kernel hypothesis $\ker (I_{n} - W) = span {1_{n}}$ , and $1 \leq q < n$ .

[F1]

LLE forms $M = (I_{n} - W)^{T} (I_{n} - W)$ from a matrix $W$ whose rows sum to one and minimizes $tr (Y^{T} M Y)$ subject to $Y^{T} 1_{n} = 0$ and $Y^{T} Y = I_{q}$ (Finite locally linear embedding with minimum-norm weights and a simple constant kernel).

[F2]

The standard real coordinate inner product is $⟨ a, b ⟩ = \sum_{i < n} a_{i} b_{i}$ (The standard formulas $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and $\sum_{k < n} x_{k} \overline{y_{k}}$ on $C^{n}$ are inner products).

[F3]

The subspace $1_{n}^{⊥}$ has an orthonormal basis (Every finite-dimensional real or complex inner product space has an orthonormal basis).

[F4]

The space decomposes as $R^{n} = span {1_{n}} \oplus 1_{n}^{⊥}$ (For a subspace $W$ of a finite-dimensional inner product space, $V = W \oplus W^{⊥}$ ).

[F5]

For a real symmetric matrix, maximizing $tr (Q^{T} A Q)$ over orthonormal q-frames gives the sum of its q largest eigenvalues, with the stated tie-space equality cases (The maximum trace over q-dimensional orthonormal frames is the sum of the top q eigenvalues).

[F6]

The trace of a square matrix is the sum of its diagonal entries (The trace $tr (A)$ as the sum of the diagonal entries).

[F7]

A self-adjoint endomorphism of a finite-dimensional real inner-product space has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

Proof

1.1givenF1F2algebra

Put $A = I_{n} - W$ . Then $A 1_{n} = 0$ by [F1], and $M = A^{T} A$ is symmetric with $M 1_{n} = 0$ . For every $v$ , $v^{T} M v = (A v)^{T} (A v) = \sum_{r} (A v)_{r}^{2} \geq 0$ by [F2]. Also $M v = 0$ implies $0 = v^{T} M v = \sum_{r} (A v)_{r}^{2}$ , hence $A v = 0$ ; conversely $A v = 0$ implies $M v = 0$ . Therefore $\ker M = \ker A = span {1_{n}}$ .

2.1step 1.1F2F3F4F7algebra

By [F4], $R^{n} = span {1_{n}} \oplus S$ for $S = 1_{n}^{⊥}$ , and [F3] gives an orthonormal basis matrix $E \in R^{n \times (n - 1)}$ for $S$ . Symmetry and $M 1_{n} = 0$ imply $M (S) \subseteq S$ , because $1_{n}^{T} M v = (M 1_{n})^{T} v = 0$ for $v \in S$ . The restriction is self-adjoint and has matrix $R = E^{T} M E$ , which is symmetric and positive definite: if $c \neq 0$ , then $E c \in S ∖ {0}$ , so $E c \notin \ker M$ by step 1.1 and $c^{T} R c = (E c)^{T} M (E c) = \sum_{r} (A E c)_{r}^{2} > 0$ . By [F7], the restriction has an orthonormal eigenbasis; for each unit eigenvector with eigenvalue $μ$ , positive definiteness gives $μ > 0$ . List its eigenvalues as $0 < μ_{1} \leq \dots \leq μ_{n - 1}$ .

3.1step 2.1F5F6algebra

For every feasible $Y$ , its columns lie in $S$ , so $Y = E Q$ with $Q = E^{T} Y$ and $Q^{T} Q = I_{q}$ . Substitution gives $Y^{T} M Y = Q^{T} R Q$ , hence $tr (Y^{T} M Y) = tr (Q^{T} R Q)$ by [F6]. Apply [F5] to $- R$ , whose eigenvalues in descending order are $- μ_{1} \geq \dots \geq - μ_{n - 1}$ . It follows that $tr (Q^{T} R Q) \geq \sum_{j = 1}^{q} μ_{j}$ , with equality exactly for the q-dimensional bottom eigenspaces, including arbitrary choices inside a tie.

4.1step 2.1step 3.1F3F5∎

Taking $Q$ to have orthonormal columns spanning q bottom eigendirections of $R$ and setting $Y = E Q$ satisfies both constraints and attains the bound in step 3.1. This proves the minimum and its equality cases.

4 · Examples, counterexamples and false statements

None yet.

PCA, kernel PCA, MDS, and manifold embeddings

2 · Logical flowchart

3 · Definitions, theorems and proofs

Finite centering matrices and centered data

Definition

Definition references

The maximum trace over q-dimensional orthonormal frames is the sum of the top q eigenvalues

Statement

Statement references

Facts & Assumptions

Proof

Finite configurations with equal Gram matrices have isometric linear spans

Statement

Statement references

Facts & Assumptions

Proof

Deterministic finite nearest-neighbor lists and graph symmetrizations

Definition

Definition references

The finite centering matrix is the orthogonal projection onto the zero-sum subspace

Statement

Statement references

Facts & Assumptions

Proof

Rank-q principal component analysis by Frobenius reconstruction error

Definition

Definition references

Kernel principal component analysis for a finite positive-semidefinite Gram matrix

Definition

Definition references

Classical multidimensional scaling from a finite dissimilarity matrix

Definition

Definition references

Minimum-norm affine reconstruction weights for a finite LLE neighborhood

Definition

Definition references

The top right singular subspace minimizes rank-q PCA Frobenius reconstruction error

Statement

Statement references

Facts & Assumptions

Proof

Double-centering a finite positive-semidefinite Gram matrix preserves positive semidefiniteness

Statement

Statement references

Facts & Assumptions

Proof

Double-centering Euclidean squared distances recovers their centered Gram matrix

Statement

Statement references

Facts & Assumptions

Proof

Finite LLE affine least-squares weights have a unique minimum-norm minimizer

Statement

Statement references

Facts & Assumptions

Proof

Finite ISOMAP with deterministic neighborhoods and connected-graph shortest paths

Definition

Definition references

Metric distance-stress multidimensional scaling

Definition

Definition references

Finite locally linear embedding with minimum-norm weights and a simple constant kernel

Definition

Definition references

Under the simple constant-kernel condition, LLE trace minimizers are bottom positive eigenvectors

Statement

Statement references

Facts & Assumptions

Proof

4 · Examples, counterexamples and false statements

Sources