Skip to content

4.3-final-2000

Final Exam, 2000 · Section 4.3: Least Squares Approximations Source: finalexam_1.pdf, p. 51

Problem

8. (a) (4 points) If \(U\Sigma V^T\) is the singular value decomposition of \(A\) (\(m\) by \(n\)) give a formula for the best least squares solution \(\bar{x}\) to \(Ax = b\). (Simplify your formula as much as possible).

(b) (4 points) Write down the equations for the straight line \(b = C + Dt\) to go through all four of the points \((t_1, b_1)\), \((t_2, b_2)\), \((t_3, b_3)\), \((t_4, b_4)\). Those four points lie on a line provided the vector \(b = (b_1, b_2, b_3, b_4)\) lies in ____.

(c) (4 points) Suppose \(S\) is the subspace spanned by the columns of some \(m\) by \(n\) matrix \(A\). Give the formula for the projection matrix \(P\) that projects each vector in \(R^m\) onto the subspace \(S\). Explain where this formula comes from and any condition on \(A\) for it to be correct.

(d) (4 points) Suppose \(x\) and \(y\) are both in the row space of a matrix \(A\), and \(Ax = Ay\). Show that \(x - y\) is in the nullspace of \(A\). Then prove that \(x = y\).

Solution (a) For \(A = U\Sigma V^T\) with independent columns (all singular values positive), \[ \bar{x} = V\Sigma^{-1}U^T b. \] (Equivalently \(\bar{x} = (A^TA)^{-1}A^T b = V(\Sigma^T\Sigma)^{-1}V^T V\Sigma^T U^T b = V\Sigma^{-1}U^T b\).) (b) The equations \(C + Dt_i = b_i\) for \(i = 1, 2, 3, 4\): \[ \begin{bmatrix} 1 & t_1 \\ 1 & t_2 \\ 1 & t_3 \\ 1 & t_4 \end{bmatrix} \begin{bmatrix} C \\ D \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix}. \] The four points lie on a line provided the vector \(b = (b_1, b_2, b_3, b_4)\) lies in the column space of this 4 by 2 matrix (the columns \((1, 1, 1, 1)\) and \((t_1, t_2, t_3, t_4)\)). (c) \(P = A(A^TA)^{-1}A^T\), provided \(A^TA\) is invertible (the columns of \(A\) are independent, so \(A\) has rank \(n\)). Derivation: the closest point to \(b\) in \(S = C(A)\) is \(p = A\bar{x}\), where \(\bar{x}\) solves the normal equations \(A^TA\bar{x} = A^T b\) (the error \(b - A\bar{x}\) is orthogonal to every column of \(A\)). Then \(p = A(A^TA)^{-1}A^T b\), so \(P = A(A^TA)^{-1}A^T\). (d) \(A(x - y) = Ax - Ay = 0\), so \(x - y\) is in the nullspace of \(A\). Since \(x\) and \(y\) are both in the row space of \(A\), so is \(x - y\). But the row space \(C(A^T)\) and the nullspace \(N(A)\) are orthogonal complements in \(R^n\), intersecting only at the zero vector. Hence \(x - y = 0\), and \(x = y\).

Keywords: singular value decomposition, least squares, projection matrix, row space