Given a large sparse matrix $\Sigma$, I want to find a (block) diagonal matrix $\Omega$ which approximates $\Sigma^{-1}$.

In this specific problem, we know that $\Sigma$ is a block tridiagonal matrix. The blocks are of size $3 \times 3$. The blocks on the diagonal of $\Sigma$ stem from covariance matrices, i.e. they are symmetric positive semi-definite. The block $\Sigma_{i,i}$ represents the measurement uncertainty of the parameter block $i$ in my nonlinear least squares problem. The blocks $\Sigma_{i,i+1}$ on the upper diagonal represent the covariance matrix between parameter $i$ and $i+1$. (In general, they are smaller than the blocks on the diagonal, if that helps.) Therefore, $\Sigma$ is symmetric, positive semi-definite, and contains only real values.

As stated above, I am interested in finding the blockdiagonal matrix $\Omega$ which (best) approximates $\Sigma^{-1}$ in the sense that $\Omega \cdot \Sigma \approx I$. In the literature, I've often seen that the off-diagonal entries of $\Sigma$ are ignored which makes it easy to construct $\Omega$. I'd think there should be better approximations for finding $\Omega$.

I've also found this question, which is interested in the diagonal of the exact inverse. Again, I'd intuitively expect that this is not optimal as the off-diagonal entries of $\Omega$ are not small compared to its diagonal entries. This question aims to find any sparse matrix that approximates the inverse, but I am specifically interested in an approximation of a block diagonal form.

What is the best way to approach this problem?

  • $\begingroup$ Are you aware that, most often, the inverse of a tridiagonal matrix can be far from sparse ? In particular far from a tridiagonal matrix (se the example of matrices $M$ and $D$ I give in one of my questions (math.stackexchange.com/q/1774670)). $\endgroup$ – Jean Marie Sep 3 '16 at 10:25
  • $\begingroup$ Yes, I am aware of that. $\endgroup$ – stereo Sep 3 '16 at 10:34
  • $\begingroup$ Why do you expect, that there exist a block diagonal $\Omega$, such that $\Omega\Sigma\approx I$? If this is the case, then $\Sigma$ is close to block diagonal and you can ignore off-diagonals. There are other methods, but they works only for some $\Sigma$ and in general can produce worse approximation. $\endgroup$ – Pawel Kowal Sep 3 '16 at 11:49
  • $\begingroup$ Actually, I am not sure that such a matrix $\Omega$ exists. If you can make a strong argument that for my specific problem such a matrix a) does not exist, or b) can not be constructed efficiently, then I'd be satisfied and would drop this problem. $\endgroup$ – stereo Sep 3 '16 at 12:10

If $\Omega\Sigma = I + E$, with $\|E\|$ small, then $\Sigma^{-1}\Omega^{-1} \approx I - E$, and $\Sigma-\Omega^{-1} \approx \Sigma E$, thus $\|\Sigma-\Omega^{-1}\| \approx \|\Sigma\| \|E\|$.

Since $\Omega^{-1}$ is block diagonal, this implies, that norm of off-diagonal elements of $\Sigma$, $\Sigma_{off}$ is small: $\|\Sigma_{off}\|_1 \leq \|\Sigma\|_1 \|E\|_1$. This follows from: $\|X\|_1 \geq |X_{off}\|_1$ for any matrix $X$, where $X_{off}$ is a matrix constructed from $X$ by zeroing elements on block diagonals.

In your case off-diagonal entries of $\Sigma$ are not small compared to its diagonal elements, therefore you cannot find block diagonal $\Omega$, such that $\Omega\Sigma \approx I$.


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.