8
$\begingroup$

This question is motivated by a question I'm facing in vector-valued kernel methods (also known as Gaussian Processes and co-krieging).

Suppose I have $N$ data $X := \{x_n\}_{n=1}^N$ , where each $x_n \in \mathbb{R}^D$. My question: Under what conditions or choices of kernel functions will the following hold?

$$k(x, X) \; k(X, X)^{-1} \; k(X, x) = k(x, x)$$

For example, I think the following is true: If we choose kernel $k(\cdot, \cdot)$ as a vanilla inner (i.e. dot) product and if I slightly abuse notation by referring to $X$ as a matrix in $\mathbb{R}^{N \times D}$, then we have:

$$k(x, X) \; k(X, X)^{-1} \; k(X, x) = x^T X^T (X X^T)^{-1} X x$$

and we know that this will simplify to $x^T x = k(x, x)$ iff $x$ lives in the row space of $X$.

  1. Is this correct?

  2. Are more general versions of this result possible?

I'd be happy to take clarifying questions!

$\endgroup$
6
  • $\begingroup$ Regarding your point 1, don't you need to assume that the Gram matrix is invertible? Which in turn requires $N \le D$ for the dot product kernel? $\endgroup$
    – Luca Citi
    Jan 6 at 1:16
  • $\begingroup$ I think the pseudoinverse suffices, no? If $x$ is in the row space of $X$, I think it should be preserved $\endgroup$ Jan 6 at 5:57
  • 1
    $\begingroup$ I see. If you change the inverse to a pseudoinverse, then I believe the statement is true when $N\ge D$ as long as $X$ is full rank. You can see it by taking the SVD of $X=UDV'$. $\endgroup$
    – Luca Citi
    Jan 6 at 8:56
  • 1
    $\begingroup$ More in general, if $X$ is full rank $r=\min(N,D)$, then $X=U\Sigma V'$ with $\Sigma$ diagonal $r\times r$ and invertible. Then $x' X' (XX')^{−1}Xx=x'VV'x$. If $N\ge D=r$ then this reduces to $x'x$. When $D \ge N=r$ then $V'$ is a wide matrix and $VV'$ is not the identity matrix so the condition in your title doesn't hold for general $x$ (i.e. a general test point not necessarily living in the space spanned by the training set $X$). $\endgroup$
    – Luca Citi
    Jan 6 at 10:36
  • 1
    $\begingroup$ Regarding your point 2, the considerations in the comment above still apply, albeit to the mapped space $\phi(x)$ rather than the original feature space $x$ (where $k(x,z)=\phi(x)'\phi(z)$. Since in most cases the kernel is chosen to nonlinearity map the original feature space into a higher dimensional one (making the new $D$ larger than $N$ even when the original $D$ wasn't), I think the condition in the title tends to not hold in practice in most cases. $\endgroup$
    – Luca Citi
    Jan 6 at 10:44

2 Answers 2

7
$\begingroup$

Consider the so-called kernel shift functions $k(.,\,x)$ and $k(.,\,x_i)$ for $i=1$ to $N$. These functions are defined on $\mathbb{R}^d$. Let $Y(u)$ a centered Gaussian Process with index $u \in \mathbb{R}^d$ and with covariance kernel $k$. let us assume for simplicity that $k(X,\,X)$ is invertible.

The condition of the OP, say (1), is equivalent to any of the two following

(2) The conditional variance $\text{Var}[Y(x) \,\vert\, Y(X) ]$ is zero i.e. $Y(x)$ can be perfectly predicted from $Y(X) := [Y(x_i)]_i$.

(3) The kernel shift $k(.,\,x)$ is a linear combination of the $N$ kernel shifts $k(.,\,x_i)$.

The equivalence of (1) and (2) is easily deduced from the expression of the so-called Kriging variance. $$ \text{Var}[Y(x) \,\vert\, Y(X) ] = k(x, \, x) - k(x,\,X) \, k(X, \, X)^{-1} \, k(X, \, x). $$ The equivalence of (1) and (3) holds because the unknown coefficients of the linear combination in (3) come by solving a linear system with matrix $k(X, \,X)$.

These equivalent conditions obviously depend much on the chosen Kernel and can be further detailed for some specific choices of the kernel as in the OP. However when the kernel is positive definite, the conditions never hold when $x$ is not in the set $\{x_i\}_i$ because otherwise the square matrix $k(X^\star, \, X^\star)$ would fail to be positive definite where $X^\star$ is the matrix adding a new row $x$ to $X$.

