1
$\begingroup$

Background:

I am writing some software can fit a mathematical curve to data using different regression techniques. I currently have Ordinary Least Squares and Least Absolute Deviations mostly implemented, and am now working on Total Least Squares. In TLS, both x and y distances from the curve are minimized, rather than just y.

Problem:

In order to get my software to work, I need a closed-form solution to finding the minimum distance between a point $(x_{n}, y_{n})$ and a function $f(x)$ on an unbounded domain. It also needs to be reasonably fast to compute (so preferably non-iterative) because this operation could possibly be carried out thousands of times during the curve fitting process.

What I Know So Far:

  • I know that a global minimum value must exist. The distance between $(x_{n}, y_{n})$ and $(x, f(x))$ can be modeled by $\sqrt{(x_n-x)^2 + (y_n-f(x))^2}$, which I believe (from what I've read) is coercive, which implies the existence of a global minimum.
  • The minimum value must be less than or equal to $|y_n - f(x_n)|$, assuming $f(x_n)$ is defined.

My Plea:

Can someone at least point me in a direction?

$\endgroup$
  • 1
    $\begingroup$ A closed-form exact solution for an arbitrary function $f$? No such thing! $\endgroup$ – Robert Israel Aug 19 '15 at 4:54
  • $\begingroup$ Not even if the minimum is guaranteed to exist? $\endgroup$ – Mr. Nielsen Aug 19 '15 at 5:00
0
$\begingroup$

Suppose $f(x)$ is a polynomial of degree $d$ with rational coefficients, and for convenience take $(x_n, y_n) = (0,0)$. You want to minimize $g(x) = x^2 + f(x)^2$ (the square of your distance): the minimum occurs at a root of $g'(x) = 2 x + 2 f(x) f'(x)$, a polynomial of degree $2d-1$ which will usually be irreducible over the rationals, so the root would be an algebraic number of degree $2d-1$. You then evaluate $g(x)$ at such a root: the result will again be likely to be algebraic of degree $2d-1$. So unless you can solve polynomials of high degree in "closed form", you're not going to be able to do this exactly.

For example, try $f(x) = x^3 + x + 1$. The minimum occurs at a root of $6\,{x}^{5}+8\,{x}^{3}+6\,{x}^{2}+4\,x+2$, and the minimum value is a root of ${z}^{5}-2\,{z}^{4}+\frac {31}{27}{z}^{3}+{\frac {2}{27}} z -\frac{1}{27}$. That polynomial has Galois group $S_5$, so no solution in radicals.

$\endgroup$
  • $\begingroup$ Would it change anything if $f(x)$ was approximated by many small line segments? $\endgroup$ – Mr. Nielsen Aug 19 '15 at 19:48
  • $\begingroup$ Then in general you'd have to look at each segment. Each individually is easy, but a lot of them would take a lot of time. $\endgroup$ – Robert Israel Aug 19 '15 at 20:50

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.