# Fast algorithm for computing matrix square root using randomized linear algebra?

Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?

• I am not really sure I understand the question. You could write a version of the Cholesky decomposition that uses random choices. You could randomly permute the rows and columns, perform a Cholesky decomposition then "unpermute" the rows and columns. Is this what you mean?
– fred
Oct 16 '15 at 14:49
• I think peow is referring to the matrix square root en.wikipedia.org/wiki/Square_root_of_a_matrix. Oct 16 '15 at 14:58
• @JesseChan, I'm guessing the confusion was about randomized algorithms. That's where I'm stuck. Oct 16 '15 at 15:04
• Ah. I think randomized algorithms are referring to linear algebraic methods based on randomized sampling of the range of a matrix. These converge in an expected value sense. amath.colorado.edu/faculty/martinss/Pubs/… Oct 16 '15 at 15:19

## 1 Answer

Randomized algorithms can accurately approximate your matrix if it has rapidly decaying singular values (i.e. a Gaussian sampling of the range is likely to pick up the action of the matrix). Since your matrix is symmetric, you could approximate a truncated eigenvalue decomposition using random linear algebra and simply take the square root of the eigenvalues.

I'm not sure of any explicit algorithms based on randomized linear algebra (RLA) which approximate the matrix square root explicitly. You could also try iterative algorithms for the matrix square root (Wikipedia shows a few examples) and try to exploit RLA there in matrix-vector multiplications or applying matrix inverses, though this may not work well since inverses typically need the smallest singular values.