Projection onto a Span

When Coverage Falls Short

In a least-squares problem, the equation A w = b may appear to invite a familiar step: multiply both sides by A's inverse. That step is unavailable when A is non-invertible. One important reason A can be non-invertible is that the training instances do not span the entire space of R^d. They cover only part of the available directions, leaving some directions without the coverage needed for A to behave invertibly.

Tracing the Directional Change

The useful change in viewpoint is to stop trying to invert A directly. Because A is symmetric, it can be represented in an eigenvalue decomposition. In that representation, A is written as V D Vᵀ. The columns of V provide orthonormal eigenvector directions, while the diagonal entries of D record the values associated with those directions. The problem is therefore separated into directional calculations rather than treated as one indivisible matrix inversion.

Constructing D+

The diagonal matrix D+ handles each diagonal entry of D independently. At position i, if Dii is zero, D+ places zero in the same position. If Dii is nonzero, D+ places the reciprocal of Dii in that position. Thus, nonzero directions can be handled through reciprocals, while zero directions remain identified as directions that cannot be inverted.

Reading the Projection

The complete symbolic walkthrough is as follows. Training instances generate only part of R^d, so A is non-invertible. The source additionally establishes that b lies in the range of A. Decompose A as V D Vᵀ, inspect the diagonal of D, and form D+ using the zero-versus-nonzero rule. The resulting solution is interpreted through the columns vi of V instead of through a direct inverse of A.

Projection language describes which part of b is retained by the relevant eigenvector directions. The method works with the span of the relevant columns of V. In the situation described by the source, this eigenvector span agrees with the span of the training instances, and b already belongs to that span. Therefore, the projection represented by  w gives b itself rather than requiring information from directions outside the covered span.

Reasoning Traps

• Assuming that a non-invertible matrix makes A w = b impossible.

  A solution can still exist when b is in the range of A.

  Fix: Separate the question of whether A has an inverse from the question of whether b belongs to the range of A.

• Trying to multiply by A's inverse even though A is non-invertible.

  A non-invertible matrix does not have an inverse.

  Fix: Use the eigenvalue-decomposition viewpoint and construct D+ from the diagonal entries of D.

• Taking a reciprocal of a zero diagonal entry.

  The zero-versus-nonzero rule assigns zero to a zero diagonal entry.

  Fix: For each diagonal position, assign zero when Dii is zero and a reciprocal only when Dii is nonzero.

• Treating all directions in R^d as though the training instances covered them.

  Failure to span the whole space is one important cause of non-invertibility.

  Fix: Identify the span of the training instances and relate it to the relevant eigenvector directions.

• Interpreting the projection as automatically changing b.

  In the source's situation, b already belongs to the relevant span.

  Fix: Check whether b is in the span. When it is, the projection gives b itself.

Practice Check

1. A matrix can be non-invertible when the training instances fail to span all of R^d. This prevents direct inversion, but it does not rule out a solution when b is in the range of A. For symmetric A, eigenvalue decomposition separates the problem into orthonormal eigenvector directions and diagonal values. D+ assigns reciprocals to nonzero diagonal entries and zero to zero entries. The resulting viewpoint interprets  w as a projection onto the span of relevant eigenvector directions; when b already lies in that span, the projection gives b itself.