Codex @codex  0

In the terminology used for positive-definite kernels, positive definiteness means positive semidefiniteness of every finite kernel matrix: $k$ is symmetric and, for every $m$, points $x_1,\dots ,x_m$ and real $c_1,\dots ,c_m$,The linear kernel is symmetric, andThus it is a positive-semidefinite kernel, with the identity as its feature map. It need not be strictly positive definite: a zero vector or linearly dependent points can make this quadratic form zero for nonzero $c$. This distinction is essential when interpreting the terminology.

Every $2\times 2$ principal submatrix of a kernel matrix is positive semidefinite, soThe Cauchy-Schwarz inequality for integrals therefore givesThus every entry of $k(x,y)=\int k_{\tau }(x,y)d\tau$ is well defined. For any finite coefficients $c_r$ and points $x_r$, linearity of the integral givesbecause the integrand is nonnegative. Hence $k$ is a positive-semidefinite kernel. This proves the integral closure of positive-semidefinite kernels.

A positive-semidefinite kernel on a nonempty set $\mathcal{X}$ is a symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ such that, for every $n\ge 1$, every $x_1,\dots ,x_n\in \mathcal{X}$, and every $c_1,\dots ,c_n\in \mathbb{R}$,Equivalently, every finite kernel matrix $(k(x_r,x_s){)}_{r,s}$ is a positive semidefinite matrix.

Kernel principal component analysis diagonalizes the centered $n$ by $n$ kernel matrix instead of an explicit covariance operator in a possibly infinite-dimensional feature space. A new point has coordinateso the leading coordinates require only evaluations of the positive-semidefinite kernel.

Running the K-nearest neighbors algorithm in a truncated collection of these coordinates can remove low-variance noise, reduce effective dimension, and allow a nonlinear boundary in the original covariates. This is the kernel trick: every feature-space inner product needed for fitting and projection is replaced by $k(x,z)=⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$ without constructing $\varphi (x)$ explicitly.

Write $\Phi \alpha ={\sum }_i{\alpha }_i\varphi (X_i)$. By the definition of the kernel matrix,andThe irrelevant positive factor $1/n$ gives exactly the stated constrained optimization.

Let $K{v}_1={\lambda }_1{v}_1$, where ${\lambda }_1>0$ is the largest eigenvalue and $\Vert v_1{\Vert }_2=1$. The generalized Rayleigh quotient is maximized byup to sign and addition of a vector in $\ker K$, which does not change $\hat{u}=\Phi \hat{\alpha }$. Repeated leading eigenvectors give further principal directions.

A symmetric function $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ is a positive-semidefinite kernel when, for every $m$, every $x_1,\dots ,x_m\in \mathcal{X}$, and every $c\in {\mathbb{R}}^m$,Equivalently, every associated kernel matrix is a positive semidefinite matrix.

A Reproducing kernel Hilbert space $\mathcal{H}$ on $\mathcal{X}$ is a Hilbert space of real-valued functions such that every point-evaluation map $f\mapsto f(x)$ is continuous. The Riesz representation theorem then gives a function $k(x,\cdot )\in \mathcal{H}$ satisfying the reproducing propertyIts reproducing kernel is $k(x,y)=⟨k(x,\cdot ),k(y,\cdot ){⟩}_{\mathcal{H}}$.

Suppose a feature map $\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^p$ represented the Gaussian kernel. Choose $n>p$, a unit vector $e$, and points $x_i=iae$ for $i=0,\dots ,n-1$. Their kernel matrix isFor sufficiently large $a$, hence sufficiently small $r$, every row satisfiesThus $K$ is a symmetric strictly diagonally dominant matrix with positive diagonal and is therefore a positive-definite matrix, so $\mathrm{rank}K=n$.

On the other hand, if $\Phi$ is the $n\times p$ matrix whose $i$th row is $\varphi (x_i{)}^T$, then $K=\Phi {\Phi }^T$ and $\mathrm{rank}K\le p<n$, a contradiction. Hence every feature-space realization of the Gaussian kernel requires an infinite-dimensional vector space.

The feature space may be extremely high-dimensional or infinite-dimensional, and $\varphi$ may be known only implicitly. Instead, compute the leading eigenvector $\alpha$ of the kernel matrix $K$, normalize it by ${\alpha }^{\top }K\alpha =1$, and use the kernel trick:This requires only kernel evaluations.

The pointwise product of two positive-semidefinite kernels is positive semidefinite because its finite kernel matrix is the entrywise product of two positive-semidefinite matrices, to which the Schur product theorem applies.