Least Squares Algorithm

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.

Programming

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.

How do training examples lying in a lower-dimensional subspace make the matrix non-invertible?

Key point

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?

Yes, every non-invertible system is unsolvable.
No, a solution is possible when b is in the range of A.
Only if A has no zero eigenvalues.

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.

How does Âw project b onto the subspace spanned by the eigenvectors with nonzero eigenvalues?

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.

How does eigenvalue decomposition separate the directions that can be solved from the directions that cannot?

Key point

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.

What changes in D+ for a nonzero eigenvalue versus a zero eigenvalue, and how does that affect the solution?

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

Worked example

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?

1
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}.
2
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.
3
Build D+
Inspect each diagonal position. Replace every nonzero diagonal value with its reciprocal, and place zero wherever the corresponding diagonal value is zero.
4
Interpret the result
Read the resulting solution through the columns of V. The relevant directions are the eigenvector directions associated with the nonzero eigenvalues.
5
Use the range condition
Since b lies in the range of A, the projection onto the relevant eigenvector span gives b itself.

Result

The method solves through the eigenvalue decomposition and D+ rather than through a nonexistent direct inverse of A. In the stated range condition, Âw is the projection of b onto the relevant span, and that projection equals b.

Which directions are not handled by reciprocation, and why must they not be treated as ordinary invertible directions?

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 Â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	Â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.

Distinguishing the inverse question from the range and projection questions.

Reasoning Errors

Common mistake
Assuming that a non-invertible matrix makes A w = b automatically unsolvable.
What it looks like
Treating the lack of A inverse as proof that no w can satisfy the equation.
Why it fails
The source states that a solution can exist when b is in the range of A.
Do this instead
Check the range condition conceptually before concluding that the system has no solution.
Common mistake
Trying to multiply by A inverse after learning that A is non-invertible.
What it looks like
Writing w = A⁻¹b even though A has no inverse.
Why it fails
A non-invertible matrix does not have an inverse, so the direct inverse procedure is unavailable.
Do this instead
Use the eigenvalue decomposition and handle the diagonal entries through D+.
Common mistake
Taking the reciprocal of every diagonal entry of D.
What it looks like
Applying 1 divided by Dii even when Dii is zero.
Why it fails
D+ assigns zero to a zero diagonal entry rather than taking its reciprocal.
Do this instead
Use the two-case rule: reciprocal for nonzero entries and zero for zero entries.
Common mistake
Treating the projection as unrelated to the training-instance span.
What it looks like
Interpreting Âw as a vector formed from arbitrary directions.
Why it fails
The projection is onto the span of relevant eigenvector columns, which agrees with the training-instance span in the stated situation.
Do this instead
Track the span of the nonzero-eigenvalue eigenvectors and ask whether b lies in that span.
Common mistake
Assuming that every direction in R^{^d} is available to the matrix.
What it looks like
Ignoring the fact that the training instances span only part of R^d.
Why it fails
Incomplete coverage of R^{^d} is one stated cause of non-invertibility.
Do this instead
First identify which directions the training instances cover before reasoning about inversion.

What is the difference between an exact solution, a least-squares projection, and an invalid inverse argument?

Practice Check

MEDIUM

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 Âw as a projection onto the span of the relevant eigenvector columns.

Your attempt (not saved)

Worked example

Practice Answer

Explain the method for the stated non-invertible matrix and range condition.

1
Explain non-invertibility
The training instances span only part of R^{^d}, so the matrix lacks coverage of all directions needed to behave invertibly.
2
Decompose
Represent A as V D Vᵀ, separating orthonormal eigenvector directions from their diagonal values.
3
Construct D+
Use zero in D+ where D has zero, and use reciprocals where D has nonzero entries.
4
Interpret the output
The resulting operation is read through the eigenvector columns. Âw is the projection of b onto the span of the relevant directions.
5
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.

Result

The solution is analyzed direction by direction through V, D, and D+, rather than by using a nonexistent inverse of A.

Key Takeaways

1
Training instances that span only part of R^{^d} can make the matrix A non-invertible.
2
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.
3
For symmetric A, eigenvalue decomposition A = V D Vᵀ separates orthonormal eigenvector directions from their diagonal values.
4
D+ uses reciprocals for nonzero diagonal entries and zero for zero diagonal entries.
5
Â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.

At a glance

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.

Related concepts

Eigenvalue Decomposition

More concepts starting with L