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?
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.