6.8 Applications of inner product spaces

Big idea

Three problems that look unrelated turn out to be one problem. Weighting some measurements more heavily than others, separating a data set into a constant part plus a linear trend plus a curvature term, and approximating a signal by a few sines and cosines are all projections onto a subspace.

What changes between them is which inner product is in force and which orthogonal basis is chosen for the subspace. Choose the weights and you have weighted least squares. Choose an orthogonal basis of polynomials and the fit splits into independent pieces you can read one at a time. Choose sines and cosines and the pieces are frequencies.

The reason each of these is worth setting up as a projection is the same reason orthogonal bases were worth building in the first place: with an orthogonal basis, every coefficient is a single quotient, and adding a term to the model does not disturb the terms already computed.

Decoder

“Weighted least squares” sounds like a different method; it is the same method in a different inner product. Minimizing $\sum w_i^2(y_i - f(x_i))^2$ is minimizing the ordinary squared length of the residual after every row of the system has been multiplied by its weight. So you scale the rows and then run least squares as usual.

“Trend analysis” sounds like statistics vocabulary; it is a change of basis. The data are projected onto the same space of low-degree polynomials as before, but expressed in an orthogonal basis, so the constant, linear, and quadratic contributions are separate numbers instead of coupled coefficients.

Definitions and results

Weighted inner product for fitting. Give observation $i$ a positive weight $w_i$ and use $\langle \mathbf{u}, \mathbf{v} \rangle = \sum w_i^2 u_iv_i$. A larger weight means a larger penalty for missing that observation, so the fit is pulled toward the observations you trust.

Weighted normal equations. Let $W$ be the diagonal matrix of weights. The weighted least-squares problem for $X\beta \approx \mathbf{y}$ is the ordinary one for $WX\beta \approx W\mathbf{y}$, so the parameters solve

$$ (WX)^T(WX)\hat{\beta} = (WX)^TW\mathbf{y} $$

Written out with sums, each term of the ordinary normal equations picks up a factor of $w_i^2$.

Weighted orthogonality of residuals. The residual is orthogonal to the columns of $X$ in the weighted product, not the ordinary one: $\sum w_i^2 r_i = 0$ when the model has a constant term, rather than $\sum r_i = 0$. Checking with the wrong product will make a correct fit look wrong.

Trend analysis. Observations at $n + 1$ distinct input values are a vector under the evaluation inner product. Build an orthogonal basis $\{p_0, p_1, p_2, \dots\}$ of polynomials with $p_k$ of degree $k$, by running Gram-Schmidt on $1, t, t^2, \dots$. Project the data onto the span of the first few. The coefficient of $p_0$ is the constant level, of $p_1$ the linear trend, of $p_2$ the quadratic component, and so on. Because the basis is orthogonal, truncating after $p_1$ gives exactly the best linear fit: dropping later terms does not change the earlier coefficients.

Fourier approximation. Take the space of functions with inner product $\langle f, g \rangle = \int_0^{2\pi} f(t)g(t)\,dt$. The functions $1, \cos t, \sin t, \cos 2t, \sin 2t, \dots$ are mutually orthogonal under it, so the best approximation to $f$ from combinations of the first several is the projection, and each coefficient is an integral divided by the squared length of its basis function. Those coefficients are the Fourier coefficients, and the truncated sum is the $n$-th order Fourier approximation.

The discrete version. Sample at finitely many evenly spaced points and the integrals become sums. The sampled sines and cosines are ordinary vectors in $\mathbb{R}^n$, still mutually orthogonal, and the whole computation is a projection in $\mathbb{R}^n$ with no calculus in it.

Worked examples

Weighting the middle measurement

Fit a line $y = \beta_0 + \beta_1 x$ to three observations at $x = -1, 0, 1$ with values $y = 1, 2, 9$, where the middle measurement is twice as reliable: weights $w = 1, 2, 1$.

The weighted normal equations use $w_i^2 = 1, 4, 1$. Compute the sums: $\sum w_i^2 = 6$, $\sum w_i^2 x_i = -1 + 0 + 1 = 0$, and $\sum w_i^2 x_i^2 = 1 + 0 + 1 = 2$. Since the middle sum is zero, the two equations separate:

$$ 6\beta_0 = \sum w_i^2 y_i = 1 + 8 + 9 = 18, \qquad 2\beta_1 = \sum w_i^2 x_iy_i = -1 + 0 + 9 = 8 $$

So $\beta_0 = 3$ and $\beta_1 = 4$, and the weighted fit is $y = 3 + 4x$.

