1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Wolfgang Bangerth Nov 10 '14 at 5:11
  • $\begingroup$ @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. $\endgroup$ – user3138073 Nov 10 '14 at 5:39
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user3138073 Nov 11 '14 at 5:43
  • $\begingroup$ The reason is that I am working on sparse generalized eigenvalue problem. Therefore, if I work on $y$, then I cannot obtain sparse $x$. $\endgroup$ – user3138073 Nov 11 '14 at 5:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Nov 12 '14 at 3:07
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.