polynomial regression

Suppose your data curves rather than runs straight. Polynomial regression fits a curve y = c_0 + c_1 x + c_2 x^2 + ... + c_d x^d through the points by least squares. The lovely surprise is that, although the curve is nonlinear in x, it is perfectly LINEAR in the unknown coefficients c_0, ..., c_d — so the whole machinery of linear least squares applies unchanged. The same idea covers any model that is a linear combination of fixed functions: sines and cosines, exponentials, splines — collectively called general linear regression.

The mechanics: build the design matrix A whose columns are the chosen functions evaluated at the data points. For a degree-d polynomial through points x_1, ..., x_m, row i is (1, x_i, x_i^2, ..., x_i^d). Then you solve the least-squares problem A c = y for the coefficient vector c, exactly as before — preferably by QR, not the normal equations. Each column is a 'feature'; the residual r = y - A c being orthogonal to the columns means the fit has squeezed out all the signal those features can explain. Choosing the functions is modeling; finding the best coefficients is linear algebra.

Two honest warnings. First, more flexibility is not better: a high-degree polynomial can wiggle through every training point yet predict garbage between them — overfitting, the bias-variance trade-off in action. Second, and specific to polynomials, the monomial basis (1, x, x^2, ...) makes the design matrix a Vandermonde matrix, which becomes catastrophically ill-conditioned as the degree grows, so the coefficients become numerically meaningless. The cure is to use a better-conditioned basis — orthogonal polynomials like Chebyshev, or centering and scaling x — rather than raw powers.