Do RBF kernel matrices tend to be ill-conditioned?

Question

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!

Answer 1

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.

Answer 2

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.