9
$\begingroup$

I use RBF kernel function to implement one kernel based machine learning algorithm(KLPP), the resulting kernel matrix $K$ $$K(i,j)= \exp\left({\frac{-(x_{i}-x_{j})^2}{ \sigma_{m}^2}}\right)$$ is shown to be extremely ill-conditioned.The condition number of L2-norm comes $10^{17}-10^{64}$

Is there any way to make it well-conditioned? I guess parameter $ \sigma$ needs to be tuned, but I don't know how exactly.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ well, if you make $\sigma_m$ smaller you improve the condition number. $\endgroup$ – user189035 Jun 7 '13 at 7:28
10
$\begingroup$

Reducing the kernel width $\sigma_m$ will usually reduce the condition number.

However, kernel matrices can become singular, or close to singular, for any basis function or point distribution, provided the basis functions overlap. The reason for this is actually quite simple:

  • The kernel matrix $K$ is singular when its determinant $\det(K)$ is zero.
  • Swapping two points $x_i$ and $x_j$ in your interpolation is equivalent to exchanging two rows in $K$, assuming your trial points remain constant.
  • Swapping two rows in a matrix switches the sign of its determinant.

Now imagine picking two points $x_i$ and $x_j$ and slowly rotating them so that they switch places. While doing this, the determinant of $K$ will switch sign, becoming zero at some point in between. At this point, $K$ is, by definition, singular.

$\endgroup$
  • $\begingroup$ Aren't K matrices symmetric -- swapping two points swaps rows and columns ? $\endgroup$ – denis Jun 13 '13 at 15:52
  • $\begingroup$ @Denis That is only the case if your nodes and trial points are the same and you move both. This is why, in the second bullet, I wrote "assuming your trial points remain constant." $\endgroup$ – Pedro Jun 16 '13 at 10:37
  • $\begingroup$ the kernel matrix of Gaussians (the OP's question) are positive semi-definite anyway ? $\endgroup$ – denis Jun 16 '13 at 11:00
  • $\begingroup$ @Denis: Again, this is a question of how you define your RBF interpolation problem. Consider the most general case where you have $N$ RBFs centred on the points $x_i$, $i=1\dots N$, and you want to minimize the interpolation at the $M$ points $\xi_j$, $j=1\dots M$. The poster's example assumes $M=N$ and $\xi_j=x_i$. If we initially set $M\leftarrow N$ and $\xi_j \leftarrow x_i$, and then just move the $x_i$, we can trivially generate singular $K$. $\endgroup$ – Pedro Jun 16 '13 at 11:11
3
$\begingroup$

A couple of suggestions:

  1. Choose $\sigma \sim$ the average distance | random $x$ - nearest $x_i$. (A cheap approximation for $N$ points uniformly distributed in the unit cube in $\mathbb{R}^d, d\ 2 .. 5$, is 0.5 / $N^{1/d}$.)
    We want $\phi( |x - x_i| )$ to be large for $x_i$ near $x$, small for background noise; plot that for a few random $x$.

  2. Shift $K$ away from 0, $K \to K + \lambda I$, $\lambda \sim 10^{-6}$ or so; that is, regularize.

  3. Look at the weights from solving $(K + \lambda I) w = f$. If some are still huge (regardless of condition number), that would tend to confirm Boyd (below) that Gaussian RBF is fundamentally weak.

(One alternative to RBF is Inverse-distance weighting, IDW. It has the advantage of auto-scaling, the same for nearest distances 1 2 3 $\dots$ as for 100 200 300 $\dots$ Also I find explicit user choice of $Nnear$, the number of near neighbors to consider, clearer than grid search on $\sigma, \lambda$ .)

John P. Boyd, The uselessness of the Fast Gauss Transform for summing Gaussian radial basis function series, says

the Gaussian RBF interpolant is ill-conditioned for most series in the sense that the interpolant is the small difference of terms with exponentially large coefficients.

Hope this helps; please share your experience.

$\endgroup$

Your Answer

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

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