Is there a fast algorithm for computing the matrix square root of a real symmetric matrix using random matrices or randomized algorithms?
$\begingroup$
$\endgroup$
4
-
$\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$– fredOct 16, 2015 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 ChanOct 16, 2015 at 14:58
-
$\begingroup$ @JesseChan, I'm guessing the confusion was about randomized algorithms. That's where I'm stuck. $\endgroup$– Bill BarthOct 16, 2015 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 ChanOct 16, 2015 at 15:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 16, 2015 at 16:20