I know how to calculate a least-squares regression, which minimizes the sum of the squares of the distances to the line. Instead, I want to minimize the the maximum distance (of any point) to the line. Can someone point me in the right direction .... is there a formula or would it be some kind of iterative refinement?
You need more fit coefficients, that is, a higher order fit. First order (linear) being y = mx +b, now you are talking about a polynomial fit curve with higher order like y = ax^3 + bx^2 + cx +d. For a perfect fit you need n-1 orders, that is to fit to 4 points exactly requires a 3rd order polynomial fit curve. My apologies if I have missed your point or have oversimplified.
I'll add a few words. You can fit to a higher order than n-1 by all means but you may see some unpleasant behaviour between your data points. Yes, the curve may pass perfectly through your points but may also reach extreme values in between. Thats why you try to restrict your polynomial to the necessary order. I once did all the curve fitting of analog telemetry parameters for an oceanographic research satellite program at the Jet Propulsion Laboratory. I rarely used more than a 6th order fit. They started getting wild looking above that.
Thanks, but I do want a straight line that minimize the the maximum distance (of any point) to the line.
Ok, you want to minimize the "lack of fit" of your line I think. Take a look: http://en.wikipedia.org/wiki/Lack-of-fit_sum_of_squares
Lack of fit sounds good. Other possible answers would be weighted least squares or iteratively re-weighted least squares. There might be some other method where you fit only the worst fitted points based on outlier detection or decile/quartile, not sure the official name though.
distance from a line y=kx+c to a point (x_i, y_i) is abs (-kx_i+y_i-c)/sqrt(1+k^2), so for n data points you are looking for a pair (k,c) that minimizes max {abs(-kx_i+y_i-c)/sqrt(1+k^2)} for i=1,...n this is a so-called minimax problem and you have a non-linear function. i think you could use matlab to solve this: http://www.mathworks.de/access/helpdesk/help/toolbox/optim/ug/fminimax.html
Looks like a perfect solution is beyond my scope, but with this method I have a pretty good approximation. Visually, it is what I was looking for.