Check with the weighted orthogonality conditions. The fitted values are $-1$, $3$, $7$, so the residuals are $2$, $-1$, $2$. Then $\sum w_i^2 r_i = 2 - 4 + 2 = 0$ and $\sum w_i^2 x_ir_i = -2 + 0 + 2 = 0$. Both hold. Note that the plain sum $2 - 1 + 2 = 3$ is not zero, which is correct: the ordinary condition does not apply here.

Compare with equal weights. Then $\beta_0$ is the mean $12/3 = 4$ and $\beta_1 = \sum x_iy_i / \sum x_i^2 = 8/2 = 4$, giving $y = 4 + 4x$. Doubling the weight on the middle point, whose value $2$ sits below the trend, pulled the intercept from $4$ down to $3$ and left the slope unchanged.

Splitting data into trend components

Take the same observations, now as a vector under the evaluation inner product at $t = -1, 0, 1$. The orthogonal polynomial basis built earlier in the chapter is $p_0 = 1$, $p_1 = t$, $p_2 = t^2 - \tfrac{2}{3}$, with squared lengths $3$, $2$, and $\tfrac{2}{3}$.

Compute the three coefficients. For the constant term, $\langle g, p_0 \rangle = 1 + 2 + 9 = 12$, so $c_0 = 12/3 = 4$. For the linear term, $\langle g, p_1 \rangle = -1 + 0 + 9 = 8$, so $c_1 = 8/2 = 4$. For the quadratic term,

$$ \langle g, p_2 \rangle = 1\left(\tfrac{1}{3}\right) + 2\left(-\tfrac{2}{3}\right) + 9\left(\tfrac{1}{3}\right) = \tfrac{1}{3} - \tfrac{4}{3} + 3 = 2 $$

so $c_2 = 2 \div \tfrac{2}{3} = 3$.

The decomposition is $g = 4p_0 + 4p_1 + 3p_2$. Expanding, $4 + 4t + 3t^2 - 2 = 3t^2 + 4t + 2$, which reproduces the data exactly: $3 - 4 + 2 = 1$ at $t = -1$, $2$ at $t = 0$, and $3 + 4 + 2 = 9$ at $t = 1$.

The point of the orthogonal basis is what you can now read off. The constant level is $4$, the linear trend is $4t$, and the curvature contributes $3p_2$. Truncating after the linear term leaves $4 + 4t$, which is precisely the unweighted least-squares line computed in the previous example. No refitting was needed to drop a term.

A discrete Fourier projection

Sample at the four points $t = 0, \tfrac{\pi}{2}, \pi, \tfrac{3\pi}{2}$ and record each basis function as a vector of its four values:

$$ \mathbf{c}_0 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{c}_1 = \begin{bmatrix} 1 \\ 0 \\ -1 \\ 0 \end{bmatrix}, \quad \mathbf{s}_1 = \begin{bmatrix} 0 \\ 1 \\ 0 \\ -1 \end{bmatrix}, \quad \mathbf{c}_2 = \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} $$

coming from $1$, $\cos t$, $\sin t$, and $\cos 2t$. All six pairs have dot product zero, so this is an orthogonal basis for $\mathbb{R}^4$. The squared lengths are $4$, $2$, $2$, and $4$.

Project the sampled signal $\mathbf{y} = (3, 5, 1, 3)$. The coefficients are $\mathbf{y} \cdot \mathbf{c}_0 / 4 = 12/4 = 3$, then $\mathbf{y} \cdot \mathbf{c}_1 / 2 = (3 - 1)/2 = 1$, then $\mathbf{y} \cdot \mathbf{s}_1 / 2 = (5 - 3)/2 = 1$, and finally $\mathbf{y} \cdot \mathbf{c}_2 / 4 = (3 - 5 + 1 - 3)/4 = -1$.

Check by rebuilding: $3\mathbf{c}_0 + \mathbf{c}_1 + \mathbf{s}_1 - \mathbf{c}_2$ has entries $3 + 1 + 0 - 1 = 3$, $3 + 0 + 1 + 1 = 5$, $3 - 1 + 0 - 1 = 1$, and $3 + 0 - 1 + 1 = 3$. That is $\mathbf{y}$.

Now drop the highest frequency. The best approximation from the span of $\mathbf{c}_0, \mathbf{c}_1, \mathbf{s}_1$ is $3 + \cos t + \sin t$ sampled at those points, and the error is the discarded term $-\mathbf{c}_2$, of length $2$. Discarding high-frequency terms is exactly projecting onto a smaller subspace, and the size of what you dropped is the price.

Practice

The orthogonal basis is what makes each of these applications a list of quotients, and building one is the Gram-Schmidt drill.

Then the projection itself, which is the shared computation behind all three applications.

Quiz

Five items on weighted fits, orthogonal bases, and projections.