PaperlayerView exact revision on arXiv

Source-linked AI summary

Eigenvalue and Generalized Eigenvalue Problems: Tutorial

Benyamin Ghojogh, Fakhri Karray, Mark Crowley

arXiv:1903.11240v3stat.MLcs.LG

TL;DR

The paper addresses the need for a tutorial treatment of eigenvalue and generalized eigenvalue problems and their roles in optimization and machine learning. It introduces their formulations, decompositions, optimization connections, examples, and solution methods. The resulting tutorial connects these problems to PCA, kernel supervised PCA, and Fisher discriminant analysis.

  • Problem

    Eigenvalue and generalized eigenvalue problems require a unified introduction covering their definitions, optimization formulations, applications, and solutions.

  • Method

    The paper develops the two problem types, eigen-decomposition, optimization forms, machine-learning examples, and solution procedures.

  • Results

    The tutorial shows how optimization problems yield eigenvalue or generalized eigenvalue problems and applies them to PCA, kernel supervised PCA, and Fisher discriminant analysis.

  • Takeaways & Limitations

    Eigenvalue and generalized eigenvalue formulations provide a common framework for the paper’s machine-learning examples and their associated optimization problems.

Abstract

from arXiv · show

This paper is a tutorial for eigenvalue and generalized eigenvalue problems. We first introduce eigenvalue problem, eigen-decomposition (spectral decomposition), and generalized eigenvalue problem. Then, we mention the optimization problems which yield to the eigenvalue and generalized eigenvalue problems. We also provide examples from machine learning, including principal component analysis, kernel supervised principal component analysis, and Fisher discriminant analysis, which result in eigenvalue and generalized eigenvalue problems. Finally, we introduce the solutions to both eigenvalue and generalized eigenvalue problems.

1. Introduction

The paper motivates eigenvalue and generalized eigenvalue problems as broadly useful tools, especially for identifying informative directions in data. It then outlines a tutorial covering their formulations, optimization origins, solutions, and machine-learning examples.

  • Eigenvalue and generalized eigenvalue problems are important across machine learning, physics, statistics, and mathematics.
  • For a covariance matrix, eigenvectors identify data-spread directions and eigenvalues quantify the spread along those directions.
  • The tutorial introduces both problem types, their solutions, and the optimization problems that produce them.
  • Machine-learning examples include principal component analysis, kernel supervised principal component analysis, and Fisher discriminant analysis.

2. Introducing Eigenvalue and Generalized Eigenvalue Problems

The paper defines eigenvalue and generalized eigenvalue problems through matrix–vector relations and their decompositions. It distinguishes the generalized problem by its matrix pair and explains the associated eigenvectors, eigenvalues, and eigenpairs.

  • Eigenvalue Problem: An eigenvalue problem associates matrix eigenvectors with eigenvalues through a matrix–vector relation and its matrix-form decomposition.
  • Eigenvalue Problem: For symmetric matrices, eigenvectors are orthogonal or orthonormal; for nonsymmetric matrices, they need not be.
  • Eigenvalue Problem: Eigenvalue decomposition, also called eigen-decomposition or spectral decomposition, represents the matrix using eigenvectors and eigenvalues.
  • Generalized Eigenvalue Problem: A generalized eigenvalue problem is defined for a pair of symmetric matrices (A, B), called a pair or pencil.
  • Generalized Eigenvalue Problem: The generalized eigenvectors and eigenvalues form eigenpairs, and the order of the matrix pair matters.

3. Eigenvalue Optimization

