Weighted Least Squares, linear algebra II lesson

Approximate the point $b = (1, 0)$ by a multiple $t(1, 1)$ . Ordinary distance picks $t = \tfrac12$ . If an error in the first coordinate should cost twice as much as an error in the second, the best multiple changes, although neither the target nor the line has moved. Weighted least squares replaces the dot product by a weighted inner product and applies the projection theorem there, which leads to the weighted normal equations and to a clear line between a unique fitted vector and coefficients that may not be unique. Throughout, $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$ , $A^{*}$ is the conjugate transpose, inner products are conjugate-linear in the first argument, and a tuple such as $(1, i)$ stands for a column vector.

Key terms

Positive definite weight matrix

Definition A matrix $W \in \mathbb{F}^{m \times m}$ is a positive definite weight matrix if it is Hermitian, $W^{*} = W$ , and

\begin{gathered} x^{*}Wx > 0 \\[0.4em] \text{for every nonzero } x \in \mathbb{F}^m. \end{gathered}

Over $\mathbb{R}$ this means that $W$ is real symmetric with $x^{\mathsf{T}}Wx > 0$ for $x \ne 0$ . A diagonal matrix qualifies exactly when its diagonal entries are positive real numbers. Such a $W$ is invertible, because $Wx = 0$ gives $x^{*}Wx = 0$ and hence $x = 0$ . A Hermitian matrix with $x^{*}Wx \le 0$ for some nonzero $x$ , such as a singular positive semidefinite matrix or an indefinite one, is not a weight in this sense. Multiplying $W$ by a constant $c > 0$ multiplies every weighted squared error by $c$ , so it does not change which fit is best.

In plain words The weight matrix declares how much each error vector costs, and positive definiteness says that every nonzero error costs something.

Example The Hermitian matrix $W$ with rows $(2, i)$ and $(-i, 2)$ is positive definite. Expanding $\lvert x_1 + ix_2 \rvert^2$ shows

x^{*}Wx = \lvert x_1 \rvert^2 + \lvert x_2 \rvert^2 + \lvert x_1 + ix_2 \rvert^2,

which is positive unless $x = 0$ . At $x = (1, i)$ the value is $1 + 1 + 0 = 2$ . The real symmetric matrix with rows $(1, 2)$ and $(2, 1)$ is not a weight, since $x = (1, -1)$ gives $x^{\mathsf{T}}Wx = -2$ . Fitting the target $0$ by multiples $t(1, -1)$ with this matrix gives the would-be squared error $-2t^2$ , which decreases without bound, so no best fit exists. The matrix $\operatorname{diag}(1, 0)$ is not a weight either, since it gives the nonzero vector $(0, 1)$ zero cost.

Weighted inner product

Definition Let $W \in \mathbb{F}^{m \times m}$ be a positive definite weight matrix. The weighted inner product on $\mathbb{F}^m$ and its norm are

\begin{gathered} \langle x, y \rangle_W = x^{*}Wy, \\[0.4em] \lVert x \rVert_W = \sqrt{x^{*}Wx}. \end{gathered}

It is linear in $y$ , conjugate symmetric because $\overline{y^{*}Wx} = x^{*}W^{*}y = x^{*}Wy$ , and positive definite because $W$ is, so it is an inner product. Conversely, every inner product on $\mathbb{F}^m$ has this form, with $W$ the Gram matrix $W_{ij} = \langle e_i, e_j \rangle$ of the standard basis. For a diagonal weight $W = \operatorname{diag}(w_1, \dots, w_m)$ the squared length is

\lVert r \rVert_W^2 = w_1 \lvert r_1 \rvert^2 + \cdots + w_m \lvert r_m \rvert^2.

In plain words The weighted inner product measures lengths and angles with the costs built in. In the real plane its unit circle is an ellipse.

Example On $\mathbb{R}^2$ with $W = \operatorname{diag}(2, 1)$ , the vector $(1, 0)$ has weighted length $\sqrt{2}$ , the same as $(0, \sqrt{2})$ , and the unit circle becomes the ellipse $2x_1^2 + x_2^2 = 1$ . The vectors $(1, 1)$ and $(1, -2)$ are orthogonal in this inner product, since $2 \cdot 1 \cdot 1 + 1 \cdot (-2) = 0$ , although their dot product is $-1$ .

