I have been working on Kernels for SVM, so I would like to prove that the matrix \begin{align}
K = \begin{bmatrix}
f\left(x_1, x_1\right) & \cdots & f\left(x_1, x_N\right)\\
\vdots & \ddots & \vdots\\
f\left(x_N, x_1\right) & \cdots & f\left(x_N, x_N\right)\\
\end{bmatrix} \in \mathbb R^{N\times N}
\end{align}
is indeed PSD, where $$f(x,y) = \frac{x \cdot y}{\|x\|^{2}+\|y\|^{2}-x \cdot y}, \; \forall x, y\in \mathbb R^n_{>0}.$$
So I want to prove that this holds:
$$ \sum_{i=1}^{N} \sum_{j=1}^{N} c_i c_j K_{ij} \geq 0 $$
for all $c_i, c_j \in \mathbb{R}^N$. I have been trying to found some counterexample, but It seems that this is indeed PSD, however I don't know how to apply the regular methods that I have been thaught.
Best Answer
We have $|x\cdot y|\le\sqrt{\|x\|^2\|y\|^2}\le\frac{\|x\|^2+\|y\|^2}{2}$. Hence $\frac{|x\cdot y|}{\|x\|^2+\|y\|^2}\le\frac12$ and $$ f(x,y) =\frac{\frac{x\cdot y}{\|x\|^2+\|y\|^2}}{1-\frac{x\cdot y}{\|x\|^2+\|y\|^2}} =\sum_{k=1}^\infty\left(\frac{x\cdot y}{\|x\|^2+\|y\|^2}\right)^k $$ can be expressed as an absolutely convergent power series. Therefore $$ K=\sum_{k=1}^\infty G^{\large\circ k}\circ H^{\large\circ k}, $$ where $G^{\large\circ k}$ and $H^{\large\circ k}$ are the $k$-fold Hadamard products of $G=\left(x_i\cdot x_j\right)_{i,j\in\{1,2,\ldots,N\}}=X^\top X$ and \begin{aligned} H &=\left(\frac{1}{\|x_i\|^2+\|x_j\|^2}\right)_{i,j\in\{1,2,\ldots,N\}}\\ &=\left(\int_0^\infty e^{-s(\|x_i\|^2+\|x_j\|^2)}ds\right)_{i,j\in\{1,2,\ldots,N\}}\\ &=\int_0^\infty v(s)v(s)^\top ds \end{aligned} respectively, where $v:\mathbb R_{\ge0}\to\mathbb R_{>0}^N$ denotes the vector-valued function $v(s)=(e^{-s\|x_1\|^2},e^{-s\|x_2\|^2},\ldots,e^{-s\|x_N\|^2})^\top$. Since $G$ and $H$ are Gram matrix or sum of Gram matrices, they are positive semidefinite. It follows from Schur product theorem that $G^{\large\circ k}\circ H^{\large\circ k}$ is also PSD. Hence $K$, an infinite sum of PSD matrices, is PSD.
Note that we only need each $x_i$ to be a nonzero vector. We don't need them to be entrywise positive.