With Schölkopf, Hirsch, Fadely, and Foreman-Mackey, we had a long session in my office about blind deconvolution, image priors, and so on. Schölkopf had an intuition—at variance with mine—that locality-sensitive hashing will beat a kd-tree for fast lookup of image patches in any massive data-driven prior on image contents. Fadely was volunteered to find out if this is true. Of course the kd-tree can be used to get exact results and the hashing may only give approximate results, so there is a difference, but I had the impression that the kd-tree is hard to beat. It might also depend on scale. Time to call in Lang and Mierle!
On blind deconvolution, we argued about the representation of the high-resolution scene and all agreed on two points: The first is that the model one builds of the imaging data should represent one's beliefs about the causal processes that create that imaging data. The second is that the parameterization of the high-resolution scene should be connected to the specific questions one wants to ask about that scene.
I've not had much luck getting fast exact nearest neighbors, except in pretty low-dimensional settings. I've learned to be pretty skeptical of overly-general claims to the contrary.
ReplyDeleteFrom the paper, this work on learning fast approximate lookup seems pretty sensible:
http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
It's one of the things I'll try next time I want to speed up anything neighborhood based. (BSD-licensed software available.)