The power of rank-1 perturbations in matrix nearness problems.

Abstract: This talk concerns matrix nearness problems related to eigenvalues, singular values, and pseudospectra. Such problems arise in a wide range of applications, including dynamical systems, where they appear in questions of robust stability and control, as well as graph-based problems such as clustering and ranking. These problems lead to algorithms based on structured matrix perturbations that move eigenvalues, singular values, or Rayleigh quotients to prescribed locations.

Remarkably, the optimal perturbations are often of rank one, or projections of rank-1 matrices onto a given linear structure, such as a prescribed sparsity pattern. In the approach presented here, these optimal rank-1 perturbations are computed by a two-level iteration combining eigenvalue optimization with root-finding.

The eigenvalue optimization problem, with equality or inequality constraints on the perturbation size, is solved using gradient-based differential equations for rank-1 matrices. In practice, this amounts to evolving two vectors that represent the rank-1 matrix toward a stationary point. The root-finding component determines the optimal perturbation size by solving a scalar nonlinear equation. The two algorithmic components can either be nested or applied in an alternating fashion. Numerical experiments illustrate the efficiency of the approach for several eigenvalue- and singular-value–based nearness problems. The talk is largely based on a recent monograph written jointly with Christian Lubich.

numerical analysisoptimization and control

Audience: researchers in the topic

CAM seminar

Series comments: Online streaming via zoom on exceptional cases if requested. Please contact the organizers at the latest Monday 11:45.