  Models in which the covariance matrix has the structure of a sparse matrix
plus a low rank perturbation are ubiquitous in data science applications. It is
often desirable for algorithms to take advantage of such structures, avoiding
costly matrix computations that often require cubic time and quadratic storage.
This is often accomplished by performing operations that maintain such
structures, e.g. matrix inversion via the Sherman-Morrison-Woodbury formula. In
this paper we consider the matrix square root and inverse square root
operations. Given a low rank perturbation to a matrix, we argue that a low-rank
approximate correction to the (inverse) square root exists. We do so by
establishing a geometric decay bound on the true correction's eigenvalues. We
then proceed to frame the correction as the solution of an algebraic Riccati
equation, and discuss how a low-rank solution to that equation can be computed.
We analyze the approximation error incurred when approximately solving the
algebraic Riccati equation, providing spectral and Frobenius norm forward and
backward error bounds. Finally, we describe several applications of our
algorithms, and demonstrate their utility in numerical experiments.
