Pseudoinverse and the shortest solution to least squares

May 03, 2020 | 2 min read

When we try to solve $Ax=b$ for least squares, we solve $A^TA\hat{x}=A^Tb$. However, since $A$ may have dependent columns, the solution to $A^TA\hat{x}=A^Tb$ is not exact.

A solution can be $x^+ = A^+b$ where $A^+$ is the pseudoinverse of $A$. To see that $x^+ = A^+b$ is a solution to $A^TA\hat{x}=A^Tb$:

Using SVD, we have $AA^+b = (u_1u_1^T + \dots + u_ru_r^T)b = (u_1^Tb)u_1 + \dots + (u_r^Tb)u_r$ and using the result I proved on here, {$u_1, \dots , u_r$} can be a basis to $C(A)$, we know $AA^+b$ is the projection of $b$ onto $C(A)$ and hence $(b - AA^+b) \isin N(A^T)$ and so $A^T(b - AA^+b) = 0$.

So, how special is $x^+ = A^+b$? It is the shortest one among all solutions to $A^TA\hat{x}=A^Tb$.

To see such result, we first observe the SVD of $A^T$ and $A^+$:

Using the result I proved on here again, we know $A^T$ and $A^+$ have the same four subspaces. Hence, $x^+ = A^+b \isin C(A^+)$ which is $C(A^T)$ and $\perp N(A)$.

Now, any other $\hat{x}$ which satisfies $A^TA\hat{x}=A^Tb$, $\hat{x}-x^+ \isin N(A^TA)$ which is $N(A)$. Then, we have:

Then, we consider $(\hat{x} - x^+)^T(\hat{x}-x^+)$:

i.e. $|\hat{x}|^2 - |x^+|^2 = (\hat{x} - x^+)^T(\hat{x}-x^+) = |\hat{x}-x^+|^2$
$\therefore |\hat{x}|^2 = |\hat{x}-x^+|^2 + |x^+|^2$ and hence $x^+ = A^+b$ is the shortest one among all solutions $\hat{x}$ to $A^TA\hat{x} = A^Tb$. Then, we know $x^+ = A^+b$ is the shortest solution to least squares of $Ax=b$.

Written by Danny Siu who lives in Hong Kong. You should follow him on Twitter

• ← When the modulus m is a product of distinct primes, the decryption will always work