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

Question

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!

Answer 1

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.$

Answer 2

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$.

Answer 3

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$.