Application of GEVD in Pattern Recognition

In pattern recognition, there are problems where we are given samples (x∈ℜⁿ) from different populations or pattern classes. The well-known problem of linear discriminant analysis (LDA) [Chatterjee et al. Nov 97, May 97, Mar 97] seeks a transform W∈ℜ^nXp (p≤n), such that the interclass distance (measured by the scatter of the patterns around their mixture mean) is maximized, while at the same time the intra-class distance (measured by the scatter of the patterns around their respective class means) is as small as possible. The objective of this transform is to group the classes into well-separated clusters. The former scatter matrix, known as the mixture scatter matrix, is denoted by A, and the latter matrix, known as the within-class scatter matrix, is denoted by B [Fukunaga 90]. When the first column w of W is needed (i.e., p=1), the problem can be formulated in the constrained optimization framework as

Maximize w^TAw subject to w^TBw = 1.     (7.1)

A twin problem to (7.1) is to maximize the Rayleigh quotient criterion [Golub and VanLoan 83] with respect to w:

.     (7.2)

A solution to (7.1) or (7.2) leads to the generalized eigen-decomposition problem Aw=λBw, where λ is the largest generalized eigenvalue of A with respect to B. In general, the p columns of W are the p≤n orthogonal unit generalized eigenvectors ϕ₁,...,ϕ_p of A with respect to B where

, and for i=1,…,p,     (7.3)

where λ₁> ... >λ_p>λ_p+1≥ ... ≥λ_n>0 are the p largest generalized eigenvalues of A with respect to B in descending order of magnitude. In summary, LDA is a powerful feature extraction tool for the class separability feature [Chatterjee May 97], and our adaptive algorithms are suited to this.

Application of GEVD in Signal Processing

Next, let’s discuss an analogous problem of detecting a desired signal in the presence of interference. Here, we seek the optimum linear transform W for weighting the signal plus interference such that the desired signal is detected with maximum power and minimum interference. Given the matrix pair (A,B), where A is the correlation matrix of the signal plus interference plus noise and B is the correlation matrix of interference plus noise, we can formulate the signal detection problem as the constrained maximization problem in (7.1). Here, we maximize the signal power and minimize the power of the interference. The solution for W consists of the p≤n largest generalized eigenvectors of the matrix pencil (A,B). Adaptive generalized eigen-decomposition algorithms also allow the tracking of slow changes in the incoming data [Chatterjee et al. Nov 97, Mar 97; Chen et al. 2000].

Methods for Generalized Eigen-Decomposition

We first define the problem for the non-adaptive case. Each of the three generalized eigenvalue problems (AΦ=BΦΛ, ABΦ=ΦΛ, and BAΦ=ΦΛ, where A and B are real, symmetric, nXn matrices and B is positive definite) can be reduced to a standard symmetric eigenvalue problem using a Cholesky factorization of B as either B=LL^T or B=U^TU. With B = LL^T, we can write AΦ=BΦΛ as

(L⁻¹AL^−T)(L^TΦ) = (L^TΦ)Λ or CΨ = ΨΛ.     (7.4)

In the adaptive case, we can extend these techniques by first (adaptively) computing a matrix W_k for each sample B_k, where W_k tends to the inverse Cholesky factorization L^–1 of B with probability one (w.p.1) as k→∞. Any of the algorithms in Chapter 3 can be considered here. Next, we consider a sequence {}, which is used to adaptively compute a matrix V_k, where V_k tends to the eigenvector matrix of lim_k→∞E[C_k] w.p.1 as k→∞. Any of the algorithms in Chapters 5 and 6 can be considered for this purpose. In conjunction, the two steps yield W_kV_k, which is proven to converge w.p.1 to Φ as k→∞. Thus, the two steps can proceed simultaneously and converge strongly to the eigenvector matrix Φ. A full description of this method is given in [Chatterjee et al. May 97, Mar 97]. In this chapter, I offer a variety of new techniques to solve the generalized eigen-decomposition problem for the adaptive case.

Outline of This Chapter

In Section 7.2, I list the objective functions from which I derive the adaptive generalized eigen-decomposition algorithms. In Sections 7.3, 7.4, and 7.5, I present adaptive algorithms for the homogeneous, deflation, and weighted variations, respectively, from the OJA objective function. In Sections 7.6, 7.7, and 7.8, I analyze the same three variations for the mean squared error (XU) objective function and convergence proofs for the deflation case. In Sections 7.9, 7.10, and 7.11, I discuss algorithms derived from the penalty function (PF) objective function. In Sections 7.12, 7.13, and 7.14, I consider the augmented Lagrangian 1 (AL1) objective function, and in Sections 7.15, 7.16, and 7.17, I present the augmented Lagrangian 2 (AL2) objective function. In Sections 7.18, 7.19, and 7.20, I present the information theory (IT) criterion, and in Sections 7.21, 7.22, and 7.23, I describe the Rayleigh quotient (RQ) criterion. In Section 7.24, I discusses the experimental results, and in Section 7.25, I present conclusions.

