TheoremStatement: 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.

Kernel ridge regression equals the Gaussian-process posterior mean

Statement

Assume AC. Let $T$ be a set, let $k : T \times T \to R$ be a symmetric kernel whose every finite Gram quadratic form is nonnegative, and let $m : T \to R$ . Let $H$ be a real Hilbert space of functions on $T$ such that, for every $x \in T$ , the section $k_{x} : T \to R$ , $k_{x} (t) = k (t, x)$ , belongs to $H$ and satisfies $h (x) = ⟨ h, k_{x} ⟩_{H}$ for every $h \in H$ . Assume $m \in H$ . For a nonempty finite ordered list $X = (x_{i})_{i = 1}^{n}$ (repetitions allowed), let $K = K_{X X} = (k (x_{i}, x_{j}))$ , $m_{X} = (m (x_{i}))$ , and take $y \in R^{n}$ and $σ > 0$ . On the affine space $m + H$ , define $J (g) = \sum_{i = 1}^{n} (y_{i} - g (x_{i}))^{2} + σ^{2} ∥ g - m ∥_{H}^{2} .$ Then $J$ has a unique minimizer $g_{*} = m + \sum_{i = 1}^{n} α_{i} k_{x_{i}}, α = (K + σ^{2} I_{n})^{- 1} (y - m_{X}) .$ Its evaluation vector is $(g_{*} (x_{i}))_{i = 1}^{n} = m_{X} + K (K + σ^{2} I_{n})^{- 1} (y - m_{X}) .$ Under AC, the mean and kernel determine a canonical cylinder-space Gaussian-process prior. If it is observed at $X$ with independent $N_{n} (0, σ^{2} I_{n})$ noise, this vector is the conditional mean of the latent evaluation vector given the observation $Y = y$ . The Hilbert-space existence and reproducing-section properties are hypotheses here; the theorem makes no general kernel-to-Hilbert-space existence claim.

Statement references

Rasmussen and Williams, GPML, Chapter 6 §§6.1–6.4, printed pp. 129–150

Hastie, Tibshirani, and Friedman, ESL, 2nd ed., §5.8, printed pp. 167–173

Treil, Linear Algebra Done Wrong, Chapter 5 §§5.3.2, 5.4.1

Facts & Assumptions

Given: AC; the kernel, real Hilbert space, reproducing-section identities, mean function $m \in H$ , finite list $X$ , response $y$ , and scalar $σ > 0$ in the Statement; and the Gaussian-process observation model for the final comparison.

[A1]

AC is the axiom used by the Gaussian-process and finite conditional-normal interfaces. The Axiom of Choice

[F1]

The observation model defines $K_{X X}$ , $m_{X}$ , and $Y = f_{X} + ε$ ; an independent Gaussian noise vector with covariance $R$ is added to the latent evaluations. Finite Gaussian-process regression observation model

[F2]

Every finite-dimensional subspace of a real inner-product space has an orthonormal basis, and projection onto it gives a unique orthogonal decomposition with the Pythagorean identity. Projection onto a finite-dimensional subspace of an inner-product space

[F3]

A finite-dimensional positive-semidefinite operator has a positive-semidefinite square root whose square is the operator. A non-negative operator has a unique non-negative square root

[F4]

For a linear map $C$ between finite-dimensional inner-product spaces, $β$ minimizes $∥ C β - b ∥$ exactly when $C^{*} (C β - b) = 0$ . 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$

[F5]

Under AC, the finite Gaussian-process posterior at test list $X_{*}$ has mean $m_{*} + K_{* X} (K_{X X} + R)^{- 1} (y - m_{X})$ when the observed covariance is positive definite. Finite Gaussian-process regression posterior and predictive law

[F6]

In the finite observation model, $K_{X X} + R$ is positive definite exactly when its ordinary inverse formulas are defined. Positive definiteness is exactly the inverse condition for the observed GP covariance

Proof

Given: The hypotheses in the Statement.

1.1F1givenconstructalgebra