If $N$ is large the condition holds approximately for all $x$ provided that $X$ becomes dense is some suitable meaning. To be more precise, consider the (semi-) distance $d_k(u,\,u')$ related to the kernel as defined by $$ d^2_k(u,\, u') := k(u,\,u) + k(u',\,u') -2 k(u, \, u'), \qquad u,\, u'\in \mathbb{R}^d. $$ Note that $d_k(u,\,u') = \| k(.,\,u) - k(.,\,u')\|_{\mathcal{K}}$ where $\| . \|_{\mathcal{K}}$ is the norm in the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{K}$ of the kernel $k$. Also $d_k(u,\,u') = \| Y(u) - Y(u')\|_{L^2}$. The distance of $x$ to the design set $X$ is $d_K(x,\, X) := \min_{1 \leq i \leq N} d_k(x,\, x_i)$. If this distance tends to zero for $N \to \infty$ then we have $\lim_{N \to \infty} \text{Var}[Y(x) \,\vert\, Y(X) ] = 0$. Indeed the Kriging variance is $\| Y(x) - \mathbb{E}[Y(x) \vert Y(X) ]\|_{L^2}^2$ hence is smaller than $\| Y(x) - Y(x_i)\|_{L^2}^2$ for all $i$.

$\endgroup$
3
$\begingroup$

Let's consider the more general case $$k(x, X) \; k(X, X)^{+} k(X, x) = k(x, x)$$ where $A^{+}$ is the pseudoinverse of $A$.

Let's start with linear kernels: $k(x,z)=x^{\top}z$. Let's consider the case that $X$ is full rank with rank $r=\min(N,D)$. The SVD of $X$ is $X=U\Sigma V^{\top}$ where $\Sigma$ is diagonal $r\times r$ and invertible and $V^{\top}$ is $r \times D$ with orthonormal rows (hence $V^{\top}V=I_r$) while $U$ is $N \times r$ with orthonormal columns (hence $U^{\top}U=I_r$). As a result $x^{\top}X^{\top}(XX^{\top})^{+} X\,x=x^{\top}VV^{\top}x$.

If $N\ge D=r$ then $V$ is square (hence $VV^{\top}=I_r$ too) and the equality sought $x^{\top}X^{\top}(XX^{\top})^{+} X\,x=x^{\top}x$ holds.

When $D>N=r$ then $V^{\top}$ is a wide matrix and $VV^{\top}$ is not the identity matrix so the equality sought doesn't hold for general $x$ (i.e. a general test point not necessarily living in the space spanned by the training set $X$). It does, however, in the special case that $x$ is in the $N$-dimensional row space of $X$ because replacing $x = X^{\top}\xi = V \Sigma U^{\top}\xi$ into $x^{\top}VV^{\top}x$ gives $\xi^{\top}U \Sigma V^{\top}VV^{\top}V \Sigma U^{\top}\xi = \xi^{\top}U \Sigma \Sigma U^{\top}\xi = \xi^{\top}U \Sigma V^{\top} V \Sigma U^{\top}\xi = x^{\top}x$.

For nonlinear kernels $k(x,z)=\phi(x)^{\top}\phi(z)$ the considerations above still apply, albeit to the mapped space $\phi(x)$ rather than the original feature space $x$. Since in most cases the kernel is chosen to nonlinearity map the original feature space into a higher dimensional one (making the new $D$ larger than $N$ even when the original $D$ wasn't), the condition in the title tends to not hold in practice in most cases.

A further restriction to the validity of the equality for nonlinear kernels is that the corresponding situation for the special case "$x$ in the row space of $X$" may now be even less relevant. The issue is that vectors living in the row space of the matrix with rows $\phi(x_n)$ may not be the image through $\phi()$ of many vectors $x$ in the original space. Let's consider the example $\phi([x_1,x_2]^{\top})=[x_1,x_2,x_1^2+x_2^2]^{\top}$ that maps the 2-d Cartesian plane onto a paraboloid and $\mathcal{X}=\{[1,0]^{\top},[0,1]^{\top}\}$. Then $\phi([1,0]^{\top})=[1,0,1]^{\top}$ and $\phi([0,1]^{\top})=[0,1,1]^{\top}$ and the row space spanned by the two training points is the 2-d plane $[\tau_1,\tau_2,\tau_1+\tau_2]$ (with implicit equation $x_3=x_1+x_2$) however this only intersects the paraboloid (with implicit equation $x_3=x_1^2+x_2^2$) when $x_1$ and $x_2$ belong to the circle $x_1^2+x_2^2-x_1-x_2=0$. In other words the space spanned by the images of two training vectors only leads to a one-dimensional manifold in the original feature space.

Another compelling example is with a RBF kernel and $\mathcal{X}=\{[1],[2]\}$. The 1-d feature space is mapped into an infinitely dimensional one. Additionally, the row space of the matrix with rows $\phi(x_n)$ only intersects the image of $\mathbb{R}$ through $\phi()$ at the training points. In other words $$\begin{bmatrix}e^{-(x-1)^2} \\ e^{-(x-2)^2} \end{bmatrix}^{\top} \begin{bmatrix} 1 & e^{-(2-1)^2} \\ e^{-(1-2)^2} & 1 \end{bmatrix}^{-1} \begin{bmatrix}e^{-(x-1)^2} \\ e^{-(x-2)^2} \end{bmatrix} = e^{-(x-x)^2}$$ only for $x\in \{1,2\}$ as we can see here. Here the space spanned by the images of two training vectors only leads to a zero-dimensional manifold in the original feature space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.