6
$\begingroup$

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
    **Hint**: $\|BQ\|_F^2 = \mathrm{tr}(Q^T B^T B Q)$.2011-12-22
  • 0
    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?2011-12-23
  • 0
    Yes, it has to do both with properties of the trace (**hint**: cyclic invariance) *and* of orthogonal matrices (**hint**: eigenvalues), actually.2011-12-23
  • 0
    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.2011-12-28
  • 0
    I understood what you meant. The hints were meant with the understanding that $Q$ was not square.2011-12-28
  • 0
    Finally! Here it goes: If the QR-decomposition of $A=QR$, append columns to $Q$ s.t. $P=[Q$ $\tilde{Q}]$ is an orthogonal matrix. $||B||_F^2=||BP||_F^2$ (can be proved using cyclic invariance of trace operator) $=||BQ||_F^2+||B\tilde{Q}||_F^2\ge||BQ||_F^2 $ I didn't have to invoke anything about the eigenvalues of orthogonal matrices though.2011-12-28
  • 0
    Good. (And, yes, you did, implicitly).2011-12-28
  • 0
    Using $P^TP=PP^T=I$, $||BP||_F^2=$ tr$(P^TB^TBP)=$ tr$(PP^TB^TB)=$ tr$(B^TB)=$ $||B||_F^2$. How am I using a property of the eigenvalues of an orthogonal matrix?2011-12-31

1 Answers 1

1

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$)