# Least-squares left-inverse having smallest Frobenius norm

While trying to prove that the left-inverse of $A$ provided by the least-squares solution to $y=Ax$ has the smallest Frobenius norm, I am stuck at a point which I describe below:

Let $B$ be any left-inverse of a full-rank tall matrix $A$, i.e., $BA=I$. Let the QR-decomposition: $A=QR$. In this case, $R$ is invertible since A is full-rank and $Q$ has orthonormal columns as always.

I want to show that $\|B\|_F \ge \|BQ\|_F$. Any ideas? The rest of the proof to show that the least-squares left-inverse has the smallest Frobenius norm is in place and I will be done if I can show this.

• Hint: $\|BQ\|_F^2 = \mathrm{tr}(Q^T B^T B Q)$. – cardinal Dec 22 '11 at 18:05
• Ya, which is equal to tr$((R^TR)^{-1})$, which is equal to the Frobenius norm of the least-squares left inverse. Hence, I want to show that $||B||_F\ge||BQ||_F$. I am sorry but I don't see how this can be proved with the hint you provided. Has it got something to do with properties of trace and/or orthogonal matrices which I am failing to see? – rk2 Dec 23 '11 at 19:36
• Yes, it has to do both with properties of the trace (hint: cyclic invariance) and of orthogonal matrices (hint: eigenvalues), actually. – cardinal Dec 23 '11 at 22:33
• I am sorry for mentioning "orthogonal matrix" in my previous comment since I think that is usually reserved for square matrices with orthonormal columns. In this case, $Q$ is not necessarily a square matrix (it has the same size as $A$); it has orthonormal columns however. Is it some other orthogonal matrix whose eigenvalues help us? I tried to see if I could get some orthogonal matrix from tr$(Q^TB^TBQ)=$ using the cyclic invariance property: tr$(Q^TB^TBQ)=$ tr$(QQ^TB^TB)$, but $QQ^T$ is not an orthogonal matrix. – rk2 Dec 28 '11 at 19:16
• I understood what you meant. The hints were meant with the understanding that $Q$ was not square. – cardinal Dec 28 '11 at 19:19

I actually came across a different way of proving that $||B_{ls}||_F\le ||B||_F$ where $B_{ls}$ is the least-squares left-inverse and $B$ is any left-inverse, based on Prof. Stephen Boyd's lecture notes. Reproducing the proof below:

Let $U\Sigma V^T$ be the SVD of $A$. Then $B_{ls}=V\Sigma^{-1}U^T$. Define $Z:=B-B_{ls}$

Since both $B$ and $B_{ls}$ are left-inverses of $A$, $ZA=(B-B_{ls})A=0\implies ZU\Sigma V^T=0 \implies ZU=0$ This implies that $ZB_{ls}^T=0$

Hence, $BB^T=(B_{ls}+Z)(B_{ls}+Z)^T=B_{ls}B_{ls}^T+ZZ^T$

$\therefore BB^T-B_{ls}B_{ls}^T$ is a positive semidefinite matrix $\implies$ tr$(BB^T-B_{ls}B_{ls}^T)\ge 0\implies$ tr$(BB^T)\ge$ tr$(B_{ls}B_{ls}^T)$

Since the non-zero eigenvalues of $PQ$ and $QP$ are the same, this also means that tr$(B^TB) \ge$ tr$(B_{ls}^TB_{ls}) \implies ||B||\ge ||B_{ls}||$.

(This also proves indirectly that $||B||_F\ge ||BQ||_F$)