5
$\begingroup$

Let $\mathbb{S}_n$ denote the set of $n \times n$ symmetric positive semidefinite matrices. I am trying to figure out whether $k: \mathbb{S}_n \times \mathbb{S}_n \to \mathbb{R}_+$ defined as:

$$k(A, B) = \text{Tr}[(A^{1/2} B A^{1/2})^{1/2}]$$

is a positive definite kernel. Can anyone find a counterexample showing it is not? Or prove it is indeed a positive definite kernel?

Some analysis so far: Having failed to find a counterexample numerically, I am trying to show: $$\sum_{ij} k(A_i, A_j) x_i x_j \geq 0$$ holds for any $A_1, \dots, A_m \in \mathbb{S}_n$ and $x_1, \dots, x_m \in \mathbb{R}$. Without loss of generality we can assume that $x_1, \dots, x_m \in \{-1, +1\}$ since the change of $x_i \mapsto \text{sign}(x_i)$ and $A_i \mapsto x_i^2 A_i$ preserves the value on the left hand side above and all matrices remain positive semidefinite after this change of variables.

Let $\mathcal{P}$ denote the set of indices where $x_i x_j = +1$ and let $\mathcal{N}$ denote the set of indices where $x_i x_j = -1$. Then we just need to show the following inequality holds: $$\sum_{i=1}^m \text{Tr}[A_i] + 2 \sum_{(i,j)\in\mathcal{P}} k(A_i, A_j) \geq 2 \sum_{(i,j)\in\mathcal{N}} k(A_i, A_j)$$ This is where I'm stuck, or maybe a different approach is needed.

$\endgroup$
6
  • 1
    $\begingroup$ Unless if I'm misunderstanding the definition of positive definite kernel, I think no. Take $A = \text{diag}(1,0)$, $B=\text{diag}(1,1)$ and $C = \text{diag}(0,1)$ and form the associated kernel matrix. The determinant should be $\sqrt{2}-2<0$. $\endgroup$ Commented Feb 20, 2023 at 5:42
  • $\begingroup$ $\mathbb{S}$ depends on a dimension (size of matrices) and hence the answer should depend on $n$. Shouldn't $\mathbb{S}$ be denoted $\mathbb{S}_n$? (I also assume they are meant to be symmetric) $\endgroup$
    – YCor
    Commented Feb 20, 2023 at 9:09
  • 2
    $\begingroup$ Indeed in restriction to 2-dim nonnegative diagonal matrices, this reads as $k((x_1,y_1),(x_2,y_2))=\sqrt{x_1x_2}+\sqrt{y_1y_2}$. For the three matrices $A,B,C$ proposed by @JasonGaitonde we get the Gram matrix $\begin{pmatrix}1 & 1 & 0\\1 & 2 & 1\\ 0 & 1 & 1\end{pmatrix}$ whose eigenvalues are $0,1,3$, so it is $\ge 0$. $\endgroup$
    – YCor
    Commented Feb 20, 2023 at 9:19
  • 1
    $\begingroup$ @YCor ah whoops -- bad algebra error! I thought the middle 2 was $\sqrt{2}$... $\endgroup$ Commented Feb 20, 2023 at 10:41
  • $\begingroup$ Indeed, now that I think about it, diagonal matrices cannot provide a counterexample, as the entries are a genuine Gram matrix after applying the coordinate-wise square root to the underlying diagonal matrices. Interesting question! $\endgroup$ Commented Feb 20, 2023 at 10:47

1 Answer 1

3
$\begingroup$

Counterexample for $n = 2$ :

Let $A_k$ be the orthonormal projection on the span of $$(\cos(2 \pi (k-1) / 5), \sin(2 \pi (k-1) / 5))^\mathsf{T} , \quad k = 1...5.$$

Then $k(A_k,A_l) = \vert \cos(2 \pi (k-l) / 5) \vert$ .

The corresponding matrix has the eigenvalue $-0.11803398874989484820458683436563811772$ with multiplicity $2$ .

$\endgroup$

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.