1
$\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$
  • $\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$ – Omnomnomnom Dec 8 '14 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$ – user1551 Dec 8 '14 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$ – Ufuk Can Bicici Dec 8 '14 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$ – Omnomnomnom Dec 8 '14 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.