5
$\begingroup$

I have a large real matrix A of size $40K\times 400K$, is there an efficient way to calculate the largest eigenvalue of $A^T A$ (size $400K\times 400K$)?

Thanks.

$\endgroup$
3
  • $\begingroup$ What is $A'$? The transpose? $\endgroup$
    – Julien
    Jan 2, 2013 at 21:15
  • $\begingroup$ Indeed, the transpose. Ill clarify, thanks. $\endgroup$
    – yoki
    Jan 2, 2013 at 21:16
  • 3
    $\begingroup$ For what it is worth, this is equal to the largest eigenvalue of $AA^{T}$ (size $40K\times 40K$). $\endgroup$ Jan 2, 2013 at 22:29

1 Answer 1

9
$\begingroup$

Assuming you want the eigenvalue of largest magnitude (not the largest positive eigenvalue) the most efficient algorithm is power iteration: pick an initial vector $v_0$, then iterate

$$v_i = A^T\left(A\frac{v_{i-1}}{\|v_{i-1}\|}\right).$$

Then $\|v_i\|$ will converge almost surely to the largest magnitude eigenvalue of $A^TA$.

EDIT: Notice that computing $A^TA$ is exceedingly expensive and does not need to be done; the utility of power iteration is that it finds the largest eigenvalue using only matrix-vector products. I've added parentheses to clarify.

EDIT 2: Of course, since $A^TA$ is symmetric positive-semidefinite, the eigenvalues are nonnegative and the largest magnitude eigenvalue is also the largest eigenvalue.

$\endgroup$
12
  • $\begingroup$ The problem is that it is too big for me to even calculate $A^T$. $\endgroup$
    – yoki
    Jan 2, 2013 at 21:21
  • 1
    $\begingroup$ Note that you never explicitly compute $A^TA.$ You only need to compute matrix-vector products $Ax$ and $A^Tx$. If these operations are too expensive... you're out of luck, I'm afraid. $\endgroup$
    – user7530
    Jan 2, 2013 at 21:23
  • $\begingroup$ @user7530, Can you clarify what you mean by "almost surely"? If it does converge, how are you supposed to know if it or isn't the largest magnitude eigenvalue? Regards $\endgroup$
    – Amzoti
    Jan 2, 2013 at 21:25
  • 2
    $\begingroup$ You must normalize the vector before you multiply: $\widehat{v_{i-1}} = v_{i-1}/\|v_{i-1}\|$. $\endgroup$
    – user7530
    Jan 2, 2013 at 21:35
  • 1
    $\begingroup$ @Jonas I've edited the answer in case the hat notation isn't standard $\endgroup$
    – user7530
    Jan 3, 2013 at 4:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .