Pseudoinverses and Minimum-Norm Solutions

Definition Let $\Sigma$ be an $m \times n$ rectangular diagonal matrix with diagonal entries $\sigma_1 \ge \cdots \ge \sigma_q \ge 0$, where $q = \min(m, n)$, and let $r$ be the number of positive entries. Its pseudoinverse $\Sigma^{+}$ is the $n \times m$ rectangular diagonal matrix whose diagonal entries are $1/\sigma_1, \dots, 1/\sigma_r$ followed by $q - r$ zeros. So the shape is transposed, every positive entry is replaced by its reciprocal, and every zero stays zero. The $m \times m$ product $\Sigma\Sigma^{+}$ and the $n \times n$ product $\Sigma^{+}\Sigma$ are both diagonal, with $r$ leading ones on the diagonal and zeros everywhere else. The rule depends on whether an entry is exactly zero. A small positive entry gets a large reciprocal, and replacing it by zero instead is truncation, a different procedure that needs its own stated criterion.

Definition Let $A$ be a real $m \times n$ matrix with a singular value decomposition $A = U\Sigma V^{\top}$. Its pseudoinverse is the $n \times m$ matrix

It does not depend on which SVD is used, because for every $\mathbf{b}$ the vector $A^{+}\mathbf{b}$ is the unique least-squares solution of $A\mathbf{x} = \mathbf{b}$ of smallest norm, as the last card shows. If $A$ has rank $r \ge 1$, only the first $r$ columns of $U$ and $V$ meet nonzero entries of $\Sigma^{+}$, so a compact SVD $A = U_r\Sigma_r V_r^{\top}$ already gives $A^{+} = V_r\Sigma_r^{-1}U_r^{\top}$. The two products of $A^{+}$ with $A$ are

Since $\Sigma\Sigma^{+}$ keeps exactly the coordinates along $\mathbf{u}_1, \dots, \mathbf{u}_r$ and $\Sigma^{+}\Sigma$ exactly those along $\mathbf{v}_1, \dots, \mathbf{v}_r$, the first product is the orthogonal projection of $\mathbb{R}^m$ onto $\operatorname{Col} A$ and the second is the orthogonal projection of $\mathbb{R}^n$ onto $\operatorname{Row} A$. The first equals $I_m$ only when $r = m$, and the second equals $I_n$ only when $r = n$. When $A$ is square and invertible, $A^{+} = A^{-1}$. When $A$ has full row rank $m$, $A^{+} = A^{\top}(AA^{\top})^{-1}$, and when $A$ has full column rank $n$, $A^{+} = (A^{\top}A)^{-1}A^{\top}$. These two formulas need their rank conditions, since otherwise the matrix to be inverted is singular. Transposing an SVD shows that $(A^{\top})^{+} = (A^{+})^{\top}$.

Definition Let $A$ be a real $m \times n$ matrix. Because $\operatorname{Row} A$ and $\operatorname{Null} A$ are orthogonal complements in $\mathbb{R}^n$, every input splits uniquely as $\mathbf{x} = \mathbf{x}_{\text{row}} + \mathbf{x}_{\text{null}}$ with $\mathbf{x}_{\text{row}}$ in $\operatorname{Row} A$ and $\mathbf{x}_{\text{null}}$ in $\operatorname{Null} A$, namely

The vector $\mathbf{x}_{\text{null}}$ is the null-space component of $\mathbf{x}$. It has no effect on the output, $A\mathbf{x} = A\mathbf{x}_{\text{row}}$, and by the Pythagorean theorem $\lVert \mathbf{x} \rVert^2 = \lVert \mathbf{x}_{\text{row}} \rVert^2 + \lVert \mathbf{x}_{\text{null}} \rVert^2$. Two inputs give the same output exactly when their difference lies in $\operatorname{Null} A$, that is, exactly when they have the same row-space component and differ only in their null-space components.

Definition Let $A$ be a real $m \times n$ matrix and $\mathbf{b}$ a vector in $\operatorname{Col} A$, so that $A\mathbf{x} = \mathbf{b}$ is consistent. Among its solutions there is exactly one of smallest Euclidean norm, the minimum-norm solution $\mathbf{x}^{+}$, and

It is the unique solution in $\operatorname{Row} A$, equivalently the unique solution orthogonal to $\operatorname{Null} A$. Indeed $A^{+}\mathbf{b}$ lies in $\operatorname{Row} A$, since the columns of $V\Sigma^{+}$ lie in the span of $\mathbf{v}_1, \dots, \mathbf{v}_r$ with $r = \operatorname{rank} A$, and $AA^{+}\mathbf{b} = \mathbf{b}$, since $AA^{+}$ projects onto $\operatorname{Col} A$, which contains $\mathbf{b}$. Every solution has the form $\mathbf{x}^{+} + \mathbf{h}$ with $\mathbf{h}$ in $\operatorname{Null} A$, and

so every $\mathbf{h} \ne \mathbf{0}$ makes the norm strictly larger. When $A$ has full row rank every $\mathbf{b}$ is consistent and $\mathbf{x}^{+} = A^{\top}(AA^{\top})^{-1}\mathbf{b}$. The criterion uses Euclidean length in the given coordinates. If the unknowns carry unrelated units, rescaling them can change which solution is selected, so the scaling has to be chosen deliberately.

Definition Let $A$ be a real $m \times n$ matrix of rank $r$ and let $\mathbf{b}$ be any vector in $\mathbb{R}^m$. Among all least-squares solutions of $A\mathbf{x} = \mathbf{b}$ there is exactly one of smallest Euclidean norm, and it is $A^{+}\mathbf{b}$. To prove it, take an SVD $A = U\Sigma V^{\top}$ and write $\boldsymbol{\beta} = U^{\top}\mathbf{b}$ and $\mathbf{c} = V^{\top}\mathbf{x}$. Orthogonal matrices preserve length, so

The second sum does not depend on $\mathbf{x}$, and it is empty when $r = m$. So $\mathbf{x}$ is a least-squares solution exactly when $c_i = \beta_i / \sigma_i$ for $i = 1, \dots, r$, while $c_{r+1}, \dots, c_n$ are free. Among these the norm is smallest exactly when every free coordinate is $0$. That choice is $\mathbf{c} = \Sigma^{+}\boldsymbol{\beta}$, which means $\mathbf{x} = V\Sigma^{+}U^{\top}\mathbf{b} = A^{+}\mathbf{b}$. If $\mathbf{b}$ lies in $\operatorname{Col} A$, the residual is zero and this is the minimum-norm solution of the previous card. If $A$ has full column rank, so $r = n$, nothing is free, the least-squares solution is unique, and it equals $(A^{\top}A)^{-1}A^{\top}\mathbf{b}$.