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.

  • $\begingroup$ I think that considering just diagonal matrices shows that no such bound exists. (All your assumptions do not say anything about the small entries on the diagonal, which can be used to get a large norm of the pseudo inverses. $\endgroup$ – Dirk Jun 30 '19 at 10:41

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.

| cite | improve this answer | |

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.