# Is there a way to quickly compute diagonal entries of inverse of a positive definite matrix?

Suppose you have an $$n\times p$$ tall matrix $$\mathbf{X}$$, where $$n \gg p$$. I need a quick way to compute the diagonal entries of $$(\mathbf{X}^\top \mathbf{X})^{-1}$$ for some confidence intervals of regression coefficients. Since $$\mathbf{X}^\top \mathbf{X}$$ is positive definite given linearly independent columns, my initial thought was to do Cholesky decomposition, but I don't know where to take it from there. An iterative method is also fine.

Any help would be appreciated. Thanks!

Once you have a Cholesky decomposition $$X^T X = L L^T$$ you have $$(X^T X)^{-1} = (L L^T)^{-1} = (L^{-1})^T L^{-1}$$

For a matrix $$A,$$ the $$i$$-th column on $$A$$ is given by $$Ae_i$$ and the $$i$$-th diagonal entry of a square matrix $$A$$ is thus given by $$e_i^T A e_i.$$

Therefore, the $$i$$-th diagonal entry of $$(X^T X)^{-1}$$ is given by

$$e_i^T (X^T X)^{-1} e_i = e_i^T (L^{-1})^T L^{-1} e_i =(L^{-1}e_i)^T L^{-1} e_i = \| L^{-1} e_i \|^2$$

That is, the $$i$$-th diagonal entry of $$(X^T X)^{-1}$$ is the squared norm of the $$i$$-th column of $$L^{-1}.$$

Further, note that for issues of numerical stability and performance, you should compute $$L^{-1} e_i$$ by solving $$Lx_i = e_i$$ via back-substitution rather than other methods of inverting $$L.$$

• This solution is extremely elegant. Thank you! Commented Apr 1, 2020 at 15:56
• @MatthewK Thanks. Happy to help. Commented Apr 1, 2020 at 15:57

If you are thinking to calculate the eigenvalues of (X^TX)^{-1}, then most efficient way:

Apply the Singular Value Decomposition:

Then $$X = UDV^T$$ where $$U,V$$ are orthogonal matrices ($$U^T = U^{-1}$$ and $$V^T = V^{-1}$$ )and $$D = diag(\sigma_1,\dots, \sigma_n)$$ is a diagonal matrix and $$\sigma_i$$ are singular values.

Since $$X$$ is a positive definite matrix, this implies that all its eigenvalues are positive and therefore so will singular values.

Then:

$$X^TX = VD^TDV^T$$ and $$D^TD$$ which is still a diagonal matrix contains positive eigenvalues of $$X^TX$$. Then, we can compute $$(X^TX)^{-1}$$ which is simply:

$$(X^TX)^{-1} = V(D^TD)^{-1}VT$$.

So since, each diagonal entry in $$D^TD$$ is $$\sigma_i^2 > 0$$ then, each entry in $$(D^TD)^{-1}$$ is $$\frac{1}{\sigma_i^2}$$.

So eigenvalues of $$(X^TX)^{-1}$$ are $$\{\frac{1}{\sigma_i^2}\}_{i=1}^n$$.

a priori, there is no better method than the naive method which consists in

$$(*)$$ calculating $$X^TX$$ and $$(X^TX)^{-1}$$.

Indeed, Case 1. We don't know $$X^TX$$. Then the complexity of $$(*)$$ is $$np^2+p^3\approx np^2$$.

If we follow (for example) the Ragib's method, then the complexity is $$np^2$$ for $$X^TX$$, $$p^3/2$$ for $$L$$ and $$p^3/2$$ for solving the equations $$Lx_i=e_i$$, that is, $$np^2$$ for $$X^TX$$ and $$p^3$$ for the sequel.

Case 2. We know $$X^TX$$. Then both complexities are $$p^3$$.