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.

In many applications that is not with high requirements, it is common to use $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ or $A^{\text T}(AA^{\text T}+\lambda I)^{-1}$ ($\lambda$ is small) to approximate the Moore-Penrose pseudoinverse $A^{\dagger}$. But from the properties of Moore-Penrose pseudoinverse, how do we know that $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ and $A^{\text T}(AA^{\text T}+\lambda I)^{-1}$ will be close to the exact solution?

It seems that $$ \lim_{\lambda \rightarrow 0}(A^{\text T}A+\lambda I)^{-1}A^{\text T} = A^{\dagger} $$ I want to know why this happens (You can try in Matlab for verification). Besides, it is also possible for $A^{\text T}A + \lambda I$ to be singular. The whole thing is confusing me.

And the question following this is, if we want to restrict the error of $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ approximating the $A^{\dagger}$ to a certain extent, can we know the upper bound for the $\lambda$ according to some criterions?

share|improve this question
    
Not sure if that is your question, but you know it approximates the inverse since when multiplying in the correct side with A, you get I back. –  ido Nov 29 '12 at 9:01
    
If you can use singular value decompositon, the proof is utterly clear. However, if you want to prove the statement "from the properties of Moore-Penrose pseudoinverse" (I take you mean the four defining properties of M-P inverse), I am also inclined to see such a proof. –  user1551 Nov 29 '12 at 13:06

1 Answer 1

up vote 3 down vote accepted

What happens is that $$ A^{\dagger}=\lim_{\lambda\searrow0}(A^TA+\lambda I)^{-1}A^T=\lim_{\lambda\searrow0}A^T(AA^T+\lambda I)^{-1} $$

Proof:

Write $A=WDV$ the singular value decomposition (i.e. $D$ is diagonal with non-negative diagonal, $W,V$ are unitaries). Then $A^TA=V^TD^2V$, and $(A^TA+\lambda I)^{-1}=V^T(D^2+\lambda I)^{-1}V$. $$ (A^TA+\lambda I)^{-1}A^T-(A^TA+\mu I)^{-1}A^T=V^T(D^2+\lambda I)^{-1}VV^TDW^T-V^T(D^2+\mu I)^{-1}VV^TDW^T=V^T(D^2+\lambda I)^{-1}DW^T-V^T(D^2+\mu I)^{-1}DW^T=V^T[(D^2+\lambda I)^{-1}D-(D^2+\mu I)^{-1}D]W^T=V^T(D^2+\lambda I)^{-1}D[(\mu-\lambda)I](D^2+\mu I)^{-1}DW^T. $$ As $(D^2+\lambda I)^{-1}D=f(D)$ where $f_\lambda(t)=t/(t^2+\lambda)$ and $f(0)=0$, the norm of $(D^2+\lambda I)^{-1}D$ is bounded (by the inverse of the smallest nonzero singular value of $A$) irrespective of $\lambda$. So the estimate above yields that $$ \|(A^TA+\lambda I)^{-1}A^T-(A^TA+\mu I)^{-1}A^T\|\leq c|\lambda-\mu| $$ for an appropriate constant $c$. This proves that $$ B=\lim_{\lambda\searrow0}(A^TA+\lambda I)^{-1}A^T $$ exists. Now $$ ABA=\lim_{\lambda\searrow0}A(A^TA+\lambda I)^{-1}A^TA=\lim_{\lambda\searrow0}A(I-\lambda(A^TA+\lambda I)^{-1})=A-\lim_{\lambda\searrow0}\lambda A(A^TA+\lambda I)^{-1}=A-W\lim_{\lambda\searrow0}A\lambda D(D^2+\lambda I)^{-1}V=A-W\lim_{\lambda\searrow0}\lambda f_\lambda(t)V. $$ As $f_\lambda(0)=0$ and $\lambda f_\lambda(t)\to0$ when $t\ne0$, the expression in the limit goes to zero, so $ABA=A$.

In a similar way one shows that $BAB=B$.

Finally, $AB$ is symmetric as $$ AB=\lim_{\lambda\searrow0}A(A^TA+\lambda I)^{-1}A^T=\lim_{\lambda\searrow0}WD(D^2+\lambda I)^{-1}DW^T=\lim_{\lambda\searrow0}WD^2(D^2+\lambda I)^{-1}W^T. $$ The matrices $D^2(D^2+\lambda I)^{-1}$ are symmetric, and so are their conjugates by $W$, and so is the limit. Similarly, $BA$ is symmetric.

As the Moore-Penrose pseudoinverse is unique, $B=A^\dagger$.

share|improve this answer
    
Yes, and I want to know why this happens. Besides, it is also possible that $A^{\text T}A + \lambda I$ is singular. The whole thing is confusing me. –  Chen Nov 29 '12 at 12:52
    
I'll add a proof. –  Martin Argerami Nov 29 '12 at 13:05
    
Thanks very much for the help! –  Chen Nov 30 '12 at 6:10

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.