Speaker
Description
Fundamental properties of weighted graphs, such as connectivity and centrality, are characterized by eigenvalues or eigenvectors of either the weighted adjacency matrix or of matrices related to it, such as the graph Laplacian. Here we study exemplary problems of robustness of partitioning/ranking, which can be viewed as matrix nearness problems that refer to eigenvalues or eigenvectors of structured symmetric real matrices. We propose algorithms that do eigenvalue/eigenvector optimization without eigenvalues/eigenvectors but work directly with the quadratic form (Rayleigh quotients).
This requires only matrix-vector products and vector inner products.
Our method is based on reformulating the problem and minimizing a suitable functional in the eigenvalues/eigenvectors.
After determining the gradient system associated with this functional, we introduce a low-rank projected system, suggested by the underlying low-rank structure of the extremizers of the functional.
Integrating this low-rank system requires both a moderate computational effort and a memory requirement, as shown in some illustrative numerical examples.
This is inspired by joint works with M. Benzi (SNS, Pisa), with C. Lubich (Universität Tübingen), and with S. Sicilia (University of Mons).
