Rank-1 Matrix Differential Equations for Structured Eigenvalue Optimization

A new approach to solving eigenvalue optimization problems for large structured matrices is proposed and studied. The class of optimization problems considered is related to computing structured pseudospectra and their extremal points, and to structured matrix nearness problems such as computing the distance to instability or to singularity under structured perturbations. The perturbation structure can be a general linear structure. We focus on the practically important cases of large matrices with a given sparsity pattern and on perturbation matrices with given range and corange. It is known that analogous eigenvalue optimization for unstructured complex matrices favorably works with rank-1 matrices. The novelty of the present paper is that structured eigenvalue optimization can still be performed with rank-1 matrices, which yields a significant reduction of storage and in some cases of the computational cost. Optimizers are shown to be rank-1 matrices orthogonally projected onto the given structure. This is used in the numerical algorithms. The numerical approach comes in two different versions. If the rank-1 matrices projected onto the structure form a manifold and if the orthogonal projection onto the corresponding tangent spaces is known and computationally inexpensive, as is the case for matrices with given range and corange, then the method relies on a gradient system on this manifold. Otherwise, in particular for matrices with a given sparsity pattern, the method relies on the orthogonal projection of the free gradient onto the tangent space of the manifold of complex rank-1 matrices. The solution of this rank-1 system is then projected onto the structure. It is shown that there is a bijective correspondence between the stationary points of the gradient system on the structure space and of the rank-1 system. Near a local minimizer the rank-1 tangent projection is very close to the identity map, and so the computationally favorable rank-1 projected system behaves locally like the gradient system. Numerical experiments illustrate the two approaches for large matrices with a given sparsity pattern and for perturbation matrices with given range and corange.