The Pseudoinverse and Four Projectors

Definition Let $A \in \mathbb{F}^{m \times n}$ have rank $r$ and a full singular value decomposition $A = U\Sigma V^{*}$. Let $\Sigma^{+} \in \mathbb{R}^{n \times m}$ have entries $(\Sigma^{+})_{ii} = 1/\sigma_i$ for $i \le r$ and every other entry $0$. So $\Sigma^{+}$ has the transposed shape, the positive singular values are reciprocated and the zeros stay zero. The pseudoinverse of $A$ is

In compact form,

so $A^{+}u_i = v_i/\sigma_i$ for $i \le r$ and $A^{+}u_i = 0$ for $i > r$. The result does not depend on which singular value decomposition is used, because the free choices of singular vectors cancel in each block $\sigma^{-1}V_\sigma U_\sigma^{*}$ and the zero directions do not appear at all. The next lesson characterizes $A^{+}$ by four equations as well. If $A = 0$, then $A^{+}$ is the $n \times m$ zero matrix. If $A$ is square and invertible, then $A^{+} = A^{-1}$. If $A$ has full column rank, $r = n$, then $A^{*}A$ is invertible and $A^{+} = (A^{*}A)^{-1}A^{*}$. If $A$ has full row rank, $r = m$, then $A^{+} = A^{*}(AA^{*})^{-1}$. Both formulas follow by writing each side in singular coordinates.

Definition Let $A \in \mathbb{F}^{m \times n}$ and $b \in \mathbb{F}^m$. A vector $\hat{x} \in \mathbb{F}^n$ is a least-squares solution of $Ax = b$ if $\lVert A\hat{x} - b \rVert \le \lVert Ax - b \rVert$ for every $x \in \mathbb{F}^n$. Take a full singular value decomposition and put $c = U^{*}b$ and $y = V^{*}x$. Unitary matrices preserve norms, so

The last sum does not depend on $x$. Each term of the first sum vanishes exactly when $y_i = c_i/\sigma_i$, and the coordinates $y_{r+1}, \dots, y_n$ do not appear. So least-squares solutions always exist, and the least-squares solution set is

the set of all vectors $A^{+}b + z$ with $z \in \ker A$. The vector $A^{+}b$ is the solution with $y_{r+1} = \cdots = y_n = 0$. The minimum squared residual is $\sum_{i > r} \lvert c_i \rvert^2$. Equivalently, $x$ is a least-squares solution exactly when $Ax = AA^{+}b$, and exactly when it solves the normal equations $A^{*}Ax = A^{*}b$, which in singular coordinates read $\sigma_i^2 y_i = \sigma_i c_i$ for $i \le r$. The set is a single point exactly when $\ker A = \{0\}$, that is $r = n$, and the minimum residual is zero exactly when $b \in \operatorname{im} A$.

Definition Let $A \in \mathbb{F}^{m \times n}$ and $b \in \mathbb{F}^m$. The theorem says that among all least-squares solutions of $Ax = b$, the vector $A^{+}b$ has the smallest norm and is the only one with that norm. It is called the minimum-norm least-squares solution. The proof uses the compact form. The vector

lies in the span of $v_1, \dots, v_r$, which is $(\ker A)^{\perp}$. Every least-squares solution is $A^{+}b + z$ with $z \in \ker A$, and by the Pythagorean identity

which is larger than $\lVert A^{+}b \rVert^2$ unless $z = 0$. Equivalently, $A^{+}b$ is the unique least-squares solution in $(\ker A)^{\perp} = \operatorname{im} A^{*}$. When $b \in \operatorname{im} A$ it is the exact solution of smallest norm. When $A = 0$, every input is a least-squares solution and the minimum-norm one is $A^{+}b = 0$.

Definition Let $A \in \mathbb{F}^{m \times n}$ have rank $r$ and compact singular value decomposition $A = U_r\Sigma_rV_r^{*}$. Then

This matrix is Hermitian and idempotent, and its image is the span of $u_1, \dots, u_r$, which is $\operatorname{im} A$, the column space of $A$. So $AA^{+}$ is the orthogonal projector of $\mathbb{F}^m$ onto the column space. For every $b \in \mathbb{F}^m$, the vector $AA^{+}b$ is the point of $\operatorname{im} A$ closest to $b$, and it is the fitted output $A\hat{x}$ of every least-squares solution $\hat{x}$. In the full decomposition it is $U$ times the diagonal matrix with $r$ ones followed by $m - r$ zeros times $U^{*}$. It equals $I_m$ exactly when $r = m$.

Definition With the same notation,

It is the orthogonal projector of $\mathbb{F}^n$ onto the span of $v_1, \dots, v_r$. Since $A^{*}u_i = \sigma_iv_i$, that span is $\operatorname{im} A^{*}$, which equals $(\ker A)^{\perp}$. This subspace is the row space of $A$. Over $\mathbb{R}$ it is spanned by the rows of $A$, and over $\mathbb{C}$ by the complex conjugates of the rows, written as columns. For every $x \in \mathbb{F}^n$, applying $A$ and then $A^{+}$ gives $A^{+}(Ax) = (A^{+}A)x$, the row space component of $x$, and $A(A^{+}Ax) = Ax$. The projector equals $I_n$ exactly when $r = n$.

Definition If $P \in \mathbb{F}^{k \times k}$ is the orthogonal projector onto a subspace $S$, then $I_k - P$ is Hermitian and idempotent, since $(I_k - P)^2 = I_k - 2P + P^2 = I_k - P$, and its image is $\ker P = S^{\perp}$. So $I_k - P$ is the orthogonal projector onto $S^{\perp}$. Applied to the two projectors above, the $m \times m$ matrix $I_m - AA^{+}$ projects $\mathbb{F}^m$ onto $(\operatorname{im} A)^{\perp} = \ker A^{*}$, and the $n \times n$ matrix $I_n - A^{+}A$ projects $\mathbb{F}^n$ onto $(\operatorname{im} A^{*})^{\perp} = \ker A$. They give two orthogonal splittings,

for every $b \in \mathbb{F}^m$ and $x \in \mathbb{F}^n$. The least-squares residual is $(I_m - AA^{+})b$, and the least-squares solution set can be written as $A^{+}b + (I_n - A^{+}A)w$ with $w \in \mathbb{F}^n$. The four projectors live in two different spaces, two of size $m \times m$ and two of size $n \times n$, and even when $m = n$ the output projector $AA^{+}$ and the input projector $A^{+}A$ are in general different matrices.