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.
Best Answer
Here is one approach.
Determinant is product of eigenvalues.
You can estimate singular values of $X$ : $\sigma_i$.
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.