1
$\begingroup$

Consider $K$ vectors $x_1,\dots,x_K$ in $\mathbb{R}^N$. Define the $K\times K$ matrix $A$ whose $(i,j)$ entry is given as $$A_{ij}=\exp(-\frac{||x_i-x_j||^2}{2})$$ Is this matrix Positive Semi-Definite?

$\endgroup$
1
  • 3
    $\begingroup$ In my opinion, this is not a research level question, but a standard textbook exercise. $\endgroup$
    – Suvrit
    Sep 23, 2015 at 13:03

1 Answer 1

6
$\begingroup$

Yes, it is. We write $A_{ij}=B_{ij}C_{ij}$, where $$B_{ij}=e^{-\|x_i\|^2/2}e^{-\|x_j\|^2/2}; \quad C_{ij}=e^{(x_i,x_j)}.$$ By Schur's theorem on elementwise product of positive definite matrices, it is enough to show that $B_{ij}$ and $C_{ij}$ are positive semidefinite. Positive definiteness of $B_{ij}$ is obvious. Positive definiteness of $C_{ij}$ follows from positive definiteness of the matrix $(x_i,x_j)$, Taylor expansion of the exponent and application of Schur's theorem to elementwise powers of the matrix $(x_i,x_j)$.

$\endgroup$

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