Weighted orthogonality

Definition Let $W \in \mathbb{F}^{m \times m}$ be a positive definite weight matrix. Vectors $x, y \in \mathbb{F}^m$ are $W$ -orthogonal if $\langle x, y \rangle_W = x^{*}Wy = 0$ . For $A \in \mathbb{F}^{m \times n}$ , $b \in \mathbb{F}^m$ and a coefficient vector $x \in \mathbb{F}^n$ , the residual $r = b - Ax$ is $W$ -orthogonal to the column space of $A$ exactly when

A^{*}W(b - Ax) = 0.

Indeed $\langle Az, r \rangle_W = z^{*}A^{*}Wr$ for every $z \in \mathbb{F}^n$ . If $A^{*}Wr = 0$ , this is zero for every $z$ . If it is zero for every $z$ , the choice $z = A^{*}Wr$ gives the ordinary squared norm $\lVert A^{*}Wr \rVert^2 = 0$ , so $A^{*}Wr = 0$ . By the projection theorem in the inner product $\langle \cdot, \cdot \rangle_W$ , the vector $Ax$ is the point of the column space closest to $b$ in the weighted norm exactly when this condition holds.

In plain words Perpendicular now means perpendicular for the weighted inner product. A residual can look slanted in an ordinary drawing and still be orthogonal in the weighted geometry.

Example Fit $b = (1, 0)$ by $t(1, 1)$ with $W = \operatorname{diag}(2, 1)$ . At $t = \tfrac23$ the residual is $r = (\tfrac13, -\tfrac23)$ , and

\langle (1, 1), r \rangle_W = 2 \cdot \tfrac13 - \tfrac23 = 0,

so $r$ is $W$ -orthogonal to the line, even though its dot product with $(1, 1)$ is $-\tfrac13$ . The ordinary fit $t = \tfrac12$ has residual $(\tfrac12, -\tfrac12)$ , which is orthogonal for the dot product but has weighted inner product $\tfrac12$ with $(1, 1)$ . Its weighted squared error is $\tfrac34$ , larger than the $\tfrac23$ of the weighted fit.

Weighted normal equations

Definition Let $A \in \mathbb{F}^{m \times n}$ and $b \in \mathbb{F}^m$ , and let $W \in \mathbb{F}^{m \times m}$ be a positive definite weight matrix. A coefficient vector $\hat{x} \in \mathbb{F}^n$ minimizes the weighted squared error $(b - Ax)^{*}W(b - Ax)$ exactly when it solves the weighted normal equations

A^{*}WA\,\hat{x} = A^{*}Wb.

They are the orthogonality condition of the previous card, rearranged. They always have a solution, because the projection theorem supplies a closest point $p$ of the column space, and every $\hat{x}$ with $A\hat{x} = p$ solves them. The $n \times n$ matrix $A^{*}WA$ is Hermitian with $z^{*}A^{*}WAz = \lVert Az \rVert_W^2 \ge 0$ . It is positive definite, hence invertible, exactly when the columns of $A$ are linearly independent, and then

\hat{x} = (A^{*}WA)^{-1}A^{*}Wb.

With $W = I$ these are the ordinary normal equations, and over $\mathbb{R}$ they read $A^{\mathsf{T}}WA\,\hat{x} = A^{\mathsf{T}}Wb$ . The formula describes the answer. Forming and inverting $A^{*}WA$ is not always the most accurate way to compute it.

In plain words Each column gives one equation, which says that the residual is orthogonal to that column in the weighted inner product. Solving them gives the coefficients of the best fit.

Example Fit a line $c_0 + c_1 t$ to the data points $(0, 1)$ , $(1, 0)$ and $(2, 3)$ with weights $3$ , $3$ and $1$ , so that the last point counts a third as much as each of the others. Here $W = \operatorname{diag}(3, 3, 1)$ and

A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \qquad b = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix},

