# Relation of kernels and Cholesky decomposition

I am trying to find an intuition on why we require that kernels are positive semi definite and I have found this:

We are given a dataset $X$ of size $n \times d$ where $n$ is the number of samples and $d$ is the number of features. If we want to express all the inner products between each data point in a matrix we can write: \begin{align} K = XX^T = \begin{bmatrix} x_1^Tx_1 & x_1^Tx_2 & \dots \\ x_2^Tx_1 & \ddots \\ \vdots \end{bmatrix} \end{align}

If we have a feature transformation $\phi(x)$ then the equivalent kernel would become: \begin{align} K = \phi(X)\phi(X)^T = \begin{bmatrix} \phi(x_1)^T\phi(x_1) & \phi(x_1)^T\phi(x_2) & \dots \\ \phi(x_2)^T\phi(x_1) & \ddots \\ \vdots \end{bmatrix} \end{align}

My understanding is that if we have a known $\phi$ and calculate $K$ as shown above, then $K$ is always going to be positive semi definite. Now let's think about it the other way around: we have a function $k(x,y)$ that takes two data points and calculates the inner product directly in the transformed space without first transforming each data point. We can calculate $K$ directly: \begin{align} K = \begin{bmatrix} k(x_1,x_1) & k(x_1,x_2) & \dots \\ k(x_2,x_1) & \ddots \\ \vdots \end{bmatrix} \end{align}

If a matrix is positive semidefinite then we can use Cholesky decomposition to write it as $K=LL^T$. Therefore if the obtained $K$ is not positive semidefinite then there is no way to decompose it and therefore there is no way there is a feature transformation $\phi$ that first maps the data points to a higher dimensional space such that $K=\phi(X)\phi(X)^T$.

Now that I have explained my intuition, my question is this: Cholesky decomposition decomposes a matrix to 2 triangular matrices $L$ and $L^T$. Let's say I have both a kernel function $k(x,y)$ and the corresponding map $\phi$ and I calculate $K$ directly using $k$. If I decompose $K$, is the resulting matrix $L$ going to be the same as $\phi(X)$? If not, does that mean that there exist two datasets $X_1$ and $X_2$ such that $\phi(X_1)\phi(X_1)^T = \phi(X_2)\phi(X_2)^T$ and one of them has the property that $\phi(X_1) = L$? Additionally, does that also imply that there exist two feature transformations $\phi_1$ and $\phi_2$ such that for the same dataset $X$ we have $\phi_1(X)\phi_1(X)^T = \phi_2(X)\phi_2(X)^T$ and one of them has the property $\phi_1(X) = L$?

I might be over-complicating things but I came up with these questions while trying to find an intuition for positive semi-definiteness of kernels and I thought maybe someone knows the answer.

• I have two comments. Firstly, the reason kernels are used (according to everything I've seen) is that there are times when the kernel is easy to calculate, but the feature map is not. For example, the feature map for the radial basis function would map to an infinite dimensional space. I don't know if the feature map is known. Secondly there is Mercer's theorem which says that every kernel function is 'inner product' on an appropriate space. – meh Nov 28 '17 at 22:15

In general the Cholesky decomposition for $K$ is not the feature map $\Phi(x)$. $K$ is positive definite iff $K=BB^T$ for some matrix $B$. However, $B$ is not unique. It could be the Cholesky $L$. It could also be derived from the eigenvectors of $K$: write $K=U\Sigma U^*$, and since $\Sigma$ is diagonal and has positive entries, let $B:=U\sqrt{\Sigma}$, where the square-root is entry-wise. In particular, if $U$ is not triangular, then neither is $B$.
Edit: Proof that $K=BB^T$ iff $K$ is positive (semi) definite.
$\Rightarrow$: This is trivial: if $K=BB^T$, then $v^TKv=\|Bv\|_2^2\geq 0$.
$\Leftarrow$: If $K$ is positive definite, then it's also symmetric (by definition of positive definite), hence is diagonalizable: $K=U\Sigma U^*$, where $\Sigma$ is diagonal containing all eigenvalues of $K$. Since positive definite is eqivalent to $v^TKv\geq 0$, this implies each eigenvalue is non-negative. So you can define $\sqrt{\Sigma}$ by taking the entry-wise square-root of $\Sigma$, and since $\Sigma$ is diagonal, $\sqrt{\Sigma}^2=\Sigma$. Thus let $B=U\sqrt{\Sigma}$, so that $K=BB^T$.