Jun 10 – 11, 2022
Dipartimento di Matematica, Università di Pisa
Europe/Rome timezone

Computing the Square Root of a Low-Rank Perturbation of the Scaled Identity Matrix

Jun 10, 2022, 5:00 PM
30m
Aula Magna (Dipartimento di Matematica, Università di Pisa)

Aula Magna

Dipartimento di Matematica, Università di Pisa

L.go B. Pontecorvo, 5 56127 Pisa (PI) Italy

Speaker

Nick Higham (University of Manchester)

Description

We consider the problem of computing the square root of a perturbation of the scaled identity matrix, $A = \alpha I_n + UV^{*}$, where $U$ and $V$ are $n \times k$ matrices with $k \leq 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 \times k$ matrix $\alpha 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 much smaller residual than existing alternatives and can be significantly faster when the perturbation $UV^*$ has low rank.

This is joint work with Massimiliano Fasi and Xiaobo Liu.

Presentation materials

There are no materials yet.