Define the linear evaluation map $S : H \to R^{n}$ by $(S h)_{i} = h (x_{i})$ . It is bounded because $∥ S h ∥_{2}^{2} = \sum_{i} ∣ ⟨ h, k_{x_{i}} ⟩_{H} ∣^{2} \leq ∥ h ∥_{H}^{2} \sum_{i} ∥ k_{x_{i}} ∥_{H}^{2}$ . The reproducing identities then give its adjoint $S^{*} β = \sum_{i} β_{i} k_{x_{i}}$ , since $⟨ S h, β ⟩ = \sum_{i} β_{i} ⟨ h, k_{x_{i}} ⟩_{H} = ⟨ h, S^{*} β ⟩_{H}$ . Consequently $S S^{*} = K$ and $V = ran (S^{*}) = span {k_{x_{i}} : 1 \leq i \leq n}$ .

1.2F1F6givenalgebra

For every $c \in R^{n}$ , $c^{T} (K + σ^{2} I_{n}) c = c^{T} K c + σ^{2} ∥ c ∥^{2} \geq σ^{2} ∥ c ∥^{2}$ , because $K$ is a Gram matrix of the positive-semidefinite kernel. Hence $A = K + σ^{2} I_{n}$ is positive definite and, by [F6], its ordinary inverse exists. Put $r = y - m_{X}$ , $α = A^{- 1} r$ , and $h_{0} = S^{*} α$ .

2.1F2step 1.1givenalgebra

Write $g = m + h$ , so $J (m + h) = ∥ r - S h ∥^{2} + σ^{2} ∥ h ∥_{H}^{2}$ . By [F2], each $h$ decomposes uniquely as $p + q$ with $p \in V$ and $q ⊥ V$ . Then $S q = 0$ by the reproducing identities, and $∥ p + q ∥_{H}^{2} = ∥ p ∥_{H}^{2} + ∥ q ∥_{H}^{2}$ . Thus $J (m + p + q) = J (m + p) + σ^{2} ∥ q ∥_{H}^{2}$ , so minimization reduces to $V$ .

2.2F3F4step 1.1step 1.2algebra

Let $B = K^{1 / 2}$ be supplied by [F3], and define $C : R^{n} \to R^{n} \oplus R^{n}$ by $C β = (K β, σ B β)$ . For $h = S^{*} β$ , its objective is $∥ C β - (r, 0) ∥^{2}$ , because $S h = K β$ and $∥ S^{*} β ∥_{H}^{2} = β^{T} K β = ∥ B β ∥^{2}$ . The normal equation is $C^{*} C β = C^{*} (r, 0)$ , that is $(K^{2} + σ^{2} K) β = K r$ . Our $α$ satisfies it because $(K^{2} + σ^{2} K) α = K (K + σ^{2} I_{n}) α = K r$ . Therefore [F4] makes $h_{0}$ a minimizer on $V$ .

2.3step 1.1step 1.2algebra

For any $d \in H$ , $S h_{0} - r = K α - r = - σ^{2} α$ and $S^{*} (S h_{0} - r) = - σ^{2} h_{0}$ . Expanding both squared norms and using the adjoint identity gives $J (m + h_{0} + d) - J (m + h_{0}) = ∥ S d ∥^{2} + σ^{2} ∥ d ∥_{H}^{2}$ . This is nonnegative and is zero only for $d = 0$ , so the minimizer is unique on all of $H$ , not just on $V$ .

3.1A1F1F5step 1.2step 2.2∎

The minimizing function is $g_{*} = m + h_{0} = m + \sum_{i} α_{i} k_{x_{i}}$ , and $S h_{0} = K α$ , giving the displayed evaluation vector. For Gaussian observations with $R = σ^{2} I_{n}$ , [F5] at test list $X_{*} = X$ gives the same conditional-mean vector; $A = K + R ≻ 0$ by step 1.2, so its inverse hypothesis holds.

Depends on

Used by

Statistical and numerical limits of finite kernel solve guarantees Remark

Dependency tree · two levels

22 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

Carl Edward Rasmussen and Christopher K. I. Williams, Gaussian Processes for Machine Learning, Chapter 6 §§6.1–6.4 (standard reference, not scraped)
Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §5.8 (standard reference, not scraped)
Sergei Treil, Linear Algebra Done Wrong, Chapter 5 §§5.3.2, 5.4.1 (standard reference, not scraped)