Projection onto a Span

Non-invertibility can arise when training instances do not span the entire space of R^d.

Programming

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.

How do training-instance vectors cover only part of R^{^d}, and why does that leave some directions unconstrained?

Tracing the Directional Change

What do you think happens?

Suppose A is non-invertible, but b lies in the range of A. Must the equation A w = b have no solution?

Yes, because every non-invertible matrix makes A w = b impossible
No, because b can still be in the range of A
Only if all eigenvalues are nonzero

Reveal answer

Answer:

No, because b can still be in the range of A

The absence of an inverse prevents direct inversion, but it does not prevent a solution when b is in the range of A.

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.

How does eigenvalue decomposition transform A w = b into separate calculations along eigenvector directions?

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.

What changes in an eigenvector direction when D+ processes a zero or nonzero diagonal entry?

Worked example

Applying the D+ rule symbolically

A diagonal entry Dii is either zero or nonzero. Determine the corresponding entry of D+.

1
Inspect the entry
Look at one diagonal position Dii at a time.
2
Handle a nonzero entry
If Dii is nonzero, place its reciprocal in the same position of D+.
3
Handle a zero entry
If Dii is zero, place zero in the same position of D+ rather than attempting to take a reciprocal.
4
Interpret the result
The resulting diagonal matrix preserves the distinction between directions that can be handled through reciprocals and directions that cannot be inverted.

Result

For every diagonal position, D+ contains 1 / Dii when Dii is nonzero and 0 when Dii is zero.

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 Â w gives b itself rather than requiring information from directions outside the covered span.

What happens to b when only the eigenvector directions contained in the relevant span are retained?

Reasoning Traps

Common mistake
Assuming that a non-invertible matrix makes A w = b impossible.
What it looks like
Treating the absence of A's inverse as proof that no w can satisfy the equation.
Why it fails
A solution can still exist when b is in the range of A.
Do this instead
Separate the question of whether A has an inverse from the question of whether b belongs to the range of A.
Common mistake
Trying to multiply by A's inverse even though A is non-invertible.
What it looks like
Using A inverse as though it existed in a least-squares derivation.
Why it fails
A non-invertible matrix does not have an inverse.
Do this instead
Use the eigenvalue-decomposition viewpoint and construct D+ from the diagonal entries of D.
Common mistake
Taking a reciprocal of a zero diagonal entry.
What it looks like
Replacing a zero Dii with a reciprocal in D+.
Why it fails
The zero-versus-nonzero rule assigns zero to a zero diagonal entry.
Do this instead
For each diagonal position, assign zero when Dii is zero and a reciprocal only when Dii is nonzero.
Common mistake
Treating all directions in R^{^d} as though the training instances covered them.
What it looks like
Ignoring the fact that the training instances generate only part of R^d.
Why it fails
Failure to span the whole space is one important cause of non-invertibility.
Do this instead
Identify the span of the training instances and relate it to the relevant eigenvector directions.
Common mistake
Interpreting the projection as automatically changing b.
What it looks like
Assuming Â w must differ from b because it is called a projection.
Why it fails
In the source's situation, b already belongs to the relevant span.
Do this instead
Check whether b is in the span. When it is, the projection gives b itself.

How should you distinguish a usable eigenvector direction, a zero-eigenvalue direction, and an incorrectly assumed unique inverse solution?

Practice Check

MEDIUM

Explain, in your own words, why the following procedure is appropriate when A is non-invertible but b lies in the range of A: write A as V D Vᵀ, inspect the diagonal entries of D, construct D+ by taking reciprocals of nonzero entries and assigning zero to zero entries, and interpret Â w through the span of the relevant columns of V.

Hints

Begin by explaining why directly multiplying by A's inverse is not available.
Connect the training-instance span to the relevant eigenvector span.
Explain why b is unchanged by the projection in the situation described.

Your attempt (not saved)

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 Â w as a projection onto the span of relevant eigenvector directions; when b already lies in that span, the projection gives b itself.

Key Takeaways

Failure of the training instances to span R^{^d} can make A non-invertible.
A non-invertible matrix can still have a solution to A w = b when b lies in the range of A.
Eigenvalue decomposition writes symmetric A as V D Vᵀ and separates the problem into eigenvector directions.
D+ uses reciprocals for nonzero diagonal entries and zero for zero diagonal entries.
Â w is understood as a projection onto the relevant eigenvector span, which equals b when b is already in that span.

Related concepts

More concepts starting with P