TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

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.

Depends on

Used by

A rank-one centered data matrix is reconstructed exactly by rank-one PCA Example

Cited to discharge well-definedness by Rank-q principal component analysis by Frobenius reconstruction error.

Dependency tree · two levels

36 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

The Elements of Statistical Learning, second edition, corrected 12th printing (standard reference, not scraped)
Maria Cameron, Linear and Nonlinear Dimensionality Reduction, lecture notes (standard reference, not scraped)