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



On proof of the conditionally negative definiteness of a kernel
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).


