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