1
$\begingroup$

I need to use line segments to approximate a function, f = 1/x. The range of x is from 1 to 2048 with an interval of 1. I will pick 10 locations for x and interpolate y between two adjacent x using line segment. The error between interpolated values and real values is expected to be minimum. I am using MATLAB for implementation.

The problem is that picked points are in order. If the picked points are modified, the points between two picked points will be changed accordingly. How can I write an objective function for such case?

I have little experience of optimization using MATLAB. How do I write an objective function that need to be optimized?

$\endgroup$
2
  • $\begingroup$ What do you mean by "with an interval of 1"? $\endgroup$ – nicoguaro May 6 '15 at 13:03
  • 1
    $\begingroup$ I am a little bit confused about what you are trying to do. Do you mean that you will only have 10 points (and thus 9 line segments) to approximate the function f between 1 and 2048? Or do you you mean that you will have an arbitrary number of points (presumable fairly large) evenly spaced between 1 and 2048 and that you then want to pick 10 x points (that probably don't coincide with your interpolations points) and thus use the line segment to interpolate the approximate y values? $\endgroup$ – James May 21 '15 at 1:32
1
$\begingroup$

First, I would like to mention that what you define as 'error' is pretty important. You could obtain error estimates based on an assortment of different norms or error measures, each most likely resulting in a slightly different solution. Optimality will always be depending on the error/cost function.

Next, I personally formulated it as a Weighted Nonlinear Least Squares problem, where the location of each x point used for interpolation is a part of a vector seeking to be optimized using the standard Weighted Least Squares styled cost function.

I did a first attempt trying to use gradient descent with this formulation, trying out the results with a few different guesses. A guess I formulated before I even attempted this numerically has found to be roughly optimal when I plugged it into the numerical algorithm.

This sub-optimal analytical solution is:

$$x = e^{(-as)}$$

where $a = -ln(2048)$, and $s \in [0, 1]$. For this problem, choose 10 equally spaced apart values for $s$ starting at $s$ = 0 and ending at $s$ = 1. This generates a set of x values increasingly spreading apart as x increases.

Now, I got some pretty worthwhile results with the approach I did, but I am not sure if it's totally optimal or not with respect to the cost function I made. I would recommend tackling this problem using a more global optimization approach, such as Particle Swarm Optimization, Genetic Optimization, etc.

Here's some possibly helpful references:

Basic $L^p$ Norm Info

Least Squares Info

$\endgroup$
3
  • $\begingroup$ Given the relative simplicity of the problem, I think that typically the error measure would be designed so as to make objective function convex. Then a local optimization can be used. (This is however not always the case.) $\endgroup$ – GeoMatt22 Oct 23 '15 at 0:28
  • $\begingroup$ You're correct @GeoMatt22! In that event, it could be better. However, I don't know what convex cost function could be used. I will note, I actually solved this type of problem later by using an adaptive segmenting approach, and it worked very well. So that might be better. $\endgroup$ – spektr Oct 23 '15 at 1:04
  • $\begingroup$ I am not an expert, but I believe for "sum pointwise error" objectives, convexity of the pointwise error metric translates to convexity of the objective function. The Wikipedia page I linked above mentions the Huber metric as a classic "robust" local measure which is convex. These robust m-estimators are widely used in computer vision applications (e.g. here). $\endgroup$ – GeoMatt22 Oct 23 '15 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.