Are there variations on least-squares approximations?

In least-squares approximations the normal equations act to project a vector existing in N-dimensional space onto a lower dimensional space, where our problem actually lies, thus providing the "best" solution we can hope for (the orthogonal projection of the N-vector onto our solution space). The "best" solution is the one that minimizes the Euclidean distance (two-norm) between the N-dimensional vector and our lower dimensional space.

There exist other norms and other spaces besides $\mathbb{R}^d$, what are the analogues of least-squares under a different norm, or in a different space?

-
If you consider it equivalent to say you are minimizing error induced by noise, then euclidean distance is correct when the noise is Gaussian, but if it is Laplacian then the absolute value would be better. I'm not sure if you would consider this answer valid but if you want I can expand it as full answer. – Jonathan Fischoff Jul 25 '10 at 22:51
I would like to see that whenever you get a chance. (This is a real question of mine, btw.) – Tom Stephens Jul 25 '10 at 22:57
If no one beats me to it I'll put it together after I rewrite my bent coin question. – Jonathan Fischoff Jul 25 '10 at 23:05
Great, I want to see a solution to that before I want to see one here -that problem looked outrageous! – Tom Stephens Jul 25 '10 at 23:12

The usual cases treated apart from least squares are the one-norm and infinity-norm (Chebyshev) cases; they crop up in function approximation for instance.

Usually both of these are solved via linear programming techniques.

-

For regression, least sum of squares criterion tried to fit your function through the mean of the data. In other words, with enough degrees of freedom, value of your fitted function for x will be the average of all observed values at x. Least sum of absolute values instead produces a function that'll go through the median of observed values. Some discussion on this

-

Sure, there are variations on least-squares approximations.

Here's an engineering answer (not really a pure math answer): On one project I did at my company, we had a thermal model that was approximating the thermal transfer function from measured power to device temperature. The cost of error in the positive direction (underestimating temperature) was worse than the cost of the same error in the negative direction (overestimating temperature) -- so we used a weighting function that was (K * error ^ 2) where K was 1 for negative temperature error and greater than 1 (e.g. 1.5 or 2) for positive temperature error.

We thought about using more complicated mappings (10 degrees underestimate much worse than 1 degree underestimate) but didn't want to go there... I assume this has some analog to a utility function (e.g. expected monetary gain of a system with random outcome has nonlinear mapping to "happiness" or "utility") where nonlinearity is intentionally introduced.

You could do something similar for approximating functions with polynomials: a least-squares fit treats error in a linear way, but there may be places in the function (e.g. at the ends or at the center) where minimizing error is more or less important.

-