The Moore--Penrose Pseudoinverse and Regularised Least Squares

By [L1], after choosing singular values ${\sigma }_1,\dots ,{\sigma }_r>0$ one may write $A=U\left[\begin{array}{cc}\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r)& 0\\ 0& 0\end{array}\right]V^{\ast }\mathrm{.}$

Define ${\mathrm{\Sigma }}^{+}:=\left[\begin{array}{cc}\mathrm{diag}({\sigma }_1^{-1},\dots ,{\sigma }_r^{-1})& 0\\ 0& 0\end{array}\right],B:=V{\mathrm{\Sigma }}^{+}{U}^{\ast }\mathrm{.}$ Then $\mathrm{\Sigma }{\mathrm{\Sigma }}^{+}\mathrm{\Sigma }=\mathrm{\Sigma }$, ${\mathrm{\Sigma }}^{+}\mathrm{\Sigma }{\mathrm{\Sigma }}^{+}={\mathrm{\Sigma }}^{+}$, and the two products $\mathrm{\Sigma }{\mathrm{\Sigma }}^{+}$ and ${\mathrm{\Sigma }}^{+}\mathrm{\Sigma }$ are diagonal with only $0$ and $1$ on the diagonal, hence are self-adjoint.

Multiplying the relations of step 2.1 by the unitary factors $U$ and $V$ shows $ABA=A,BAB=B,(AB{)}^{\ast }=AB,(BA{)}^{\ast }=BA\mathrm{.}$ Thus $B$ is a Moore--Penrose pseudoinverse of $A$ in the sense of [L2].

Let $C$ be any other Moore--Penrose pseudoinverse of $A$, and put $D:=V^{\ast }CU$. Then the same unitary transport used in step 3.1 gives $\mathrm{\Sigma }D\mathrm{\Sigma }=\mathrm{\Sigma },D\mathrm{\Sigma }D=D,$ with $\mathrm{\Sigma }D$ and $D\mathrm{\Sigma }$ self-adjoint.

Write $\mathrm{\Sigma }=\left[\begin{array}{cc}S& 0\\ 0& 0\end{array}\right],D=\left[\begin{array}{cc}X& Y\\ Z& W\end{array}\right],$ where $S=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r)$. From $\mathrm{\Sigma }D\mathrm{\Sigma }=\mathrm{\Sigma }$ one gets $SXS=S$, hence $X=S^{-1}$. Because $\mathrm{\Sigma }D$ is self-adjoint, its upper-right block satisfies $SY=0$, so $Y=0$. Because $D\mathrm{\Sigma }$ is self-adjoint, its lower-left block satisfies $ZS=0$, so $Z=0$. With these identities, the equation $D\mathrm{\Sigma }D=D$ reduces to $\left[\begin{array}{cc}X& 0\\ 0& 0\end{array}\right]=\left[\begin{array}{cc}X& 0\\ 0& W\end{array}\right],$ so $W=0$. Hence $D={\mathrm{\Sigma }}^{+}$ and therefore $C=V{\mathrm{\Sigma }}^{+}{U}^{\ast }=B$.

Step 3.1 gives existence and step 5.1 gives uniqueness, so every finite real or complex matrix has a unique Moore--Penrose pseudoinverse.

Because $A^{+}$ satisfies the Penrose equations for $A$, the same equations read in reverse order show that $A$ satisfies the Penrose equations for $A^{+}$: $A^{+}A{A}^{+}=A^{+},A{A}^{+}A=A,$ and the products $A^{+}A$ and $A{A}^{+}$ are already self-adjoint.

Put $B:=V^{\ast }{A}^{+}{U}^{\ast }$. Using [L2] and the Penrose equations for $A$, $(UAV)B(UAV)=UA{A}^{+}AV=UAV,$ and similarly $B(UAV)B=B$. The products $(UAV)B$ and $B(UAV)$ are $U(A{A}^{+})U^{\ast }$ and $V^{\ast }(A^{+}A)V$, hence self-adjoint.

By uniqueness in [L1], the Moore--Penrose pseudoinverse of $A^{+}$ is $A$. Hence $(A^{+}{)}^{+}=A$.

