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

  • $\begingroup$ 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? $\endgroup$ – fred Oct 16 '15 at 14:49
  • $\begingroup$ I think peow is referring to the matrix square root en.wikipedia.org/wiki/Square_root_of_a_matrix. $\endgroup$ – Jesse Chan Oct 16 '15 at 14:58
  • $\begingroup$ @JesseChan, I'm guessing the confusion was about randomized algorithms. That's where I'm stuck. $\endgroup$ – Bill Barth Oct 16 '15 at 15:04
  • $\begingroup$ 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/… $\endgroup$ – Jesse Chan Oct 16 '15 at 15:19

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.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.