Underdetermined equations

Consider the same case of $y = Ax$, but this time, there are more variables than equations. In this case, many choices of $x$ can lead to the same $y$. We can describe the set of solutions as

The solutions has $dim N(A)$ degrees of freedom, because you can add anything in the null space and change nothing.

Least Norm solution

The least-norm solution is given by

which is the solution to $y = Ax$ that minimizes $||x||$. We can show this by supposing that there exists another solution. Then, $A(x - x_{ln}) = 0$, and

which means that

by using a good add-subtract trick and pythagorean’s theorem, we get

as desired.

Interpretations

We know that $x - x_{ln}\in N(A)$, so we know that $x_{ln} \perp N(A)$. Therefore, you can think of it as the “essence” of the solution with no “fluff” of the null space.

Through QR factorization

Find the QR factorization of $A^T$. In this case, then

Through Lagrange multipliers

You can always set things up using the lagrange multiplier, which yields

And you get

which yields the same solution: $x = A^T(AA^T)^{-1}y$.

Left Inverses and Right Inverses

There’s a reason why we are looking at these. Now, we can get a feel for what left and right inverses are!

Right inverses (full-rank, “fat” matrices)

We define the pseudoinverse or right inverse $A^+$ as

This is the pseudoinverse because $AA^+ = I$. Geometrically, if you take any output point and map it into a higher-dimensional input point, and then map it forward, it should yield the same output point. It is not the same in the opposite direction, as many inputs yield the same output.

From our previous results, get get that $A^T(AA^T)^{-1}Ax = x + z, z \in N(A)$. Therefore, it follows that

is a projection onto $N(A)$.

Left inverses (full-rank, “skinny” matrix)

The pseudoinverse or left inverse of $A$ is

This is a pseudoinverse because $A^+A = I$. Geometrically, $A^+$ maps every output to the closest input. In some cases, when the output $\in R(A)$, it maps it directly to the true input.

From our least-squares inquiry, we know that

is a projection of a vector onto $R(A)$.