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.

  • 3
    $\begingroup$ Hint: $\|BQ\|_F^2 = \mathrm{tr}(Q^T B^T B Q)$. $\endgroup$ – cardinal Dec 22 '11 at 18:05
  • $\begingroup$ 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? $\endgroup$ – rk2 Dec 23 '11 at 19:36
  • $\begingroup$ Yes, it has to do both with properties of the trace (hint: cyclic invariance) and of orthogonal matrices (hint: eigenvalues), actually. $\endgroup$ – cardinal Dec 23 '11 at 22:33
  • $\begingroup$ 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. $\endgroup$ – rk2 Dec 28 '11 at 19:16
  • $\begingroup$ I understood what you meant. The hints were meant with the understanding that $Q$ was not square. $\endgroup$ – 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$)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.