Regressions: Linear \& Otherwise

Regressions, ubiquitously used in statistics,
are just ``projection onto a subspace''.
They go under the name ``the method of least squares''
and were pioneered by Gau\ss, who used them to compute the orbits of
asteroids (based on observations).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Abstractly:

Given a collection of $n$ data points, collected at $n$ sample points,
it's a point in $\bR^n$. Linear functions (or whatever) sit inside
this as a subspace (defined by the sample points).
Linear (or whatever) regression is
``project the data vector onto the linear subspace,
  then express in terms of the obvious basis in linear functions''

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Concretely:

Suppose your data points are $(x_i,y_i)$
(at sample point $x_i$, you record value $y_i$).
Then your data vector is $(y_1,\dots,y_n) \in \bR^n$.

If you evaluated the linear function $a+bx$ at those same sample
points, you'd get the output vector $(a+bx_1, \dots, a+bx_n)$.
In other words, linear functions sit inside $\bR^n$ as a plane
(so long as you have at least 2 data points),
given by $A*(a,b)$ where
$$A^t =
[1   \cdots 1]
[x_1 \cdots x_n]$$
The span of $A$ is exactly ``how linear functions are embedded'',
where the $1$ corresponds to ``constant'',
  (the function $1$ always evaluates to $1$)
the $x_i$ corresponds to ``data point $x_i$''.
  (the function $x$ evaluates to $x_i$).

Now orthogonally project onto this subspace, and express in terms of
the basis $1,x$ on linear functions.

The formula for orthogonal projection (onto the image of $A$) is
$$A(A^t A)^{-1}A^t$$
Since we want to express the result in terms of the given basis for
$\im A$, we can drop the left-most $A$
  (remember why this is the formula:
   $A^t$ takes inner products with the basis vectors of image $A$,
   while multiplying by $A$ uses these as coefficients
   of the basis vectors of image $A$ to put you in the image;
   the $(A^t A)^{-1}$ is a correction in case your basis isn't
   orthonormal.
   So dropping the left-most $A$ is exactly what we want.)
and the formula for least-squared regressions is:
$$(A^t A)^{-1}A^t$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Quadratic and More variables

For quadratic regressions, do as before, but now
$$A^t =
[1     \dots 1    ]
[x_1   \dots x_n  ]
[x_1^2 \dots x_n^2]$$
as the rows are ``the value of $1,x,x^2$ at $x_i$''
(since the columns correspond to the functions $1,x,x^2$).
...and likewise for higher order.

If you have more variables, then just write your sample points in some
order (say, lex: $(x_1,y_1),\dots,(x_1,y_n),(x_2,y_1),\dots$)
and do the same; obviously can incorporate $xy, x^2 y^3$, etc.

So you'd get
$$A^t =
[1   ... 1   1   ... 1]
[x_1 ... x_1 x_2 ... x_m]
[y_1 ... y_n y_1 ... y_n]$$
...and the various outputs (data points) should line up in the
corresponding way
(i.e., $d(x_1,y_1), d(x_1,y_2), \dots$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Oh, and if you have several outputs,
you can just fit 'em separately.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Constant regressions

The answer to "the best constant approximation" is the -average-.

Indeed, you can do this the other way:
given a set of points/a function, take the average.
This is an operation, an answer, -in search of a question-:
it is a construction, but what problem does it solve?

the variational (optimization) problem it solves is "best constant
approx"
[in the L^2 sense; in L^\infty, the answer is the average of sup
 and inf, while in L^1, anything between sup and inf works equally
 well.
 This is cute to draw in R^2 (i.e., fit a constant to 2 values),
 and it gives you more of a feel for the neighborhoods]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Polynomial regression

Since the van~der~Monde matrix is invertible,
and size $(d+1) \times (d+1)$, given $d+1$ data points
(assuming distinct sample points)
there's a unique degree $d$ polynomial passing through 'em.
If you have fewer data points, there's many polynomials passing
through 'em, but only 1 of the lowest degree:
given 2 points, there's a 1-parameter family of quadratics passing
through 'em, only 1 of which is a line (the rest are parabolae).

Incidentally, if you use the same sample point twice and take a linear
regression, you get ``lines of all slopes that pass through the
average value at that point'' -- this parameter corresponds to the
kernel.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Oh, and the invertibility of the van~der~Monde matrix
is exactly the statement that any $n+1$ on the rational normal curve
are in (affine) general (linear) position.
(which characterizes the curve)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
BTW, the general polynomial regression matrix \& formula is a
generalization (of sorts) of the van~der~Monde matrix (\& inverse).

This is rather similar to how the Grammian generalizes (sorta) the
determinant;
again, note the use of the transpose and how you thus essentially
need an inner product.
(Obviously the van~der~Monde matrix is written w/r/t a basis;
 I'm talking about the Grammian)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Dunno if this is mentioned above:
constant regression
(best fit constant) is aka -averaging-.
This is a simple case;
it's also easy to visualize the projection:
  you're projecting onto the -diagonal-.