Summary of Objective Functions for Adaptive GEVD Algorithms

Summary of Generalized Eigenvector Algorithms

For all algorithms, I describe an objective function J(w_i; A, B) and an update rule of the form

In the following discussions, I denote Φ=[ϕ₁ ... ϕ_n]∈ℜ^nXn as the orthonormal generalized eigenvector matrix of A with respect to B, and Λ= diag(λ₁,...,λ_n) as the generalized eigenvalue matrix, such that λ₁>λ₂>...>λ_p>λ_p+1≥...≥λ_n>0. I use the subscript (i) to denote the i^th permutation of the indices {1,2,…,n}.

OJA Homogeneous Algorithm

The objective function for the OJA homogeneous algorithm can be written as

,     (7.5)

for i=1,…,p (p≤n). From the gradient of (7.5) with respect to we obtain the following adaptive algorithm:

for i=1,…,p,     (7.6)

where η_k is a decreasing gain constant. Defining , from (7.6) we get

.     (7.7)

OJA Deflation Algorithm

The objective function for the OJA deflation adaptive GEVD algorithm is

,     (7.8)

for i=1,…,p. From the gradient of (7.8) with respect to , we obtain the OJA deflation adaptive gradient descent algorithm as

,     (7.9)

for i=1,…,p (p≤n). The matrix form of the algorithm is

,     (7.10)

where UT[⋅] sets all elements below the diagonal of its matrix argument to zero.

OJA Weighted Algorithm

The objective function for the OJA weighted adaptive GEVD algorithm is

     (7.11)

for i=1,…,p, where c₁,…,c_p (p≤n) are small positive numbers satisfying

c₁ > c₂ > … > c_p > 0, p ≤ n.     (7.12)

Given a diagonal matrix C =  diag (c₁, …, c_p), p ≤ n, the OJA weighted adaptive algorithm is

.     (7.13)

OJA Algorithm Python Code

XU Homogeneous Algorithm

The objective function for the XU homogeneous adaptive GEVD algorithm is

     (7.14)

for i=1,…,p (p≤n). From the gradient of (7.14) with respect to , we obtain the XU homogeneous adaptive gradient descent algorithm as

     (7.15)

for i=1,…,p, whose matrix form is

.     (7.16)

XU Deflation Algorithm

The objective function for the XU deflation adaptive GEVD algorithm is

     (7.17)

for i=1,…,p (p≤n). From the gradient of (7.17) with respect to , we obtain

, (7.18)

where UT[⋅] sets all elements below the diagonal of its matrix argument to zero. Chatterjee et al. [Mar 00, Thms 1, 2] proved that W_k converges with probability one to [±ϕ₁ ±ϕ₂ … ±ϕ_p] as k→∞.

XI Weighted Algorithm

The objective function for the XU weighted adaptive GEVD algorithm is

     (7.19)

for i=1,…,p (p≤n), where c₁,…,c_p are small positive numbers satisfying (7.12). The adaptive algorithm is

,  (7.20)

where C = diag(c₁,…,c_p).

XU Algorithm Python Code

PF Homogeneous Algorithm

We obtain the objective function for the PF homogeneous generalized eigenvector algorithm by writing the Rayleigh quotient criterion (7.2) as the following penalty function:

,     (7.21)

where μ > 0 and i=1,…,p (p≤n). From the gradient of (7.21) with respect to , we obtain the PF homogeneous adaptive algorithm:

,     (7.22)

where I_p is a pXp identity matrix.

PF Deflation Algorithm

The objective function for the PF deflation GEVD algorithm is

, (7.23)

where μ > 0 and i=1,…,p. The adaptive algorithm is

,     (7.24)

where UT[⋅] sets all elements below the diagonal of its matrix argument to zero.

PF Weighted Algorithm

The objective function for the PF weighted GEVD algorithm is

, (7.25)

where c₁ > c₂ > … > c_p > 0 (p ≤ n), μ > 0, and i=1,…,p. The corresponding adaptive algorithm is

,     (7.26)

where C =  diag (c₁, …, c_p).

PF Algorithm Python Code

AL1 Homogeneous Algorithm

We apply the augmented Lagrangian method of nonlinear optimization to the Rayleigh quotient criterion (7.4) to obtain the objective function for the AL1 homogeneous GEVD algorithm as

,

,     (7.27)

for i=1,…,p (p≤n), where (α, β₁, β₂, …, β_p) are Lagrange multipliers and μ is a positive penalty constant. Taking the gradient of with respect to and equating the gradient to 0 and using the constraint , we obtain

