Nyström Approximation Bounds for Gaussian Kernels

Definitions and mathematical statement

The supplied record leaves the ambient domain and norm unspecified. Write $\mathcal D$ for the intended domain on which the expression $\lVert x-y\rVert$ is defined. For a positive bandwidth $\sigma>0$, the usual interpretation of the displayed Gaussian kernel is \[ k_\sigma(x,y)=\exp\!\left(-\frac{\lVert x-y\rVert^2}{2\sigma^2}\right),\qquad x,y\in\mathcal D. \] Positivity of the bandwidth is an explicit interpretive condition here; the supplied statement does not specify the bandwidth's domain or whether it varies asymptotically.

For finite ordered point lists $A=(a_i)_{i=1}^{p}$ and $B=(b_j)_{j=1}^{q}$ in $\mathcal D$, define \[ K(A,B)=\left(k_\sigma(a_i,b_j)\right)_{1\le i\le p,\,1\le j\le q}. \] In particular, write $X=(x_i)_{i=1}^{n}$ and $Z=(z_j)_{j=1}^{r}$. If $K(Z,Z)$ is invertible, define the approximation and its residual by \[ \widehat K_{X,Z}=K(X,Z)K(Z,Z)^{-1}K(Z,X),\qquad R_{X,Z}=K(X,X)-\widehat K_{X,Z}. \] Invertibility is necessary for the supplied formula and is not guaranteed by any hypothesis supplied in the record.

The requested task is to establish an approximation theorem, asymptotic in a parameter $m$, for \[ K(X,X)\approx K(X,Z)K(Z,Z)^{-1}K(Z,X), \] with explicit dependence on $m,X,Z$. A possible way to express the requested quantitative information would be a bound \[ \lVert R_{X,Z}\rVert_{\star}\le B(m,X,Z;\sigma), \] where the matrix norm, admissible configurations, bound, and required asymptotic behavior must be specified. This inequality is only a schematic description of the requested result, not a theorem asserted by this draft. The source does not define $m$, relate it to $n$ or $r$, specify how $X,Z$ vary with $m$, or define the meaning of $\approx$. Its literature assessment also refers to specific hypotheses involving $M,X,Z$, but neither $M$ nor those hypotheses are supplied. Consequently, a fully quantified mathematical statement cannot be recovered from this record alone.

Short English statement

The problem asks for a quantitative approximation of a Gaussian kernel matrix using the displayed Nyström formula, with explicit dependence on $m,X,Z$. The meaning of $m$, the ambient geometry, the conditions on the point configurations, and the required error criterion are missing, so the intended asymptotic theorem remains unresolved.

Sources

• Local UnsolvedMath registry, supplied record with permanent ID $30002680$, title Nyström Approximation Bounds for Gaussian Kernels, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2014. The record describes the material as collected from Oberwolfach Reports workshop discussions.
• Supplied source citation: Mini-Workshop: Asymptotic Statistics on Stratified Spaces (2015), Oberwolfach Reports, pp. 2481--2527, DOI 10.4171/owr/2014/44. https://doi.org/10.4171/owr/2014/44. Also listed among the literature sources as Oberwolfach Report 44/2014. The supplied title's year 2015 differs from the recorded proposed year and report designation 2014; this discrepancy is unresolved.
• Supplied literature source: Memory Efficient Kernel Approximation. https://jmlr.csail.mit.edu/papers/volume18/15-025/15-025.pdf.
• Literature assessment dated exactly 2026-08-21: supplied dated curation, not independently verified. The record labels the problem partially solved and reports that Nyström and related kernel-matrix literature provides general low-rank constructions and Gaussian-kernel error analyses, while a complete theorem with the report's specific $M,X,Z$ hypotheses was not identified. The background describes this as dated literature triage derived from supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified, with the explanation that mathematical content was preserved while notation, typography, or omitted definitions were repaired for publication. This is a supplied editorial assertion, not independent mathematical or source verification by this draft.