ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

A training Gram matrix does not determine a test prediction

Example

On the two-point set ${x, z}$ , put $ϕ_{0} (x) = e_{1}$ , $ϕ_{0} (z) = e_{2}$ , $ϕ_{1} (x) = e_{1}$ , and $ϕ_{1} (z) = (1 / 2, \sqrt{3} / 2)^{T}$ , where $e_{1}, e_{2}$ are the standard basis vectors of $R^{2}$ . For $j \in {0, 1}$ , define $k_{j} (s, t) = ϕ_{j} (s)^{T} ϕ_{j} (t)$ and let $H_{j} = {f_{v} : v \in R^{2}}$ , where $f_{v} (t) = v^{T} ϕ_{j} (t)$ and $⟨ f_{v}, f_{w} ⟩_{H_{j}} = v^{T} w$ . Each feature pair is linearly independent, so this defines a real Hilbert space of functions; its kernel sections are $k_{j} (\cdot, s) = f_{ϕ_{j} (s)}$ and reproduce evaluation. Thus $H_{j}$ is an actual real RKHS for $k_{j}$ , and the corresponding matrices in the order $(x, z)$ are $G_{0} = (\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array})$ and $G_{1} = (\begin{array}{cc} 1 & 1 / 2 \\ 1 / 2 & 1 \end{array})$ . With the single training point $x$ , response $y = 1$ , and shift $τ > 0$ , both training Gram matrices are $[1]$ and both coefficient vectors equal $1 / (1 + τ)$ . The two exact test predictions $k_{j} (z, x) a_{j}$ are $0$ and $1 / (2 (1 + τ))$ , respectively.

For a rank-one Nyström approximation of $G_{0}$ , use the sketch $S = (1, 1 / 10)^{T}$ . The Nyström matrix is

$\tilde{K} = G_{0} S (S^{T} G_{0} S)^{†} S^{T} G_{0} = (\begin{array}{cc} 100 / 101 & 10 / 101 \\ 10 / 101 & 1 / 101 \end{array}) .$

With training point $x$ , response $1$ , and $τ = 1$ , the exact test prediction for $G_{0}$ is $0$ , whereas the Nyström coefficient is $\tilde{a} = (100 / 101 + 1)^{- 1} = 101 / 201$ and its test prediction is ${\tilde{K}}_{z x} \tilde{a} = 10 / 201$ . The training Gram error is $1 / 101$ , and the training fitted-value error is $∣ 1 / 2 - 100 / 201 ∣ = 1 / 402$ , while the test-prediction error is $10 / 201$ .

Example references

The training coefficient solves the shifted Gram system.

The Nyström matrix is formed by the positive-semidefinite compression formula.

The training coefficient gives the unique RKHS minimizer for each PSD kernel.

Facts & Assumptions

Given: The two-point set, feature vectors, RKHS constructions, Gram matrices, training points, responses, shifts, and rank-one Nyström sketch in the Example.

[A1]

The feature maps, finite RKHSs, matrices $G_{0}, G_{1}$ , training input $x$ , test input $z$ , responses, shifts, and sketch are exactly those stated in the Example.

[F1]

Positive semidefinite kernels and reproducing kernel Hilbert spaces: a real kernel is positive semidefinite when it is symmetric and every finite Gram quadratic form is nonnegative; an RKHS has reproducing kernel sections.

[F2]

Regularized kernel prediction system: the coefficient for a training Gram matrix $K$ is $(K + τ I)^{- 1} y$ .

[F3]

The positive-semidefinite Nyström approximation: for a PSD matrix $K$ and a finite sketch $S$ , the Nyström matrix is $K S (S^{T} K S)^{†} S^{T} K$ .

[F4]

The kernel ridge system uniquely minimizes the mean-square RKHS objective: for a real RKHS kernel, training list length $n$ , and $λ > 0$ , the coefficient with $τ = n λ$ gives the unique minimizer of the corresponding mean-square RKHS objective.

Verification

Given: The matrices and training setup in [A1].

1.1givenA1F1algebra

For each $j$ , the feature vectors $ϕ_{j} (x), ϕ_{j} (z)$ are linearly independent. Hence $v \mapsto f_{v}$ is injective, the stated inner product makes $H_{j}$ a complete two-dimensional real inner-product space, and $k_{j} (\cdot, s) = f_{ϕ_{j} (s)}$ satisfies $⟨ f_{v}, k_{j} (\cdot, s) ⟩_{H_{j}} = v^{T} ϕ_{j} (s) = f_{v} (s)$ . For any finite list $(t_{i})$ in ${x, z}$ and real coefficients $(c_{i})$ , $\sum_{i, j} c_{i} c_{j} k_{j} (t_{i}, t_{j}) = ∥ \sum_{i} c_{i} ϕ_{j} (t_{i}) ∥_{2}^{2} \geq 0$ . Thus each $k_{j}$ is a positive-semidefinite kernel with the displayed Gram matrix and an explicitly specified real RKHS.

2.1givenA1F2F4step 1.1algebra

For the training list consisting of $x$ , both training Gram matrices equal $[1]$ . By [F2], both shifted systems give coefficient $1 / (1 + τ)$ and training fitted value $1 / (1 + τ)$ . The list length is $n = 1$ , so setting $λ = τ > 0$ gives $τ = n λ$ ; the actual RKHSs established in step 1.1 let [F4] identify these coefficients with the unique kernel-ridge minimizers. The exact test predictions are $k_{0} (z, x) / (1 + τ) = 0$ and $k_{1} (z, x) / (1 + τ) = 1 / (2 (1 + τ))$ .

3.1givenA1F2F3step 2.1algebra∎

Since $G_{0} S = (1, 1 / 10)^{T}$ and $S^{T} G_{0} S = 101 / 100$ , [F3] gives the displayed rank-one matrix $\tilde{K}$ . Its training entry is $100 / 101$ , so [F2] gives $\tilde{a} = (100 / 101 + 1)^{- 1} = 101 / 201$ at $τ = 1$ . The approximate test prediction is $(10 / 101) (101 / 201) = 10 / 201$ ; the exact prediction under $G_{0}$ is zero. The training fitted-value difference is $∣ 1 / 2 - (100 / 101) (101 / 201) ∣ = ∣ 1 / 2 - 100 / 201 ∣ = 1 / 402$ , while the test-prediction difference is $10 / 201$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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-Gunnar Martinsson and Joel A. Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms, §19.1.6 (standard reference, not scraped)