A practical guide to radial basis functions (2007) [pdf] | Hacker News Reader

A practical guide to radial basis functions (2007) [pdf]

num.math.uni-goettingen.de

54 pointsPhithagoras4 comments

This looks pretty good from a quick skim (it's 2007 so I probably saw it 10+ years ago, but don't remember). I did my PhD on radial basis functions, and they seem surprisingly unknown for something so useful. RBFs provide a really easy way to interpolate through scattered data of any number of dimensions. I interpolated through point data, integral data, and derivative data (but didn't use them to solve DEs like this).

They also made a good well-obfuscated "peak hello world" attempt: https://news.ycombinator.com/item?id=23211972

That fits a multiquadric RBF (p2) (with linear terms, because it's conditionally positive definite; p5-6) to some carefully chosen data, then evaluates it (at the same points again, because I was in a hurry...) and converts to characters.

I first heard about them at Siggraph 2001. This paper https://dl.acm.org/doi/10.1145/383259.383266 by an acquaintance described a way of fitting RBFs to very large point clouds. The trick was to use Fast Multipole Methods, which are a bit like treecodes for n-body problems: https://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation

Fitting an RBF naively involves inverting a matrix as big as the number of points, but the FMM techniques use approximation to make the task practical.

JP Lewis has some course notes which explain the basics of RBF techniques well: http://scribblethink.org/Courses/ScatteredInterpolation/scat...

For a slightly more technical account, try Sage Shaw's excellent contribution to this Wikipedia page: https://en.wikipedia.org/wiki/Radial_basis_function_interpol...

Yes, I'm familiar with that paper. It's very complicated to implement - back when I was researching I didn't encounter any papers by others who had replicated it, and citations often mentioned its complexity. There are simpler ways to scale RBFs. I did it piecewise, using overlapping subdomains (each with ~200 points, so a small linear system) blended with partition of unity, and it scaled to millions of points in an embarrassingly parallelisable way. Here's a result I've linked on HN before, filling a hole in a point cloud (a small one, ~24000 points): https://imgur.com/a/k6AQi

Those course notes have some interesting stuff in them, thanks!

A Rust implementation, with visuals and pointers to other resources: https://crates.io/crates/rbf-interp

Reply on news.ycombinator.com