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.

Exact Nyström capture gives the exact kernel ridge fit

Example

Let $K = diag (4, 1)$ , $S = I_{2}$ , $y = (p, q)^{T}$ , and $τ > 0$ . The Nyström matrix is $\tilde{K} = K$ , and the original and sketched coefficient vectors and fitted vectors are both $((4 + τ)^{- 1} p, (1 + τ)^{- 1} q)^{T}$ and $(4 (4 + τ)^{- 1} p, (1 + τ)^{- 1} q)^{T}$ , respectively.

Example references

The positive-semidefinite Nyström approximation: The Nyström matrix is $K S (S^{T} K S)^{†} S^{T} K$ .

A Nyström matrix is exact when the sketch captures the range of the Gram matrix.

A zero Gram-matrix perturbation gives identical coefficients and training fits.

Facts & Assumptions

Given: $K = diag (4, 1)$ , $S = I_{2}$ , $y = (p, q)^{T}$ , and $τ > 0$ .

[A1]

The finite matrix, sketch, response, and shift are those stated in the Example.

[F1]

The positive-semidefinite Nyström approximation: $\tilde{K} = K S (S^{T} K S)^{†} S^{T} K$ .

[F2]

Nyström is positive semidefinite, dominated by A, and exact when it captures the range: if $Ran (K S) = Ran (K)$ , then $\tilde{K} = K$ .

[F3]

Regularized kernel prediction system: for $G ⪰ 0$ , $a_{G} = (G + τ I)^{- 1} y$ and $u_{G} = G a_{G}$ .

[F4]

Kernel ridge predictions are stable under Gram-matrix perturbations: a Gram perturbation of norm $δ$ gives coefficient error at most $δ ∥ y ∥_{2} / τ^{2}$ and fitted-vector error at most $δ ∥ y ∥_{2} / τ$ .

Verification

Given: The matrix and sketch in [A1].

1.1givenA1F1F2algebra

Since $S = I_{2}$ , $K S = K$ , hence $Ran (K S) = Ran (K)$ . By [F2], the Nyström matrix equals $K$ .

2.1givenF3F4step 1.1algebra∎

The shifted matrix is $K + τ I_{2} = diag (4 + τ, 1 + τ)$ , so its inverse gives $a_{K} = ((4 + τ)^{- 1} p, (1 + τ)^{- 1} q)^{T}$ and multiplication by $K$ gives the displayed fitted vector. Step 1.1 makes the same calculations apply to $\tilde{K}$ , while [F4] with $δ = 0$ confirms both errors vanish.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 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, §14.2 (standard reference, not scraped)