low-complexity matrix inversion algorithm for a near-identity matrix?

Question

As I know, the general complexity of matrix inversion is $O(n^3)$, but it is a little bit high. My matrix is $(I + A)$ , where $I$ is an $n \times n$ identity matrix and $A$ is a hermitian matrix and the norm of all its elements are very small (near $1/100$). Therefore, I think it's a particular matrix that close to an identity matrix.

So, is there any effective algorithm that can solve the inversion of the matrix with low-complexity ? hopefully , it can be reduced to $O(n^2)$. High accuracy is not very necessary.

Answer 1

$(I+A)(I-A) = I - AA$. If $A$ is small enough, then you may be able to approximate $(I+A)^{-1}$ by $I-A$.

If you don't need to compute the inverse but only need to solve $(I+A)^{-1}v$ then you can improve accuracy by taking the rational series $I - A + AA/2 + ...$ upto the desired tolerance and then compute matrix-vector products $v - Av + A(Av)/2 + ...$. This will reduce the complexity to $O(n^2)$

Hard to say more without more structure on $A$.

Answer 2

There is something called a fast randomized low-rank SVD. The time complexity is $\mathcal{O}(n^{2}\log(k) +nl^{2}) $ The inversion at the end doesn't take much time. There are other similar matrix decompositions like this. There are likely ones made for Hermitian matrices as well.