3 ms·

I am a frequentist by training and got a little confused by Bayesian and engineering terminology while flipping through the posts. Bear with me. Did I understa

by gerty 11y ago

I am a frequentist by training and got a little confused by Bayesian and engineering terminology while flipping through the posts. Bear with me. Did I understand well that kernel interpolation is what we'd call a kind of non-noisy kernel regression? If it's the case and dimension d of the regressors is large, multivariate non-parametric estimation will have very slow convergence, won't it?

mccourt 11y ago
I also get confused by the notation, so you are not alone. I think it is fair to say that kernel interpolation is a non-noisy kernel regression. Of course, this would also depend on your choice of terminology ... I use the word regression to mean any sort of fitting of specific basis functions to data - the fit doesn't have to be perfect. Interpolation, at least in my mind, means that the fit does have to be perfect. So when I say kernel interpolation I think it is fine to think of it as regression that perfectly passes through any data points. Technically, I like to think of the fact that the data has noise as independent of the strategy that you use to fit it. So you could perfectly interpolate noisy data (a bad idea) and you could do a regression on noise-less data (also bad, but not as bad). But yeah, I think it's probably safe to say "non-noisy kernel regression". As far as your real question, chapter 9 of my book talks about that, and the reason I mention that here is that it is a complicated question. Just to confirm, when you say dimension you mean physical dimension, not the number of pieces of data, right? The classical convergence bounds all deal with the smoothness of the data (or rather the function that generated the data) and the smoothness of the reproducing kernel. The relevance of the smoothness is augmented by the dimension, so the dimension can be relevant. Arguably, this is why statisticians like Michael Stein would say that Gaussians are not appropriate for low dimensions (too much smooothness) but are necessary for high dimensions (because without the smoothness the convergence is too slow). Some recent results (http://epubs.siam.org/doi/abs/10.1137/10080138X http://epubs.siam.org/doi/abs/10.1137/10080138X) talk about dimension independent bounds, but with some caveats, and almost entirely from the numerical analysis standpoint (which can be tough to read). Sorry to sort of fork the answer into pieces there. Anything else I can help with?
- gerty 11y ago
  Thanks for the answer and the SIAM reference, I did manage to pick up something interesting from there, I think. Smoothness, dimensionality and also adaptivity are vast topics indeed. Good luck with the future work!
  - mccourt 11y ago
    I tried to do some digging to find easy to access (both through the web, but also not terribly complicated) references on error bounds for kernels interpolation. I don't think there is one ... although the internet will surely correct me if I'm wrong. The original source that I often return to (even before I look in my book) is Wendland's 2005 book "Scattered Data Approximation". But that book is really tough to read, even for me. Lots of tough math. Fasshauer's 2007 book "Meshfree Approximation Methods in Matlab" is much easier to read, but references Wendland's book for most of the heavy lifting. There is a newer branch of study on convergence dealing with what are called "sampling inequalities". In many ways, the math behind these is even worse as it usually requires a bunch of polynomial theory, but the results are more easily accessible. In particular, Christian Rieger and Barbara Wolmuth have outstanding content on this which is readily available on the web. In particular, I was able to find Christian's PhD thesis (https://www.deutsche-digitale-bibliothek.de/binary/JOWXLCGSV4NBOC5ZMLW553MRS6X65BFB/full/1.pdf https://www.deutsche-digitale-bibliothek.de/binary/JOWXLCGSV...) which provides a good journey from the start to actual results. Sorry I can't provide a cleaner statement about this. Maybe the most basic point I can make about convergence here would be to reference the early part of Christian's thesis where he alludes to the theorem that says the quality of an interpolant sort of looks like: error of interpolant = O(h^{k-d}) That is a gross simplification, but gives the gist of the result. h is the "fill distance" (or grid width for structured data) k is the smoothness of the kernel and d is the dimension of the data. This indicates why smooth kernels (large k) are needed to get the convergence for high d.

by gerty 11y ago

mccourt 11y ago

I also get confused by the notation, so you are not alone. I think it is fair to say that kernel interpolation is a non-noisy kernel regression. Of course, this would also depend on your choice of terminology ... I use the word regression to mean any sort of fitting of specific basis functions to data - the fit doesn't have to be perfect. Interpolation, at least in my mind, means that the fit does have to be perfect. So when I say kernel interpolation I think it is fine to think of it as regression that perfectly passes through any data points. Technically, I like to think of the fact that the data has noise as independent of the strategy that you use to fit it. So you could perfectly interpolate noisy data (a bad idea) and you could do a regression on noise-less data (also bad, but not as bad). But yeah, I think it's probably safe to say "non-noisy kernel regression". As far as your real question, chapter 9 of my book talks about that, and the reason I mention that here is that it is a complicated question. Just to confirm, when you say dimension you mean physical dimension, not the number of pieces of data, right? The classical convergence bounds all deal with the smoothness of the data (or rather the function that generated the data) and the smoothness of the reproducing kernel. The relevance of the smoothness is augmented by the dimension, so the dimension can be relevant. Arguably, this is why statisticians like Michael Stein would say that Gaussians are not appropriate for low dimensions (too much smooothness) but are necessary for high dimensions (because without the smoothness the convergence is too slow). Some recent results (http://epubs.siam.org/doi/abs/10.1137/10080138X http://epubs.siam.org/doi/abs/10.1137/10080138X) talk about dimension independent bounds, but with some caveats, and almost entirely from the numerical analysis standpoint (which can be tough to read). Sorry to sort of fork the answer into pieces there. Anything else I can help with?

gerty 11y ago
Thanks for the answer and the SIAM reference, I did manage to pick up something interesting from there, I think. Smoothness, dimensionality and also adaptivity are vast topics indeed. Good luck with the future work!
- mccourt 11y ago
  I tried to do some digging to find easy to access (both through the web, but also not terribly complicated) references on error bounds for kernels interpolation. I don't think there is one ... although the internet will surely correct me if I'm wrong. The original source that I often return to (even before I look in my book) is Wendland's 2005 book "Scattered Data Approximation". But that book is really tough to read, even for me. Lots of tough math. Fasshauer's 2007 book "Meshfree Approximation Methods in Matlab" is much easier to read, but references Wendland's book for most of the heavy lifting. There is a newer branch of study on convergence dealing with what are called "sampling inequalities". In many ways, the math behind these is even worse as it usually requires a bunch of polynomial theory, but the results are more easily accessible. In particular, Christian Rieger and Barbara Wolmuth have outstanding content on this which is readily available on the web. In particular, I was able to find Christian's PhD thesis (https://www.deutsche-digitale-bibliothek.de/binary/JOWXLCGSV4NBOC5ZMLW553MRS6X65BFB/full/1.pdf https://www.deutsche-digitale-bibliothek.de/binary/JOWXLCGSV...) which provides a good journey from the start to actual results. Sorry I can't provide a cleaner statement about this. Maybe the most basic point I can make about convergence here would be to reference the early part of Christian's thesis where he alludes to the theorem that says the quality of an interpolant sort of looks like: error of interpolant = O(h^{k-d}) That is a gross simplification, but gives the gist of the result. h is the "fill distance" (or grid width for structured data) k is the smoothness of the kernel and d is the dimension of the data. This indicates why smooth kernels (large k) are needed to get the convergence for high d.