I'd like to evaluate a single entry $s_{ik}$ of the $\mathbf{S}$ matrix, using Markov chain Monte Carlo approach. The posterior of $\mathbf{S}$ has a Gaussian likelihood with a covariance matrix $$\mathbf{P}_{k^2\times k^2}=[\mathbf{R}^T\mathbf{R}+\gamma\mathbf{I}_{k^2}]^{-1}$$ where $\mathbf{R}=\mathbf{S}_{k\times k}\otimes\mathbf{S}_{k\times k}$ (the Kronecker product). How can I do rank one updates of $\mathbf{S}$ matrix and compute efficiently the inverse when only one $\mathbf{s}_i$ (the $i$-th row of $\mathbf{S}$) is modified?

For instance, if we have $$\mathbf{M}=(\mathbf{S}^T\mathbf{S}+\lambda\mathbf{I}_{k})^{-1},$$since the first term can be expressed as $\sum_{i}\mathbf{s}_i\mathbf{s}_i$ then calculating $\mathbf{S}_{-i,k}$ can be done by removing the influence of a single vector $\mathbf{s}_i$ is a rank-one update to $\mathbf{M}^{-1}$, so we have $$\mathbf{M}_{-i}=(\sum_{j\neq i} \mathbf{s}_j^T\mathbf{s}_j+\lambda\mathbf{I})^{-1},$$ then we can use Sherman–Morrison formula and we get $$\mathbf{M}_{-i}=( \mathbf{M}^{-1}-\mathbf{s}_i^T\mathbf{s}_i)^{-1}=\mathbf{M}-\frac{\mathbf{M}\mathbf{s}_i^T\mathbf{s}_i\mathbf{M}}{\mathbf{s}_i\mathbf{M}\mathbf{s}_i^T-1}.$$ Any suggestion for computing inverse of $\mathbf{P}$ ($\mathbf{P}_{-i}$) for just one rank update of $\mathbf{s}$ (deleting the $i$-th row)?? Update:

I think I can write $$\mathbf{P}_{-i}^{-1}=\mathbf{P}^{-1}-(\mathbf{S}\otimes \mathbf{s}_i)^T(\mathbf{S}\otimes \mathbf{s}_i)-(\mathbf{s}_i\otimes\mathbf{S})^T(\mathbf{s}_i\otimes\mathbf{S})+(\mathbf{s}_i\otimes\mathbf{s}_i)^T(\mathbf{s}_i\otimes\mathbf{s}_i).$$ Computing $\mathbf{P}^{-1}+(\mathbf{s}_i\otimes\mathbf{s}_i)^T(\mathbf{s}_i\otimes\mathbf{s}_i)$ is similar to $\mathbf{M}_{-i}$ calculation, since the denominator becomes a number and not a matrix, therefore I would not need to do matrix inversion. If I try to solve inversion problem in this case recursively for the second and third term of $\mathbf{P}_{-i}$ then I need to invert big matrices in the denominators which I am trying to avoid.

I am wondering how I can compute $\mathbf{P}_{-i}$ from here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.