Taking adjoints of the Penrose equations for $A$ shows that $(A^{+}{)}^{\ast }$ obeys $A^{\ast }(A^{+}{)}^{\ast }{A}^{\ast }=A^{\ast },(A^{+}{)}^{\ast }{A}^{\ast }(A^{+}{)}^{\ast }=(A^{+}{)}^{\ast },$ and that $A^{\ast }(A^{+}{)}^{\ast }$ and $(A^{+}{)}^{\ast }{A}^{\ast }$ are self-adjoint.

Therefore $(A^{+}{)}^{\ast }$ is the Moore--Penrose pseudoinverse of $A^{\ast }$, so uniqueness in [L1] gives $(A^{\ast }{)}^{+}=(A^{+}{)}^{\ast }$.

So $B$ is a Moore--Penrose pseudoinverse of $UAV$, and [L1] yields $(UAV{)}^{+}=V^{\ast }{A}^{+}{U}^{\ast }$. Together with steps 2.1 and 3.1, this proves the three claims.

By [L4], write $A=U\mathrm{\Sigma }{V}^{\ast }$. Define $B:=V{\mathrm{\Sigma }}^{+}{U}^{\ast }$ by reciprocating the positive singular values and leaving the zero block fixed. Direct diagonal multiplication verifies the four Penrose equations, so uniqueness in [L1] gives $B=A^{+}$. Hence $A{A}^{+}=U(\mathrm{\Sigma }{\mathrm{\Sigma }}^{+})U^{\ast },A^{+}A=V({\mathrm{\Sigma }}^{+}\mathrm{\Sigma })V^{\ast }\mathrm{.}$

The products $\mathrm{\Sigma }{\mathrm{\Sigma }}^{+}\in M_m(\mathbb{F})$ and ${\mathrm{\Sigma }}^{+}\mathrm{\Sigma }\in M_n(\mathbb{F})$ are the respective rank-$r$ diagonal projections, each with $1$ in its nonzero singular directions and $0$ elsewhere, where $r$ is the number of nonzero singular values from [L2]. Hence $A{A}^{+}$ and $A^{+}A$ are self-adjoint idempotents.

By [L3], $A{A}^{+}$ and $A^{+}A$ are orthogonal projections onto their image spaces. In the singular basis, $\mathrm{im}(A{A}^{+})$ is the span of the left singular vectors corresponding to the nonzero singular values, which is exactly $\mathrm{im}A$.

The same computation shows that $\mathrm{im}(A^{+}A)$ is the span of the right singular vectors corresponding to the nonzero singular values, which is exactly $\mathrm{im}{A}^{\ast }$.

Therefore $A{A}^{+}$ and $A^{+}A$ are the orthogonal projections onto $\mathrm{im}A$ and $\mathrm{im}{A}^{\ast }$ respectively.

Apply [L1] to $A$: $A^{+}A$ is the orthogonal projection onto $\mathrm{im}{A}^{\ast }$. Apply [L1] again to $A^{+}$ and use [L2] to identify $(A^{+}{)}^{+}=A$; then $A^{+}A$ is also the orthogonal projection onto $\mathrm{im}{A}^{+}$. Orthogonal projections onto a given space are unique, so $\mathrm{im}{A}^{+}=\mathrm{im}{A}^{\ast }$.

Using [L2] in the same way, $A{A}^{+}$ is both the orthogonal projection onto $\mathrm{im}A$ and the orthogonal projection onto $\mathrm{im}(A^{+}{)}^{\ast }$. Hence $\mathrm{im}(A^{+}{)}^{\ast }=\mathrm{im}A$.

By [L3] and step 1.1, $\ker A=(\mathrm{im}{A}^{\ast }{)}^{\perp }=(\mathrm{im}{A}^{+}{)}^{\perp }=\ker (A^{+}{)}^{\ast }\mathrm{.}$

By [L3] and step 2.1, $\ker A^{\ast }=(\mathrm{im}A{)}^{\perp }=(\mathrm{im}(A^{+}{)}^{\ast }{)}^{\perp }=\ker A^{+}\mathrm{.}$

