Let $I$ be the identity matrix of size $n \times n$, $ v_0, v_1, ... v_k$ be $k$ linearly independent vectors and $y$ be a vector.
I want to find an algorithm solving the following equation : $ ( I + \sum_k v_kv_k^t )x = y$.
In this case $k $ is always much lower than $n$.
My first approach was to compute $ ( I + \sum_k v_kv_k^T )$ then solve the equation, wich gives an algorithm in $O(n^3+kn^2)$.
Using algorithm 1 from there. I get better results with an algorithm in $O(nk^2)$ (much better since $k < n$ ).
But I would like to use the fact that the perturbed matrix is the identity and that the perturbations are symmetric, All other algorithms I found were slower ($O(n^2k)$ or $O(n^2k^2)$).
Any hints to find a faster algorithm are welcome.