# On proof of the conditionally negative definiteness of a kernel

Let the kernel be $f(\mathbf{x},\mathbf{y}) = \arccos(\mathbf{x}^T \mathbf{y})$, where $\mathbf{x}$ and $\mathbf{y}$ are $\ell_2$ normalized vectors of the same dimensionality, and $\arccos(\cdot): [-1,1] \to [0,\pi]$ is the inverse cosine function.

Question: Is $f$ conditionally negative definite? If yes, how can I prove it?

I know the definition of a conditionally negative definite kernel, but I find it difficult to apply.

A kernel $f: (\mathcal{X} \times \mathcal{X}) \to \mathbb{R}$ is called (conditionally) negative definite if it it symmetric and $\sum_{i,j=1}^m c_i c_j f(x_i,x_j) \leq 0$ for all $m \in \mathbb{N}$, $\{x_1,\cdots,x_m\} \subseteq \mathcal{X}$ and $\{c_1,\cdots,c_m\} \subseteq \mathbb{R}$ with $\sum_{i=1}^m c_i = 0$.

Here a direct approach. Recall the power-series \begin{equation*} \arccos(z) = \frac\pi2 - \sum_{k\ge0}\binom{2k}{k}\frac{z^{2k+1}}{4^k(2k+1)}. \end{equation*} From this series it is clear that $\arccos(x^Ty)$ is conditionally negative definite (because it is of the form "const $-$ positive definite").
EDIT: (15/12/2015). Here are some more details. Observe that with the above powerseries representation, we have \begin{equation*} f(x_i^Tx_j) = \frac\pi2 - k(x_i,x_j), \end{equation*} where $k(x,y)$ is a positive definite kernel (to see this observe that the power series has nonnegative coefficients, and since $(x_i^Tx_j)^{2k+1}$ is pointwise product of kernels, it is itself a kernel).
Thus, we have in particular that the matrix $F := [f(x_i^Tx_j)] = c11^T-[k(x_i,x_j)]$, so that it immediately follows \begin{equation*} z^TFz = c(z^T1)^2 - z^TKz \le 0, \end{equation*} because the first term is zero whenever $z^T1=0$ (as stipulated for cnd matrices), and because $z^TKz \ge 0$ as $K$ is a kernel.
Note: The above argument does not yield that $f^n$ is cnd (it may likely not be cnd, but I don't have time right now to think about it).
• Thanks very much for your answer! I have two follow-up questions: (1) Why does the form of "const - positive definite" yield conditionally negative definiteness? Is there any theorem related to it? To me, it is not that obvious; (2) Does this result lead to the conditionally negative definiteness of $f^n$, e.g., $n=2$? Much appreciated!