Steps 1.1, 2.1, 3.1, and 2.2 give the image and kernel identities.

By [L4], choose an SVD $A=U\mathrm{\Sigma }{V}^{\ast }$, and by [L1] the diagonal matrix $\mathrm{\Sigma }$ has the form $\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_n)$ with every ${\sigma }_i>0$.

Then $A^{\ast }A=V{\mathrm{\Sigma }}^{\ast }\mathrm{\Sigma }{V}^{\ast }=V\mathrm{diag}({\sigma }_1^2,\dots ,{\sigma }_n^2)V^{\ast },$ so [L3] gives $(A^{\ast }A{)}^{-1}=V\mathrm{diag}({\sigma }_1^{-2},\dots ,{\sigma }_n^{-2})V^{\ast }\mathrm{.}$

Multiplying by $A^{\ast }=V{\mathrm{\Sigma }}^{\ast }{U}^{\ast }$ yields $B:=(A^{\ast }A{)}^{-1}{A}^{\ast }=V\mathrm{diag}({\sigma }_1^{-1},\dots ,{\sigma }_n^{-1})U^{\ast }\mathrm{.}$ Direct diagonal multiplication shows that $B$ satisfies all four Penrose equations for $A$, so uniqueness in [L2] gives $B=A^{+}$.

Therefore $A^{\ast }A$ is invertible and $A^{+}=(A^{\ast }A{)}^{-1}{A}^{\ast }$.

Because $A$ has full row rank, the adjoint $A^{\ast }$ has full column rank. Applying [L1] to $A^{\ast }$ gives $(A^{\ast }{)}^{+}=((A^{\ast }{)}^{\ast }{A}^{\ast }{)}^{-1}(A^{\ast }{)}^{\ast }=(A{A}^{\ast }{)}^{-1}A\mathrm{.}$

Taking adjoints and using [L2], $A^{+}=((A^{\ast }{)}^{+}{)}^{\ast }=((A{A}^{\ast }{)}^{-1}A{)}^{\ast }=A^{\ast }(A{A}^{\ast }{)}^{-1}\mathrm{.}$

In particular $A{A}^{\ast }$ is invertible and the displayed formula holds.

By [L1], $A{A}^{+}b$ is the orthogonal projection of $b$ onto $\mathrm{im}A$. Therefore the residual $b-A{A}^{+}b$ lies in $(\mathrm{im}A{)}^{\perp }=\ker A^{\ast }$ by [L4], so $A^{\ast }(A{A}^{+}b-b)=0$ and [L3] shows that $A^{+}b$ is a least-squares minimiser.

By [L2] and [L5], $A^{+}b\in \mathrm{im}{A}^{+}=\mathrm{im}{A}^{\ast }=(\ker A{)}^{\perp }$. Thus $A^{+}b$ is orthogonal to every vector in $\ker A$.

