6
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – nino
    Commented Dec 15, 2015 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.