NLA MT25, Pseudoinverses
Flashcards
@Define the pseudoinverse of a rectangular matrix $M \in \mathbb R^{m \times n}$.
Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse $M^\dagger$ is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]
@State properties of $M^\dagger$ that relates it to symmetry properties that would be expected for the actual inverse.
- $M M^\dagger M = M$
- $M^\dagger M M^\dagger = M^\dagger$
- $M M^\dagger = (M M^\dagger)^\top$
- $M^\dagger M = (M^\dagger M)^\top$
(note also that in fact these 4 properties are sufficient to determine the pseudoinverse uniquely).
Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]
@State a property of $M^\dagger$ that relates it to the ordinary inverse when $M$ is nonsingular.
When $M$ is nonsingular,
\[M^\dagger = M^{-1}.\]Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]
@State a property of $M^\dagger$ that relates it to the identity when $M$ is full rank.
- If $M$ is full rank and $m \ge n$, then $M^\dagger M = I _ n$, and
- If $M$ is full rank and $m \le n$, then $M M^\dagger = I _ m$.
Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]
@State a property of $M^\dagger$ that relates it to least-square problems.
Suppose $\min _ x \|Ax - b\|$ is a full-rank least-squares problem. Then the solution is
\[x = A^\dagger b.\]Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]
@State a property of $M^\dagger$ that relates it to underdetermined linear systems.
Given a full-rank underdetermined system $Ax = b$ where $A \in \mathbb R^{m \times n}$ with $m < n$ and $r = m$, the general solution is
\[x = A^\dagger b + V _ {r, \bot} z\]for arbitrary $z$, and the minimum-norm solution is
\[x = A^\dagger b.\]Suppose $M$ is rank-$r$ and has economical SVD $M = U _ r \Sigma _ r V _ r^\top$ where $U _ r \in \mathbb R^{m \times r}, \Sigma _ r \in \mathbb R^{r \times r}, V _ r \in \mathbb R^{n \times r}$ and so that $\Sigma _ r \succ 0$. Then the pseudoinverse is
\[M^\dagger = V _ r \Sigma _ r^{-1} U _ r^\top \in \mathbb R^{n \times m}\]
@State a property of $M^\dagger$ that relates to its spectral norm.
Bite-sized
For a tall full-rank $A \in \mathbb R^{m \times n}$ ($m \ge n$, $\mathrm{rank}(A) = n$), the pseudoinverse simplifies to $A^\dagger = $ $(A^\top A)^{-1} A^\top$. For a fat full-rank $A$ ($m \le n$, $\mathrm{rank}(A) = m$), $A^\dagger = $ $A^\top (A A^\top)^{-1}$.
The Moore-Penrose conditions characterise $A^\dagger$ uniquely: $A A^\dagger A = A$, $A^\dagger A A^\dagger = A^\dagger$, $(A A^\dagger)^\top = A A^\dagger$, and $(A^\dagger A)^\top = $ $A^\dagger A$. These four conditions are often taken as the definition of the pseudoinverse.
Singular values of the pseudoinverse: if $A$ has positive singular values $\sigma _ 1 \ge \cdots \ge \sigma _ r > 0$ (and zeros if rank-deficient), then $A^\dagger$ has singular values $1/\sigma _ r \ge \cdots \ge 1/\sigma _ 1$ (and zeros). Hence $\ \vert A^\dagger\ \vert _ 2 = 1/\sigma _ r = 1/\sigma _ {\min}^{\mathrm{nz}}(A)$.