4.3-exam2-2007-johnson¶
Quiz 1, 2007 (johnson) · Section 4.3: Least Squares Approximations Source: exam2_1.pdf, pp. 147-148, 148-150
Problem¶
1 (30 pts.) A given circuit network (directed graph) which has an \(m \times n\) incidence matrix \(A\) (rows = edges, columns = nodes) and a conductance matrix \(C\) [diagonal = inverse of the (positive) resistance of each edge] given by:
Suppose the unknowns are the vector \(v\) of voltages at each node, and you are given a vector \(d\) of applied voltage drops across each edge (e.g. if you connect a battery to each edge). In this case, Kirchhoff's laws plus Ohm's law gives the equation:
(a) Sketch the network, labelling each edge from 1 to 4 corresponding to each row of \(A\), and each node from \(1\) to \(3\) corresponding to each column of \(A\), and put an arrow to show the direction of each edge.
(b) Is \(A^T C A v = A^T C d\) always solvable for all \(d\)? Why or why not? [You can use the fact, from class, that \(\operatorname{rank}(A^T C A) = \operatorname{rank}(A) = n - 1\). Hint: think about the subspaces; little or no calculation is necessary. This is not the same as whether \(A^T C A v = s\) is solvable for all \(s\).]
(c) Solve for \(v\) when \(C = I\) (all resistances = 1) and \(d = (5 \; 0 \; 0 \; 0)^T\). To get a unique solution, set the voltage on node 1 to \(v_1 = 0\) ("ground")--this simplifies life to a 3 by 2 matrix problem, since you then only have 2 unknowns \(v_2\) and \(v_3\). [Recall that the null space of \(A\) is the span of \((1 \; 1 \; 1)^T\), so we can add any constant to the solutions.]
(d) For the same \(d\) as in (c), what is the minimum value (minimum over all \(v\)) of \(\|Av - d\|^2\)?
Solution
1a. The network has three nodes \(1, 2, 3\) and four edges: edges 1 and 2 both go from node 2 to node 3; edge 3 goes from node 1 to node 3; edge 4 goes from node 1 to node 2. (These directions are read off from the rows of the incidence matrix \(A\).) 1b. Yes. Since \(\operatorname{rank}(A^T C A) = \operatorname{rank}(A) = n - 1\), and \(\operatorname{rank}(A^T C A) \le \operatorname{rank}(A^T C) \le \operatorname{rank}(A^T) = \operatorname{rank}(A)\), we see that \(\operatorname{rank}(A^T C A) = \operatorname{rank}(A^T C)\). Since the column space of \(A^T C\) contains the column space of \(A^T C A\), and both have the same dimension, the two column spaces are the same. Thus for any \(d\), \(A^T C d\) lies in the column space of \(A^T C A\). In other words, the equation is always solvable. (Alternatively: \(C(A^T C) \subseteq C(A^T) = C(A^T C A)\), with the latter equality because \(C(A^T)\) and \(C(A^T C A)\) have the same dimension [\(\operatorname{rank}(A^T C A) = \operatorname{rank}(A) = \operatorname{rank}(A^T)\)] and \(C(A^T C A) \subseteq C(A^T)\). Recall that \(C(AB) \subseteq C(A)\) for any \(A\) and \(B\), since \(ABx\) is made of the columns of \(A\).) Common errors: many students wrote that, since \(A^T C A\) is singular, there isn't always a solution--this is incorrect because the right-hand side is not an arbitrary vector, it is only vectors \(A^T C d\) in \(C(A^T C)\). Several students wrote that we must have \(Av = d\), which is not true since \(A^T C\) is not invertible (or even square). Several students wrote that, if you ignore the \(C\), this is just like a least-squares problem and least-squares problems are always solvable--this is on the right track (the \(A^T\) on the right-hand side is truly the key here), but the least-squares problems we've studied were only when \(A\) has full column rank, which isn't true here. 1c. The equation becomes \(A^T A v = A^T d\). We calculate: \[ A^T A = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 3 & -2 \\ -1 & -2 & 3 \end{bmatrix}, \qquad A^T d = \begin{bmatrix} 0 \\ 5 \\ -5 \end{bmatrix}. \] Solving by elimination gives \(2v_1 - v_2 - v_3 = 0\) and \(v_2 - v_3 = 2\), so the general solution is \(v = (a+1, \; a+2, \; a)^T\), where \(a\) is an arbitrary number (the multiple of the nullspace vector). To get \(v_1 = 0\), let \(a = -1\), and the unique solution is \[ v = \begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix}. \] (A faster way: we can set \(v_1 = 0\) immediately after constructing \(A^T A\), equivalent to deleting the first column, leaving us with the \(3 \times 2\) problem which has the solution \(v_3 = -1\), \(v_2 = 1\) as above. Another fast way: if we set \(v_1 = 0\) at the very beginning, i.e. delete the first column of \(A\) to obtain a \(4 \times 2\) matrix, the solution is the same as above.) 1d. In order to minimize \(\|Av - d\|^2\), we would solve \(A^T A v = A^T d\), but this is precisely what we already did in part (c)! So the minimum is attained at \(v = (0, 1, -1)^T\) from above, and is given by: \[ \left\| A \begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix} - d \right\|^2 = \left\| \begin{bmatrix} 2 \\ 2 \\ 1 \\ -1 \end{bmatrix} - \begin{bmatrix} 5 \\ 0 \\ 0 \\ 0 \end{bmatrix} \right\|^2 = (-3)^2 + 2^2 + 1^2 + (-1)^2 = 15. \]Keywords: incidence matrix, least squares, column space, solvability