1
$\begingroup$

I have a large number of $N$ (20770) measurements. I need to perfom a calculation on all of them, but this is computationally too expensive. Therefore, I am looking for a way to select a subset of $p$ (~300) measurements. Then, I can use any of those $N$ measurements, look which one of the subset $p$ is closest, and use the calculation for this reference measurement; like a lookup-table. The aim of the subset is thus not to be representative of the full set, but to span the entire range in each relevant dimension.

I can think of several ways to establish this subset (such as using EOFs to maximise variability, or something along the lines of Chevallier et al. (2006) but the latter lacks algorithm details), but I don't want to spend months on this, as it is not essential that it is done in the best possible way; a simpler but sub-optimal way is highly preferrable. A simple way I can think of is to bucket my measurements based on $d$ dimensions (say $d=6$). Then, I can lookup which reference measurement fits in the same $d$-dimensional bucket as the current measurement, and use the calculation for that reference measurement.

My fear is that I am reinventing the wheel and spending time on developing a poor homegrown solution to a problem that has well-established solutions along with implementation in popular languages. That brings me to my question:

Is the problem described above one encountered commonly enough so that there exists: (1) a name and literature on alternative solutions, and (2) open-source implementations of those solutions in popular packages, in particular for Python?

$\endgroup$
5
  • $\begingroup$ You will be, as they say, cursed by the dimensionality. In six dimensions you can cut each dimension into fewer than three classes on average (because even $3^6 \gt 300$)--and, of course, with effectively just one class for any additional dimensions. For most applications this will be too crude. Your only hope is that the data follow a multivariate functional form that has a very parsimonious description. Is there any possibility of that? $\endgroup$
    – whuber
    Jan 16, 2015 at 18:47
  • $\begingroup$ What if, in my database, almost all classes are empty? I have 20770 elements, and with my bucketing I have 5760000 classes. 304 classes are non-empty, with at least 1 and at most 840 measurements in a class. (Almost) all subsequent measurements will fall in those 304 classes or ones that are very close. So my class database is actually very sparse. I'm not sure what a "parsimonious description" means. $\endgroup$
    – gerrit
    Jan 16, 2015 at 19:31
  • $\begingroup$ Also, I'm not sure if interpolation is even necessary — if the class in which a measurement fits corresponds to the class for which I have a reference measurement (and it should, because that's how I constructed the references), I would simply take that reference as such (I guess that would effectively be nearest-neighbour with distances defined by the bucketing). $\endgroup$
    – gerrit
    Jan 16, 2015 at 19:33
  • $\begingroup$ And that indeed is a (crude) form of interpolation. Unless I have grossly misunderstood your purpose--which is to use a small set of well-distributed values in order to predict all the other values--then your question is definitely about interpolation. It is interesting in that you have the opportunity to design the interpolating function (rather than merely interpolating given data). A "parsimonious description" is one that is not as complex as specifying 300 7-tuples (six coordinates and one value for each), such as a function that incorporates (say) only 20 parameters. $\endgroup$
    – whuber
    Jan 16, 2015 at 20:15
  • $\begingroup$ @whuber I get it. My question is indeed about interpolation, then. My confusion was that I don't need some parameterisation fit to the data (which is what I usually do when interpolating). $\endgroup$
    – gerrit
    Jan 16, 2015 at 20:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.