3
$\begingroup$

Given a near singular covariance matrix, the standard method of 'fixing' it seems to be to add a small damping coefficient $c>0$ to the diagonal, which serves to bump all the eigenvalues up by this amount.

Is there a way to determine the optimal value of this damping coefficient without resorting to some iterative procedure where I jump back and forth between inverting the matrix to look for infinities and NaNs and making $c$ increasingly small?

I could look at the minimum eigenvalue fairly cheaply, but it seems like the correct choice for $c$ would still also depend on both the entries of the matrix as well as its size.

Finally, it's more important that my algorithm always works than it is that the perturbation is as small as possible, so I'm willing to accept more error for the sake of a procedure with some sort of guarantee that it will always work.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ What do you mean by "optimal"? If you know the maximum eigenvalue of $C$ and you want a 2-norm condition number bigger than $\tau$, then pick $c$ so that the ratio of the largest eigenvalue over $c$ is bigger than $\tau$. $\endgroup$ – Brian Borchers Apr 26 '16 at 20:50
  • $\begingroup$ @BrianBorchers is the condition number really what I want? For instance a diagonal matrix with $\epsilon$ on the diagonal has condition number 1, despite being very close to singular. Also don't I want smaller condition numbers in general, not larger? $\endgroup$ – Thoth Apr 26 '16 at 21:04
  • 3
    $\begingroup$ You haven't answered my question about what's optimal- a lot depends on what you want. The condition number is the ratio of the largest eigenvalue to the smallest. Adding c to the diagonal will increase the smallest eigenvalue (with very little effect on the largest eigenvalue) and reduce the condition number of C. $\endgroup$ – Brian Borchers Apr 26 '16 at 21:26
  • $\begingroup$ @BrianBorchers, what I meant was why would I want a lower bound on an acceptable condition number? Wouldn't I want an upper bound on an acceptable condition number? I suppose optimal would be the smallest $c$ such that there is no overflow when I take the inverse. I get your point about the condition number though, that's probably the best way to go about it, since I just have to grab the largest eigenvalue as well as the smallest to compute it. $\endgroup$ – Thoth Apr 26 '16 at 21:31
  • $\begingroup$ To continue my comment, are there any heuristics for deciding how small I should want my condition number to be? Does it just come down to how many digits of accuracy I want to make sure I keep? $\endgroup$ – Thoth Apr 26 '16 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.