The paper shows how constrained optimization problems produce eigenvalue problems, with scalar and matrix formulations leading to eigenvectors and eigenvalues of A. Maximization selects the largest eigenvalues, while minimization selects the smallest.

  • Optimization Form 1: Constrained optimization over φ yields Aφ = λφ, so φ is an eigenvector of A and λ is its eigenvalue.
  • Optimization Form 2: For matrix-valued optimization, the columns of Φ are eigenvectors of A and the diagonal elements of Λ are eigenvalues.
  • Optimization Forms 1–2: Maximization orders eigenvalues and eigenvectors from largest to smallest, whereas minimization orders them from smallest to largest.
  • Optimization Form 3: The Frobenius-norm formulation reduces to an eigenvalue problem by setting A = XX⊤, giving Aφ = λφ.
  • Optimization Form 5: The scalar Rayleigh-Ritz formulation also yields an eigenvalue problem for A, with the optimization direction determining the selected eigenvalue.

4. Generalized Eigenvalue Optimization

The paper derives generalized eigenvalue problems from constrained optimization involving matrices A and B. Their solutions identify eigenvectors and eigenvalues, with ordering determined by whether the objective is maximized or minimized.

  • Optimization Form 1: Constrained optimization involving A and B yields Aφ = λBφ, the generalized eigenvalue problem for (A, B).
  • Optimization Form 1: In the generalized problem, φ is the eigenvector and λ is the eigenvalue.
  • Optimization Forms 1–2: Maximization selects the eigenvector with the largest eigenvalue, whereas minimization selects the eigenvector with the smallest eigenvalue.
  • Optimization Form 1: The ordinary eigenvalue problem is a special case of the generalized problem when B = I.
  • Optimization Form 2: For matrix-valued generalized optimization, the columns of Φ are eigenvectors of A and the diagonal elements of Λ are eigenvalues.

5. Examples for the Optimization Problems

The paper illustrates how machine-learning optimization problems become eigenvalue or generalized eigenvalue problems, using PCA, kernel supervised PCA, and Fisher discriminant analysis.

  • Principal Component Analysis: PCA selects projection directions from the covariance matrix, with the leading direction given by its eigenvector with largest eigenvalue.For multiple directions, the columns of U span the PCA subspace.
  • Reconstruction in PCA: PCA can also be formulated as minimizing reconstruction error between the original data and its projection-based reconstruction.For centered data, the covariance matrix is S = XX⊤.
  • Kernel Supervised PCA: Kernel supervised PCA uses kernel matrices for inputs and labels, with centered kernel optimization yielding a generalized eigenvalue problem.The resulting problem is the pair (KxHKyHKx, Kx), whose Θ and Λ contain eigenvectors and eigenvalues.
  • Fisher Discriminant Analysis: Fisher discriminant analysis maximizes a criterion based on between-class and within-class scatter matrices.The stationarity condition gives SBw = λSWw, with w selected as the eigenvector associated with the largest eigenvalue.

6. Solution to Eigenvalue Problem

The eigenvalue problem is solved by finding the roots of a determinant equation and then obtaining the corresponding eigenvectors.

  • Eigenvalue solution: A linear system has non-trivial solutions only when its determinant vanishes, producing a d-degree polynomial equation for the eigenvalues.The determinant condition is applied to the eigenvalue equations to obtain the roots.
  • Eigenvalue solution: The polynomial roots are the eigenvalues; substituting each root into the linear system yields its corresponding eigenvector.Each eigenvector can be normalized because its direction is the relevant quantity.

7. Solution to Generalized Eigenvalue Problem

The generalized eigenvalue problem is solved through determinant-based reductions, an invertible-matrix transformation, or a rigorous symmetric reduction procedure.

  • Problem formulation: The Rayleigh quotient is stationary precisely when the generalized eigenvalue equation holds for some scalar λ.This converts the optimization perspective into a linear system.
  • Problem formulation: The ordinary eigenvalue problem is the special case of the generalized problem obtained when B = I.The determinant solution framework therefore applies directly to this special case.
  • Quick solution: When B is invertible, left-multiplication by B^-1 converts the generalized problem into an ordinary eigenvalue problem for C = B^-1A.If B is singular, the paper describes strengthening its main diagonal by a small positive ε as a numerical workaround.
  • Rigorous solution: The rigorous method diagonalizes B, constructs a symmetric transformed matrix, solves its eigenvalue problem, and recovers the generalized eigenvectors and eigenvalues.The paper presents these operations as an algorithmic sequence for finding Φ and Λ.
  • Rigorous solution: The paper summarizes the rigorous procedure as a sequence of matrix decompositions and recovery steps, with ε-based regularization available when ΛB is singular.The resulting instructions are given as Algorithm 1.

