This seems like a standard problem, but unable to find a solution online.


Suppose we have two singular PSD matrices A and B with the following assumptions:


$ 0 < x \leq ||A|| \leq y$


$ 0 < ||B|| = z$


$||A - B|| \leq \delta$


Can an upper bound be provided for:


$ ||A^\dagger - B^\dagger || $


The final bound would be useful with any specific norm. If an upper bound is only possible with additional assumptions, that would be useful to know as well.


I'm interested in using this for an application where $B$ is the expected value of a random graph Laplacian and the bounds on $A$ are a high probability interval.



Difference of pseudoinverse bound under assumptions
This goes in line with Dirk's comment above; essentially one is constrained by the small eigenvalues of the matrices in getting any kind of estimate. 


Stewart [On the Perturbation of Pseudo-Inverses, Projections and Linear Least Squares Problems, SIAM Review Vol. 19, No. 4 (Oct., 1977), pp. 634-662] gives some generic bounds. For example, if $\|\cdot\|$ is any of the Schatten $p$--norms, then in your notation,


$$ \|A^\dagger-B^\dagger\|\leq \frac{1+\sqrt{5}}{2}\max\{\|A^\dagger\|\_2^2,\|B^\dagger\|\_2^2\}\delta. $$


If the ranks are the same, then the max term turns into $\|A^\dagger\|\_2\|B^\dagger\|\_2$.


However, I don't know of any more specific bounds in your case. You may look at some of the literature on the Nystrom method (e.g., <http://www.jmlr.org/papers/volume17/gittens16a/gittens16a.pdf>). There should be a lot of references there, and needing to bound the quantity you're interested in arise naturally there.