so the weighted normal equations are

\begin{bmatrix} 7 & 5 \\ 5 & 7 \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \end{bmatrix} = \begin{bmatrix} 6 \\ 6 \end{bmatrix},

with solution $c_0 = c_1 = \tfrac12$ . The fitted values are $(\tfrac12, 1, \tfrac32)$ , and the residual $r = (\tfrac12, -1, \tfrac32)$ satisfies $A^{\mathsf{T}}Wr = 0$ , since $3 \cdot \tfrac12 - 3 + \tfrac32 = 0$ and $-3 + 2 \cdot \tfrac32 = 0$ . The unweighted fit is $\tfrac13 + t$ . Giving the third point less weight produces a flatter line that stays closer to the first two points.

Uniqueness of the fitted vector

Definition In the setting of the weighted normal equations, the fitted vector $p = A\hat{x}$ is the same for every minimizer $\hat{x}$ . It is the orthogonal projection of $b$ onto the column space of $A$ in the inner product $\langle \cdot, \cdot \rangle_W$ , and it depends only on $b$ , $W$ and that column space. If $\hat{x}_0$ is one minimizer, the set of all minimizers is

\hat{x}_0 + \ker A = \{ \hat{x}_0 + z \mid Az = 0 \}.

Two minimizers give the same unique closest point, so their difference lies in $\ker A$ , and adding a vector of $\ker A$ does not change $A\hat{x}$ . The coefficient vector is therefore unique exactly when $\ker A = \{0\}$ , that is, when the columns of $A$ are linearly independent.

In plain words The best fitted output is always unique. Its recipe in terms of the columns is unique only when no column is a combination of the others.

Example Take both columns of $A$ equal to $(1, 1)$ , with $b = (1, 0)$ and $W = \operatorname{diag}(2, 1)$ . The weighted normal equations

\begin{bmatrix} 3 & 3 \\ 3 & 3 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 2 \end{bmatrix}

say only that $x_1 + x_2 = \tfrac23$ . The coefficient vectors $(\tfrac23, 0)$ , $(0, \tfrac23)$ and $(\tfrac13, \tfrac13)$ all solve them. They differ by multiples of $(1, -1)$ , which spans $\ker A$ , and each one gives the same fitted vector $(\tfrac23, \tfrac23)$ .

Inner product from sample values

Definition Let $t_1, \dots, t_N$ be distinct real nodes and $w_1, \dots, w_N$ positive weights. On $\mathcal{P}_d$ , the polynomials of degree at most $d$ with coefficients in $\mathbb{F}$ , set

\langle p, q \rangle = \sum_{k=1}^{N} w_k\,\overline{p(t_k)}\,q(t_k).

This is linear in $q$ and conjugate symmetric. It is positive definite, and so an inner product, exactly when $N \ge d + 1$ . If $N \ge d + 1$ , then $\langle p, p \rangle = \sum_k w_k \lvert p(t_k) \rvert^2 = 0$ forces $p(t_k) = 0$ at $d + 1$ or more points, so $p = 0$ . If $N \le d$ , the nonzero polynomial $(t - t_1) \cdots (t - t_N)$ lies in $\mathcal{P}_d$ and has norm $0$ , so the formula gives only a seminorm. With the sample vector $s(p) = (p(t_1), \dots, p(t_N))$ and $W = \operatorname{diag}(w_1, \dots, w_N)$ the formula reads $\langle p, q \rangle = s(p)^{*}W s(q)$ . Projecting $p$ onto a subspace $U = \operatorname{span}\{u_1, \dots, u_n\}$ in this inner product is therefore weighted least squares, with $b = s(p)$ and with the columns $s(u_1), \dots, s(u_n)$ forming $A$ .

In plain words Two polynomials are compared only through their weighted values at the chosen nodes. There must be enough nodes to tell any two different polynomials apart.

