I'm given a probability distribution vector $p \in \mathbb{R}^n$ - $p^T \mathbf{1} = 1$ and $p_i \ge 0$. Given the matrix $$H = \mathbf{diag}(p) - p p^T$$ Is there any fast/easy way of calculating its square root without having to do full Cholesky decomposition?
Note that the matrix itself is PSD with the vector $\mathbf{1}$ being the eigenvector with corresponding eigenvalue $0$.
It's trivial to compute the Cholesky factorization of $\mbox{diag}(p)$. Subtracting $pp^{T}$ is a rank-one update (sometimes called a "downdate" because of the subtraction), and methods based on the Sherman-Morrison-Woodbury formula can be used to compute the updated Cholesky factorization easily.
See the Wikipedia page on the Cholesky factorization and particularly the section on rank one downdating.