Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
    
Did you make any progress? Cheers. (Also, if this is homework, then the homework tag should be added.) –  cardinal Dec 24 '11 at 18:47
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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