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.
 A: 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$. 
