LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge 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 ridge leave-one-out identity yields the generalized cross-validation score

Statement

Let $A \in R^{m \times n}$ with $m \geq 1$ , let $b \in R^{m}$ , and let $λ > 0$ . Define $x_{λ} = (A^{T} A + λ I)^{- 1} A^{T} b, H_{λ} = A (A^{T} A + λ I)^{- 1} A^{T},$ so the fitted vector is $H_{λ} b$ . For row $a_{i}^{T}$ of $A$ , let $x_{λ}^{(- i)}$ be the same Tikhonov minimizer after deleting row $i$ and entry $b_{i}$ . Then $1 - (H_{λ})_{i i} > 0$ and $b_{i} - a_{i}^{T} x_{λ}^{(- i)} = \frac{((I - H_{λ}) b)_{i}}{1 - (H_{λ})_{i i}} .$ Consequently exact leave-one-out squared prediction error is $\sum_{i = 1}^{m} {(\frac{((I - H_{λ}) b)_{i}}{1 - (H_{λ})_{i i}})}^{2},$ and its mean over the $m$ observations is $1 / m$ times this sum. Replacing every diagonal leverage $(H_{λ})_{i i}$ in the mean by their average $tr (H_{λ}) / m$ gives the GCV score $GCV (λ) = \frac{∥ (I - H_{λ}) b ∥^{2}}{m (1 - tr (H_{λ}) / m)^{2}} .$ This trace-average replacement is the GCV approximation. As a function of the data, it equals the exact mean leave-one-out squared prediction error exactly when all diagonal entries of $H_{λ}$ are equal; for a particular data vector the two scores may coincide accidentally. When the diagonal entries are equal, the unnormalized leave-one-out sum is $m$ times the GCV score.

Facts & Assumptions

Given: A real matrix $A \in R^{m \times n}$ , $m \geq 1$ , data $b \in R^{m}$ , a parameter $λ > 0$ , and the standard Tikhonov solution after any row deletion.

[F1]

The Tikhonov regularised least-squares objective $∥ A x - b ∥_{2}^{2} + λ ∥ x ∥_{2}^{2}$ for $λ > 0$ : For finite matrices, the Tikhonov objective is $∥ A x - b ∥^{2} + λ ∥ x ∥^{2}$ .

[F2]

For every $λ > 0$ , the Tikhonov objective is strictly convex and has the unique minimiser $(A^{*} A + λ I)^{- 1} A^{*} b$ : Its unique minimizer is $(A^{T} A + λ I)^{- 1} A^{T} b$ .

[F3]

Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition: The singular value decomposition gives orthonormal left and right singular vectors and nonnegative singular values.

Proof

1.1givenF1F2F3algebra

Put $G = A^{T} A + λ I$ . For every nonzero $z$ , $z^{T} G z = ∥ A z ∥^{2} + λ ∥ z ∥^{2} > 0$ , so $G$ is positive definite and invertible; [F1]–[F2] give $x_{λ} = G^{- 1} A^{T} b$ . The SVD [F3] shows $H_{λ}$ has eigenvalues $σ_{j}^{2} / (σ_{j}^{2} + λ)$ on the left singular vectors and zero on their orthogonal complement. Every eigenvalue is in $[0, 1)$ , so $I - H_{λ}$ is positive definite and $1 - (H_{λ})_{i i} > 0$ for every coordinate vector.

2.1givenstep 1.1algebra

Fix $i$ , write $a = a_{i}$ , $h = a^{T} G^{- 1} a = (H_{λ})_{i i}$ , and $G_{-} = G - a a^{T} = A_{- i}^{T} A_{- i} + λ I$ . The same positive-definiteness argument makes $G_{-}$ invertible. Direct multiplication verifies $G_{-}^{- 1} = G^{- 1} + G^{- 1} a a^{T} G^{- 1} / (1 - h)$ ; the denominator is positive by step 1.1. Substituting $A^{T} b - a b_{i}$ for the reduced right-hand side and simplifying gives $x_{λ}^{(- i)} = x_{λ} - G^{- 1} a ((I - H_{λ}) b)_{i} / (1 - h)$ . Multiplying by $a^{T}$ and using $a^{T} G^{- 1} a = h$ yields the stated deleted residual identity.

3.1step 1.1step 2.1algebra∎

Squaring the deleted residual identity and summing over $i$ proves the exact leave-one-out sum; dividing by $m$ gives its mean. Replacing all $h_{i} = (H_{λ})_{i i}$ by $\overset{ˉ}{h} = m^{- 1} \sum_{i} h_{i} = tr (H_{λ}) / m$ in that mean gives $m^{- 1} \sum_{i} ((I - H_{λ}) b)_{i}^{2} / (1 - \overset{ˉ}{h})^{2} = ∥ (I - H_{λ}) b ∥^{2} / [m (1 - \overset{ˉ}{h})^{2}]$ , the displayed design convention for GCV. If all $h_{i} = \overset{ˉ}{h}$ , the exact mean has the same formula. Conversely, if the exact mean and GCV agree for every $b$ , then $z = (I - H_{λ}) b$ ranges over all of $R^{m}$ because step 1.1 makes $I - H_{λ}$ positive definite and hence invertible. Equality of the two diagonal quadratic forms for all $z$ forces $(1 - h_{i})^{- 2} = (1 - \overset{ˉ}{h})^{- 2}$ for every $i$ ; all terms $1 - h_{i}$ are positive by step 1.1, so $h_{i} = \overset{ˉ}{h}$ for every $i$ . This is equality as formulas in the data; individual data vectors may yield accidental equality.

Depends on

Used by

Dependency tree · two levels

9 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

Per Christian Hansen, Introduction to Inverse Problems, Chapter 5: Regularization Parameter Choice (standard reference, not scraped)