Efficient way to calculate inverse and determinant of $I + XX^T$

Question

Problem

Let $A_{n \times n} = I_{n \times n} + XX^T$, where $X : n \times p$ matrix.

I would like to get the "computationally efficient" form of the following:

• $A^{-1}$
• $\mathrm{det}(A)$

By "computational efficiency", I mean something that minimizes computer time complexity (e.g. LU decomposition of $XX^T$).

---

Try

So using Woodbury matrix identity,

$$ A^{-1} = (I + XX^T)^{-1} = I - X (I + X^T X)^{-1} X^T $$

but again

$$ (I + X^T X)^{-1} = I - X^T(I + XX^T)^{-1} X $$

it gets circular.

And for the determinant, matrix determinant lemma,

$$ \mathrm{det}(I_n + XX^T) = \mathrm{det}(I_p+X^TX) $$

but I'm not sure how to proceed.

Any help will be appreciated.

Answer 1

Here is one approach.

1. Determinant is product of eigenvalues.

2. You can estimate singular values of $X$ : $\sigma_i$.

3. Then eigenvalues of $XX^T$ will be squares of those singular values (and pad with zeros if needed).

Now determinant will be $\prod_i (1+{\sigma_i}^2)$ because of Brauer's theorem I think.

This will be efficient if $n$ and $p$ are of very different sizes because the number of non-zero singular values will be maximally the smallest of those. Singular values can be estimated with power method for example.