4
$\begingroup$

Suppose I have a symmetric matrix $A_{1000\times 1000}$, which can be represented by:

$A = J G J^T$

where $J$ in 1000x3 is full column rank dense matrix; $G$ in 3x3 is a nonsingular dense matrix.

What is the fastest way to obtain ONLY the maximum eigenvalue of $A$?

I know that the eigenvalue problem of symmetric matrix can be faster than that of general dense matrix, but can the following features of the problem make it even faster ?

  1. only the maximum eigenvalue of $A$ is needed;

  2. $A = J G J^T$, rank($A$) = 3, and $A$ has only 3 nonzero eigenvalues

Can $LDL^T$ decomposition work any good? I would prefer to implement it via Eigen C++.

Does $B=J^TJG$ has the same nonzero eigenvalues as $A$?

$\endgroup$
  • 1
    $\begingroup$ It seems the problem can be converted as a 3x3 dimensional eigenvalue problem... $\endgroup$ – LCFactorization Feb 6 '14 at 7:06
6
$\begingroup$

We have the matrix $A$ that can be expressed as

$A = JGJ^T$.

The first thing is to calculate the QR decomposition of matrix $J$. Because of the low rank of the matrix it can be done very fast with, for instance, modified Gram Schmidt algorithm. Now we can write $A$ as

$A = QR G R^TQ^T$,

where $Q$ is an orthonormal matrix ($Q^T Q = I$). We define $F$ as follows

$F = R G R^T$,

where $F$ is a $3\times3$ matrix. here the eigenvalues of $F$ will be the same than the ones of your original matrix $A$. But you probably want to calculate also the eigenvectors of $A$, so we continue.

Calculate the eigen decomposition of $F$:

$F = XDX^T$,

where $D$ is a diagonal matrix, and $X$ is orthonormal ($X^T X = I$). Then, inserting that expression for $F$ in the formula for $A$ we obtain

$A = QXDX^TQ^T$,

that can be rewritten as

$A = YDY^T$,.

So $Y = QX$ is a orthonormal matrix whose columns are the eigenvectors of $A$, and $D$ is the diagonal matrix with the eigenvalues of $A$. It is unique except for the ordering of the columns of $Y$ and $D$.

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