Least Squares Algorithm
Non-invertibility can arise when training instances do not span the entire space of R^d.
When Inversion Breaks
In least squares, the equation A w = b may look as though it should be solved by multiplying both sides by the inverse of A. That plan fails when A is non-invertible, because a non-invertible matrix has no inverse. One important cause is that the training instances do not span the entire space of R^d. The matrix then lacks full coverage of the directions needed to behave invertibly.
Non-invertibility is not merely an algebraic inconvenience. It records that the training instances fail to cover every direction in R^d. The matrix cannot therefore be treated as if every direction had an available inverse operation.
A Solvable Non-Invertible System
What do you think happens?
If A is non-invertible, must the equation A w = b have no solution?
Reveal answer
Answer: No, a solution is possible when b is in the range of A.
The absence of an inverse does not prevent a solution when b is in the range of A. Non-invertibility prevents the direct inverse procedure; it does not by itself prove that the equation has no solution.
This distinction is central. A non-invertible matrix does not support the operation of multiplying by A⁻¹, because A⁻¹ does not exist. However, the equation A w = b can still have a solution if b lies in the range of A. The least squares treatment therefore changes the question: instead of demanding a direct inverse of A, it analyzes which directions A can represent and handles those directions separately.
Eigenvalue Decomposition
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: A = V D Vᵀ. This representation separates the matrix into orthonormal directions, represented by the columns of V, and diagonal values, represented by D. The diagonal values reveal which directions can be handled by reciprocation and which directions require special treatment.
Eigenvalue decomposition does not magically create an inverse for A. Instead, it exposes the diagonal entries of D so that each eigenvector direction can be handled according to whether its associated diagonal value is zero or nonzero.
Constructing D+
The diagonal matrix D+ handles the entries of D one at a time. For diagonal position i, if Dii is zero, D+ places zero in the same position. If Dii is nonzero, D+ places its reciprocal there. Thus D+ preserves the information that a zero diagonal direction cannot be inverted while still allowing nonzero directions to be handled through reciprocals.
| Entry in D | Entry in D+ | Interpretation |
|---|---|---|
| Dii is nonzero | The reciprocal of Dii | The associated direction is handled through reciprocation. |
| Dii is zero | 0 | The associated direction is not inverted. |
The construction rule for each diagonal position of D+.
Symbolic Walkthrough
Handling a Matrix with Missing Directions
Suppose the training instances generate only part of R^d, so A is non-invertible, while b lies in the range of A. How does the least squares method proceed?
Identify the limitation: Because A is non-invertible, there is no inverse of A to multiply by. The missing coverage comes from the training instances spanning only part of R^d.
Decompose A: Represent A as V D Vᵀ. The columns of V provide orthonormal eigenvector directions, and D records the diagonal values associated with those directions.
Build D+: Inspect each diagonal position. Replace every nonzero diagonal value with its reciprocal, and place zero wherever the corresponding diagonal value is zero.
Interpret the result: Read the resulting solution through the columns of V. The relevant directions are the eigenvector directions associated with the nonzero eigenvalues.
Use the range condition: Since b lies in the range of A, the projection onto the relevant eigenvector span gives b itself.
The method solves through the eigenvalue decomposition and D+ rather than through a nonexistent direct inverse of A. In the stated range condition, Âw is the projection of b onto the relevant span, and that projection equals b.
The important state change is not from one numerical matrix to another arbitrary matrix. It is from an undifferentiated matrix equation to a direction-by-direction view. The columns of V identify the directions, while the diagonal entries of D determine whether each direction receives a reciprocal in D+ or remains represented by zero.
Projection and Exactness
The expression Âw is understood geometrically as a projection of b onto the span of the relevant eigenvector columns. The relevant span is formed by the eigenvector directions associated with nonzero eigenvalues. In the situation described by the source, this span agrees with the span of the training instances, and b already belongs to it. Therefore the projection gives b itself.
| Situation | What the source supports | Correct interpretation |
|---|---|---|
| A is invertible | A direct inverse may be considered | Do not confuse this with the non-invertible case. |
| A is non-invertible and b is in the range of A | A w can still have a solution | The absence of an inverse does not by itself prevent a solution. |
| Projection through relevant eigenvector directions | Âw is the projection of b onto the relevant span | When b is already in that span, the projection gives b itself. |
| A has zero diagonal entries in D | Those positions receive zero in D+ | Do not take reciprocals of zero entries. |
Reasoning Errors
Assuming that a non-invertible matrix makes A w = b automatically unsolvable.
The source states that a solution can exist when b is in the range of A.
Fix:
Check the range condition conceptually before concluding that the system has no solution.Trying to multiply by A inverse after learning that A is non-invertible.
A non-invertible matrix does not have an inverse, so the direct inverse procedure is unavailable.
Fix:
Use the eigenvalue decomposition and handle the diagonal entries through D+.Taking the reciprocal of every diagonal entry of D.
D+ assigns zero to a zero diagonal entry rather than taking its reciprocal.
Fix:
Use the two-case rule: reciprocal for nonzero entries and zero for zero entries.Treating the projection as unrelated to the training-instance span.
The projection is onto the span of relevant eigenvector columns, which agrees with the training-instance span in the stated situation.
Fix:
Track the span of the nonzero-eigenvalue eigenvectors and ask whether b lies in that span.Assuming that every direction in R^d is available to the matrix.
Incomplete coverage of R^d is one stated cause of non-invertibility.
Fix:
First identify which directions the training instances cover before reasoning about inversion.
Practice Check
A symmetric matrix A comes from training instances that span only part of R^d. You are told that b lies in the range of A. Describe the reasoning sequence you would use to analyze A w = b without writing A inverse.
Hints
- Start by explaining why the missing directions make A non-invertible.
- Write the eigenvalue decomposition in the form A = V D Vᵀ.
- State separately what happens to a zero and a nonzero diagonal entry when forming D+.
- Finish by interpreting Âw as a projection onto the span of the relevant eigenvector columns.
Practice Answer
Explain the method for the stated non-invertible matrix and range condition.
Explain non-invertibility: The training instances span only part of R^d, so the matrix lacks coverage of all directions needed to behave invertibly.
Decompose: Represent A as V D Vᵀ, separating orthonormal eigenvector directions from their diagonal values.
Construct D+: Use zero in D+ where D has zero, and use reciprocals where D has nonzero entries.
Interpret the output: The resulting operation is read through the eigenvector columns. Âw is the projection of b onto the span of the relevant directions.
Apply the given condition: Because b lies in the range of A, it lies in the relevant span in the stated situation, so the projection gives b itself.
The solution is analyzed direction by direction through V, D, and D+, rather than by using a nonexistent inverse of A.
Key Takeaways
- Training instances that span only part of R^d can make the matrix A non-invertible.
- A non-invertible A has no direct inverse, but A w = b can still have a solution when b lies in the range of A.
- For symmetric A, eigenvalue decomposition A = V D Vᵀ separates orthonormal eigenvector directions from their diagonal values.
- D+ uses reciprocals for nonzero diagonal entries and zero for zero diagonal entries.
- Âw is interpreted as a projection of b onto the span of relevant eigenvector directions; in the stated range condition, that projection gives b itself.
Key Takeaways
- Incomplete coverage of R^d by the training instances is a key cause of non-invertibility.
- The lack of an inverse does not automatically eliminate solutions to A w = b.
- Eigenvalue decomposition changes the problem into direction-by-direction operations on D.
- D+ preserves zero diagonal positions and reciprocates nonzero diagonal positions.
- The resulting least squares interpretation is a projection onto the span of relevant eigenvector directions.