8. Conclusion

The paper provides a tutorial introduction to eigenvalue and generalized eigenvalue problems, their optimization formulations, machine-learning examples, and solution methods.

  • Conclusion: The tutorial introduces both problem types, discusses the optimization problems that yield them, and illustrates them through machine-learning examples.The examples include PCA, kernel supervised PCA, and Fisher discriminant analysis.
  • Conclusion: It also introduces solutions to both eigenvalue and generalized eigenvalue problems.

A. Relation of Eigenvalue and Singular Value Decompositions

Singular value decomposition is closely related to eigen-decomposition: singular vectors arise from eigenvectors of AA⊤ and A⊤A, while singular values are square roots of the corresponding eigenvalues.

  • Forms of SVD: SVD decomposes a matrix in complete or incomplete form, differing in the shape of the diagonal matrix containing singular values.Complete SVD uses a rectangular diagonal matrix, whereas incomplete SVD uses a square diagonal matrix.
  • Forms of SVD: The number of singular values in complete SVD is min(α, β).
  • SVD properties: In both SVD forms, left and right singular vectors are orthonormal, making U and V orthogonal matrices.For untruncated square orthogonal matrices, the corresponding inverse relations also hold.
  • Relation to eigen-decomposition: The left and right singular vectors are eigenvectors of AA⊤ and A⊤A, respectively, while singular values are square roots of the associated eigenvalues.

B. Proof of Why the Lagrange Multiplier is Diagonal in the Eigenvalue Problem

The orthogonality constraints in the eigenvalue optimization problem produce a diagonal Lagrange multiplier matrix because stationarity yields an eigenvalue problem with diagonal eigenvalue matrix.

  • Constraint structure: The orthogonality constraint contains unit-length constraints for each column and pairwise orthogonality constraints between columns.Symmetry reduces the d × d constraints to d(d −1)/2 + d independent constraints.
  • Derivation: Grouping the associated dual variables in the trace-form Lagrangian and setting its derivative to zero yields an eigenvalue problem.
  • Diagonal multiplier: Because the eigenvalue matrix is diagonal, one valid solution has a diagonal Lagrange multiplier matrix.
  • Equivalent solutions: Diagonalizing a symmetric multiplier matrix with an orthogonal eigen-decomposition preserves the eigenvalue-problem solution after right multiplication by the eigenvector matrix.

B.2. Proof of Being Diagonal

The diagonal form of the Lagrange multiplier can be assumed without loss of generality through an orthogonal change of variables, and the resulting eigenvalues determine optimization ordering.

  • Diagonalization: A symmetric, potentially non-diagonal multiplier matrix can be orthogonally diagonalized into eigenvectors and a diagonal eigenvalue matrix.
  • Change of variables: Changing variables from Φ to M = ΦV rewrites the Lagrangian with the diagonal matrix Ω, so the multiplier may be taken as diagonal.
  • Rayleigh-Ritz quotient: For the Rayleigh-Ritz quotient, A must be symmetric and x must be non-zero; scaling x by a scalar leaves the quotient unchanged.
  • Rayleigh-Ritz quotient: The Rayleigh-Ritz optimization is equivalent to optimizing under a unit-norm constraint, whose constant can be replaced without changing the derivative-based solution.
  • Generalized quotient: For the generalized quotient, symmetric positive-definite B permits Cholesky conversion to an ordinary Rayleigh-Ritz quotient.
  • Matrix variables: For matrix variables, the trace-based Rayleigh-Ritz equivalences are approximate rather than exact, unlike the vector-variable case.
Loading 1903.11240v3…