0

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.

Conny
  • 137
  • 1
  • 10

1 Answers1

2

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

kimchi lover
  • 24,277
  • Note that you need the $x_{i}$ to be distinct. Any repeated values and you've lost linear independence. – Brian Borchers Jan 27 '19 at 21:38
  • @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. – Conny Feb 04 '19 at 10:11
  • 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 https://en.wikipedia.org/wiki/Bochner%27s_theorem; for Fourier transforms see https://en.wikipedia.org/wiki/Fourier_transform (and for your problem, formula 206 in https://en.wikipedia.org/wiki/Fourier_transform#Square-integrable_functions,_one-dimensional). The business about "dual" is probably needless pedanticism; the integral over $V$ is covered by the Wikipedia article on FT. – kimchi lover Feb 04 '19 at 19:03
  • @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$ – dohmatob May 21 '21 at 09:46