Example The line fit in the normal equations card is a projection of this kind. On $\mathcal{P}_2$ with nodes $0, 1, 2$ and weights $3, 3, 1$ , the data $(1, 0, 3)$ are the samples of $p(t) = 2t^2 - 3t + 1$ , and the projection of $p$ onto $\mathcal{P}_1$ is $\tfrac12 + \tfrac12 t$ . With only the nodes $-1$ and $1$ and weights $1$ , the formula is an inner product on $\mathcal{P}_1$ but not on $\mathcal{P}_2$ , because $t^2 - 1$ vanishes at both nodes. The polynomials $t^2$ and $1$ then have the same samples $(1, 1)$ . A fit from $\mathcal{P}_2$ to these samples has a unique fitted sample vector, but every polynomial $1 + c(t^2 - 1)$ produces it.

Check yourself

Fit $b = (1, 0)$ by $t(1, 1)$ with the weight $W = \operatorname{diag}(1, 3)$ . Find $t$ , the residual and the weighted squared error, and check that the residual is $W$ -orthogonal to $(1, 1)$ .

Show the answer

The normal equation is the scalar equation $(1 + 3)\,t = 1$ , so $t = \tfrac14$ . The fitted point is $(\tfrac14, \tfrac14)$ and the residual is $(\tfrac34, -\tfrac14)$ . Its weighted inner product with $(1, 1)$ is $\tfrac34 + 3 \cdot (-\tfrac14) = 0$ , and the weighted squared error is

\tfrac{9}{16} + 3 \cdot \tfrac{1}{16} = \tfrac{3}{4}.

The heavy weight now sits on the second coordinate, so the fit moves toward the second coordinate of $b$ , which is $0$ .

Is $\langle p, q \rangle = p(0)\,q(0) + 3\,p(2)\,q(2)$ an inner product on the real polynomials $\mathcal{P}_1$ ? On $\mathcal{P}_2$ ?

Show the answer

On $\mathcal{P}_1$ it is. The formula is symmetric and bilinear, and a polynomial of degree at most $1$ that vanishes at the two distinct nodes $0$ and $2$ is the zero polynomial, so $\langle p, p \rangle > 0$ for $p \ne 0$ . On $\mathcal{P}_2$ it is not, because $t^2 - 2t = t(t - 2)$ is nonzero and has $\langle p, p \rangle = 0$ . Positive weights alone are not enough. The number of distinct nodes must be at least $d + 1$ .

Let $W = \operatorname{diag}(1, 1, 2)$ and $b = (1, 2, 4)$ , and let $A$ have columns $(1, 0, 1)$ , $(0, 1, 0)$ and $(1, 1, 1)$ . Find all minimizers of the weighted squared error, the fitted vector and the residual, and check weighted orthogonality.

Show the answer

The third column is the sum of the first two, so the columns are dependent and $\ker A$ is spanned by $(1, 1, -1)$ . The weighted normal equations are

\begin{bmatrix} 3 & 0 & 3 \\ 0 & 1 & 1 \\ 3 & 1 & 4 \end{bmatrix} \hat{x} = \begin{bmatrix} 9 \\ 2 \\ 11 \end{bmatrix}.

The third equation is the sum of the first two, which say $\hat{x}_1 + \hat{x}_3 = 3$ and $\hat{x}_2 + \hat{x}_3 = 2$ . So the minimizers are $\hat{x} = (3, 2, 0) + s(-1, -1, 1)$ for every scalar $s$ , and all of them give the fitted vector $p = (3, 2, 3)$ . The residual $r = (-2, 0, 1)$ satisfies

\begin{aligned} \langle (1, 0, 1), r \rangle_W &= -2 + 2 \cdot 1 = 0, \\[0.4em] \langle (0, 1, 0), r \rangle_W &= 0, \end{aligned}

so $r$ is also $W$ -orthogonal to the third column, which is the sum of the first two. The weighted squared error is $4 + 0 + 2 = 6$ . The ordinary dot product of $r$ with $(1, 0, 1)$ is $-1$ , so the residual is orthogonal only in the weighted sense.

Weighted Least Squares

Key terms

Positive definite weight matrix

Weighted inner product

Weighted orthogonality

Weighted normal equations

Uniqueness of the fitted vector

Inner product from sample values

Check yourself

How this lesson connects

Builds on

Used later in