# Efficient way to solve generalized eigenvalue problem when the number of dimensions is greater than the number of samples

I am trying to solve the generalized eigenvalue problem:

$$C_e v = \lambda C_o v.$$

$C_e$ and $C_o$ are both covariance matrices generated from data with $10512$ dimensions and about $2000$ samples. More specifically this is gridded forecast data, the grid has $10512$ points, and I have $2000$ samples. $C_e$ is generated from forecast data and $C_o$ is generated from analysis data. (This detail is inconsequential).

The dimensions of the covariance matrices, $C_e$ and $C_o$, are $10512\times 10512$.

The problem is solvable, but very computationally expensive for dimensions of those size.

Now, if this were just a standard eigenvalue problem, where I want to calculate the principal components of a data with $10512$ dimensions and $2000$ samples, the eigenproblem would be:

$$C_e v = \lambda v.$$

However, there is a trick where instead of using the covariance matrix, $C = 1/(N-1) \cdot X^\top X$, I could use the gram matrix, $G = 1/(N-1) \cdot X X^T$. The gram matrix will have dimensions of $2000 \times 2000$. Calculating the eigenvectors of this matrix is less computationally expensive than calculating the eigenvectors of $C$, which is $10512 \times 10512$. I could then use the eigenvectors of $G$ to calculate the eigenvectors of $C$. This is explained well here: Is PCA still done via the eigendecomposition of the covariance matrix when dimensionality is larger than the number of observations?

So, I am wondering if there is a similar "trick" to finding the eigenvectors for the generalize eigenvalue problem. I.e. maybe I can use the matrices $G_e$ and $G_o$ somehow?

• By "number of dimensions" do you mean "count"? Regardless, what statistical application of the generalized eigenvalue problem do you have in mind? What distinction are you making between a Gram matrix and a covariance matrix? What roles would these have in the problem you are imagining? – whuber Mar 1 '16 at 19:35
• Brain, "Generalized eigenproblem" is, most often, refers to the eigendecomposition of an asymmetric matrix. But X'X vs XX' decomposition to do PCA - these both matrices are symmetric. So standard eigendecomposition does it. Is it possible to use the gram matrices as opposed to the covariance matrices? Yes of course. – ttnphns Mar 1 '16 at 19:52
• Hi ttnphns, thank you for your comment. I don't think I asked my question well enough..I have edited it to be more clear. I specifically need to solve Av = yBv. (where y is lambda) – BrainPermafrost Mar 1 '16 at 20:10
• Interesting problem! My gut feeling is that it should be possible, but I don't see a way to do it (yet)... – amoeba Mar 1 '16 at 21:37
• Can you mention why are you interested in solving this generalized eigenproblem for two covariance matrices? I am wondering in what context it arises. – amoeba Mar 2 '16 at 14:26