# Deflation for generalized eigenvalue problem

We know that principle component analysis (PCA) is a eigenvalue problem. Let $A$ be the covariance matrix of $X$, PCA aims to find the eigenvalue of $A$:

$\max v'Av$, subject to $v'v=1$

Multiple PCs can be found by deflation:

Let $\hat{X}=X-\sum_{i=1}^k v_iv_i'X$ (or equivalently $\hat{A}=(I-\sum_{i=1}^k v_iv_i')A(I-\sum_{i=1}^k v_iv_i')$) where $v_i, i = 1,\dots,k$ is the first $k$ PCs and then the $k+1$st PC can be computed by solving the $1$st PC of $\hat{A}$.

I am wondering if there is a similar deflation method to find the first $k$ eigenvectors for the generalized eigenvalue problem:

$\max \frac{v'Av}{v'Bv}$

where $A$ and $B$ are some covariance matrices: $A=Cov(X), B=Cov(Y)$.

Thanks!

• The last formula is missing the $X-$ part of the first formula. Also, what is the relationship of $X$ in that formula and the matrices $A,B$? – Wolfgang Bangerth Nov 10 '14 at 5:11
• @Wolfgang Bangerth Thanks for pointing out that. I have fixed it. My initial idea for the solution is probably wrong, so I've removed it. – user3138073 Nov 10 '14 at 5:39

The thing to realize is that solving the eigenvalue problem $$Ax = \lambda B x,$$ for which the largest eigenvalue is given by $$\lambda_\text{max} = \max_x \frac{x^T A x}{x^T B x},$$ is entirely equivalent to solving the regular eigenvalue problem $$B^{-T/2} A B^{-1/2} x = \lambda x.$$ You can see that by writing $$\lambda_\text{max} = \max_x \frac{x^T A x}{x^T B x} = \max_x \frac{x^T A x}{(B^{1/2}x)^T (B^{1/2} x)} = \max_{y=B^{1/2}x} \frac{y^T B^{-T/2} A B^{-1/2} y}{y^T y}.$$ What this means is that if you know how to do the deflation for the matrix $A$, then you just need to apply it now for the matrix $B^{-T/2} A B^{-1/2}$.

• Thanks for the answer @Wolfgang Bangerth. However, the problem here is that it is not allowed to use this transformation. In other words, I am wondering if there is a deflation method works on $x$ explicitly. – user3138073 Nov 11 '14 at 5:43
• The reason is that I am working on sparse generalized eigenvalue problem. Therefore, if I work on $y$, then I cannot obtain sparse $x$. – user3138073 Nov 11 '14 at 5:46
• I didn't mean to suggest to ever compute $B^{1/2}$ or $B^{-1/2}$. But you can write down all of the formulas with these factors and then think about multiplying them from the left or right with appropriate factors to obtain a method that can actually be used without ever computing these factors. – Wolfgang Bangerth Nov 12 '14 at 3:07

Six deflation methods for sparse PCA were discussed in this paper:

• Hotelling's deflation and orthogonal Hotelling's deflation;
• Projection deflation and orthogonal projection deflation;
• Schur complement deflation;
• Reforming sparse PCA problem.

Personally I prefer the orthogonal projection deflation and it can be extended to the generalized eigenvalue problem. Consider the problem as, $$min_v v^TAv,s.t.v^TBv=1.$$ At $t$-th iteration, obtain vector $q_t\propto(I-Q_{t-1}Q_{t-1}^TB)v_t$ where $q_t^TBq_t=1$ and $Q_{t-1}=[q_{1:(t-1)}]$. This can be thought as a result of the weighted Gram-Schmidt process from the set $\{v_t\}$. Then the matrix $A$ is updated as, $$A_{t+1}=(I-B^Tq_tq_t^T)A_t(I-q_tq_t^TB),$$ where the matrix $B$ can be kept intact. It works fine for non-sparse generalized eigenvalue problems.

I further tested this for sparse generalized eigenvalue problems, using the algorithm in this paper. The process mentioned here only guarantees that, $(v_t)^TA_sv_t=0, \forall{t<s}$. Thus $V^TBV\neq I$. The orthogonality property, unfortunately, has to be realized in other ways.