Computing the Square Root of a Low-Rank Perturbation of the Scaled Identity Matrix
Massimiliano Fasi, Nicholas John Higham, Xiaobo Liu · SIAM Journal on Matrix Analysis and Applications · 2023
Abstract. We consider the problem of computing the square root of a perturbation of the scaled identity matrix, [Formula: see text], where [Formula: see text] and [Formula: see text] are [Formula: see text] matrices with [Formula: see text]. This problem arises in various applications, including computer vision and optimization methods for machine learning. We derive a new formula for the [Formula: see text]th root of [Formula: see text] that involves a weighted sum of powers of the [Formula: see text]th root of the [Formula: see text] matrix [Formula: see text]. This formula is particularly attractive for the square root, since the sum has just one term when [Formula: see text]. 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 [Formula: see text] has low rank.