Perturbation Analysis of An Eigenvector-Dependent Nonlinear Eigenvalue Problem With Applications?

Yunfeng Cai, Zhigang Jia, Zheng‐Jian Bai

TL;DR

This paper introduces a novel perturbation analysis for a class of nonlinear eigenvalue problems (NEPs) that arise in crucial scientific applications like electronic structure calculations. The authors develop a condition number and computable error bounds, offering a way to quantify the sensitivity of these problems and assess the quality of approximate solutions.

What Problem Does This Paper Address?

Many scientific and engineering problems, particularly in quantum chemistry and data analysis, are modeled by nonlinear eigenvalue problems (NEPs) of the form $A(P)V = VA$, where $V$ is a matrix of orthonormal eigenvectors and $A(P)$ is a function of $P=VV^H$. These problems are often solved using iterative methods like the self-consistent field (SCF) approach. However, in real-world scenarios, the matrices involved are subject to errors and noise, leading to a "perturbed" NEP. A key challenge is to understand how these perturbations affect the computed solutions and to reliably assess the accuracy of approximations obtained from these perturbed problems. This paper addresses this by providing theoretical tools to analyze the sensitivity of NEPs and quantify the error in approximate solutions.

Methods

The authors employ a combination of established mathematical theorems and novel techniques to analyze the perturbed NEP. They leverage the Weyl Theorem and the Davis-Kahan sin $\Theta$ theorem to bound the distance between the true and perturbed eigenvector subspaces. Additionally, Brouwer's fixed-point theorem is used to establish the existence of solutions to the perturbed problem. A significant contribution is the introduction of a condition number for NEPs, which quantifies the problem's sensitivity to perturbations. Two distinct approaches are presented for the perturbation analysis, each offering different strengths. Furthermore, the paper derives computable error bounds that can be used to estimate the quality of an approximate solution obtained from numerical methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical validation using simulated data for specific applications.

Key Insights and Ideas

  • Quantifying Sensitivity: The paper introduces a condition number that effectively measures how sensitive the NEP's solution is to small changes in the input matrices. This is crucial for understanding the reliability of numerical results.
  • Bridging Theory and Practice: The work provides theoretical guarantees for the convergence and accuracy of numerical methods used for NEPs, bridging the gap between abstract mathematical models and practical computational challenges.
  • Error Bounds as Quality Metrics: The derived error bounds offer a concrete way for practitioners to assess the quality of their computed solutions, especially when dealing with noisy or discretized problems.
  • Two-Pronged Approach: The use of two distinct analytical approaches (one based on fixed-point theorems and another inspired by Sun's work) provides a robust framework and allows for comparison of different analytical perspectives.

Key Results

The paper establishes theoretical results that provide upper bounds on the distance between the true solution and the solution of a perturbed NEP. Specifically:

  • Perturbation Bounds: Theorems 2.1 and 2.3 provide bounds on the perturbation of the eigenvector subspace. Theorem 2.3's bound is shown to be sharper under certain conditions.
  • Condition Number: A condition number is defined, which depends on the eigenvalue gap of the unperturbed problem and a local Lipschitz constant of the matrix function $A(P)$. A large gap and small Lipschitz constant indicate a well-conditioned problem.
  • Error Bounds: Corollaries 2.8 and 2.9 provide computable error bounds that can be used to assess the quality of approximate solutions. These bounds are demonstrated to be sharp in numerical experiments.
  • Numerical Validation: The theoretical results are validated through numerical experiments on the Kohn-Sham equation (from electronic structure theory) and the trace ratio optimization problem (from dimensionality reduction). These experiments show that the derived bounds are effective and often sharp.

Limitations and Future Work

  • Assumptions: The applicability of some theorems relies on certain conditions, such as the eigenvalue gap $g$ being sufficiently large relative to the perturbation magnitude $d$. When these conditions are not met, the bounds may not be applicable or sharp.
  • Computational Cost: While the error bounds are computable, their computation might still involve some overhead.
  • Future Work: The authors suggest that the developed framework can be extended to other types of nonlinear eigenvalue problems and to analyze the convergence of iterative solvers for these problems more deeply. The paper also hints at the potential for further refinement of the perturbation bounds and condition numbers.

Summary updated

Abstract

The eigenvector-dependent nonlinear eigenvalue problem (NEPv) $A(P)V=VΛ$, where the columns of $V\in\mathbb{C}^{n\times k}$ are orthonormal, $P=VV^{\mathrm{H}}$, $A(P)$ is Hermitian, and $Λ=V^{\mathrm{H}}A(P)V$, arises in many important applications, such as the discretized Kohn-Sham equation in electronic structure calculations and the trace ratio problem in linear discriminant analysis. In this paper, we perform a perturbation analysis for the NEPv, which gives upper bounds for the distance between the solution to the original NEPv and the solution to the perturbed NEPv. A condition number for the NEPv is introduced, which reveals the factors that affect the sensitivity of the solution. Furthermore, two computable error bounds are given for the NEPv, which can be used to measure the quality of an approximate solution. The theoretical results are validated by numerical experiments for the Kohn-Sham equation and the trace ratio optimization.
BibTeX
@inproceedings{cai2018perturbation,
  author = {Yunfeng Cai and Zhigang Jia and Zheng‐Jian Bai},
  title = {{Perturbation Analysis of An Eigenvector-Dependent Nonlinear Eigenvalue Problem With Applications?}},
  booktitle = {BIT},
  year = {2018},
}
Figure