0
$\begingroup$

I'm trying to prove that, given mutually different points $x_1,\dots,x_m$, the Gram matrix $G$ for the Gaussian kernel has $rank(G)=m$. If I can prove that the Gaussian kernel is strictly positive definite I could follow that all eigenvalues $\lambda_1,\dots,\lambda_m$ of $G$ are positive. Therefore, $det(G)=\Pi_{i=1}^m \lambda_i \neq 0$ which implies $rank(G)=m$. Is there an easy way to show that the Gaussian kernel is strictly positive definite? I've already searched on StackExchange but I couldn't find an explanation I could understand.

Thanks in advance!

EDIT: The definition of the Gram matrix is the following: Given a kernel $k$ and data $x_1,\dots,x_m \in X$, the $m \times m$ matrix $G=(g_{ij})$ with $g_{ij}=k(x_i,x_j)$ is called Gram matrix.

$\endgroup$
2
  • $\begingroup$ Can you give a formula for a typical entry of $G$, please, so we can be absolutely sure we understand what you are asking? $\endgroup$ Jan 27, 2019 at 20:48
  • $\begingroup$ @kimchilover I added the definition of the Gram matrix to the question. $\endgroup$
    – Conny
    Jan 27, 2019 at 20:56

1 Answer 1

2
$\begingroup$

We are given $m$ distinct vectors $x_1,\ldots,x_m \in X$. We may assume your vector space $X$ is finite dimensional with dual $V$, by restricting to the linear span of the $x_r$ if needed.

Let $k(x,y)=\exp(-\|x-y\|^2) =\int_V \exp(i\langle v,x-y\rangle) g(v)dv$, where $g(v)$ is the Fourier transform of $\exp(-\|x\|^2)$. Note that $g(v)>0$ for almost all $v$.

For numbers $a_r\in\mathbb C$ let $Q=\sum_{r=k}^m\sum_{s=1}^m a_r \overline a_s k(x_r,x_s)$. It is easy to see that $Q=\int_V |P(v)|^2 g(v)dv$, where $P(v)=\sum_{r=1}^m a_r \exp(i \langle v,x_r\rangle)$. If the $a_r$ do not all vanish, $|P(v)|>0$ for almost all $v$. Then the integrand of $\int_V |P(v)|^2 g(v)dv$ is non-negative almost everywhere, and hence $Q>0$.

$\endgroup$
4
  • $\begingroup$ Note that you need the $x_{i}$ to be distinct. Any repeated values and you've lost linear independence. $\endgroup$ Jan 27, 2019 at 21:38
  • $\begingroup$ @kimchilover Thanks for your answer! I did not have time to think about it until now and I'm not too familiar with Fourier transform. What do you mean with dual $V$? The space of linear functionals from $X$ to $\mathbb{R}$? And how do you get the equality to the integral over $V$? Sorry that I have so many questions. $\endgroup$
    – Conny
    Feb 4, 2019 at 10:11
  • $\begingroup$ One problem with this forum is that it's often hard to know the background one can assume in answering a question; sorry about that. For your problem in general, see en.wikipedia.org/wiki/Bochner%27s_theorem; for Fourier transforms see en.wikipedia.org/wiki/Fourier_transform (and for your problem, formula 206 in en.wikipedia.org/wiki/…). The business about "dual" is probably needless pedanticism; the integral over $V$ is covered by the Wikipedia article on FT. $\endgroup$ Feb 4, 2019 at 19:03
  • $\begingroup$ @kimchilover Nice anwer! I wonder whether one can use this to get a quantitative bound, by which I $Q \ge \alpha \|a\|^2$, for some $\alpha>0$. I'm optimistic in the case the $x_i$'s a well-separated, in the sense that $\|x_i - x_j\| \ge c$ for all $(i,j)$ such that $i \ne j$ $\endgroup$
    – dohmatob
    May 21, 2021 at 9:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .