Lecture 9: Four Ways to Solve Least Squares Problems

What this lecture covers

This lecture asks how to solve Ax = b when no exact solution exists, the standard situation in data fitting where there are more measurements than unknowns. It sits early in the course's move from pure linear algebra toward the applications, using least squares as the bridge topic before singular value decomposition ideas carry into deeper data problems.

After watching, you should be able to define the pseudo-inverse of a matrix from its SVD, derive the normal equations A^T A x = A^T b from minimizing the squared error, and see why the projection of b onto the column space of A is the geometric picture behind both. The lecture also opens a third method, Gram-Schmidt orthogonalization, which is finished in the next lecture.

Key ideas

• Pseudo-inverse (A+): for a matrix that isn't invertible, A+ is the best substitute: it inverts A on the row space and column space, and sends anything in the null space to zero.
• SVD-based formula: writing A = U Sigma V^T, the pseudo-inverse is A+ = V Sigma+ U^T, where Sigma+ replaces each nonzero singular value with its reciprocal and leaves the zero entries as zero.
• Least squares problem: when Ax = b has no solution (b is not in the column space of A), the best you can do is minimize ‖Ax - b‖^2.
• Normal equations: minimizing that squared error leads to the linear system A^T A x = A^T b, solvable whenever A has independent columns.
• Geometric picture: the best Ax is the projection of b onto the column space of A; the leftover b - Ax is the error orthogonal to that space.
• Equivalence of methods: when A has independent columns (no null space), solving the normal equations gives the same answer as applying the pseudo-inverse, x = A+ b = (A^T A)^{-1} A^T b.
• One-sided inverse: (A^T A)^{-1} A^T is a left inverse of A (it gives the identity when applied on the left) but not a full two-sided inverse.
• Gram-Schmidt (introduced): a way to replace the columns of A with orthogonal columns before solving, illustrated on a two-column example by subtracting off the projection onto the first column.

Walkthrough

Course logistics and the plan ahead (0:01)

Strang opens with administrative notes: there's no final exam, homework will be replaced later in the term by a project drawing on the course material, and the class is moving into the chapter on least squares before returning to topics like sparse solutions and the pseudo-inverse in more depth.

Defining the pseudo-inverse with the four subspaces (5:14)

Using the picture of the row space, column space, and their orthogonal null spaces, Strang explains that a matrix A is genuinely invertible only between the row space and column space. The pseudo-inverse mimics this: it undoes A on the row/column space pair and maps everything in the orthogonal null space to zero, since there's no way to recover information that A already destroyed.

Building the SVD formula for A+ (14:32)

Starting from A = U Sigma V^T, Strang works out what the inverse would look like if A were invertible, then generalizes to the case where Sigma is rectangular with some zero entries. The pseudo-inverse Sigma+ inverts the nonzero singular values one by one and leaves the rest as zero, giving A+ = V Sigma+ U^T.

Setting up the least squares problem (22:37)

The lecture turns to fitting a straight line C + Dx through noisy measurement points, the classic example of an unsolvable Ax = b. Because there are more data points than the two unknowns C and D, the system is overdetermined and generally has no exact solution, so the columns of A are the constant term and the measurement locations.

Minimizing the error and deriving the normal equations (28:45)

Following Gauss's approach, Strang minimizes ‖Ax - b‖^2, expands it, and takes the derivative to reach the boxed equation A^T A x = A^T b. He pairs this with the geometric picture: b sits outside the column space of A, and the best Ax is its projection onto that space, leaving an orthogonal error term.

Connecting the normal equations to the pseudo-inverse (37:03)

When A has independent columns, A^T A is invertible even though A itself is not, and Gauss's method works directly. Strang argues (without a full symbolic check) that in this case x = (A^T A)^{-1} A^T b equals A+ b, and notes that (A^T A)^{-1} A^T is a left inverse of A but not a two-sided inverse.

Starting Gram-Schmidt as a third method (46:19)

With time running out, Strang previews the Gram-Schmidt method: replace the columns of A with orthogonal vectors, which makes the least squares system easier to solve. He demonstrates on two columns, keeping the first as is and subtracting off its projection from the second to make it orthogonal, and says the fourth method will be introduced next time.

Before you watch

• Know the SVD (A = U Sigma V^T), including what singular values and the matrices U and V represent.
• Be comfortable with the four fundamental subspaces of a matrix: row space, column space, and their orthogonal null spaces.
• Some familiarity with projections onto a subspace will help with the geometric argument.

Check your understanding

1. Why does the pseudo-inverse send vectors in the null space of A to zero rather than trying to invert them?
2. How is Sigma+ constructed from Sigma in the SVD, and why can't you simply take the reciprocal of every entry?
3. Starting from ‖Ax - b‖^2, sketch how differentiating leads to the normal equations A^T A x = A^T b.
4. Why does A having independent columns guarantee that A^T A is invertible, even when A itself is not square or invertible?
5. In what sense is (A^T A)^{-1} A^T an inverse of A, and in what sense is it not?