and for j=1,…,p.     (7.28)

Replacing (α, β₁, β₂, …, β_p) in the gradient of (7.27), we obtain the AL1 homogeneous adaptive gradient descent generalized eigenvector algorithm:

 (7.29)

where μ > 0. Defining , we obtain

, (7.30)

where I_p is a pXp identity matrix.

AL1 Deflation Algorithm

The objective function for the AL1 deflation GEVD algorithm is

,     (7.31)

for i=1,…,p (p≤n). Following the steps in Section 7.6.1 we obtain the adaptive algorithm:

. (7.32)

AL1 Weighted Algorithm

The objective function for the AL1 weighted GEVD algorithm is

,

,     (7.33)

for i=1,…,p (p≤n), where (α, β₁, β₂, …, β_p) are Lagrange multipliers, μ is a positive penalty constant, and c₁ > c₂ > … > c_p > 0. The adaptive algorithm is

, (7.34)

where C =  diag (c₁, …, c_p).

AL1 Algorithm Python Code

AL2 Homogeneous Algorithm

The unconstrained objective function for the AL2 homogeneous GEVD algorithm is

,     (7.35)

for i=1,…,p, where μ is a positive penalty constant. From (7.35), we obtain the adaptive gradient descent algorithm:

, (7.36)

for i=1,…,p, the matrix version of which is

.     (7.37)

AL2 Deflation Algorithm

The objective function for the AL2 deflation GEVD algorithm is

, (7.38)

for i=1,…,p. The adaptive GEVD algorithm is

. (7.39)

AL2 Weighted Algorithm

The objective function for the AL2 weighted generalized eigenvector algorithm is

,     (7.40)

for i=1,…,p, where c₁ > c₂ > … > c_p > 0 (p ≤ n). The adaptive algorithm is

, (7.41)

where C =  diag (c₁, …, c_p), p ≤ n.

AL2 Algorithm Python Code

IT Homogeneous Algorithm

The objective function for the information theory homogeneous GEVD algorithm is

     (7.42)

for i=1,…,p, where (α, β₁, β₂, …, β_p) are Lagrange multipliers and ln(.) is logarithm base e. By equating the gradient of (7.42) with respect to to 0 and using the constraint , we obtain

α = 0 and ,     (7.43)

for j=1,…,p. Replacing (α, β₁, β₂, …, β_p) in the gradient of (7.42), we obtain the IT homogeneous adaptive gradient descent algorithm for the generalized eigenvector:

,     (7.44)

for i=1,…,p, whose matrix version is

,     (7.45)

where DIAG[⋅] sets all elements except the diagonal of its matrix argument to zero.

IT Deflation Algorithm

The objective function for the IT deflation GEVD algorithm is

     (7.46)

for i=1,…,p, where (α, β₁, β₂, …, β_p) are Lagrange multipliers. From (7.43), we obtain the adaptive gradient algorithm:

 (7.47)

IT Weighted Algorithm

The objective function for the IT weighted GEVD algorithm is

     (7.48)

for i=1,…,p, where (α, β₁, β₂, …, β_p) are Lagrange multipliers. By solving (α, β₁, β₂, …, β_k) and replacing them in the gradient of (7.48), we obtain the adaptive algorithm:

.     (7.49)

IT Algorithm Python Code

RQ Homogeneous Algorithm

We obtain the objective function for the Rayleigh quotient homogeneous GEVD algorithm from the Rayleigh quotient criterion (7.2) as follows:

 (7.50)

for i=1,…,p, where (α, β₁, β₂, …, β_p) are Lagrange multipliers. By equating the gradient (7.50) with respect to to 0, and using the constraint , we obtain

α = 0 and for j=1,…,p.     (7.51)

Replacing (α, β₁, β₂, …, β_p) in the gradient of (7.50) and making a small approximation, we obtain the RQ homogeneous adaptive gradient descent algorithm for the generalized eigenvector:

,     (7.52)

for i=1,…,p, whose matrix version is

.     (7.53)

RQ Deflation Algorithm

The objective function for the RQ deflation GEVD algorithm is

, (7.54)

for i=1,…,p, where (α, β₁, β₂, …, β_p) are Lagrange multipliers. By solving (α, β₁, β₂, …, β_k) and replacing them in the gradient of (7.54), we obtain the adaptive algorithm:

. (7.55)

RQ Weighted Algorithm

The objective function for the RQ weighted GEVD algorithm is

,     (7.56)

for i=1,…,p, where (α, β₁, β₂, …, β_p) are Lagrange multipliers. By solving (α, β₁, β₂, …, β_k) and replacing them in the gradient of (7.56), we obtain the adaptive algorithm:

.     (7.57)

RQ Algorithm Python Code