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

Kernel ridge predictions are stable under Gram-matrix perturbations

Statement

Let $K, \tilde{K} \in R^{n \times n}$ be symmetric matrices such that $x^{T} K x \geq 0$ and $x^{T} \tilde{K} x \geq 0$ for every $x \in R^{n}$ , with $n \geq 1$ , let $y \in R^{n}$ , and let $τ > 0$ . Write $I_{n}$ for the identity matrix. For $G \in {K, \tilde{K}}$ define $a_{G} = (G + τ I_{n})^{- 1} y$ and $u_{G} = G a_{G}$ . Define $∥ x ∥_{2} = (\sum_{i} x_{i}^{2})^{1 / 2}$ for vectors and $∥ M ∥_{2} = \sup_{∥ x ∥_{2} = 1} ∥ M x ∥_{2}$ for matrices. If $∥ K - \tilde{K} ∥_{2} \leq δ$ for some $δ \geq 0$ , then

$∥ a_{K} - a_{\tilde{K}} ∥_{2} \leq \frac{δ ∥ y ∥_{2}}{τ^{2}}, ∥ u_{K} - u_{\tilde{K}} ∥_{2} \leq \frac{δ ∥ y ∥_{2}}{τ} .$

In particular, let $S \in R^{n \times s}$ with $s \geq 0$ and $\tilde{K} = K S (S^{T} K S)^{†} S^{T} K$ , where $M^{†}$ denotes the unique matrix satisfying the four Moore–Penrose equations. Choose $0 \leq r \leq n$ and an orthogonal eigenbasis $K = U diag (λ_{1}, \dots, λ_{n}) U^{T}$ with $U^{T} U = I_{n}$ and $λ_{1} \geq \dots \geq λ_{n} \geq 0$ . Write $U = (U_{1} U_{2})$ with the first $r$ eigenvectors in $U_{1}$ , let $Λ_{2} = diag (λ_{r + 1}, \dots, λ_{n})$ and $Λ_{2}^{1 / 2} = diag (\sqrt{λ_{r + 1}}, \dots, \sqrt{λ_{n}})$ , and set $Ω_{1} = U_{1}^{T} S$ and $Ω_{2} = U_{2}^{T} S$ . If $Ω_{1}$ has full row rank, meaning $rank (Ω_{1}) = r$ , with the empty-row convention when $r = 0$ , then the same bounds hold with $δ = λ_{r + 1} + ∥ Λ_{2}^{1 / 2} Ω_{2} Ω_{1}^{†} ∥_{2}^{2}$ , using $λ_{n + 1} = 0$ and zero norm for empty blocks.

Statement references

Regularized kernel prediction system: The systems use $a_{G} = (G + τ I)^{- 1} y$ and $u_{G} = G a_{G} = y - τ a_{G}$ .

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

The Nyström approximation is positive semidefinite.

Under the full-row-rank leading-sketch hypothesis, the displayed deterministic spectral residual bound holds.

The Moore–Penrose inverse is the unique matrix satisfying the four Penrose equations.

Facts & Assumptions

Given: Positive-semidefinite matrices $K, \tilde{K}$ , vector $y$ , scalar $τ > 0$ , and the norm error $∥ K - \tilde{K} ∥_{2} \leq δ$ in the Statement.

[F1]

Regularized kernel prediction system: for a positive-semidefinite matrix $G$ , $a_{G} = (G + τ I_{n})^{- 1} y$ and $u_{G} = G a_{G} = y - τ a_{G}$ .

[F2]

Inverse norm bound for a regularized Gram matrix: $G + τ I_{n}$ is invertible, $∥ (G + τ I_{n})^{- 1} ∥_{2} \leq 1 / τ$ , and the two shifted inverses satisfy the resolvent identity.

[F3]

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

[F4]

Nyström is positive semidefinite, dominated by A, and exact when it captures the range: every such $\tilde{K}$ is positive semidefinite.

[F5]

Nyström deterministic spectral residual bound under a full-row-rank leading sketch: if $Ω_{1}$ has full row rank, then $∥ K - \tilde{K} ∥_{2} \leq λ_{r + 1} + ∥ Λ_{2}^{1 / 2} Ω_{2} Ω_{1}^{†} ∥_{2}^{2}$ under the eigenbasis and block definitions in the Statement.

Proof

1.1givenF2algebra

Put $A = K + τ I_{n}$ and $B = \tilde{K} + τ I_{n}$ . By [F2], both inverses exist and have norm at most $1 / τ$ .

2.1givenF1step 1.1algebra

The resolvent identity gives $a_{K} - a_{\tilde{K}} = (A^{- 1} - B^{- 1}) y = A^{- 1} (\tilde{K} - K) B^{- 1} y$ . Taking norms and applying the bounds from step 1.1 and the assumed Gram error gives $∥ a_{K} - a_{\tilde{K}} ∥_{2} \leq δ ∥ y ∥_{2} / τ^{2}$ .

3.1F1step 2.1algebra

By [F1], $u_{K} = y - τ a_{K}$ and $u_{\tilde{K}} = y - τ a_{\tilde{K}}$ . Subtracting these equalities and using step 2.1 gives $∥ u_{K} - u_{\tilde{K}} ∥_{2} = τ ∥ a_{K} - a_{\tilde{K}} ∥_{2} \leq δ ∥ y ∥_{2} / τ$ .

4.1givenF3F4F5step 2.1step 3.1algebra∎

In the Nyström case, [F4] supplies positive semidefiniteness of $\tilde{K}$ , and [F5] supplies the stated value of $δ$ whenever $Ω_{1}$ has full row rank. Substituting that bound into steps 2.1 and 3.1 proves the conditional Nyström conclusion.

Depends on

Used by

Dependency tree · two levels

16 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

Alex Gittens and Michael W. Mahoney, Revisiting the Nyström Method, §4.1.1 (standard reference, not scraped)
Per-Gunnar Martinsson and Joel A. Tropp, Randomized Numerical Linear Algebra: Foundations & Algorithms, §14.2 (standard reference, not scraped)