3

I have finite series of intervals of real numbers, Ri = (Rimin, Rimax) and series of real numbers ti, i=1..N.

My goal is to find a function f:R->R, where for each i is f(ti) in interval Ri.

In following image on X axis are ti values under each red line, which correspond to intervals Ri and green line is one of the possible solutions (in this case constant).

Fitting a function

I know that I need the function f to be continuous and differentiable to at least third degree and it also should be "as smooth as possible". When it is possible to be linear, it should be. I thought of solution where I would fit middle-points of intervals with some spline, but that will bring problems with over-fitting and it is clear that the function could be "smoother" in some sense, though i don't have exact metric for that. In my example image it will create a clearly bad solution and this will be the case even if no linear solution exists.

I know that this "smoothness" criteria is somehow vague. Function f will be a movement of machine in one axis in time, so I need it to move as little as possible without any jumps or rapid velocity changes, but I don't want to define this too precisely, as it would narrow down possible approaches.

I have never encountered a similar problem neither in work nor during my studies and i don't know whether it has some standard name which i could google and research further. I tried to search for descriptions and keywords of my problem, but with no success.

I don't know if it is question for SO or MO, but i need to create an algorithm for finding function f so I am posting it here.

Any help will be much appreciated.

Matej

Axarydax
  • 16,353
  • 21
  • 92
  • 151
Matej
  • 86
  • 3
  • Minimizing smoothness while maintaining values within the intervals leads to a constrained optimization problem. The smoothness criterion is usually formulated as the integral of the square of the second derivative. When the function is a cubic polynomial, the smoothness criterion is a quadratic. I don't know if there are any open source packages which can handle constrained quadratic optimization; pretty sure there are commercial packages to do it. – Robert Dodier May 04 '15 at 17:26
  • You can also impose soft constraints in the form of a cost function which is zero if the output is in the interval and some increasing positive value outside it; add that to the smoothness criterion and minimize the whole mess. This is probably simpler to solve but may not find an exact solution. – Robert Dodier May 04 '15 at 17:32

1 Answers1

1

Here is a paper which treats this problem:

"On Linear Interpolation under Interval Data"

They give an algorithm, but you have to check if it satisfies all your requirements. Otherwise, there are several references given which might be more fruitful. It seems that there is quite a bit of literature on this under the keyword of "unknown but bounded" errors.

cfh
  • 4,576
  • 1
  • 24
  • 34
  • Thank you, it seems quite promising at the first glance. I will let you know if it helped after i read it more closely. – Matej May 04 '15 at 12:28
  • I dunno. It looks like they don't take smoothness (which OP mentioned as a criterion) into account. – Robert Dodier May 04 '15 at 17:25
  • @RobertDodier: It seems they leave the system of basis functions free... so why not choose splines, which have a lot of smoothness naturally? – cfh May 04 '15 at 17:31
  • The smoothness of a spline depends on its parameters, right? Splines aren't smoother than other functions as a class. – Robert Dodier May 04 '15 at 17:40
  • @RobertDodier: If you take splines of degree p with non-repeated knots, they are globally C^(p-1)-smooth. – cfh May 04 '15 at 17:41
  • To say a function has at least so many continuous derivatives is not the same thing as saying that its smoothness, as quantified by integrated square second derivative or anything else, is maximal. – Robert Dodier May 04 '15 at 19:25
  • @RobertDodier: Smoothness is a bit of an overloaded term in mathematics, but generally it's closely related to how many derivatives a function has. [See here.](http://en.wikipedia.org/wiki/Smoothness) If you want to get even more precise, then norms come into play (as you said, for instance some integrals of squared derivatives) -- but derivatives are the primary characteristic of a smooth function. – cfh May 04 '15 at 19:30
  • Counting the number of derivatives isn't any use when actually fitting a function. By that measure, all cubic splines have the same smoothness. To distinguish among the functions in a given class, one must adopt a criterion which depends on the parameters of the approximating function. – Robert Dodier May 04 '15 at 19:39