3
$\begingroup$

I am developing a machine learning software, where I am trying to apply kernel methods. I have N uniformly sampled scalar values, $\{x_1,\dots,x_N\}$ from a given interval $[a,b]$. My aim is to execute a Kernel PCA operation and therefore I build the Gram matrix for these inputs as $K(i,j)=\exp(-\gamma(x_i-x_j)^2)$. Note since I work with scalar values, the norm in the Gaussian function becomes simply the difference between two values. Additionally, I always set $\gamma > 0$.

My problem is, $K$ turns out to be always rank-deficient and not positive definite. When I calculate its eigenvalues, some negative eigenvalues show up, which means that the matrix is not positive definite.

I superficially knew that K should be an invertible, positive definite matrix in case of Gaussian Kernel functions. Then I have made some research and found the question here: Gaussian Kernels, Why are they full rank? Another user asked something similar to me; he wants to learn why the Gaussian Kernel's Gram matrix is full rank. The answer says that in order a Gram matrix for a general kernel function, with entries $x_1,\dots,x_n$ to be positive definite, for each $x_i \in \{x_1,\dots,x_N\}$ in the set, the kernel functions $K(.,x_i)$ must be linearly independent. And then for Gaussian Kernel functions a proof was given which shows that $K(x_1,x_i),\dots,K(x_N,x_i)$ are always linearly independent. So the Gram matrix for the Gaussian kernel must be positive definite.

In practice, I fail to reproduce this result, as I have said, the Gram matrix $K$ is always rank deficient and indefinite.

I suspect the following: Theoretically, all $\{x_1,\dots,x_N\}$ samples generate a positive definite Gram matrix, but since I have limited real number precision in a computer program, $K$ turns out to be "almost" full rank.

My questions are: First, Is my theoretical approach correct; should I really get a positive definite gram matrix for every input set (in theory)? Second; can this precision problem really be the culprit here? How I can fix that and obtain a "confident" positive definite Gram matrix, which doesn't misbehave?

(I am using C++ and OpenCV by the way. I thought that this is a more maths related question than purely coding related, so I asked it here)

$\endgroup$
4
  • $\begingroup$ Note that the Gram matrix should be calculated as $X^*X$ rather than $X^TX$ ($*$ is the conjugate-transpose, $T$ is the ordinary transpose). If you calculate it in this way, the Gram matrix will always be positive semidefinite. $\endgroup$ Commented Dec 8, 2014 at 16:58
  • 3
    $\begingroup$ It is well known that the Gaussian kernel is strictly positive definite. As long as your sample points $x_1,\ldots,x_N$ are drawn from a continuous distribution, the probability that $K$ is positive definite is $1$. So, what you encountered is clearly a numerical artefact (if not a programming error). When the interval $[a,b]$ is too narrow, or when $\gamma$ is not big enough, it's very easy for $K$ to become ill-conditioned, although it should be positive definite in theory. $\endgroup$ Commented Dec 8, 2014 at 17:34
  • $\begingroup$ @Omnomnomnom By the Gram matrix, I mean the $ N \times N $ matrix which I buildfor each $(i, j) $ th entry as $ K (i, j) = \exp ( -\gamma (x_i - x_j)^2) $. How is this matrix related to conjugate transpose? I think by $ X $ you mean the matrix of feature space vectors, $[\phi (x_1), \dots, \phi (x_N)] $. Is that right? $\endgroup$ Commented Dec 8, 2014 at 18:14
  • $\begingroup$ @UfukCanBiçici yes, that's right. You seem to be calculating it correctly though (according to what you've written), my mistake. $\endgroup$ Commented Dec 8, 2014 at 18:17

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.