COMPUTING THE SQUARE ROOT OF A LOW-RANK PERTURBATION OF THE SCALED IDENTITY MATRIX∗

We consider the problem of computing the square root of a perturbation of the scaled identity matrix, A = αI_n + ^{UV ∗}, where U and V are n × k matrices with k ≤ n. This problem arises in various applications, including computer vision and optimization methods for machine learning. We derive a new formula for the pth root of A that involves a weighted sum of powers of the pth root of the k × k matrix αI_k + ^{V ∗U}. This formula is particularly attractive for the square root, since the sum has just one term when p = 2. We also derive a new class of Newton iterations for computing the square root that exploit the low-rank structure. We test these new methods on random matrices and on positive definite matrices arising in applications. Numerical experiments show that the new approaches can yield a much smaller residual than existing alternatives and can be significantly faster when the perturbation UV ^∗ has low rank.

Key words. matrix pth root, matrix square root, low-rank update, matrix iteration, Newton iteration, MATLAB

AMS subject classifications. 15A16, 65F60, 65F99