Let $x$ be any least-squares minimiser. By [L3], $x-A^{+}b\in \ker A$, so $x=A^{+}b+z$ for some $z\in \ker A$. Step 1.2 then gives $\mathrm{\parallel }x{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{A}^{+}b{\mathrm{\parallel }}_2^2+\mathrm{\parallel }z{\mathrm{\parallel }}_2^2\ge \mathrm{\parallel }{A}^{+}b{\mathrm{\parallel }}_2^2\mathrm{.}$

Equality in step 2.1 holds only when $z=0$, so the least-squares minimiser of minimum Euclidean norm is unique and equals $A^{+}b$.

Step 1.1 proves the least-squares claim and steps 2.1 and 3.1 prove the minimum-norm claim.

By [L2] and [L3], $A^{+}A$ is the orthogonal projection onto $(\ker A{)}^{\perp }$. Therefore $I-A^{+}A$ is the orthogonal projection onto $\ker A$. In particular, its image is $\ker A$ and it vanishes on $(\ker A{)}^{\perp }$.

By [L1], every least-squares minimiser has the form $A^{+}b+u$ with $u\in \ker A$. Since step 1.1 says every $u\in \ker A$ equals $(I-A^{+}A)z$ for some $z$, every least-squares minimiser has the stated form.

Conversely, if $x=A^{+}b+(I-A^{+}A)z$, then step 1.1 gives $(I-A^{+}A)z\in \ker A$. Hence $x$ differs from the least-squares minimiser $A^{+}b$ by a kernel vector, so [L1] implies that $x$ is again a least-squares minimiser.

If $b\in \mathrm{im}A$, then the least-squares residual can be $0$. Thus the least-squares minimisers are exactly the exact solutions of $Ax=b$, and steps 2.1-2.1 identify that exact solution set with the same affine family.

Steps 2.1 and 2.2 prove the if-and-only-if description, and step 3.1 gives the consistent specialisation.

Suppose $A$ has full column rank and $A=\widehat{Q}\widehat{R}$. By [L1], $A^{\ast }A={\widehat{R}}^{\ast }{\widehat{Q}}^{\ast }\widehat{Q}\widehat{R}={\widehat{R}}^{\ast }\widehat{R}\mathrm{.}$ Using [L2], $A^{+}=(A^{\ast }A{)}^{-1}{A}^{\ast }=({\widehat{R}}^{\ast }\widehat{R}{)}^{-1}{\widehat{R}}^{\ast }{\widehat{Q}}^{\ast }={\widehat{R}}^{-1}{\widehat{Q}}^{\ast }\mathrm{.}$

Suppose now that $A$ has full row rank and $A^{\ast }=\widehat{Q}\widehat{R}$ is a reduced QR factorisation of $A^{\ast }$. Applying step 1.1 to $A^{\ast }$ gives $(A^{\ast }{)}^{+}={\widehat{R}}^{-1}{\widehat{Q}}^{\ast }\mathrm{.}$ Taking adjoints yields $A^{+}=((A^{\ast }{)}^{+}{)}^{\ast }=\widehat{Q}{\widehat{R}}^{-\ast }\mathrm{.}$

These are exactly the reduced-QR pseudoinverse formulas.

By [L2], write $A=U\mathrm{\Sigma }{V}^{\ast }$ and set $x=Vy$ and $\widehat{b}:=U^{\ast }b$. Since $U$ and $V$ are unitary, $J_{\lambda }(Vy)=\mathrm{\parallel }\mathrm{\Sigma }y-\widehat{b}{\mathrm{\parallel }}_2^2+\lambda \mathrm{\parallel }y{\mathrm{\parallel }}_2^2\mathrm{.}$

If ${\sigma }_1,\dots ,{\sigma }_r$ are the nonzero singular values, then step 1.1 becomes $J_{\lambda }(Vy)={\sum }_{i=1}^r\mathrm{\mid }{\sigma }_i{y}_i-{\widehat{b}}_i{\mathrm{\mid }}^2+{\sum }_{i=r+1}^m\mathrm{\mid }{\widehat{b}}_i{\mathrm{\mid }}^2+\lambda {\sum }_{i=1}^n\mathrm{\mid }{y}_i{\mathrm{\mid }}^2\mathrm{.}$ Each variable $y_i$ appears in a one-variable quadratic with positive coefficient ${\sigma }_i^2+\lambda$ or $\lambda$, so the objective is strictly convex.

Minimising coordinatewise gives $y_i=\frac{{\sigma }_i}{{\sigma }_i^2+\lambda }{\widehat{b}}_i(1\le i\le r),y_i=0(r<i\le n)\mathrm{.}$ Equivalently, $y=({\mathrm{\Sigma }}^{\ast }\mathrm{\Sigma }+\lambda I{)}^{-1}{\mathrm{\Sigma }}^{\ast }\widehat{b}\mathrm{.}$

Returning to $x=Vy$ and using $A^{\ast }A=V{\mathrm{\Sigma }}^{\ast }\mathrm{\Sigma }{V}^{\ast }$, one gets $x_{\lambda }=V({\mathrm{\Sigma }}^{\ast }\mathrm{\Sigma }+\lambda I{)}^{-1}{\mathrm{\Sigma }}^{\ast }{U}^{\ast }b=(A^{\ast }A+\lambda I{)}^{-1}{A}^{\ast }b\mathrm{.}$

Step 2.1 proves strict convexity and step 4.1 gives the unique minimiser.

Using [L2] and the SVD from [L1], $x_{\lambda }=V({\mathrm{\Sigma }}^{\ast }\mathrm{\Sigma }+\lambda I{)}^{-1}{\mathrm{\Sigma }}^{\ast }{U}^{\ast }b\mathrm{.}$

The diagonal matrix $({\mathrm{\Sigma }}^{\ast }\mathrm{\Sigma }+\lambda I{)}^{-1}{\mathrm{\Sigma }}^{\ast }$ has diagonal entries ${\sigma }_i\mathrm{/}({\sigma }_i^2+\lambda )$ in the nonzero singular directions and $0$ in the zero singular directions. Therefore $x_{\lambda }={\sum }_{{\sigma }_i>0}\frac{{\sigma }_i}{{\sigma }_i^2+\lambda }⟨b,u_i⟩v_i\mathrm{.}$

This is exactly the stated filter-factor formula.

In the same SVD coordinates as [L1], define $B:=V{\mathrm{\Sigma }}^{+}{U}^{\ast }$ by reciprocating each positive singular value and leaving the zero block fixed. Direct diagonal multiplication verifies all four Penrose equations, so uniqueness in [L3] gives $B=A^{+}$. Consequently $A^{+}b={\sum }_{{\sigma }_i>0}\frac{1}{{\sigma }_i}⟨b,u_i⟩v_i\mathrm{.}$

Step 1.1 and [L1] show that the coefficient of $v_i$ in $x_{\lambda }-A^{+}b$ is $(\frac{{\sigma }_i}{{\sigma }_i^2+\lambda }-\frac{1}{{\sigma }_i})⟨b,u_i⟩=-\frac{\lambda }{{\sigma }_i({\sigma }_i^2+\lambda )}⟨b,u_i⟩$ for each nonzero singular value, while the zero-singular-value coefficients are $0$ in both vectors.

For each fixed nonzero ${\sigma }_i$, ${\sigma }_i\mathrm{/}({\sigma }_i^2+\lambda )\to 1\mathrm{/}{\sigma }_i$ as $\lambda \downarrow 0$, so every coefficient from step 2.1 tends to $0$. Because there are only finitely many singular directions, $\mathrm{\parallel }{x}_{\lambda }-A^{+}b{\mathrm{\parallel }}_2\to 0$.

Therefore $x_{\lambda }\to A^{+}b$, the Moore--Penrose minimum-norm least-squares solution from [L2].

By [L1], applying $A_{\tau }^{+}$ to $b={\sum }_i⟨b,u_i⟩u_i$ gives $A_{\tau }^{+}b={\sum }_{{\sigma }_i>\tau }\frac{1}{{\sigma }_i}⟨b,u_i⟩v_i\mathrm{.}$ Thus the filter is $g_{\tau }({\sigma }_i)$ with a hard cutoff at $\tau$.

By [L2], the Tikhonov solution is $x_{\lambda }={\sum }_{{\sigma }_i>0}\frac{{\sigma }_i}{{\sigma }_i^2+\lambda }⟨b,u_i⟩v_i\mathrm{.}$ Hence every nonzero singular direction is retained but damped smoothly according to $g_{\lambda }({\sigma }_i)$, while zero singular directions have filter value $g_{\lambda }(0)=0$.

Step 1.1 is the truncated-SVD filter and step 1.2 is the Tikhonov filter, so the two methods are hard and smooth spectral filters respectively.

Let $A_k\to A$ with every $A_k$ and $A$ of rank $r$. By [L2], choose SVDs $A_k=U_k{\mathrm{\Sigma }}_k{V}_k^{\ast }$ and $A=U\mathrm{\Sigma }{V}^{\ast }$. Each unitary group is a closed bounded subset of its finite-dimensional matrix space, hence compact by [L4]. Therefore every subsequence of $(U_k,V_k)$ has a convergent subsequence; along such a subsequence the limit still gives a singular value decomposition of $A$.