pseudo inverse with the minimum $l_2$ norm for each column

Question

Consider a matrix $A \in \mathbb{R}^{m\times n}$ with $m < n$. Suppose there always exists at least one matrix $B = [b_{ij}] \in \mathbb{R}^{n\times m}$ such that $AB = I$. How to choose the matrix $B$ such that $AB = I$ and $$\max_j \sum_i b_{ij}^2 $$ is minimised? It seems that the optimal $B^*$ is always the Moore–Penrose pseudoinverse of $A$ from trial and error in Matlab. Would someone kindly tell me why? Thank you very much!

Answer 1

Since $AB=I$, the range of $A$ is $R^{m}$, and thus the rank of $A$ is $m$.

We can use the compact form of the SVD to write $A$ as

$A=U\Sigma V^{T}$

where $U$ is $m$ by $m$ and orthogonal, $\Sigma$ is $m$ by $m$, diagonal, and non-singular, and $V$ is $n$ by $m$ with orthonormal columns.

The Moore-Penrose pseudoinverse of $A$ is

$A^{\dagger}=V\Sigma^{-1}U^{T}$.

It's easy to show that $AA^{\dagger}=I$. Note that this is not true if $A$ has rank less than $m$.

Any matrix $B$ such that $AB=I$ can be written as

$B=A^{\dagger}+N$

where each column of $N$ is in the null space of $A$.

The columns of $A^{\dagger}$ are in the span of $V$ while the columns of $N$ are in the perpendicular complement of the span of $V$. Thus each column $j$ of $A^{\dagger}$ is perpendicular to the corresponding column of $N$.

$A^{\dagger}_{j} \perp N_{j}.$

By the Pythagorean theorem,

$\| A^{\dagger}_{j}+N_{j} \|_{2}^{2}= \| A^{\dagger}_{j}\|_{2}^{2}+\|N_{j} \|_{2}^{2}.$

Since this is true for all columns, you can minimize

$\max_{j} \sum_{i=1}^{n}B_{i,j}^{2}$

by using $B=A^{\dagger}$. Furthermore, by adding up the columns we get

$\| B \|_{F}^{2}=\| A^{\dagger} \|_{F}^{2}+\| N \|_{F}^{2}.$

Clearly, $B=A^{\dagger}$ minimizes $\| B \|_{F}^{2}$.